001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.lib;
032:
033: import java.util.NoSuchElementException;
034:
035: // fredt@users 20020130 - patch 1.7.0 by fredt - new class
036:
037: /**
038: * jdk 1.1 compatible minimal implementation of a list object suitable for
039: * stack, queue and deque usage patterns backed by an Object[].
040: * The memory footprint of the HsqlDeque doubles when it gets full
041: * but does not shrink when it gets empty.
042: *
043: * @author fredt@users
044: * @version 1.7.2
045: * @since 1.7.0
046: */
047: public class HsqlDeque extends BaseList implements HsqlList {
048:
049: private Object[] list;
050: private int firstindex = 0; // index of first list element
051: private int endindex = 0; // index of last list element + 1
052:
053: // can grow to fill list
054: // if elementCount == 0 then firstindex == endindex
055: private static final int DEFAULT_INITIAL_CAPACITY = 10;
056:
057: public HsqlDeque() {
058: list = new Object[DEFAULT_INITIAL_CAPACITY];
059: }
060:
061: public int size() {
062: return elementCount;
063: }
064:
065: public Object getFirst() throws NoSuchElementException {
066:
067: if (elementCount == 0) {
068: throw new NoSuchElementException();
069: }
070:
071: return list[firstindex];
072: }
073:
074: public Object getLast() throws NoSuchElementException {
075:
076: if (elementCount == 0) {
077: throw new NoSuchElementException();
078: }
079:
080: return list[endindex - 1];
081: }
082:
083: public Object get(int i) throws IndexOutOfBoundsException {
084:
085: int index = getInternalIndex(i);
086:
087: return list[index];
088: }
089:
090: public void add(int i, Object o) throws IndexOutOfBoundsException {
091: throw new java.lang.RuntimeException();
092: }
093:
094: public Object set(int i, Object o) throws IndexOutOfBoundsException {
095:
096: int index = getInternalIndex(i);
097: Object result = list[index];
098:
099: list[index] = o;
100:
101: return result;
102: }
103:
104: public Object removeFirst() throws NoSuchElementException {
105:
106: if (elementCount == 0) {
107: throw new NoSuchElementException();
108: }
109:
110: Object o = list[firstindex];
111:
112: list[firstindex] = null;
113:
114: firstindex++;
115: elementCount--;
116:
117: if (elementCount == 0) {
118: firstindex = endindex = 0;
119: } else if (firstindex == list.length) {
120: firstindex = 0;
121: }
122:
123: return o;
124: }
125:
126: public Object removeLast() throws NoSuchElementException {
127:
128: if (elementCount == 0) {
129: throw new NoSuchElementException();
130: }
131:
132: endindex--;
133:
134: Object o = list[endindex];
135:
136: list[endindex] = null;
137:
138: elementCount--;
139:
140: if (elementCount == 0) {
141: firstindex = endindex = 0;
142: } else if (endindex == 0) {
143: endindex = list.length;
144: }
145:
146: return o;
147: }
148:
149: /*
150: public Object remove(int i){
151: return get(i);
152: }
153:
154: public void add(int i, Object o) {
155:
156: }
157: */
158: public boolean add(Object o) {
159:
160: resetCapacity();
161:
162: if (endindex == list.length) {
163: endindex = 0;
164: }
165:
166: list[endindex] = o;
167:
168: elementCount++;
169: endindex++;
170:
171: return true;
172: }
173:
174: public boolean addLast(Object o) {
175: return add(o);
176: }
177:
178: public boolean addFirst(Object o) {
179:
180: resetCapacity();
181:
182: firstindex--;
183:
184: if (firstindex < 0) {
185: firstindex = list.length - 1;
186:
187: if (endindex == 0) {
188: endindex = list.length;
189: }
190: }
191:
192: list[firstindex] = o;
193:
194: elementCount++;
195:
196: return true;
197: }
198:
199: public void clear() {
200:
201: firstindex = endindex = elementCount = 0;
202:
203: for (int i = 0; i < list.length; i++) {
204: list[i] = null;
205: }
206: }
207:
208: public Object remove(int index) {
209:
210: int target = getInternalIndex(index);
211: Object value = list[target];
212:
213: if (target >= firstindex) {
214: System.arraycopy(list, firstindex, list, firstindex + 1,
215: target - firstindex);
216:
217: list[firstindex] = null;
218:
219: firstindex++;
220:
221: if (firstindex == list.length) {
222: firstindex = 0;
223: }
224: } else {
225: System.arraycopy(list, target + 1, list, target, endindex
226: - target - 1);
227:
228: list[endindex] = null;
229:
230: endindex--;
231:
232: if (endindex == 0) {
233: endindex = list.length;
234: }
235: }
236:
237: if (elementCount == 0) {
238: firstindex = endindex = 0;
239: }
240:
241: return value;
242: }
243:
244: private int getInternalIndex(int i)
245: throws IndexOutOfBoundsException {
246:
247: if (i < 0 || i >= elementCount) {
248: throw new IndexOutOfBoundsException();
249: }
250:
251: int index = firstindex + i;
252:
253: if (index >= list.length) {
254: index -= list.length;
255: }
256:
257: return index;
258: }
259:
260: private void resetCapacity() {
261:
262: if (elementCount < list.length) {
263: return;
264: }
265:
266: // essential to at least double the capacity for the loop to work
267: Object[] newList = new Object[list.length * 2];
268:
269: for (int i = 0; i < list.length; i++) {
270: newList[i] = list[i];
271: }
272:
273: list = newList;
274: newList = null;
275:
276: if (endindex <= firstindex) {
277: int tail = firstindex + elementCount - endindex;
278:
279: for (int i = 0; i < endindex; i++) {
280: list[tail + i] = list[i];
281: list[i] = null;
282: }
283:
284: endindex = firstindex + elementCount;
285: }
286: }
287: /*
288: public static void main(String[] args) {
289:
290: HsqlDeque d = new HsqlDeque();
291:
292: for (int i = 0; i < 9; i++) {
293: d.add(new Integer(i));
294: }
295:
296: d.removeFirst();
297: d.removeFirst();
298: d.add(new Integer(9));
299: d.add(new Integer(10));
300:
301: for (int i = 0; i < d.size(); i++) {
302: System.out.println(d.get(i));
303: }
304:
305: System.out.println();
306: d.add(new Integer(11));
307: d.add(new Integer(12));
308:
309: for (int i = 0; i < d.size(); i++) {
310: System.out.println(d.get(i));
311: }
312:
313: d.addFirst(new Integer(1));
314: d.addFirst(new Integer(0));
315: d.addFirst(new Integer(-1));
316: d.addFirst(new Integer(-2));
317:
318: for (int i = 0; i < d.size(); i++) {
319: System.out.println(d.get(i));
320: }
321:
322: System.out.println();
323: d.removeFirst();
324: d.removeFirst();
325: d.removeFirst();
326:
327: for (int i = 0; i < d.size(); i++) {
328: System.out.println(d.get(i));
329: }
330:
331: System.out.println();
332:
333: Iterator it = d.iterator();
334:
335: for (; it.hasNext(); ) {
336: System.out.println(it.next());
337: }
338: }
339: */
340: }
|