Source code: org/hsqldb/lib/HsqlDeque.java
1 /* Copyright (c) 2001-2002, The HSQL Development Group
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9 *
10 * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * Neither the name of the HSQL Development Group nor the names of its
15 * contributors may be used to endorse or promote products derived from this
16 * software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31
32 package org.hsqldb.lib;
33
34 import java.util.Enumeration;
35 import java.util.NoSuchElementException;
36
37 // fredt@users 20020130 - patch 1.7.0 by fredt - new class
38
39 /**
40 * jdk 1.1 compatible minimal implementation of a list object suitable for
41 * stack, queue and deque usage patterns backed by an Object[].
42 * The memory footprint of the HsqlDeque doubles when it gets full
43 * but does not shrink when it gets empty.
44 *
45 * @author fredt@users
46 * @version 1.7.0
47 */
48 public class HsqlDeque {
49
50 private Object[] list;
51 private int firstindex = 0; // index of first list element
52 private int endindex = 0; // index of last list element + 1
53
54 // can grow to fill list
55 // if usedsize == 0 then firstindex == endindex
56 private int usedsize = 0; // current number of elements
57 private final int DEFAULT_INITIAL_CAPACITY = 10;
58
59 public HsqlDeque() {
60 list = new Object[DEFAULT_INITIAL_CAPACITY];
61 }
62
63 public int size() {
64 return usedsize;
65 }
66
67 public Object getFirst() throws NoSuchElementException {
68
69 if (usedsize == 0) {
70 throw new NoSuchElementException();
71 }
72
73 return list[firstindex];
74 }
75
76 public Object getLast() throws NoSuchElementException {
77
78 if (usedsize == 0) {
79 throw new NoSuchElementException();
80 }
81
82 return list[endindex - 1];
83 }
84
85 public Object get(int i) throws IndexOutOfBoundsException {
86
87 int index = getInternalIndex(i);
88
89 return list[index];
90 }
91
92 public Object set(int i, Object o) throws IndexOutOfBoundsException {
93
94 int index = getInternalIndex(i);
95 Object result = list[index];
96
97 list[index] = o;
98
99 return result;
100 }
101
102 public Object removeFirst() throws NoSuchElementException {
103
104 if (usedsize == 0) {
105 throw new NoSuchElementException();
106 }
107
108 Object o = list[firstindex];
109
110 list[firstindex] = null;
111
112 firstindex++;
113 usedsize--;
114
115 if (usedsize == 0) {
116 firstindex = endindex = 0;
117 } else if (firstindex == list.length) {
118 firstindex = 0;
119 }
120
121 return o;
122 }
123
124 public Object removeLast() throws NoSuchElementException {
125
126 if (usedsize == 0) {
127 throw new NoSuchElementException();
128 }
129
130 endindex--;
131
132 Object o = list[endindex];
133
134 list[endindex] = null;
135
136 usedsize--;
137
138 if (usedsize == 0) {
139 firstindex = endindex = 0;
140 } else if (endindex == 0) {
141 endindex = list.length;
142 }
143
144 return o;
145 }
146
147 /*
148 public Object remove(int i){
149 return get(i);
150 }
151
152 public void add(int i, Object o) {
153
154 }
155 */
156 public boolean add(Object o) {
157
158 resetCapacity();
159
160 if (endindex == list.length) {
161 endindex = 0;
162 }
163
164 list[endindex] = o;
165
166 usedsize++;
167 endindex++;
168
169 return true;
170 }
171
172 public boolean addLast(Object o) {
173 return add(o);
174 }
175
176 public boolean addFirst(Object o) {
177
178 resetCapacity();
179
180 firstindex--;
181
182 if (firstindex < 0) {
183 firstindex = list.length - 1;
184
185 if (endindex == 0) {
186 endindex = list.length;
187 }
188 }
189
190 list[firstindex] = o;
191
192 usedsize++;
193
194 return true;
195 }
196
197 public void clear() {
198
199 firstindex = endindex = usedsize = 0;
200
201 for (int i = 0; i < list.length; i++) {
202 list[i] = null;
203 }
204 }
205
206 public boolean isEmpty() {
207 return usedsize == 0;
208 }
209
210 private int getInternalIndex(int i) throws IndexOutOfBoundsException {
211
212 if (i < 0 || i >= usedsize) {
213 throw new IndexOutOfBoundsException();
214 }
215
216 int index = firstindex + i;
217
218 if (index >= list.length) {
219 index -= list.length;
220 }
221
222 return index;
223 }
224
225 // based on code by dnordahl@users
226 public Enumeration elements() {
227
228 Enumeration enum = new Enumeration() {
229
230 private int currentIndex = 0;
231
232 public Object nextElement() {
233
234 if (!hasMoreElements()) {
235 throw new NoSuchElementException("Enumeration complete");
236 }
237
238 return get(currentIndex++);
239 }
240
241 public boolean hasMoreElements() {
242 return usedsize > currentIndex;
243 }
244 };
245
246 return enum;
247 }
248
249 private void resetCapacity() {
250
251 if (usedsize < list.length) {
252 return;
253 }
254
255 // essential to at least double the capacity for the loop to work
256 Object[] newList = new Object[list.length * 2];
257
258 for (int i = 0; i < list.length; i++) {
259 newList[i] = list[i];
260 }
261
262 list = newList;
263 newList = null;
264
265 if (endindex <= firstindex) {
266 int tail = firstindex + usedsize - endindex;
267
268 for (int i = 0; i < endindex; i++) {
269 list[tail + i] = list[i];
270 list[i] = null;
271 }
272
273 endindex = firstindex + usedsize;
274 }
275 }
276 /*
277 public static void main(String[] args) {
278
279 HsqlDeque d = new HsqlDeque();
280
281 for (int i = 0; i < 9; i++) {
282 d.add(new Integer(i));
283 }
284
285 d.removeFirst();
286 d.removeFirst();
287 d.add(new Integer(9));
288 d.add(new Integer(10));
289
290 for (int i = 0; i < d.size(); i++) {
291 System.out.println(d.get(i));
292 }
293
294 System.out.println();
295 d.add(new Integer(11));
296 d.add(new Integer(12));
297
298 for (int i = 0; i < d.size(); i++) {
299 System.out.println(d.get(i));
300 }
301
302 d.addFirst(new Integer(1));
303 d.addFirst(new Integer(0));
304 d.addFirst(new Integer(-1));
305 d.addFirst(new Integer(-2));
306
307 for (int i = 0; i < d.size(); i++) {
308 System.out.println(d.get(i));
309 }
310
311 System.out.println();
312 d.removeFirst();
313 d.removeFirst();
314 d.removeFirst();
315
316 for (int i = 0; i < d.size(); i++) {
317 System.out.println(d.get(i));
318 }
319
320 System.out.println();
321
322 Enumeration en = d.elements();
323
324 for (; en.hasMoreElements(); ) {
325 System.out.println(en.nextElement());
326 }
327 }
328 */
329 }