KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > triactive > jdo > util > IntArrayList


1 /*
2  * Copyright 2004 (C) TJDO.
3  * All rights reserved.
4  *
5  * This software is distributed under the terms of the TJDO License version 1.0.
6  * See the terms of the TJDO License in the documentation provided with this software.
7  *
8  * $Id: IntArrayList.java,v 1.1 2004/01/18 03:01:07 jackknifebarber Exp $
9  */

10
11 package com.triactive.jdo.util;
12
13 import java.util.Arrays JavaDoc;
14
15
16 /**
17  * A variation on the standard ArrayList class that efficiently handles arrays
18  * of integers.
19  * Using this class rather than <tt>ArrayList</tt> avoids the need to "box" each
20  * element in an instance of <tt>java.lang.Integer</tt>.
21  * It is useful where performance is important.
22  *
23  * @author <a HREF="mailto:mmartin5@austin.rr.com">Mike Martin</a>
24  * @version $Revision: 1.1 $
25  */

26
27 public class IntArrayList implements Cloneable JavaDoc
28 {
29     private int[] elements;
30     private int size = 0;
31
32
33     /**
34      * Constructs an empty list with an initial capacity of ten.
35      */

36
37     public IntArrayList()
38     {
39         this(10);
40     }
41
42
43     /**
44      * Constructs an empty list with the specified initial capacity.
45      *
46      * @param initialCapacity
47      * The initial capacity of the list.
48      *
49      * @exception IllegalArgumentException
50      * If the specified initial capacity is negative.
51      */

52
53     public IntArrayList(int initialCapacity)
54     {
55         if (initialCapacity < 0)
56             throw new IllegalArgumentException JavaDoc("Illegal capacity: "+ initialCapacity);
57
58         elements = new int[initialCapacity];
59     }
60
61
62     /**
63      * Constructs a list containing the elements of the specified array.
64      * The <tt>IntArrayList</tt> instance has an initial capacity of 110% the
65      * size of the specified collection.
66      *
67      * @param initialContents
68      * The array whose elements are to be placed into this list.
69      */

70
71     public IntArrayList(int[] initialContents)
72     {
73         size = initialContents.length;
74         elements = new int[(int)Math.min((size * 11L)/10, Integer.MAX_VALUE)];
75
76         System.arraycopy(initialContents, 0, elements, 0, size);
77     }
78
79
80     /**
81      * Trims the capacity of this <tt>IntArrayList</tt> instance to be the
82      * list's current size.
83      * An application can use this operation to minimize the storage of an
84      * <tt>IntArrayList</tt> instance.
85      */

86
87     public void trimToSize()
88     {
89         if (size < elements.length)
90         {
91             int[] newelems = new int[size];
92             System.arraycopy(elements, 0, newelems, 0, size);
93             elements = newelems;
94         }
95     }
96
97
98     /**
99      * Increases the capacity of this <tt>IntArrayList</tt> instance, if
100      * necessary, to ensure that it can hold at least the number of elements
101      * specified by the minimum capacity argument.
102      *
103      * @param minCapacity
104      * The desired minimum capacity.
105      */

106
107     public void ensureCapacity(int minCapacity)
108     {
109         int oldCapacity = elements.length;
110
111         if (minCapacity > oldCapacity)
112         {
113             int[] newelems = new int[(int)Math.min((oldCapacity * 3L)/2, Integer.MAX_VALUE)];
114             System.arraycopy(elements, 0, newelems, 0, size);
115             elements = newelems;
116         }
117     }
118
119
120     /**
121      * Returns the number of elements in this list.
122      *
123      * @return The number of elements in this list.
124      */

125
126     public int size()
127     {
128         return size;
129     }
130
131
132     /**
133      * Tests if this list has no elements.
134      *
135      * @return <tt>true</tt> if this list has no elements;
136      * <tt>false</tt> otherwise.
137      */

138
139     public boolean isEmpty()
140     {
141         return size == 0;
142     }
143
144
145     /**
146      * Returns <tt>true</tt> if this list contains the specified element.
147      *
148      * @param elem element whose presence in this List is to be tested.
149      *
150      * @return <code>true</code> if the specified element is present;
151      * <code>false</code> otherwise.
152      */

153
154     public boolean contains(int elem)
155     {
156         return indexOf(elem) >= 0;
157     }
158
159
160     /**
161      * Searches for the first occurence of the given argument.
162      *
163      * @param elem
164      * An integer to search for.
165      *
166      * @return The index of the first occurrence of the argument in this
167      * list; returns <tt>-1</tt> if the value is not found.
168      */

169
170     public int indexOf(int elem)
171     {
172         for (int i = 0; i < size; ++i)
173         {
174             if (elements[i] == elem)
175                 return i;
176         }
177
178         return -1;
179     }
180
181
182     /**
183      * Returns the index of the last occurrence of the specified integer in
184      * this list.
185      *
186      * @param elem
187      * The desired element.
188      *
189      * @return The index of the last occurrence of the specified integer in
190      * this list; returns <tt>-1</tt> if the value is not found.
191      */

192
193     public int lastIndexOf(int elem)
194     {
195         for (int i = size - 1; i >= 0; --i)
196         {
197             if (elements[i] == elem)
198                 return i;
199         }
200
201         return -1;
202     }
203
204
205     /**
206      * Returns a copy of this <tt>IntArrayList</tt> instance.
207      *
208      * @return A clone of this <tt>ArrayList</tt> instance.
209      */

210
211     public Object JavaDoc clone()
212     {
213         try
214         {
215             IntArrayList l = (IntArrayList)super.clone();
216             l.elements = new int[size];
217             System.arraycopy(elements, 0, l.elements, 0, size);
218             return l;
219         }
220         catch (CloneNotSupportedException JavaDoc e)
221         {
222             /* Should never happen since we are Cloneable. */
223             throw new InternalError JavaDoc();
224         }
225     }
226
227
228     /**
229      * Returns an array containing all of the elements in this list.
230      *
231      * @return An array containing all of the elements in this list.
232      */

233
234     public int[] toArray()
235     {
236         int[] result = new int[size];
237         System.arraycopy(elements, 0, result, 0, size);
238         return result;
239     }
240
241
242     /**
243      * Check if the given index is in range.
244      * If not, throw an appropriate runtime exception.
245      */

246
247     private void rangeCheck(int index)
248     {
249         if (index < 0 || index >= size)
250             throw new IndexOutOfBoundsException JavaDoc("Index: " + index + ", Size: " + size);
251     }
252
253
254     /**
255      * Returns the element at the specified position in this list.
256      *
257      * @param index
258      * Index of element to return.
259      *
260      * @return
261      * The element at the specified position in this list.
262      *
263      * @exception IndexOutOfBoundsException
264      * If index is out of range <tt>(index &lt; 0 || index &gt;= size())</tt>.
265      */

266
267     public int get(int index)
268     {
269         rangeCheck(index);
270
271         return elements[index];
272     }
273
274
275     /**
276      * Replaces the element at the specified position in this list with
277      * the specified element.
278      *
279      * @param index
280      * Index of element to replace.
281      * @param element
282      * Element to be stored at the specified position.
283      *
284      * @return
285      * The element previously at the specified position.
286      *
287      * @exception IndexOutOfBoundsException
288      * If index is out of range <tt>(index &lt; 0 || index &gt;= size())</tt>.
289      */

290
291     public int set(int index, int element)
292     {
293         rangeCheck(index);
294
295         int oldValue = elements[index];
296         elements[index] = element;
297         return oldValue;
298     }
299
300
301     /**
302      * Appends the specified element to the end of this list.
303      *
304      * @param element
305      * Element to be appended to this list.
306      */

307
308     public void add(int element)
309     {
310         ensureCapacity(size + 1);
311         elements[size++] = element;
312     }
313
314
315     /**
316      * Inserts the specified element at the specified position in this
317      * list.
318      * Shifts the element currently at that position (if any) and any subsequent
319      * elements to the right (adds one to their indices).
320      *
321      * @param index
322      * Index at which the specified element is to be inserted.
323      * @param element
324      * Element to be inserted.
325      *
326      * @exception IndexOutOfBoundsException
327      * If index is out of range <tt>(index &lt; 0 || index &gt; size())</tt>.
328      */

329
330     public void add(int index, int element)
331     {
332         if (index < 0 || index > size)
333             throw new IndexOutOfBoundsException JavaDoc("Index: " + index + ", Size: " + size);
334
335         ensureCapacity(size + 1);
336         System.arraycopy(elements, index, elements, index + 1, size - index);
337         elements[index] = element;
338         ++size;
339     }
340
341
342     /**
343      * Removes the element at the specified position in this list.
344      * Shifts any subsequent elements to the left (subtracts one from their
345      * indices).
346      *
347      * @param index
348      * The index of the element to removed.
349      *
350      * @return
351      * The element that was removed from the list.
352      *
353      * @exception IndexOutOfBoundsException
354      * If index is out of range <tt>(index &lt; 0 || index &gt;= size())</tt>.
355      */

356
357     public int remove(int index)
358     {
359         rangeCheck(index);
360
361         int oldValue = elements[index];
362         int numMoved = size - index - 1;
363         if (numMoved > 0)
364             System.arraycopy(elements, index + 1, elements, index, numMoved);
365
366         --size;
367
368         return oldValue;
369     }
370
371
372     /**
373      * Removes all of the elements from this list.
374      * The list will be empty after this call returns.
375      */

376
377     public void clear()
378     {
379         size = 0;
380     }
381
382
383     /**
384      * Appends all of the elements in the specified array to the end of this
385      * list.
386      *
387      * @param ai
388      * The elements to be added to this list.
389      */

390
391     public void addAll(int[] ai)
392     {
393         int numNew = ai.length;
394         ensureCapacity(size + numNew);
395
396         System.arraycopy(ai, 0, elements, size, numNew);
397     }
398
399
400     /**
401      * Inserts all of the elements in the specified array into this list,
402      * starting at the specified position.
403      * Shifts the element currently at that position (if any) and any subsequent
404      * elements to the right (increases their indices).
405      * The new elements will appear in the list in the order that they exist in
406      * the array argument.
407      *
408      * @param index
409      * Index at which to insert first element from the specified array.
410      * @param ai
411      * Elements to be inserted into this list.
412      *
413      * @exception IndexOutOfBoundsException
414      * If index is out of range <tt>(index &lt; 0 || index &gt; size())</tt>.
415      */

416
417     public void addAll(int index, int[] ai)
418     {
419         if (index < 0 || index > size)
420             throw new IndexOutOfBoundsException JavaDoc("Index: " + index + ", Size: " + size);
421
422         int numNew = ai.length;
423         ensureCapacity(size + numNew);
424
425         int numMoved = size - index;
426         if (numMoved > 0)
427             System.arraycopy(elements, index, elements, index + numNew, numMoved);
428
429         System.arraycopy(ai, 0, elements, index, numNew);
430
431         size += numNew;
432     }
433
434
435     /**
436      * Returns <tt>true</tt> if this list contains all of the elements in the
437      * specified list.
438      * <p>
439      * This implementation iterates over the specified array, checking each
440      * element in turn to see if it's contained in this list.
441      * If all elements are so contained <tt>true</tt> is returned, otherwise
442      * <tt>false</tt>.
443      *
444      * @param ai
445      * Array to be checked for containment in this list.
446      *
447      * @return
448      * <tt>true</tt> if this list contains all of the elements in the
449      * specified array.
450      *
451      * @see #contains
452      */

453
454     public boolean containsAll(int[] ai)
455     {
456         for (int i = 0; i < ai.length; ++i)
457         {
458             if (!contains(ai[i]))
459                 return false;
460         }
461
462         return true;
463     }
464
465
466     /**
467      * Removes from this list all of its elements that are contained in the
468      * specified array.
469      * <p>
470      * This implementation iterates over this list, checking each element in
471      * turn to see if it's contained in the specified array.
472      * If it's so contained, it's removed from this list.
473      *
474      * @param ai
475      * Elements to be removed from this list.
476      *
477      * @return
478      * <tt>true</tt> if this list changed as a result of the call.
479      *
480      * @see #remove
481      * @see #contains
482      */

483
484     public boolean removeAll(int[] ai)
485     {
486         IntArrayList l = new IntArrayList(ai);
487         boolean modified = false;
488
489         for (int i = 0; i < size; ++i)
490         {
491             while (i < size && l.contains(elements[i]))
492             {
493                 remove(i);
494                 modified = true;
495             }
496         }
497
498         return modified;
499     }
500
501
502     /**
503      * Retains only the elements in this list that are contained in the
504      * specified array.
505      * In other words, removes from this list all of its elements that are not
506      * contained in the specified array.
507      * <p>
508      * This implementation iterates over this list, checking each element in
509      * turn to see if it's contained in the specified array.
510      * If it's not so contained, it's removed from this list.
511      *
512      * @param ai
513      * Elements to be retained in this list.
514      *
515      * @return
516      * <tt>true</tt> if this list changed as a result of the call.
517      *
518      * @see #remove
519      * @see #contains
520      */

521
522     public boolean retainAll(int[] ai)
523     {
524         IntArrayList l = new IntArrayList(ai);
525         boolean modified = false;
526
527         for (int i = 0; i < size; ++i)
528         {
529             while (i < size && !l.contains(elements[i]))
530             {
531                 remove(i);
532                 modified = true;
533             }
534         }
535
536         return modified;
537     }
538
539
540     /**
541      * Compares the specified object with this list for equality.
542      * Returns <tt>true</tt> if and only if the specified object is also an
543      * IntArrayList, both lists have the same size, and all corresponding pairs
544      * of elements in the two lists are equal.
545      *
546      * @param o the object to be compared for equality with this list.
547      *
548      * @return <tt>true</tt> if the specified object is equal to this list.
549      */

550
551     public boolean equals(Object JavaDoc o)
552     {
553         if (o == this)
554             return true;
555
556         if (!(o instanceof IntArrayList))
557             return false;
558
559         return Arrays.equals(toArray(), ((IntArrayList)o).toArray());
560     }
561
562
563     /**
564      * Returns the hash code value for this list.
565      *
566      * @return The hash code value for this list.
567      */

568
569     public int hashCode()
570     {
571         int hashCode = 1;
572
573         for (int i = 0; i < size; ++i)
574             hashCode = 31 * hashCode + elements[i];
575
576         return hashCode;
577     }
578
579
580     /**
581      * Returns a string representation of this list.
582      * The string representation consists of a list of the elements, enclosed
583      * in square brackets (<tt>"[]"</tt>).
584      * Adjacent elements are separated by the characters <tt>", "</tt> (comma
585      * and space).
586      * Elements are converted to strings as by <tt>String.valueOf(int)</tt>.
587      *
588      * @return
589      * A string representation of this collection.
590      */

591
592     public String JavaDoc toString()
593     {
594         StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
595         buf.append('[');
596
597         for (int i = 0; i < size; ++i)
598         {
599             if (i > 0)
600                 buf.append(", ");
601
602             buf.append(elements[i]);
603         }
604
605         buf.append(']');
606
607         return buf.toString();
608     }
609 }
610
Popular Tags