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  ;
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  [] 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  [DEFAULT_INITIAL_CAPACITY];
60      }
61  
62      public int size() {
63          return elementCount;
64      }
65  
66      public Object   getFirst() throws NoSuchElementException   {
67  
68          if (elementCount == 0) {
69              throw new NoSuchElementException  ();
70          }
71  
72          return list[firstindex];
73      }
74  
75      public Object   getLast() throws NoSuchElementException   {
76  
77          if (elementCount == 0) {
78              throw new NoSuchElementException  ();
79          }
80  
81          return list[endindex - 1];
82      }
83  
84      public Object   get(int i) throws IndexOutOfBoundsException   {
85  
86          int index = getInternalIndex(i);
87  
88          return list[index];
89      }
90  
91      public void add(int i, Object   o) throws IndexOutOfBoundsException   {
92          throw new java.lang.RuntimeException  ();
93      }
94  
95      public Object   set(int i, Object   o) throws IndexOutOfBoundsException   {
96  
97          int    index  = getInternalIndex(i);
98          Object   result = list[index];
99  
100         list[index] = o;
101 
102         return result;
103     }
104 
105     public Object   removeFirst() throws NoSuchElementException   {
106 
107         if (elementCount == 0) {
108             throw new NoSuchElementException  ();
109         }
110 
111         Object   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   removeLast() throws NoSuchElementException   {
128 
129         if (elementCount == 0) {
130             throw new NoSuchElementException  ();
131         }
132 
133         endindex--;
134 
135         Object   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   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   o) {
176         return add(o);
177     }
178 
179     public boolean addFirst(Object   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   remove(int index) {
210 
211         int    target = getInternalIndex(index);
212         Object   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   {
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 }
341
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags