KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2002, 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 implemenation of lists of
33  * long values.
34  *
35  * @see java.util.ArrayList
36  *
37  * @author Søren Bak
38  * @version 1.3 21-08-2003 19:27
39  * @since 1.0
40  */
41 public class LongArrayList extends AbstractLongList implements 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 list.
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 list. */
57     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
58
59     /** The default chunk size with which to increase the capacity of this list. */
60     public static final int DEFAULT_GROWTH_CHUNK = 10;
61
62     /** The default capacity of this list. */
63     public static final int DEFAULT_CAPACITY = 10;
64
65     /** The elements of this list (indices <tt>0</tt> to <tt>size-1</tt>). */
66     private transient long[] data;
67
68     /**
69      * The current size of this list.
70      * @serial
71      */
72     private int size;
73
74     /**
75      * The growth policy of this list (0 is relative growth, 1 is absolute growth).
76      * @serial
77      */
78     private int growthPolicy;
79
80     /**
81      * The growth factor of this list, if the growth policy is
82      * relative.
83      * @serial
84      */
85     private double growthFactor;
86
87     /**
88      * The growth chunk size of this list, if the growth policy is
89      * absolute.
90      * @serial
91      */
92     private int growthChunk;
93
94     private LongArrayList(int capacity, int growthPolicy, double growthFactor, int growthChunk) {
95         if (capacity < 0)
96             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
97         if (growthFactor < 0.0)
98             Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor));
99         if (growthChunk < 0)
100             Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk));
101         data = new long[capacity];
102         size = 0;
103         this.growthPolicy = growthPolicy;
104         this.growthFactor = growthFactor;
105         this.growthChunk = growthChunk;
106     }
107
108     /**
109      * Creates a new array list with capacity 10 and a relative
110      * growth factor of 1.0.
111      *
112      * @see #LongArrayList(int,double)
113      */
114     public LongArrayList() {
115         this(DEFAULT_CAPACITY);
116     }
117
118     /**
119      * Creates a new array list with the same elements as a
120      * specified collection. The elements of the specified collection
121      * are added to the end of the list in the collection's iteration
122      * order.
123      *
124      * @param c
125      * the collection whose elements to add to the new
126      * list.
127      *
128      * @throws NullPointerException
129      * if <tt>c</tt> is <tt>null</tt>.
130      */
131     public LongArrayList(LongCollection c) {
132         this(c.size());
133         addAll(c);
134     }
135
136     /**
137      * Creates a new array list with the same elements as a
138      * specified array. The elements of the specified array
139      * are added to the end of the list in order of the array.
140      *
141      * @param a
142      * the array whose elements to add to the new
143      * list.
144      *
145      * @throws NullPointerException
146      * if <tt>a</tt> is <tt>null</tt>.
147      *
148      * @since 1.1
149      */
150     public LongArrayList(long[] a) {
151         this(a.length);
152         System.arraycopy(a, 0, data, 0, a.length);
153         size = a.length;
154     }
155
156     /**
157      * Creates a new array list with a specified capacity and a
158      * relative growth factor of 1.0.
159      *
160      * @param capacity
161      * the initial capacity of the list.
162      *
163      * @see #LongArrayList(int,double)
164      *
165      * @throws IllegalArgumentException
166      * if <tt>capacity</tt> is negative.
167      */
168     public LongArrayList(int capacity) {
169         this(capacity, DEFAULT_GROWTH_FACTOR);
170     }
171
172     /**
173      * Creates a new array list with a specified capacity and
174      * relative growth factor.
175      *
176      * <p>The array capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
177      * This strategy is good for avoiding many capacity increases, but
178      * the amount of wasted memory is approximately the size of the list.
179      *
180      * @param capacity
181      * the initial capacity of the list.
182      *
183      * @param growthFactor
184      * the relative amount with which to increase the
185      * the capacity when a capacity increase is needed.
186      *
187      * @throws IllegalArgumentException
188      * if <tt>capacity</tt> is negative;
189      * if <tt>growthFactor</tt> is negative.
190      */
191     public LongArrayList(int capacity, double growthFactor) {
192         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK);
193     }
194
195     /**
196      * Creates a new array list with a specified capacity and
197      * absolute growth factor.
198      *
199      * <p>The array capacity increases to <tt>capacity()+growthChunk</tt>.
200      * This strategy is good for avoiding wasting memory. However, an
201      * overhead is potentially introduced by frequent capacity increases.
202      *
203      * @param capacity
204      * the initial capacity of the list.
205      *
206      * @param growthChunk
207      * the absolute amount with which to increase the
208      * the capacity when a capacity increase is needed.
209      *
210      * @throws IllegalArgumentException
211      * if <tt>capacity</tt> is negative;
212      * if <tt>growthChunk</tt> is negative.
213      */
214     public LongArrayList(int capacity, int growthChunk) {
215         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk);
216     }
217
218     // ---------------------------------------------------------------
219 // Array management
220 // ---------------------------------------------------------------
221
222     /**
223      * Computes the new capacity of the list based on a needed
224      * capacity and the growth policy.
225      *
226      * @param capacity
227      * the needed capacity of the list.
228      *
229      * @return the new capacity of the list.
230      */
231     private int computeCapacity(int capacity) {
232         int newcapacity;
233         if (growthPolicy == GROWTH_POLICY_RELATIVE)
234             newcapacity = (int)(data.length * (1.0 + growthFactor));
235         else
236             newcapacity = data.length + growthChunk;
237         if (newcapacity < capacity)
238             newcapacity = capacity;
239         return newcapacity;
240     }
241
242     /**
243      * Ensures that this list has at least a specified capacity.
244      * The actual capacity is calculated from the growth factor
245      * or growth chunk specified to the constructor.
246      *
247      * @param capacity
248      * the minimum capacity of this list.
249      *
250      * @return the new capacity of this list.
251      *
252      * @see #capacity()
253      */
254     public int ensureCapacity(int capacity) {
255         if (capacity > data.length) {
256             long[] newdata = new long[capacity = computeCapacity(capacity)];
257             System.arraycopy(data, 0, newdata, 0, size);
258             data = newdata;
259         }
260         return capacity;
261     }
262
263     /**
264      * Returns the current capacity of this list. The capacity is the
265      * number of elements that the list can contain without having to
266      * increase the amount of memory used.
267      *
268      * @return the current capacity of this list.
269      *
270      * @see #ensureCapacity(int)
271      */
272     public int capacity()
273     { return data.length; }
274
275     // ---------------------------------------------------------------
276 // Operations not supported by abstract implementation
277 // ---------------------------------------------------------------
278
279     public void add(int index, long v) {
280         if (index < 0 || index > size)
281             Exceptions.indexOutOfBounds(index, 0, size);
282         ensureCapacity(size+1);
283         // Move data
284 int block = size-index;
285         if (block > 0)
286             System.arraycopy(data, index, data, index+1, block);
287         data[index] = v;
288         size++;
289     }
290
291     public long get(int index) {
292         if (index < 0 || index >= size)
293             Exceptions.indexOutOfBounds(index, 0, size-1);
294         return data[index];
295     }
296
297     public long set(int index, long v) {
298         if (index < 0 || index >= size)
299             Exceptions.indexOutOfBounds(index, 0, size-1);
300         long result = data[index];
301         data[index] = v;
302         return result;
303     }
304
305     public long removeElementAt(int index) {
306         if (index < 0 || index >= size)
307             Exceptions.indexOutOfBounds(index, 0, size-1);
308         long result = data[index];
309         // Move data
310 int block = size-(index+1);
311         if (block > 0)
312             System.arraycopy(data, index+1, data, index, block);
313         size--;
314         return result;
315     }
316
317     /**
318      * Minimizes the memory used by this array list. The underlying
319      * array is replaced by an array whose size is exactly the number
320      * of elements in this array list. The method can be used to
321      * free up memory after many removals.
322      */
323     public void trimToSize() {
324         if (data.length > size) {
325             long[] newdata = new long[size];
326             System.arraycopy(data, 0, newdata, 0, size);
327             data = newdata;
328         }
329     }
330
331     /**
332      * Returns a clone of this array list.
333      *
334      * @return a clone of this array list.
335      *
336      * @since 1.1
337      */
338     public Object JavaDoc clone() {
339         try {
340             LongArrayList c = (LongArrayList)super.clone();
341             c.data = new long[data.length];
342             System.arraycopy(data, 0, c.data, 0, size);
343             return c;
344         } catch (CloneNotSupportedException JavaDoc e) {
345             Exceptions.cloning(); return null;
346         }
347     }
348
349     // ---------------------------------------------------------------
350 // Operations overwritten for efficiency
351 // ---------------------------------------------------------------
352
353     public int size()
354     { return size; }
355
356     public boolean isEmpty()
357     { return size == 0; }
358
359     public void clear()
360     { size = 0; }
361
362     public boolean contains(long v) {
363         for (int i = 0; i < size; i++)
364             if (data[i] == v)
365                 return true;
366         return false;
367     }
368
369     public int indexOf(long c) {
370         for (int i = 0; i < size; i++)
371             if (data[i] == c)
372                 return i;
373         return -1;
374     }
375
376     /**
377      * @since 1.2
378      */
379     public int indexOf(int index, long c) {
380         if (index < 0 || index > size)
381             Exceptions.indexOutOfBounds(index, 0, size);
382         for (int i = index; i < size; i++)
383             if (data[i] == c)
384                 return i;
385         return -1;
386     }
387
388
389     public int lastIndexOf(long c) {
390         for (int i = size-1; i >= 0; i--)
391             if (data[i] == c)
392                 return i;
393         return -1;
394     }
395
396     public boolean remove(long v) {
397         int index = indexOf(v);
398         if (index != -1) {
399             removeElementAt(index);
400             return true;
401         }
402         return false;
403     }
404
405     public long[] toArray() {
406         long[] a = new long[size];
407         System.arraycopy(data, 0, a, 0, size);
408         return a;
409     }
410
411     public long[] toArray(long[] a) {
412         if (a == null || a.length < size)
413             a = new long[size];
414         System.arraycopy(data, 0, a, 0, size);
415         return a;
416     }
417
418     public boolean equals(Object JavaDoc obj) {
419         if (this == obj)
420             return true;
421         if (!(obj instanceof LongList))
422             return false;
423         int i1 = 0;
424         LongListIterator i2 = ((LongList)obj).listIterator();
425         while(i1 < size && i2.hasNext())
426             if (data[i1++] != i2.next())
427                 return false;
428         return !(i1 < size || i2.hasNext());
429     }
430
431     public int hashCode() {
432         int h = 1;
433         for (int i = 0; i < size; i++)
434             h = (int)(31*h + DefaultLongHashFunction.INSTANCE.hash(data[i]));
435         return h;
436     }
437
438     // ---------------------------------------------------------------
439 // Serialization
440 // ---------------------------------------------------------------
441
442     /**
443      * @serialData Default fields; the capacity of the
444      * list (<tt>int</tt>); the list's elements
445      * (<tt>long</tt>).
446      *
447      * @since 1.1
448      */
449     private void writeObject(ObjectOutputStream JavaDoc s) throws IOException JavaDoc {
450         s.defaultWriteObject();
451         s.writeInt(data.length);
452         for (int i = 0; i < size; i++)
453             s.writeLong(data[i]);
454     }
455
456     /**
457      * @since 1.1
458      */
459     private void readObject(ObjectInputStream JavaDoc s) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
460         s.defaultReadObject();
461         data = new long[s.readInt()];
462         for (int i = 0; i < size; i++)
463             data[i] = s.readLong();
464     }
465
466 }
Popular Tags