KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > bak > pcj > list > LongArrayDeque


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2003 Søren Bak
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19 package bak.pcj.list;
20
21 import bak.pcj.LongIterator;
22 import bak.pcj.LongCollection;
23 import bak.pcj.hash.DefaultLongHashFunction;
24 import bak.pcj.util.Exceptions;
25
26 import java.io.Serializable JavaDoc;
27 import java.io.IOException JavaDoc;
28 import java.io.ObjectInputStream JavaDoc;
29 import java.io.ObjectOutputStream JavaDoc;
30
31 /**
32  * This class represents an array implementaion of deques of
33  * long values.
34  *
35  * @see java.util.LinkedList
36  *
37  * @author Søren Bak
38  * @version 1.3 21-08-2003 19:25
39  * @since 1.0
40  */

41 public class LongArrayDeque extends AbstractLongList implements LongDeque, Cloneable JavaDoc, Serializable JavaDoc {
42
43     /** Constant indicating relative growth policy. */
44     private static final int GROWTH_POLICY_RELATIVE = 0;
45
46     /** Constant indicating absolute growth policy. */
47     private static final int GROWTH_POLICY_ABSOLUTE = 1;
48
49     /**
50      * The default growth policy of this deque.
51      * @see #GROWTH_POLICY_RELATIVE
52      * @see #GROWTH_POLICY_ABSOLUTE
53      */

54     private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
55
56     /** The default factor with which to increase the capacity of this deque. */
57     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
58
59     /** The default chunk size with which to increase the capacity of this deque. */
60     public static final int DEFAULT_GROWTH_CHUNK = 10;
61
62     /** The default capacity of this deque. */
63     public static final int DEFAULT_CAPACITY = 10;
64
65     /** The elements of this deque (indices <tt>0</tt> to <tt>size-1</tt>). */
66     private transient long[] data;
67
68     /**
69      * The current size of this deque.
70      * @serial
71      */

72     private int size;
73
74     /** The index of the first element in this deque. */
75     private transient int first;
76
77     /** The index of the last element in this deque. */
78     private transient int last;
79
80     /**
81      * The growth policy of this deque (0 is relative growth, 1 is absolute growth).
82      * @serial
83      */

84     private int growthPolicy;
85
86     /**
87      * The growth factor of this deque, if the growth policy is
88      * relative.
89      * @serial
90      */

91     private double growthFactor;
92
93     /**
94      * The growth chunk size of this deque, if the growth policy is
95      * absolute.
96      * @serial
97      */

98     private int growthChunk;
99
100     private LongArrayDeque(int capacity, int growthPolicy, double growthFactor, int growthChunk) {
101         if (capacity < 0)
102             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
103         if (growthFactor < 0.0)
104             Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor));
105         if (growthChunk < 0)
106             Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk));
107         data = new long[capacity];
108         size = 0;
109         this.growthPolicy = growthPolicy;
110         this.growthFactor = growthFactor;
111         this.growthChunk = growthChunk;
112         this.first = 0;
113         this.last = 0;
114     }
115
116     /**
117      * Creates a new array deque with capacity 10 and a relative
118      * growth factor of 1.0.
119      *
120      * @see #LongArrayDeque(int,double)
121      */

122     public LongArrayDeque() {
123         this(DEFAULT_CAPACITY);
124     }
125
126     /**
127      * Creates a new array deque with the same elements as a
128      * specified collection. The elements of the specified collection
129      * are added to the end of the deque in the collection's iteration
130      * order.
131      *
132      * @param c
133      * the collection whose elements to add to the new
134      * deque.
135      *
136      * @throws NullPointerException
137      * if <tt>c</tt> is <tt>null</tt>.
138      */

139     public LongArrayDeque(LongCollection c) {
140         this(c.size());
141         addAll(c);
142     }
143
144     /**
145      * Creates a new array deque with the same elements as a
146      * specified array. The elements of the specified array
147      * are added the end of the deque in the order in which they
148      * appear in the array.
149      *
150      * @param a
151      * the array whose elements to add to the new
152      * deque.
153      *
154      * @throws NullPointerException
155      * if <tt>a</tt> is <tt>null</tt>.
156      *
157      * @since 1.1
158      */

159     public LongArrayDeque(long[] a) {
160         this(a.length);
161         System.arraycopy(a, 0, data, 0, a.length);
162         size = a.length;
163         first = 0;
164         last = a.length-1;
165     }
166
167     /**
168      * Creates a new array deque with a specified capacity and a
169      * relative growth factor of 1.0.
170      *
171      * @param capacity
172      * the initial capacity of the deque.
173      *
174      * @see #LongArrayDeque(int,double)
175      *
176      * @throws IllegalArgumentException
177      * if <tt>capacity</tt> is negative.
178      */

179     public LongArrayDeque(int capacity) {
180         this(capacity, DEFAULT_GROWTH_FACTOR);
181     }
182
183     /**
184      * Creates a new array deque with a specified capacity and
185      * relative growth factor.
186      *
187      * <p>The array capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
188      * This strategy is good for avoiding many capacity increases, but
189      * the amount of wasted memory is approximately the size of the deque.
190      *
191      * @param capacity
192      * the initial capacity of the deque.
193      *
194      * @param growthFactor
195      * the relative amount with which to increase the
196      * the capacity when a capacity increase is needed.
197      *
198      * @throws IllegalArgumentException
199      * if <tt>capacity</tt> is negative;
200      * if <tt>growthFactor</tt> is negative.
201      */

202     public LongArrayDeque(int capacity, double growthFactor) {
203         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK);
204     }
205
206     /**
207      * Creates a new array deque with a specified capacity and
208      * absolute growth factor.
209      *
210      * <p>The array capacity increases to <tt>capacity()+growthChunk</tt>.
211      * This strategy is good for avoiding wasting memory. However, an
212      * overhead is potentially introduced by frequent capacity increases.
213      *
214      * @param capacity
215      * the initial capacity of the deque.
216      *
217      * @param growthChunk
218      * the absolute amount with which to increase the
219      * the capacity when a capacity increase is needed.
220      *
221      * @throws IllegalArgumentException
222      * if <tt>capacity</tt> is negative;
223      * if <tt>growthChunk</tt> is negative.
224      */

225     public LongArrayDeque(int capacity, int growthChunk) {
226         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk);
227     }
228
229     // ---------------------------------------------------------------
230
// Array management
231
// ---------------------------------------------------------------
232

233     /**
234      * Computes the new capacity of the deque based on a needed
235      * capacity and the growth policy.
236      *
237      * @param capacity
238      * the needed capacity of the deque.
239      *
240      * @return the new capacity of the deque.
241      */

242     private int computeCapacity(int capacity) {
243         int newcapacity;
244         if (growthPolicy == GROWTH_POLICY_RELATIVE)
245             newcapacity = (int)(data.length * (1.0 + growthFactor));
246         else
247             newcapacity = data.length + growthChunk;
248         if (newcapacity < capacity)
249             newcapacity = capacity;
250         return newcapacity;
251     }
252
253     /**
254      * Ensures that this deque has at least a specified capacity.
255      * The actual capacity is calculated from the growth factor
256      * or growth chunk specified to the constructor.
257      *
258      * @param capacity
259      * the minimum capacity of this deque.
260      *
261      * @return the new capacity of this deque.
262      *
263      * @see #capacity()
264      */

265     public int ensureCapacity(int capacity) {
266         if (capacity > data.length) {
267             long[] newdata = new long[capacity = computeCapacity(capacity)];
268             toArray(newdata);
269             first = 0;
270             last = size;
271             data = newdata;
272         }
273         return capacity;
274     }
275
276     /**
277      * Returns the current capacity of this deque. The capacity is the
278      * number of elements that the deque can contain without having to
279      * increase the amount of memory used.
280      *
281      * @return the current capacity of this deque.
282      *
283      * @see #ensureCapacity(int)
284      */

285     public int capacity()
286     { return data.length; }
287
288     // ---------------------------------------------------------------
289
// Operations not supported by abstract list implementation
290
// ---------------------------------------------------------------
291

