001: /*
002: * Copyright 2004 (C) TJDO.
003: * All rights reserved.
004: *
005: * This software is distributed under the terms of the TJDO License version 1.0.
006: * See the terms of the TJDO License in the documentation provided with this software.
007: *
008: * $Id: IntArrayList.java,v 1.1 2004/01/18 03:01:07 jackknifebarber Exp $
009: */
010:
011: package com.triactive.jdo.util;
012:
013: import java.util.Arrays;
014:
015: /**
016: * A variation on the standard ArrayList class that efficiently handles arrays
017: * of integers.
018: * Using this class rather than <tt>ArrayList</tt> avoids the need to "box" each
019: * element in an instance of <tt>java.lang.Integer</tt>.
020: * It is useful where performance is important.
021: *
022: * @author <a href="mailto:mmartin5@austin.rr.com">Mike Martin</a>
023: * @version $Revision: 1.1 $
024: */
025:
026: public class IntArrayList implements Cloneable {
027: private int[] elements;
028: private int size = 0;
029:
030: /**
031: * Constructs an empty list with an initial capacity of ten.
032: */
033:
034: public IntArrayList() {
035: this (10);
036: }
037:
038: /**
039: * Constructs an empty list with the specified initial capacity.
040: *
041: * @param initialCapacity
042: * The initial capacity of the list.
043: *
044: * @exception IllegalArgumentException
045: * If the specified initial capacity is negative.
046: */
047:
048: public IntArrayList(int initialCapacity) {
049: if (initialCapacity < 0)
050: throw new IllegalArgumentException("Illegal capacity: "
051: + initialCapacity);
052:
053: elements = new int[initialCapacity];
054: }
055:
056: /**
057: * Constructs a list containing the elements of the specified array.
058: * The <tt>IntArrayList</tt> instance has an initial capacity of 110% the
059: * size of the specified collection.
060: *
061: * @param initialContents
062: * The array whose elements are to be placed into this list.
063: */
064:
065: public IntArrayList(int[] initialContents) {
066: size = initialContents.length;
067: elements = new int[(int) Math.min((size * 11L) / 10,
068: Integer.MAX_VALUE)];
069:
070: System.arraycopy(initialContents, 0, elements, 0, size);
071: }
072:
073: /**
074: * Trims the capacity of this <tt>IntArrayList</tt> instance to be the
075: * list's current size.
076: * An application can use this operation to minimize the storage of an
077: * <tt>IntArrayList</tt> instance.
078: */
079:
080: public void trimToSize() {
081: if (size < elements.length) {
082: int[] newelems = new int[size];
083: System.arraycopy(elements, 0, newelems, 0, size);
084: elements = newelems;
085: }
086: }
087:
088: /**
089: * Increases the capacity of this <tt>IntArrayList</tt> instance, if
090: * necessary, to ensure that it can hold at least the number of elements
091: * specified by the minimum capacity argument.
092: *
093: * @param minCapacity
094: * The desired minimum capacity.
095: */
096:
097: public void ensureCapacity(int minCapacity) {
098: int oldCapacity = elements.length;
099:
100: if (minCapacity > oldCapacity) {
101: int[] newelems = new int[(int) Math.min(
102: (oldCapacity * 3L) / 2, Integer.MAX_VALUE)];
103: System.arraycopy(elements, 0, newelems, 0, size);
104: elements = newelems;
105: }
106: }
107:
108: /**
109: * Returns the number of elements in this list.
110: *
111: * @return The number of elements in this list.
112: */
113:
114: public int size() {
115: return size;
116: }
117:
118: /**
119: * Tests if this list has no elements.
120: *
121: * @return <tt>true</tt> if this list has no elements;
122: * <tt>false</tt> otherwise.
123: */
124:
125: public boolean isEmpty() {
126: return size == 0;
127: }
128:
129: /**
130: * Returns <tt>true</tt> if this list contains the specified element.
131: *
132: * @param elem element whose presence in this List is to be tested.
133: *
134: * @return <code>true</code> if the specified element is present;
135: * <code>false</code> otherwise.
136: */
137:
138: public boolean contains(int elem) {
139: return indexOf(elem) >= 0;
140: }
141:
142: /**
143: * Searches for the first occurence of the given argument.
144: *
145: * @param elem
146: * An integer to search for.
147: *
148: * @return The index of the first occurrence of the argument in this
149: * list; returns <tt>-1</tt> if the value is not found.
150: */
151:
152: public int indexOf(int elem) {
153: for (int i = 0; i < size; ++i) {
154: if (elements[i] == elem)
155: return i;
156: }
157:
158: return -1;
159: }
160:
161: /**
162: * Returns the index of the last occurrence of the specified integer in
163: * this list.
164: *
165: * @param elem
166: * The desired element.
167: *
168: * @return The index of the last occurrence of the specified integer in
169: * this list; returns <tt>-1</tt> if the value is not found.
170: */
171:
172: public int lastIndexOf(int elem) {
173: for (int i = size - 1; i >= 0; --i) {
174: if (elements[i] == elem)
175: return i;
176: }
177:
178: return -1;
179: }
180:
181: /**
182: * Returns a copy of this <tt>IntArrayList</tt> instance.
183: *
184: * @return A clone of this <tt>ArrayList</tt> instance.
185: */
186:
187: public Object clone() {
188: try {
189: IntArrayList l = (IntArrayList) super .clone();
190: l.elements = new int[size];
191: System.arraycopy(elements, 0, l.elements, 0, size);
192: return l;
193: } catch (CloneNotSupportedException e) {
194: /* Should never happen since we are Cloneable. */
195: throw new InternalError();
196: }
197: }
198:
199: /**
200: * Returns an array containing all of the elements in this list.
201: *
202: * @return An array containing all of the elements in this list.
203: */
204:
205: public int[] toArray() {
206: int[] result = new int[size];
207: System.arraycopy(elements, 0, result, 0, size);
208: return result;
209: }
210:
211: /**
212: * Check if the given index is in range.
213: * If not, throw an appropriate runtime exception.
214: */
215:
216: private void rangeCheck(int index) {
217: if (index < 0 || index >= size)
218: throw new IndexOutOfBoundsException("Index: " + index
219: + ", Size: " + size);
220: }
221:
222: /**
223: * Returns the element at the specified position in this list.
224: *
225: * @param index
226: * Index of element to return.
227: *
228: * @return
229: * The element at the specified position in this list.
230: *
231: * @exception IndexOutOfBoundsException
232: * If index is out of range <tt>(index < 0 || index >= size())</tt>.
233: */
234:
235: public int get(int index) {
236: rangeCheck(index);
237:
238: return elements[index];
239: }
240:
241: /**
242: * Replaces the element at the specified position in this list with
243: * the specified element.
244: *
245: * @param index
246: * Index of element to replace.
247: * @param element
248: * Element to be stored at the specified position.
249: *
250: * @return
251: * The element previously at the specified position.
252: *
253: * @exception IndexOutOfBoundsException
254: * If index is out of range <tt>(index < 0 || index >= size())</tt>.
255: */
256:
257: public int set(int index, int element) {
258: rangeCheck(index);
259:
260: int oldValue = elements[index];
261: elements[index] = element;
262: return oldValue;
263: }
264:
265: /**
266: * Appends the specified element to the end of this list.
267: *
268: * @param element
269: * Element to be appended to this list.
270: */
271:
272: public void add(int element) {
273: ensureCapacity(size + 1);
274: elements[size++] = element;
275: }
276:
277: /**
278: * Inserts the specified element at the specified position in this
279: * list.
280: * Shifts the element currently at that position (if any) and any subsequent
281: * elements to the right (adds one to their indices).
282: *
283: * @param index
284: * Index at which the specified element is to be inserted.
285: * @param element
286: * Element to be inserted.
287: *
288: * @exception IndexOutOfBoundsException
289: * If index is out of range <tt>(index < 0 || index > size())</tt>.
290: */
291:
292: public void add(int index, int element) {
293: if (index < 0 || index > size)
294: throw new IndexOutOfBoundsException("Index: " + index
295: + ", Size: " + size);
296:
297: ensureCapacity(size + 1);
298: System.arraycopy(elements, index, elements, index + 1, size
299: - index);
300: elements[index] = element;
301: ++size;
302: }
303:
304: /**
305: * Removes the element at the specified position in this list.
306: * Shifts any subsequent elements to the left (subtracts one from their
307: * indices).
308: *
309: * @param index
310: * The index of the element to removed.
311: *
312: * @return
313: * The element that was removed from the list.
314: *
315: * @exception IndexOutOfBoundsException
316: * If index is out of range <tt>(index < 0 || index >= size())</tt>.
317: */
318:
319: public int remove(int index) {
320: rangeCheck(index);
321:
322: int oldValue = elements[index];
323: int numMoved = size - index - 1;
324: if (numMoved > 0)
325: System.arraycopy(elements, index + 1, elements, index,
326: numMoved);
327:
328: --size;
329:
330: return oldValue;
331: }
332:
333: /**
334: * Removes all of the elements from this list.
335: * The list will be empty after this call returns.
336: */
337:
338: public void clear() {
339: size = 0;
340: }
341:
342: /**
343: * Appends all of the elements in the specified array to the end of this
344: * list.
345: *
346: * @param ai
347: * The elements to be added to this list.
348: */
349:
350: public void addAll(int[] ai) {
351: int numNew = ai.length;
352: ensureCapacity(size + numNew);
353:
354: System.arraycopy(ai, 0, elements, size, numNew);
355: }
356:
357: /**
358: * Inserts all of the elements in the specified array into this list,
359: * starting at the specified position.
360: * Shifts the element currently at that position (if any) and any subsequent
361: * elements to the right (increases their indices).
362: * The new elements will appear in the list in the order that they exist in
363: * the array argument.
364: *
365: * @param index
366: * Index at which to insert first element from the specified array.
367: * @param ai
368: * Elements to be inserted into this list.
369: *
370: * @exception IndexOutOfBoundsException
371: * If index is out of range <tt>(index < 0 || index > size())</tt>.
372: */
373:
374: public void addAll(int index, int[] ai) {
375: if (index < 0 || index > size)
376: throw new IndexOutOfBoundsException("Index: " + index
377: + ", Size: " + size);
378:
379: int numNew = ai.length;
380: ensureCapacity(size + numNew);
381:
382: int numMoved = size - index;
383: if (numMoved > 0)
384: System.arraycopy(elements, index, elements, index + numNew,
385: numMoved);
386:
387: System.arraycopy(ai, 0, elements, index, numNew);
388:
389: size += numNew;
390: }
391:
392: /**
393: * Returns <tt>true</tt> if this list contains all of the elements in the
394: * specified list.
395: * <p>
396: * This implementation iterates over the specified array, checking each
397: * element in turn to see if it's contained in this list.
398: * If all elements are so contained <tt>true</tt> is returned, otherwise
399: * <tt>false</tt>.
400: *
401: * @param ai
402: * Array to be checked for containment in this list.
403: *
404: * @return
405: * <tt>true</tt> if this list contains all of the elements in the
406: * specified array.
407: *
408: * @see #contains
409: */
410:
411: public boolean containsAll(int[] ai) {
412: for (int i = 0; i < ai.length; ++i) {
413: if (!contains(ai[i]))
414: return false;
415: }
416:
417: return true;
418: }
419:
420: /**
421: * Removes from this list all of its elements that are contained in the
422: * specified array.
423: * <p>
424: * This implementation iterates over this list, checking each element in
425: * turn to see if it's contained in the specified array.
426: * If it's so contained, it's removed from this list.
427: *
428: * @param ai
429: * Elements to be removed from this list.
430: *
431: * @return
432: * <tt>true</tt> if this list changed as a result of the call.
433: *
434: * @see #remove
435: * @see #contains
436: */
437:
438: public boolean removeAll(int[] ai) {
439: IntArrayList l = new IntArrayList(ai);
440: boolean modified = false;
441:
442: for (int i = 0; i < size; ++i) {
443: while (i < size && l.contains(elements[i])) {
444: remove(i);
445: modified = true;
446: }
447: }
448:
449: return modified;
450: }
451:
452: /**
453: * Retains only the elements in this list that are contained in the
454: * specified array.
455: * In other words, removes from this list all of its elements that are not
456: * contained in the specified array.
457: * <p>
458: * This implementation iterates over this list, checking each element in
459: * turn to see if it's contained in the specified array.
460: * If it's not so contained, it's removed from this list.
461: *
462: * @param ai
463: * Elements to be retained in this list.
464: *
465: * @return
466: * <tt>true</tt> if this list changed as a result of the call.
467: *
468: * @see #remove
469: * @see #contains
470: */
471:
472: public boolean retainAll(int[] ai) {
473: IntArrayList l = new IntArrayList(ai);
474: boolean modified = false;
475:
476: for (int i = 0; i < size; ++i) {
477: while (i < size && !l.contains(elements[i])) {
478: remove(i);
479: modified = true;
480: }
481: }
482:
483: return modified;
484: }
485:
486: /**
487: * Compares the specified object with this list for equality.
488: * Returns <tt>true</tt> if and only if the specified object is also an
489: * IntArrayList, both lists have the same size, and all corresponding pairs
490: * of elements in the two lists are equal.
491: *
492: * @param o the object to be compared for equality with this list.
493: *
494: * @return <tt>true</tt> if the specified object is equal to this list.
495: */
496:
497: public boolean equals(Object o) {
498: if (o == this )
499: return true;
500:
501: if (!(o instanceof IntArrayList))
502: return false;
503:
504: return Arrays.equals(toArray(), ((IntArrayList) o).toArray());
505: }
506:
507: /**
508: * Returns the hash code value for this list.
509: *
510: * @return The hash code value for this list.
511: */
512:
513: public int hashCode() {
514: int hashCode = 1;
515:
516: for (int i = 0; i < size; ++i)
517: hashCode = 31 * hashCode + elements[i];
518:
519: return hashCode;
520: }
521:
522: /**
523: * Returns a string representation of this list.
524: * The string representation consists of a list of the elements, enclosed
525: * in square brackets (<tt>"[]"</tt>).
526: * Adjacent elements are separated by the characters <tt>", "</tt> (comma
527: * and space).
528: * Elements are converted to strings as by <tt>String.valueOf(int)</tt>.
529: *
530: * @return
531: * A string representation of this collection.
532: */
533:
534: public String toString() {
535: StringBuffer buf = new StringBuffer();
536: buf.append('[');
537:
538: for (int i = 0; i < size; ++i) {
539: if (i > 0)
540: buf.append(", ");
541:
542: buf.append(elements[i]);
543: }
544:
545: buf.append(']');
546:
547: return buf.toString();
548: }
549: }
|