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