292     public void add(int index, long v) {
293         if (index == 0)
294             addFirst(v);
295         else if (index == size)
296             addLast(v);
297         else {
298             if (index < 0 || index > size)
299                 Exceptions.indexOutOfBounds(index, 0, size);
300             ensureCapacity(size+1);
301             if (first < last || last == 0) { // data is in one block
302
int iidx = index+first;
303                 int end = last == 0 ? data.length : last;
304                 int block = end-iidx;
305                 if (last == 0) { // wrap one element around end
306
data[0] = data[data.length-1];
307                     System.arraycopy(data, iidx, data, iidx+1, block-1);
308                     last = 1;
309                 } else {
310                     System.arraycopy(data, iidx, data, iidx+1, block);
311                     if (++last == data.length)
312                         last = 0;
313                 }
314                 data[iidx] = v;
315             } else { // data is split
316
int iidx = (first+index) % data.length;
317                 if (iidx <= last) { // element is in left block
318
int block = last-iidx;
319                     System.arraycopy(data, iidx, data, iidx+1, block);
320                     last++;
321                     data[iidx] = v;
322                 } else { // element is in right block
323
int block = iidx-first;
324                     System.arraycopy(data, first, data, first-1, block);
325                     first--;
326                     data[iidx-1] = v;
327                 }
328             }
329             size++;
330         }
331     }
332
333     public long get(int index) {
334         if (index < 0 || index >= size)
335             Exceptions.indexOutOfBounds(index, 0, size-1);
336         return data[(first+index) % data.length];
337     }
338
339     public long set(int index, long v) {
340         if (index < 0 || index >= size)
341             Exceptions.indexOutOfBounds(index, 0, size-1);
342         int idx = (first+index) % data.length;
343         long result = data[idx];
344         data[idx] = v;
345         return result;
346     }
347
348     public long removeElementAt(int index) {
349         long result;
350         if (index == 0)
351             result = removeFirst();
352         else if (index == size-1)
353             result = removeLast();
354         else {
355             if (index < 0 || index >= size)
356                 Exceptions.indexOutOfBounds(index, 0, size-1);
357             int ridx = (first+index) % data.length;
358             result = data[ridx];
359             if (first < last || last == 0) { // data is in one block
360
// move the shorter block
361
int block1 = ridx-first;
362                 int block2 = size-block1-1;
363                 if (block1 < block2) { // move first block
364
System.arraycopy(data, first, data, first+1, block1);
365                     first++;
366                 } else { // move last block
367
System.arraycopy(data, ridx+1, data, ridx, block2);
368                     if (--last < 0)
369                         last = data.length-1;
370                 }
371             } else { // data is split
372
if (ridx < last) { // element is in left block
373
int block = last-ridx-1;
374                     System.arraycopy(data, ridx+1, data, ridx, block);
375                     last--;
376                 } else { // element is in right block
377
int block = ridx-first;
378                     System.arraycopy(data, first, data, first+1, block);
379                     if (++first == data.length)
380                         first = 0;
381                 }
382             }
383             size--;
384         }
385         return result;
386     }
387
388     /**
389      * Minimizes the memory used by this array deque. The underlying
390      * array is replaced by an array whose size is exactly the number
391      * of elements in this array deque. The method can be used to
392      * free up memory after many removals.
393      */

394     public void trimToSize() {
395         if (data.length > size) {
396             long[] newdata = toArray();
397             first = 0;
398             last = 0;
399             data = newdata;
400         }
401     }
402
403     /**
404      * Returns a clone of this array deque.
405      *
406      * @return a clone of this array deque.
407      *
408      * @since 1.1
409      */

410     public Object JavaDoc clone() {
411         try {
412             LongArrayDeque c = (LongArrayDeque)super.clone();
413             c.data = new long[data.length];
414             // This could be improved to only copying the blocks in use.
415
System.arraycopy(data, 0, c.data, 0, data.length);
416             return c;
417         } catch (CloneNotSupportedException JavaDoc e) {
418             Exceptions.cloning(); return null;
419         }
420     }
421
422     // ---------------------------------------------------------------
423
// Operations declared by LongDeque
424
// ---------------------------------------------------------------
425

