KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > hsqldb > lib > HsqlDeque


1 /* Copyright (c) 2001-2005, 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.NoSuchElementException JavaDoc;
35
36 // fredt@users 20020130 - patch 1.7.0 by fredt - new class
37

38 /**
39  * jdk 1.1 compatible minimal implementation of a list object suitable for
40  * stack, queue and deque usage patterns backed by an Object[].
41  * The memory footprint of the HsqlDeque doubles when it gets full
42  * but does not shrink when it gets empty.
43  *
44  * @author fredt@users
45  * @version 1.7.2
46  * @since 1.7.0
47  */

48 public class HsqlDeque extends BaseList implements HsqlList {
49
50     private Object JavaDoc[] 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 elementCount == 0 then firstindex == endindex
56
private static final int DEFAULT_INITIAL_CAPACITY = 10;
57
58     public HsqlDeque() {
59         list = new Object JavaDoc[DEFAULT_INITIAL_CAPACITY];
60     }
61
62     public int size() {
63         return elementCount;
64     }
65
66     public Object JavaDoc getFirst() throws NoSuchElementException JavaDoc {
67
68         if (elementCount == 0) {
69             throw new NoSuchElementException JavaDoc();
70         }
71
72         return list[firstindex];
73     }
74
75     public Object JavaDoc getLast() throws NoSuchElementException JavaDoc {
76
77         if (elementCount == 0) {
78             throw new NoSuchElementException JavaDoc();
79         }
80
81         return list[endindex - 1];
82     }
83
84     public Object JavaDoc get(int i) throws IndexOutOfBoundsException JavaDoc {
85
86         int index = getInternalIndex(i);
87
88         return list[index];
89     }
90
91     public void add(int i, Object JavaDoc o) throws IndexOutOfBoundsException JavaDoc {
92         throw new java.lang.RuntimeException JavaDoc();
93     }
94
95     public Object JavaDoc set(int i, Object JavaDoc o) throws IndexOutOfBoundsException JavaDoc {
96
97         int index = getInternalIndex(i);
98         Object JavaDoc result = list[index];
99
100         list[index] = o;
101
102         return result;
103     }
104
105     public Object JavaDoc removeFirst() throws NoSuchElementException JavaDoc {
106
107         if (elementCount == 0) {
108             throw new NoSuchElementException JavaDoc();
109         }
110
111         Object JavaDoc o = list[firstindex];
112
113         list[firstindex] = null;
114
115         firstindex++;
116         elementCount--;
117
118         if (elementCount == 0) {
119             firstindex = endindex = 0;
120         } else if (firstindex == list.length) {
121             firstindex = 0;
122         }
123
124         return o;
125     }
126
127     public Object JavaDoc removeLast() throws NoSuchElementException JavaDoc {
128
129         if (elementCount == 0) {
130             throw new NoSuchElementException JavaDoc();
131         }
132
133         endindex--;
134
135         Object JavaDoc o = list[endindex];
136
137         list[endindex] = null;
138
139         elementCount--;
140
141         if (elementCount == 0) {
142             firstindex = endindex = 0;
143         } else if (endindex == 0) {
144             endindex = list.length;
145         }
146
147         return o;
148     }
149
150 /*
151     public Object remove(int i){
152         return get(i);
153     }
154
155     public void add(int i, Object o) {
156
157     }
158 */

159     public boolean add(Object JavaDoc o) {
160
161         resetCapacity();
162
163         if (endindex == list.length) {
164             endindex = 0;
165         }
166
167         list[endindex] = o;
168
169         elementCount++;
170         endindex++;
171
172         return true;
173     }
174
175     public boolean addLast(Object JavaDoc o) {
176         return add(o);
177     }
178
179     public boolean addFirst(Object JavaDoc o) {
180
181         resetCapacity();
182
183         firstindex--;
184
185         if (firstindex < 0) {
186             firstindex = list.length - 1;
187
188             if (endindex == 0) {
189                 endindex = list.length;
190             }
191         }
192
193         list[firstindex] = o;
194
195         elementCount++;
196
197         return true;
198     }
199
200     public void clear() {
201
202         firstindex = endindex = elementCount = 0;
203
204         for (int i = 0; i < list.length; i++) {
205             list[i] = null;
206         }
207     }
208
209     public Object JavaDoc remove(int index) {
210
211         int target = getInternalIndex(index);
212         Object JavaDoc value = list[target];
213
214         if (target >= firstindex) {
215             System.arraycopy(list, firstindex, list, firstindex + 1,
216                              target - firstindex);
217
218             list[firstindex] = null;
219
220             firstindex++;
221
222             if (firstindex == list.length) {
223                 firstindex = 0;
224             }
225         } else {
226             System.arraycopy(list, target + 1, list, target,
227                              endindex - target - 1);
228
229             list[endindex] = null;
230
231             endindex--;
232
233             if (endindex == 0) {
234                 endindex = list.length;
235             }
236         }
237
238         if (elementCount == 0) {
239             firstindex = endindex = 0;
240         }
241
242         return value;
243     }
244
245     private int getInternalIndex(int i) throws IndexOutOfBoundsException JavaDoc {
246
247         if (i < 0 || i >= elementCount) {
248             throw new IndexOutOfBoundsException JavaDoc();
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 JavaDoc[] newList = new Object JavaDoc[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 }
341
Popular Tags