001: /*
002: * Modifications of Sun Microsystems code:
003: * <copyright>
004: *
005: * Copyright 1997-2004 BBNT Solutions, LLC
006: * under sponsorship of the Defense Advanced Research Projects
007: * Agency (DARPA).
008: *
009: * You can redistribute this software and/or modify it under the
010: * terms of the Cougaar Open Source License as published on the
011: * Cougaar Open Source Website (www.cougaar.org).
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
014: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
015: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
016: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
017: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
018: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
019: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
020: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
021: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
022: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
023: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
024: *
025: * </copyright>
026: */
027:
028: /*
029: * @(#)ArrayList.java 1.19 99/04/22
030: *
031: * Copyright 1997-1999 by Sun Microsystems, Inc.,
032: * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
033: * All rights reserved.
034: *
035: * This software is the confidential and proprietary information
036: * of Sun Microsystems, Inc. ("Confidential Information"). You
037: * shall not disclose such Confidential Information and shall use
038: * it only in accordance with the terms of the license agreement
039: * you entered into with Sun.
040: */
041:
042: package org.cougaar.util;
043:
044: import java.util.AbstractList;
045: import java.util.Collection;
046: import java.util.Iterator;
047: import java.util.List;
048:
049: /**
050: * A copy of java.util.ArrayList, modified so that previously
051: * private data members are here declared protected and which does not
052: * use iterators to walk itself p>
053: *
054: * This allows extending classes to have efficient access to the
055: * actual data storage elements so that the supported API extensions
056: * have first-class access.
057: *
058: * @see java.util.ArrayList
059: */
060:
061: public class ArrayListFoundation extends AbstractList implements List,
062: Cloneable, java.io.Serializable {
063: private static final long serialVersionUID = 1203987682910938923L;
064:
065: /**
066: * The array buffer into which the elements of the ArrayListFoundation are stored.
067: * The capacity of the ArrayListFoundation is the length of this array buffer.
068: */
069: protected transient Object elementData[];
070:
071: /**
072: * The size of the ArrayListFoundation (the number of elements it contains).
073: *
074: * @serial
075: */
076: protected transient int size;
077:
078: /**
079: * Constructs an empty list with the specified initial capacity.
080: *
081: * @param initialCapacity the initial capacity of the list.
082: */
083: public ArrayListFoundation(int initialCapacity) {
084: super ();
085: this .elementData = new Object[initialCapacity];
086: }
087:
088: /**
089: * Constructs an empty list.
090: */
091: public ArrayListFoundation() {
092: this (10);
093: }
094:
095: /**
096: * Constructs a list containing the elements of the specified
097: * collection, in the order they are returned by the collection's
098: * iterator. The <tt>ArrayListFoundation</tt> instance has an initial capacity of
099: * 110% the size of the specified collection.
100: */
101: public ArrayListFoundation(Collection c) {
102: size = c.size();
103: elementData = new Object[(size * 110) / 100]; // Allow 10% room for growth
104: c.toArray(elementData);
105: }
106:
107: /**
108: * Trims the capacity of this <tt>ArrayListFoundation</tt> instance to be the
109: * list's current size. An application can use this operation to minimize
110: * the storage of an <tt>ArrayListFoundation</tt> instance.
111: */
112: public void trimToSize() {
113: modCount++;
114: int oldCapacity = elementData.length;
115: if (size < oldCapacity) {
116: Object oldData[] = elementData;
117: elementData = new Object[size];
118: System.arraycopy(oldData, 0, elementData, 0, size);
119: }
120: }
121:
122: /**
123: * Increases the capacity of this <tt>ArrayListFoundation</tt> instance, if
124: * necessary, to ensure that it can hold at least the number of elements
125: * specified by the minimum capacity argument.
126: *
127: * @param minCapacity the desired minimum capacity.
128: */
129: public synchronized void ensureCapacity(int minCapacity) {
130: modCount++;
131: int oldCapacity = elementData.length;
132: if (minCapacity > oldCapacity) {
133: Object oldData[] = elementData;
134: int newCapacity = (oldCapacity * 3) / 2 + 1;
135: if (newCapacity < minCapacity)
136: newCapacity = minCapacity;
137: elementData = new Object[newCapacity];
138: System.arraycopy(oldData, 0, elementData, 0, size);
139: }
140: }
141:
142: /**
143: * Returns the number of elements in this list.
144: *
145: * @return the number of elements in this list.
146: */
147: public int size() {
148: return size;
149: }
150:
151: /**
152: * Tests if this list has no elements.
153: *
154: * @return <tt>true</tt> if this list has no elements;
155: * <tt>false</tt> otherwise.
156: */
157: public boolean isEmpty() {
158: return size == 0;
159: }
160:
161: /**
162: * Returns <tt>true</tt> if this list contains the specified element.
163: *
164: * @param elem element whose presence in this List is to be tested.
165: */
166: public boolean contains(Object elem) {
167: return indexOf(elem) >= 0;
168: }
169:
170: /**
171: * Searches for the first occurence of the given argument, testing
172: * for equality using the <tt>equals</tt> method.
173: *
174: * @param elem an object.
175: * @return the index of the first occurrence of the argument in this
176: * list; returns <tt>-1</tt> if the object is not found.
177: * @see Object#equals(Object)
178: */
179: public int indexOf(Object elem) {
180: if (elem == null) {
181: for (int i = 0; i < size; i++)
182: if (elementData[i] == null)
183: return i;
184: } else {
185: for (int i = 0; i < size; i++)
186: if (elem.equals(elementData[i]))
187: return i;
188: }
189: return -1;
190: }
191:
192: /**
193: * Returns the index of the last occurrence of the specified object in
194: * this list.
195: *
196: * @param elem the desired element.
197: * @return the index of the last occurrence of the specified object in
198: * this list; returns -1 if the object is not found.
199: */
200: public int lastIndexOf(Object elem) {
201: if (elem == null) {
202: for (int i = size - 1; i >= 0; i--)
203: if (elementData[i] == null)
204: return i;
205: } else {
206: for (int i = size - 1; i >= 0; i--)
207: if (elem.equals(elementData[i]))
208: return i;
209: }
210: return -1;
211: }
212:
213: /**
214: * Returns a shallow copy of this <tt>ArrayListFoundation</tt> instance. (The
215: * elements themselves are not copied.)
216: *
217: * @return a clone of this <tt>ArrayListFoundation</tt> instance.
218: */
219: public Object clone() {
220: try {
221: ArrayListFoundation v = (ArrayListFoundation) super .clone();
222: v.elementData = new Object[size];
223: System.arraycopy(elementData, 0, v.elementData, 0, size);
224: v.modCount = 0;
225: return v;
226: } catch (CloneNotSupportedException e) {
227: // this shouldn't happen, since we are Cloneable
228: throw new InternalError();
229: }
230: }
231:
232: /**
233: * Returns an array containing all of the elements in this list
234: * in the correct order.
235: *
236: * @return an array containing all of the elements in this list
237: * in the correct order.
238: */
239: public Object[] toArray() {
240: Object[] result = new Object[size];
241: System.arraycopy(elementData, 0, result, 0, size);
242: return result;
243: }
244:
245: /**
246: * Returns an array containing all of the elements in this list in the
247: * correct order. The runtime type of the returned array is that of the
248: * specified array. If the list fits in the specified array, it is
249: * returned therein. Otherwise, a new array is allocated with the runtime
250: * type of the specified array and the size of this list.<p>
251: *
252: * If the list fits in the specified array with room to spare (i.e., the
253: * array has more elements than the list), the element in the array
254: * immediately following the end of the collection is set to
255: * <tt>null</tt>. This is useful in determining the length of the list
256: * <i>only</i> if the caller knows that the list does not contain any
257: * <tt>null</tt> elements.
258: *
259: * @param a the array into which the elements of the list are to
260: * be stored, if it is big enough; otherwise, a new array of the
261: * same runtime type is allocated for this purpose.
262: * @return an array containing the elements of the list.
263: * @throws ArrayStoreException if the runtime type of a is not a supertype
264: * of the runtime type of every element in this list.
265: */
266: public Object[] toArray(Object a[]) {
267: if (a.length < size)
268: a = (Object[]) java.lang.reflect.Array.newInstance(a
269: .getClass().getComponentType(), size);
270:
271: System.arraycopy(elementData, 0, a, 0, size);
272:
273: if (a.length > size)
274: a[size] = null;
275:
276: return a;
277: }
278:
279: // Positional Access Operations
280:
281: /**
282: * Returns the element at the specified position in this list.
283: *
284: * @param index index of element to return.
285: * @return the element at the specified position in this list.
286: * @throws IndexOutOfBoundsException if index is out of range <tt>(index
287: * < 0 || index >= size())</tt>.
288: */
289: public Object get(int index) {
290: RangeCheck(index);
291:
292: return elementData[index];
293: }
294:
295: /**
296: * Replaces the element at the specified position in this list with
297: * the specified element.
298: *
299: * @param index index of element to replace.
300: * @param element element to be stored at the specified position.
301: * @return the element previously at the specified position.
302: * @throws IndexOutOfBoundsException if index out of range
303: * <tt>(index < 0 || index >= size())</tt>.
304: */
305: public Object set(int index, Object element) {
306: RangeCheck(index);
307:
308: Object oldValue = elementData[index];
309: elementData[index] = element;
310: return oldValue;
311: }
312:
313: /**
314: * Appends the specified element to the end of this list.
315: *
316: * @param o element to be appended to this list.
317: * @return <tt>true</tt> (as per the general contract of Collection.add).
318: */
319: public boolean add(Object o) {
320: ensureCapacity(size + 1); // Increments modCount!!
321: elementData[size++] = o;
322: return true;
323: }
324:
325: /**
326: * Inserts the specified element at the specified position in this
327: * list. Shifts the element currently at that position (if any) and
328: * any subsequent elements to the right (adds one to their indices).
329: *
330: * @param index index at which the specified element is to be inserted.
331: * @param element element to be inserted.
332: * @throws IndexOutOfBoundsException if index is out of range
333: * <tt>(index < 0 || index > size())</tt>.
334: */
335: public void add(int index, Object element) {
336: if (index > size || index < 0)
337: throw new IndexOutOfBoundsException("Index: " + index
338: + ", Size: " + size);
339:
340: ensureCapacity(size + 1); // Increments modCount!!
341: System.arraycopy(elementData, index, elementData, index + 1,
342: size - index);
343: elementData[index] = element;
344: size++;
345: }
346:
347: /**
348: * Removes a single instance of the specified element from this
349: * collection, if it is present (optional operation). More formally,
350: * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
351: * o.equals(e))</tt>, if the collection contains one or more such
352: * elements. Returns <tt>true</tt> if the collection contained the
353: * specified element (or equivalently, if the collection changed as a
354: * result of the call).<p>
355: *
356: * This implementation walks the elements of the collection looking for the
357: * specified element. If it finds the element, it removes the element
358: * from the collection.<p>
359: *
360: * @param o element to be removed from this collection, if present.
361: * @return <tt>true</tt> if the collection contained the specified
362: * element.
363: *
364: */
365: public boolean remove(Object o) {
366: int removeIndex = -1;
367:
368: if (o == null) {
369: for (int i = 0; i < size; i++) {
370: if (elementData[i] == null) {
371: removeIndex = i;
372: break;
373: }
374: }
375: } else {
376: for (int i = 0; i < size; i++) {
377: if (elementData[i].equals(o)) {
378: removeIndex = i;
379: break;
380: }
381: }
382: }
383:
384: if (removeIndex != -1) {
385: remove(removeIndex);
386: return true;
387: } else {
388: return false;
389: }
390: }
391:
392: /**
393: * Removes the element at the specified position in this list.
394: * Shifts any subsequent elements to the left (subtracts one from their
395: * indices).
396: *
397: * @param index the index of the element to removed.
398: * @return the element that was removed from the list.
399: * @throws IndexOutOfBoundsException if index out of range <tt>(index
400: * < 0 || index >= size())</tt>.
401: */
402: public Object remove(int index) {
403: RangeCheck(index);
404:
405: modCount++;
406: Object oldValue = elementData[index];
407:
408: int numMoved = size - index - 1;
409: if (numMoved > 0)
410: System.arraycopy(elementData, index + 1, elementData,
411: index, numMoved);
412: elementData[--size] = null; // Let gc do its work
413:
414: return oldValue;
415: }
416:
417: /**
418: * Removes all of the elements from this list. The list will
419: * be empty after this call returns.
420: */
421: public void clear() {
422: modCount++;
423:
424: // Let gc do its work
425: for (int i = 0; i < size; i++)
426: elementData[i] = null;
427:
428: size = 0;
429: }
430:
431: /**
432: * Appends all of the elements in the specified Collection to the end of
433: * this list, in the order that they are returned by the
434: * specified Collection's Iterator. The behavior of this operation is
435: * undefined if the specified Collection is modified while the operation
436: * is in progress. (This implies that the behavior of this call is
437: * undefined if the specified Collection is this list, and this
438: * list is nonempty.)
439: *
440: * @param c elements to be inserted into this list.
441: * @throws IndexOutOfBoundsException if index out of range <tt>(index
442: * < 0 || index > size())</tt>.
443: */
444: public boolean addAll(Collection c) {
445: modCount++;
446: int numNew = c.size();
447: ensureCapacity(size + numNew);
448:
449: if (c instanceof List) {
450: // Use List access if we can
451: List list = (List) c;
452: for (int i = 0; i < numNew; i++)
453: elementData[size++] = list.get(i);
454: } else {
455: Iterator e = c.iterator();
456: for (int i = 0; i < numNew; i++)
457: elementData[size++] = e.next();
458: }
459:
460: return numNew != 0;
461: }
462:
463: /**
464: * Inserts all of the elements in the specified Collection into this
465: * list, starting at the specified position. Shifts the element
466: * currently at that position (if any) and any subsequent elements to
467: * the right (increases their indices). The new elements will appear
468: * in the list in the order that they are returned by the
469: * specified Collection's iterator.
470: *
471: * @param index index at which to insert first element
472: * from the specified collection.
473: * @param c elements to be inserted into this list.
474: * @throws IndexOutOfBoundsException if index out of range <tt>(index
475: * < 0 || index > size())</tt>.
476: */
477: public boolean addAll(int index, Collection c) {
478: if (index > size || index < 0)
479: throw new IndexOutOfBoundsException("Index: " + index
480: + ", Size: " + size);
481:
482: int numNew = c.size();
483: ensureCapacity(size + numNew); // Increments modCount!!
484:
485: int numMoved = size - index;
486: if (numMoved > 0)
487: System.arraycopy(elementData, index, elementData, index
488: + numNew, numMoved);
489:
490: if (c instanceof List) {
491: // Use List access if we can
492: List list = (List) c;
493: for (int i = 0; i < numNew; i++)
494: elementData[index++] = list.get(i);
495: } else {
496: Iterator e = c.iterator();
497: for (int i = 0; i < numNew; i++)
498: elementData[index++] = e.next();
499: }
500:
501: size += numNew;
502: return numNew != 0;
503: }
504:
505: /**
506: * Removes from this collection all of its elements that are contained in
507: * the specified collection (optional operation).<p>
508: *
509: * This implementation walks the elements of this collection, checking each
510: * element in turn to see if it's contained in the specified collection. If
511: * it's so contained, it's removed from this collection.<p>
512: *
513: *
514: * @param c elements to be removed from this collection.
515: * @return <tt>true</tt> if this collection changed as a result of the
516: * call.
517: *
518: * @see #remove(Object)
519: * @see #contains(Object)
520: */
521: public boolean removeAll(Collection c) {
522: boolean modified = false;
523:
524: for (int i = 0; i < size; i++) {
525: if (c.contains(elementData[i])) {
526: remove(i);
527: modified = true;
528: }
529: }
530: return modified;
531: }
532:
533: /**
534: * Retains only the elements in this collection that are contained in the
535: * specified collection (optional operation). In other words, removes
536: * from this collection all of its elements that are not contained in the
537: * specified collection. <p>
538: *
539: * This implementation walks the elements of this collection, checking each
540: * element returned in turn to see if it's contained in the specified
541: * collection. If it's not so contained, it's removed from this collection.
542: *
543: * @return <tt>true</tt> if this collection changed as a result of the
544: * call.
545: *
546: * @see #remove(Object)
547: * @see #contains(Object)
548: */
549: public boolean retainAll(Collection c) {
550: boolean modified = false;
551:
552: for (int i = 0; i < size; i++) {
553: if (!c.contains(elementData[i])) {
554: remove(i);
555: modified = true;
556: }
557: }
558:
559: return modified;
560: }
561:
562: /**
563: * Returns a string representation of this collection. The string
564: * representation consists of a list of the collection's elements,
565: * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
566: * separated by the characters <tt>", "</tt> (comma and space). Elements
567: * are converted to strings as by <tt>String.valueOf(Object)</tt>.<p>
568: *
569: * This implementation creates an empty string buffer, appends a left
570: * square bracket, and walks the elements of the collection appending the string
571: * representation of each element in turn. After appending each element
572: * except the last, the string <tt>", "</tt> is appended. Finally a right
573: * bracket is appended. A string is obtained from the string buffer, and
574: * returned.
575: *
576: * @return a string representation of this collection.
577: */
578: public String toString() {
579: StringBuffer buf = new StringBuffer();
580: buf.append("[");
581: for (int i = 0; i < size; i++) {
582: buf.append(String.valueOf(elementData[i]));
583: if (i < (size - 1))
584: buf.append(", ");
585: }
586: buf.append("]");
587: return buf.toString();
588: }
589:
590: // Comparison and hashing
591:
592: /**
593: * Compares the specified object with this list for equality. Returns
594: * <tt>true</tt> if and only if the specified object is also a list, both
595: * lists have the same size, and all corresponding pairs of elements in
596: * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
597: * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
598: * e1.equals(e2))</tt>.) In other words, two lists are defined to be
599: * equal if they contain the same elements in the same order.<p>
600: *
601: * This implementation first checks if the specified object is this
602: * list. If so, it returns <tt>true</tt>; if not, it checks if the
603: * specified object is a list. If not, it returns <tt>false</tt>; if so,
604: * it iterates over both lists, comparing corresponding pairs of elements.
605: * If any comparison returns <tt>false</tt>, this method returns
606: * <tt>false</tt>. If either iterator runs out of elements before the
607: * other it returns <tt>false</tt> (as the lists are of unequal length);
608: * otherwise it returns <tt>true</tt> when the iterations complete.
609: *
610: * @param o the object to be compared for equality with this list.
611: *
612: * @return <tt>true</tt> if the specified object is equal to this list.
613: */
614: public boolean equals(Object o) {
615: if (o == this )
616: return true;
617: if (!(o instanceof List))
618: return false;
619:
620: List otherList = (List) o;
621:
622: if (size != otherList.size()) {
623: return false;
624: }
625:
626: for (int i = 0; i < size; i++) {
627: Object otherElement = otherList.get(i);
628: if (!(elementData[i] == null ? otherElement == null
629: : elementData[i].equals(otherElement)))
630: return false;
631: }
632: return true;
633: }
634:
635: /**
636: * Returns the hash code value for this list. <p>
637: *
638: * This implementation uses exactly the code that is used to define the
639: * list hash function in the documentation for the <tt>List.hashCode</tt>
640: * method.
641: *
642: * @return the hash code value for this list.
643: */
644: public int hashCode() {
645: int hashCode = 1;
646: for (int i = 0; i < size; i++) {
647: hashCode = 31
648: * hashCode
649: + (elementData[i] == null ? 0 : elementData[i]
650: .hashCode());
651: }
652: return hashCode;
653: }
654:
655: /**
656: * Removes from this List all of the elements whose index is between
657: * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
658: * elements to the left (reduces their index).
659: * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
660: * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
661: *
662: * @param fromIndex index of first element to be removed.
663: * @param toIndex index after last element to be removed.
664: */
665: protected void removeRange(int fromIndex, int toIndex) {
666: modCount++;
667: int numMoved = size - toIndex;
668: System.arraycopy(elementData, toIndex, elementData, fromIndex,
669: numMoved);
670:
671: // Let gc do its work
672: int newSize = size - (toIndex - fromIndex);
673: while (size != newSize)
674: elementData[--size] = null;
675: }
676:
677: /**
678: * Check if the given index is in range. If not, throw an appropriate
679: * runtime exception.
680: */
681: private void RangeCheck(int index) {
682: if (index >= size || index < 0)
683: throw new IndexOutOfBoundsException("Index: " + index
684: + ", Size: " + size);
685: }
686:
687: /**
688: * Save the state of the <tt>ArrayListFoundation</tt> instance to a stream (that
689: * is, serialize it). We need to be careful to not hold our monitor
690: * while serializing subobjects. Doing so is prone to deadlock. So
691: * make a copy of the elementData so it can't change while
692: * serialization is happening.
693: *
694: * @serialData The length of the array backing the <tt>ArrayListFoundation</tt>
695: * instance is emitted (int), followed by all of its elements
696: * (each an <tt>Object</tt>) in the proper order.
697: */
698: private void writeObject(java.io.ObjectOutputStream s)
699: throws java.io.IOException {
700: // Write out any hidden stuff
701: s.defaultWriteObject();
702: int sizeToWrite;
703: int lengthToWrite;
704: Object[] objectsToWrite;
705: synchronized (this ) {
706: sizeToWrite = size;
707: lengthToWrite = elementData.length;
708: objectsToWrite = new Object[sizeToWrite];
709: System.arraycopy(elementData, 0, objectsToWrite, 0,
710: sizeToWrite);
711: }
712: // Write out the current size;
713: s.writeInt(sizeToWrite);
714: // Write out array length
715: s.writeInt(lengthToWrite);
716: // Write out all elements in the proper order.
717: for (int i = 0; i < sizeToWrite; i++)
718: s.writeObject(objectsToWrite[i]);
719: }
720:
721: /**
722: * Reconstitute the <tt>ArrayListFoundation</tt> instance from a stream (that is,
723: * deserialize it).
724: */
725: private synchronized void readObject(java.io.ObjectInputStream s)
726: throws java.io.IOException, ClassNotFoundException {
727: // Read in size, and any hidden stuff
728: s.defaultReadObject();
729: size = s.readInt();
730:
731: // Read in array length and allocate array
732: int arrayLength = s.readInt();
733: elementData = new Object[arrayLength];
734:
735: // Read in all elements in the proper order.
736: for (int i = 0; i < size; i++)
737: elementData[i] = s.readObject();
738: }
739: }
|