426     public long getFirst() {
427         if (size == 0)
428             Exceptions.dequeNoFirst();
429         return data[first];
430     }
431
432     public long getLast() {
433         if (size == 0)
434             Exceptions.dequeNoLast();
435         return data[last == 0 ? data.length-1 : last-1];
436     }
437
438     public void addFirst(long v) {
439         ensureCapacity(size+1);
440         if (--first < 0)
441             first = data.length-1;
442         data[first] = v;
443         size++;
444     }
445
446     public void addLast(long v) {
447         ensureCapacity(size+1);
448         data[last] = v;
449         if (++last == data.length)
450             last = 0;
451         size++;
452     }
453
454     public long removeFirst() {
455         if (size == 0)
456             Exceptions.dequeNoFirstToRemove();
457         long result = data[first];
458         if (++first == data.length)
459             first = 0;
460         size--;
461         return result;
462     }
463
464     public long removeLast() {
465         if (size == 0)
466             Exceptions.dequeNoLastToRemove();
467         if (--last < 0)
468             last = data.length-1;
469         size--;
470         return data[last];
471     }
472
473     // ---------------------------------------------------------------
474
// Operations overwritten for efficiency
475
// ---------------------------------------------------------------
476

477     public int size()
478     { return size; }
479
480     public boolean isEmpty()
481     { return size == 0; }
482
483     public void clear() {
484         size = 0;
485         first = 0;
486         last = 0;
487     }
488
489     public boolean contains(long v) {
490         for (int i = 0, idx = first; i < size; i++) {
491             if (data[idx] == v)
492                 return true;
493             if (++idx == data.length)
494                 idx = 0;
495         }
496         return false;
497     }
498
499     public int indexOf(long c) {
500         for (int i = 0, idx = first; i < size; i++) {
501             if (data[idx] == c)
502                 return i;
503             if (++idx == data.length)
504                 idx = 0;
505         }
506         return -1;
507     }
508
509     public int lastIndexOf(long c) {
510         for (int i = size-1, idx = last-1; i >= 0; i--) {
511             if (idx < 0)
512                 idx = data.length-1;
513             if (data[idx] == c)
514                 return i;
515             idx--;
516         }
517         return -1;
518     }
519
520     public boolean remove(long v) {
521         int index = indexOf(v);
522         if (index != -1) {
523             removeElementAt(index);
524             return true;
525         }
526         return false;
527     }
528
529     public long[] toArray(long[] a) {
530         if (a == null || a.length < size)
531             a = new long[size];
532         if (last <= first) {
533             if (last == 0) { // one block at end
534
System.arraycopy(data, first, a, 0, size);
535             } else { // two blocks
536
int block1 = data.length-first;
537                 int block2 = size-block1;
538                 // copy block at end
539
System.arraycopy(data, first, a, 0, block1);
540                 // copy block at start
541
System.arraycopy(data, 0, a, block1, block2);
542             }
543         } else { // one block in middle
544
System.arraycopy(data, first, a, 0, size);
545         }
546         return a;
547     }
548
549     public boolean equals(Object JavaDoc obj) {
550         if (this == obj)
551             return true;
552         if (!(obj instanceof LongDeque))
553             return false;
554         LongDeque s = (LongDeque)obj;
555         if (size != s.size())
556             return false;
557         LongListIterator i2 = s.listIterator();
558         for (int i = 0, idx = first; i < size; i++) {
559             if (data[idx] != i2.next())
560                 return false;
561             if (++idx == data.length)
562                 idx = 0;
563         }
564         return true;
565     }
566
567     public int hashCode() {
568         int h = 1;
569         for (int i = 0, idx = first; i < size; i++) {
570             h = (int)(31*h + DefaultLongHashFunction.INSTANCE.hash(data[idx]));
571             if (++idx == data.length)
572                 idx = 0;
573         }
574         return h;
575     }
576
577     // ---------------------------------------------------------------
578
// Serialization
579
// ---------------------------------------------------------------
580

581     /**
582      * @serialData Default fields; the capacity of the
583      * deque (<tt>int</tt>); the deques's elements
584      * (<tt>long</tt>).
585      *
586      * @since 1.1
587      */

588     private void writeObject(ObjectOutputStream JavaDoc s) throws IOException JavaDoc {
589         s.defaultWriteObject();
590         s.writeInt(data.length);
591         LongIterator i = iterator();
592         while (i.hasNext())
593             s.writeLong(i.next());
594     }
595
596     /**
597      * @since 1.1
598      */

599     private void readObject(ObjectInputStream JavaDoc s) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
600         s.defaultReadObject();
601         data = new long[s.readInt()];
602         first = 0;
603         last = size;
604         for (int i = 0; i < size; i++)
605             data[i] = s.readLong();
606     }
607
608 }
Popular Tags