001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 S�ren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package com.uwyn.rife.pcj.list;
020:
021: import java.io.IOException;
022: import java.io.ObjectInputStream;
023: import java.io.ObjectOutputStream;
024: import java.io.Serializable;
025:
026: import com.uwyn.rife.pcj.IntCollection;
027: import com.uwyn.rife.pcj.hash.DefaultIntHashFunction;
028: import com.uwyn.rife.pcj.util.Exceptions;
029:
030: /**
031: * This class represents an array implemenation of lists of
032: * int values.
033: *
034: * @see java.util.ArrayList
035: *
036: * @author Søren Bak
037: * @version 1.3 21-08-2003 19:27
038: * @since 1.0
039: */
040: public class IntArrayList extends AbstractIntList implements Cloneable,
041: Serializable {
042:
043: private static final long serialVersionUID = 3943530126092701394L;
044:
045: /** Constant indicating relative growth policy. */
046: private static final int GROWTH_POLICY_RELATIVE = 0;
047:
048: /** Constant indicating absolute growth policy. */
049: private static final int GROWTH_POLICY_ABSOLUTE = 1;
050:
051: /** The default factor with which to increase the capacity of this list. */
052: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
053:
054: /** The default chunk size with which to increase the capacity of this list. */
055: public static final int DEFAULT_GROWTH_CHUNK = 10;
056:
057: /** The default capacity of this list. */
058: public static final int DEFAULT_CAPACITY = 10;
059:
060: /** The elements of this list (indices <tt>0</tt> to <tt>size-1</tt>). */
061: private transient int[] data;
062:
063: /**
064: * The current size of this list.
065: * @serial
066: */
067: private int size;
068:
069: /**
070: * The growth policy of this list (0 is relative growth, 1 is absolute growth).
071: * @serial
072: */
073: private int growthPolicy;
074:
075: /**
076: * The growth factor of this list, if the growth policy is
077: * relative.
078: * @serial
079: */
080: private double growthFactor;
081:
082: /**
083: * The growth chunk size of this list, if the growth policy is
084: * absolute.
085: * @serial
086: */
087: private int growthChunk;
088:
089: private IntArrayList(int capacity, int growthPolicy,
090: double growthFactor, int growthChunk) {
091: if (capacity < 0)
092: Exceptions.negativeArgument("capacity", String
093: .valueOf(capacity));
094: if (growthFactor < 0.0)
095: Exceptions.negativeArgument("growthFactor", String
096: .valueOf(growthFactor));
097: if (growthChunk < 0)
098: Exceptions.negativeArgument("growthChunk", String
099: .valueOf(growthChunk));
100: data = new int[capacity];
101: size = 0;
102: this .growthPolicy = growthPolicy;
103: this .growthFactor = growthFactor;
104: this .growthChunk = growthChunk;
105: }
106:
107: /**
108: * Creates a new array list with capacity 10 and a relative
109: * growth factor of 1.0.
110: *
111: * @see #IntArrayList(int,double)
112: */
113: public IntArrayList() {
114: this (DEFAULT_CAPACITY);
115: }
116:
117: /**
118: * Creates a new array list with the same elements as a
119: * specified collection. The elements of the specified collection
120: * are added to the end of the list in the collection's iteration
121: * order.
122: *
123: * @param c
124: * the collection whose elements to add to the new
125: * list.
126: *
127: * @throws NullPointerException
128: * if <tt>c</tt> is <tt>null</tt>.
129: */
130: public IntArrayList(IntCollection c) {
131: this (c.size());
132: addAll(c);
133: }
134:
135: /**
136: * Creates a new array list with the same elements as a
137: * specified array. The elements of the specified array
138: * are added to the end of the list in order of the array.
139: *
140: * @param a
141: * the array whose elements to add to the new
142: * list.
143: *
144: * @throws NullPointerException
145: * if <tt>a</tt> is <tt>null</tt>.
146: *
147: * @since 1.1
148: */
149: public IntArrayList(int[] a) {
150: this (a.length);
151: System.arraycopy(a, 0, data, 0, a.length);
152: size = a.length;
153: }
154:
155: /**
156: * Creates a new array list with a specified capacity and a
157: * relative growth factor of 1.0.
158: *
159: * @param capacity
160: * the initial capacity of the list.
161: *
162: * @see #IntArrayList(int,double)
163: *
164: * @throws IllegalArgumentException
165: * if <tt>capacity</tt> is negative.
166: */
167: public IntArrayList(int capacity) {
168: this (capacity, DEFAULT_GROWTH_FACTOR);
169: }
170:
171: /**
172: * Creates a new array list with a specified capacity and
173: * relative growth factor.
174: *
175: * <p>The array capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
176: * This strategy is good for avoiding many capacity increases, but
177: * the amount of wasted memory is approximately the size of the list.
178: *
179: * @param capacity
180: * the initial capacity of the list.
181: *
182: * @param growthFactor
183: * the relative amount with which to increase the
184: * the capacity when a capacity increase is needed.
185: *
186: * @throws IllegalArgumentException
187: * if <tt>capacity</tt> is negative;
188: * if <tt>growthFactor</tt> is negative.
189: */
190: public IntArrayList(int capacity, double growthFactor) {
191: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
192: 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 IntArrayList(int capacity, int growthChunk) {
215: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
216: growthChunk);
217: }
218:
219: // ---------------------------------------------------------------
220: // Array management
221: // ---------------------------------------------------------------
222:
223: /**
224: * Computes the new capacity of the list based on a needed
225: * capacity and the growth policy.
226: *
227: * @param capacity
228: * the needed capacity of the list.
229: *
230: * @return the new capacity of the list.
231: */
232: private int computeCapacity(int capacity) {
233: int newcapacity;
234: if (growthPolicy == GROWTH_POLICY_RELATIVE)
235: newcapacity = (int) (data.length * (1.0 + growthFactor));
236: else
237: newcapacity = data.length + growthChunk;
238: if (newcapacity < capacity)
239: newcapacity = capacity;
240: return newcapacity;
241: }
242:
243: /**
244: * Ensures that this list has at least a specified capacity.
245: * The actual capacity is calculated from the growth factor
246: * or growth chunk specified to the constructor.
247: *
248: * @param capacity
249: * the minimum capacity of this list.
250: *
251: * @return the new capacity of this list.
252: *
253: * @see #capacity()
254: */
255: public int ensureCapacity(int capacity) {
256: if (capacity > data.length) {
257: int[] newdata = new int[capacity = computeCapacity(capacity)];
258: System.arraycopy(data, 0, newdata, 0, size);
259: data = newdata;
260: }
261: return capacity;
262: }
263:
264: /**
265: * Returns the current capacity of this list. The capacity is the
266: * number of elements that the list can contain without having to
267: * increase the amount of memory used.
268: *
269: * @return the current capacity of this list.
270: *
271: * @see #ensureCapacity(int)
272: */
273: public int capacity() {
274: return data.length;
275: }
276:
277: // ---------------------------------------------------------------
278: // Operations not supported by abstract implementation
279: // ---------------------------------------------------------------
280:
281: public void add(int index, int v) {
282: if (index < 0 || index > size)
283: Exceptions.indexOutOfBounds(index, 0, size);
284: ensureCapacity(size + 1);
285: // Move data
286: int block = size - index;
287: if (block > 0)
288: System.arraycopy(data, index, data, index + 1, block);
289: data[index] = v;
290: size++;
291: }
292:
293: public int get(int index) {
294: if (index < 0 || index >= size)
295: Exceptions.indexOutOfBounds(index, 0, size - 1);
296: return data[index];
297: }
298:
299: public int set(int index, int v) {
300: if (index < 0 || index >= size)
301: Exceptions.indexOutOfBounds(index, 0, size - 1);
302: int result = data[index];
303: data[index] = v;
304: return result;
305: }
306:
307: public int removeElementAt(int index) {
308: if (index < 0 || index >= size)
309: Exceptions.indexOutOfBounds(index, 0, size - 1);
310: int result = data[index];
311: // Move data
312: int block = size - (index + 1);
313: if (block > 0)
314: System.arraycopy(data, index + 1, data, index, block);
315: size--;
316: return result;
317: }
318:
319: /**
320: * Minimizes the memory used by this array list. The underlying
321: * array is replaced by an array whose size is exactly the number
322: * of elements in this array list. The method can be used to
323: * free up memory after many removals.
324: */
325: public void trimToSize() {
326: if (data.length > size) {
327: int[] newdata = new int[size];
328: System.arraycopy(data, 0, newdata, 0, size);
329: data = newdata;
330: }
331: }
332:
333: /**
334: * Returns a clone of this array list.
335: *
336: * @return a clone of this array list.
337: *
338: * @since 1.1
339: */
340: public Object clone() {
341: try {
342: IntArrayList c = (IntArrayList) super .clone();
343: c.data = new int[data.length];
344: System.arraycopy(data, 0, c.data, 0, size);
345: return c;
346: } catch (CloneNotSupportedException e) {
347: Exceptions.cloning();
348: return null;
349: }
350: }
351:
352: // ---------------------------------------------------------------
353: // Operations overwritten for efficiency
354: // ---------------------------------------------------------------
355:
356: public int size() {
357: return size;
358: }
359:
360: public boolean isEmpty() {
361: return size == 0;
362: }
363:
364: public void clear() {
365: size = 0;
366: }
367:
368: public boolean contains(int v) {
369: for (int i = 0; i < size; i++)
370: if (data[i] == v)
371: return true;
372: return false;
373: }
374:
375: public int indexOf(int c) {
376: for (int i = 0; i < size; i++)
377: if (data[i] == c)
378: return i;
379: return -1;
380: }
381:
382: /**
383: * @since 1.2
384: */
385: public int indexOf(int index, int c) {
386: if (index < 0 || index > size)
387: Exceptions.indexOutOfBounds(index, 0, size);
388: for (int i = index; i < size; i++)
389: if (data[i] == c)
390: return i;
391: return -1;
392: }
393:
394: public int lastIndexOf(int c) {
395: for (int i = size - 1; i >= 0; i--)
396: if (data[i] == c)
397: return i;
398: return -1;
399: }
400:
401: public boolean remove(int v) {
402: int index = indexOf(v);
403: if (index != -1) {
404: removeElementAt(index);
405: return true;
406: }
407: return false;
408: }
409:
410: public int[] toArray() {
411: int[] a = new int[size];
412: System.arraycopy(data, 0, a, 0, size);
413: return a;
414: }
415:
416: public int[] toArray(int[] a) {
417: if (a == null || a.length < size)
418: a = new int[size];
419: System.arraycopy(data, 0, a, 0, size);
420: return a;
421: }
422:
423: public boolean equals(Object obj) {
424: if (this == obj)
425: return true;
426: if (!(obj instanceof IntList))
427: return false;
428: int i1 = 0;
429: IntListIterator i2 = ((IntList) obj).listIterator();
430: while (i1 < size && i2.hasNext())
431: if (data[i1++] != i2.next())
432: return false;
433: return !(i1 < size || i2.hasNext());
434: }
435:
436: public int hashCode() {
437: int h = 1;
438: for (int i = 0; i < size; i++)
439: h = 31 * h + DefaultIntHashFunction.INSTANCE.hash(data[i]);
440: return h;
441: }
442:
443: // ---------------------------------------------------------------
444: // Serialization
445: // ---------------------------------------------------------------
446:
447: /**
448: * @serialData Default fields; the capacity of the
449: * list (<tt>int</tt>); the list's elements
450: * (<tt>int</tt>).
451: *
452: * @since 1.1
453: */
454: private void writeObject(ObjectOutputStream s) throws IOException {
455: s.defaultWriteObject();
456: s.writeInt(data.length);
457: for (int i = 0; i < size; i++)
458: s.writeInt(data[i]);
459: }
460:
461: /**
462: * @since 1.1
463: */
464: private void readObject(ObjectInputStream s) throws IOException,
465: ClassNotFoundException {
466: s.defaultReadObject();
467: data = new int[s.readInt()];
468: for (int i = 0; i < size; i++)
469: data[i] = s.readInt();
470: }
471:
472: }
|