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  ;
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  
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  ("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   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   e)
221         {
222             /* Should never happen since we are Cloneable. */
223             throw new InternalError  ();
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  ("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  ("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  ("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   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   toString()
593     {
594         StringBuffer   buf = new StringBuffer  ();
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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags