001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.io.ObjectStreamField;
024: import java.io.Serializable;
025: import java.lang.reflect.Array;
026:
027: /**
028: * ArrayList is an implementation of List, backed by an array. All optional
029: * operations are supported, adding, removing, and replacing. The elements can
030: * be any objects.
031: *
032: * @since 1.2
033: */
034: public class ArrayList<E> extends AbstractList<E> implements List<E>,
035: Cloneable, Serializable, RandomAccess {
036:
037: private static final long serialVersionUID = 8683452581122892189L;
038:
039: private transient int firstIndex;
040:
041: private transient int lastIndex;
042:
043: private transient E[] array;
044:
045: /**
046: * Constructs a new instance of ArrayList with capacity for ten elements.
047: */
048: public ArrayList() {
049: this (10);
050: }
051:
052: /**
053: * Constructs a new instance of ArrayList with the specified capacity.
054: *
055: * @param capacity
056: * the initial capacity of this ArrayList
057: */
058: public ArrayList(int capacity) {
059: firstIndex = lastIndex = 0;
060: try {
061: array = newElementArray(capacity);
062: } catch (NegativeArraySizeException e) {
063: throw new IllegalArgumentException();
064: }
065: }
066:
067: /**
068: * Constructs a new instance of ArrayList containing the elements in the
069: * specified collection. The ArrayList will have an initial capacity which
070: * is 110% of the size of the collection. The order of the elements in this
071: * ArrayList is the order they are returned by the collection iterator.
072: *
073: * @param collection
074: * the collection of elements to add
075: */
076: public ArrayList(Collection<? extends E> collection) {
077: int size = collection.size();
078: firstIndex = 0;
079: array = newElementArray(size + (size / 10));
080: collection.toArray(array);
081: lastIndex = size;
082: modCount = 1;
083: }
084:
085: @SuppressWarnings("unchecked")
086: private E[] newElementArray(int size) {
087: return (E[]) new Object[size];
088: }
089:
090: /**
091: * Inserts the specified object into this ArrayList at the specified
092: * location. The object is inserted before any previous element at the
093: * specified location. If the location is equal to the size of this
094: * ArrayList, the object is added at the end.
095: *
096: * @param location
097: * the index at which to insert
098: * @param object
099: * the object to add
100: *
101: * @exception IndexOutOfBoundsException
102: * when <code>location < 0 || >= size()</code>
103: */
104: @Override
105: public void add(int location, E object) {
106: int size = lastIndex - firstIndex;
107: if (0 < location && location < size) {
108: if (firstIndex == 0 && lastIndex == array.length) {
109: growForInsert(location, 1);
110: } else if ((location < size / 2 && firstIndex > 0)
111: || lastIndex == array.length) {
112: System.arraycopy(array, firstIndex, array,
113: --firstIndex, location);
114: } else {
115: int index = location + firstIndex;
116: System.arraycopy(array, index, array, index + 1, size
117: - location);
118: lastIndex++;
119: }
120: array[location + firstIndex] = object;
121: } else if (location == 0) {
122: if (firstIndex == 0) {
123: growAtFront(1);
124: }
125: array[--firstIndex] = object;
126: } else if (location == size) {
127: if (lastIndex == array.length) {
128: growAtEnd(1);
129: }
130: array[lastIndex++] = object;
131: } else {
132: throw new IndexOutOfBoundsException();
133: }
134:
135: modCount++;
136: }
137:
138: /**
139: * Adds the specified object at the end of this ArrayList.
140: *
141: * @param object
142: * the object to add
143: * @return true
144: */
145: @Override
146: public boolean add(E object) {
147: if (lastIndex == array.length) {
148: growAtEnd(1);
149: }
150: array[lastIndex++] = object;
151: modCount++;
152: return true;
153: }
154:
155: /**
156: * Inserts the objects in the specified Collection at the specified location
157: * in this ArrayList. The objects are added in the order they are returned
158: * from the Collection iterator.
159: *
160: * @param location
161: * the index at which to insert
162: * @param collection
163: * the Collection of objects
164: * @return true if this ArrayList is modified, false otherwise
165: *
166: * @exception IndexOutOfBoundsException
167: * when <code>location < 0 || > size()</code>
168: */
169: @Override
170: public boolean addAll(int location,
171: Collection<? extends E> collection) {
172: int size = lastIndex - firstIndex;
173: if (location < 0 || location > size) {
174: throw new IndexOutOfBoundsException();
175: }
176: int growSize = collection.size();
177: if (0 < location && location < size) {
178: if (array.length - size < growSize) {
179: growForInsert(location, growSize);
180: } else if ((location < size / 2 && firstIndex > 0)
181: || lastIndex > array.length - growSize) {
182: int newFirst = firstIndex - growSize;
183: if (newFirst < 0) {
184: int index = location + firstIndex;
185: System.arraycopy(array, index, array, index
186: - newFirst, size - location);
187: lastIndex -= newFirst;
188: newFirst = 0;
189: }
190: System.arraycopy(array, firstIndex, array, newFirst,
191: location);
192: firstIndex = newFirst;
193: } else {
194: int index = location + firstIndex;
195: System.arraycopy(array, index, array, index + growSize,
196: size - location);
197: lastIndex += growSize;
198: }
199: } else if (location == 0) {
200: growAtFront(growSize);
201: firstIndex -= growSize;
202: } else if (location == size) {
203: if (lastIndex > array.length - growSize) {
204: growAtEnd(growSize);
205: }
206: lastIndex += growSize;
207: }
208:
209: if (growSize > 0) {
210: Object[] dumparray = new Object[growSize];
211: collection.toArray(dumparray);
212: System.arraycopy(dumparray, 0, this .array, location
213: + firstIndex, growSize);
214: modCount++;
215: return true;
216: }
217: return false;
218: }
219:
220: /**
221: * Adds the objects in the specified Collection to this ArrayList.
222: *
223: * @param collection
224: * the Collection of objects
225: * @return true if this ArrayList is modified, false otherwise
226: */
227: @Override
228: public boolean addAll(Collection<? extends E> collection) {
229: int growSize = collection.size();
230: if (growSize > 0) {
231: if (lastIndex > array.length - growSize) {
232: growAtEnd(growSize);
233: }
234: Object[] dumparray = new Object[growSize];
235: collection.toArray(dumparray);
236: System.arraycopy(dumparray, 0, this .array, lastIndex,
237: growSize);
238: lastIndex += growSize;
239: modCount++;
240: return true;
241: }
242: return false;
243: }
244:
245: /**
246: * Removes all elements from this ArrayList, leaving it empty.
247: *
248: * @see #isEmpty
249: * @see #size
250: */
251: @Override
252: public void clear() {
253: if (firstIndex != lastIndex) {
254: Arrays.fill(array, firstIndex, lastIndex, null);
255: firstIndex = lastIndex = 0;
256: modCount++;
257: }
258: }
259:
260: /**
261: * Answers a new ArrayList with the same elements, size and capacity as this
262: * ArrayList.
263: *
264: * @return a shallow copy of this ArrayList
265: *
266: * @see java.lang.Cloneable
267: */
268: @Override
269: @SuppressWarnings("unchecked")
270: public Object clone() {
271: try {
272: ArrayList<E> newList = (ArrayList<E>) super .clone();
273: newList.array = array.clone();
274: return newList;
275: } catch (CloneNotSupportedException e) {
276: return null;
277: }
278: }
279:
280: /**
281: * Searches this ArrayList for the specified object.
282: *
283: * @param object
284: * the object to search for
285: * @return true if <code>object</code> is an element of this ArrayList,
286: * false otherwise
287: */
288: @Override
289: public boolean contains(Object object) {
290: if (object != null) {
291: for (int i = firstIndex; i < lastIndex; i++) {
292: if (object.equals(array[i])) {
293: return true;
294: }
295: }
296: } else {
297: for (int i = firstIndex; i < lastIndex; i++) {
298: if (array[i] == null) {
299: return true;
300: }
301: }
302: }
303: return false;
304: }
305:
306: /**
307: * Ensures that this ArrayList can hold the specified number of elements
308: * without growing.
309: *
310: * @param minimumCapacity
311: * the minimum number of elements that this ArrayList will hold
312: * before growing
313: */
314: public void ensureCapacity(int minimumCapacity) {
315: if (array.length < minimumCapacity) {
316: if (firstIndex > 0) {
317: growAtFront(minimumCapacity - array.length);
318: } else {
319: growAtEnd(minimumCapacity - array.length);
320: }
321: }
322: }
323:
324: /**
325: * Answers the element at the specified location in this ArrayList.
326: *
327: * @param location
328: * the index of the element to return
329: * @return the element at the specified index
330: *
331: * @exception IndexOutOfBoundsException
332: * when <code>location < 0 || >= size()</code>
333: */
334: @Override
335: public E get(int location) {
336: if (0 <= location && location < (lastIndex - firstIndex)) {
337: return array[firstIndex + location];
338: }
339: throw new IndexOutOfBoundsException();
340: }
341:
342: private void growAtEnd(int required) {
343: int size = lastIndex - firstIndex;
344: if (firstIndex >= required - (array.length - lastIndex)) {
345: int newLast = lastIndex - firstIndex;
346: if (size > 0) {
347: System.arraycopy(array, firstIndex, array, 0, size);
348: int start = newLast < firstIndex ? firstIndex : newLast;
349: Arrays.fill(array, start, array.length, null);
350: }
351: firstIndex = 0;
352: lastIndex = newLast;
353: } else {
354: int increment = size / 2;
355: if (required > increment) {
356: increment = required;
357: }
358: if (increment < 12) {
359: increment = 12;
360: }
361: E[] newArray = newElementArray(size + increment);
362: if (size > 0) {
363: System.arraycopy(array, firstIndex, newArray, 0, size);
364: firstIndex = 0;
365: lastIndex = size;
366: }
367: array = newArray;
368: }
369: }
370:
371: private void growAtFront(int required) {
372: int size = lastIndex - firstIndex;
373: if (array.length - lastIndex + firstIndex >= required) {
374: int newFirst = array.length - size;
375: if (size > 0) {
376: System.arraycopy(array, firstIndex, array, newFirst,
377: size);
378: int length = firstIndex + size > newFirst ? newFirst
379: : firstIndex + size;
380: Arrays.fill(array, firstIndex, length, null);
381: }
382: firstIndex = newFirst;
383: lastIndex = array.length;
384: } else {
385: int increment = size / 2;
386: if (required > increment) {
387: increment = required;
388: }
389: if (increment < 12) {
390: increment = 12;
391: }
392: E[] newArray = newElementArray(size + increment);
393: if (size > 0) {
394: System.arraycopy(array, firstIndex, newArray,
395: newArray.length - size, size);
396: }
397: firstIndex = newArray.length - size;
398: lastIndex = newArray.length;
399: array = newArray;
400: }
401: }
402:
403: private void growForInsert(int location, int required) {
404: int size = lastIndex - firstIndex;
405: int increment = size / 2;
406: if (required > increment) {
407: increment = required;
408: }
409: if (increment < 12) {
410: increment = 12;
411: }
412: E[] newArray = newElementArray(size + increment);
413: if (location < size / 2) {
414: int newFirst = newArray.length - (size + required);
415: System.arraycopy(array, location, newArray, location
416: + increment, size - location);
417: System.arraycopy(array, firstIndex, newArray, newFirst,
418: location);
419: firstIndex = newFirst;
420: lastIndex = newArray.length;
421: } else {
422: System.arraycopy(array, firstIndex, newArray, 0, location);
423: System.arraycopy(array, location, newArray, location
424: + required, size - location);
425: firstIndex = 0;
426: lastIndex += required;
427: }
428: array = newArray;
429: }
430:
431: /**
432: * Searches this ArrayList for the specified object and returns the index of
433: * the first occurrence.
434: *
435: * @param object
436: * the object to search for
437: * @return the index of the first occurrence of the object
438: */
439: @Override
440: public int indexOf(Object object) {
441: if (object != null) {
442: for (int i = firstIndex; i < lastIndex; i++) {
443: if (object.equals(array[i])) {
444: return i - firstIndex;
445: }
446: }
447: } else {
448: for (int i = firstIndex; i < lastIndex; i++) {
449: if (array[i] == null) {
450: return i - firstIndex;
451: }
452: }
453: }
454: return -1;
455: }
456:
457: /**
458: * Answers if this ArrayList has no elements, a size of zero.
459: *
460: * @return true if this ArrayList has no elements, false otherwise
461: *
462: * @see #size
463: */
464: @Override
465: public boolean isEmpty() {
466: return lastIndex == firstIndex;
467: }
468:
469: /**
470: * Searches this ArrayList for the specified object and returns the index of
471: * the last occurrence.
472: *
473: * @param object
474: * the object to search for
475: * @return the index of the last occurrence of the object
476: */
477: @Override
478: public int lastIndexOf(Object object) {
479: if (object != null) {
480: for (int i = lastIndex - 1; i >= firstIndex; i--) {
481: if (object.equals(array[i])) {
482: return i - firstIndex;
483: }
484: }
485: } else {
486: for (int i = lastIndex - 1; i >= firstIndex; i--) {
487: if (array[i] == null) {
488: return i - firstIndex;
489: }
490: }
491: }
492: return -1;
493: }
494:
495: /**
496: * Removes the object at the specified location from this ArrayList.
497: *
498: * @param location
499: * the index of the object to remove
500: * @return the removed object
501: *
502: * @exception IndexOutOfBoundsException
503: * when <code>location < 0 || >= size()</code>
504: */
505: @Override
506: public E remove(int location) {
507: E result;
508: int size = lastIndex - firstIndex;
509: if (0 <= location && location < size) {
510: if (location == size - 1) {
511: result = array[--lastIndex];
512: array[lastIndex] = null;
513: } else if (location == 0) {
514: result = array[firstIndex];
515: array[firstIndex++] = null;
516: } else {
517: int elementIndex = firstIndex + location;
518: result = array[elementIndex];
519: if (location < size / 2) {
520: System.arraycopy(array, firstIndex, array,
521: firstIndex + 1, location);
522: array[firstIndex++] = null;
523: } else {
524: System.arraycopy(array, elementIndex + 1, array,
525: elementIndex, size - location - 1);
526: array[--lastIndex] = null;
527: }
528: }
529: } else {
530: throw new IndexOutOfBoundsException();
531: }
532:
533: modCount++;
534: return result;
535: }
536:
537: /**
538: * Removes the first one of the specified object in this list, if present.
539: *
540: * @param object
541: * the object to removes
542: * @return true if the list contains the object
543: * @see java.util.AbstractCollection#remove(java.lang.Object)
544: */
545: @Override
546: public boolean remove(Object object) {
547: int location = indexOf(object);
548: if (location >= 0) {
549: remove(location);
550: return true;
551: }
552: return false;
553: }
554:
555: /**
556: * Removes the objects in the specified range from the start to the end, but
557: * not including the end index.
558: *
559: * @param start
560: * the index at which to start removing
561: * @param end
562: * the index one past the end of the range to remove
563: *
564: * @exception IndexOutOfBoundsException
565: * when <code>start < 0, start > end</code> or
566: * <code>end > size()</code>
567: */
568: @Override
569: protected void removeRange(int start, int end) {
570: if (start >= 0 && start <= end
571: && end <= (lastIndex - firstIndex)) {
572: if (start == end) {
573: return;
574: }
575: int size = lastIndex - firstIndex;
576: if (end == size) {
577: Arrays.fill(array, firstIndex + start, lastIndex, null);
578: lastIndex = firstIndex + start;
579: } else if (start == 0) {
580: Arrays.fill(array, firstIndex, firstIndex + end, null);
581: firstIndex += end;
582: } else {
583: System.arraycopy(array, firstIndex + end, array,
584: firstIndex + start, size - end);
585: int newLast = lastIndex + start - end;
586: Arrays.fill(array, newLast, lastIndex, null);
587: lastIndex = newLast;
588: }
589: modCount++;
590: } else {
591: throw new IndexOutOfBoundsException();
592: }
593: }
594:
595: /**
596: * Replaces the element at the specified location in this ArrayList with the
597: * specified object.
598: *
599: * @param location
600: * the index at which to put the specified object
601: * @param object
602: * the object to add
603: * @return the previous element at the index
604: *
605: * @exception IndexOutOfBoundsException
606: * when <code>location < 0 || >= size()</code>
607: */
608: @Override
609: public E set(int location, E object) {
610: if (0 <= location && location < (lastIndex - firstIndex)) {
611: E result = array[firstIndex + location];
612: array[firstIndex + location] = object;
613: return result;
614: }
615: throw new IndexOutOfBoundsException();
616: }
617:
618: /**
619: * Answers the number of elements in this ArrayList.
620: *
621: * @return the number of elements in this ArrayList
622: */
623: @Override
624: public int size() {
625: return lastIndex - firstIndex;
626: }
627:
628: /**
629: * Answers a new array containing all elements contained in this ArrayList.
630: *
631: * @return an array of the elements from this ArrayList
632: */
633: @Override
634: public Object[] toArray() {
635: int size = lastIndex - firstIndex;
636: Object[] result = new Object[size];
637: System.arraycopy(array, firstIndex, result, 0, size);
638: return result;
639: }
640:
641: /**
642: * Answers an array containing all elements contained in this ArrayList. If
643: * the specified array is large enough to hold the elements, the specified
644: * array is used, otherwise an array of the same type is created. If the
645: * specified array is used and is larger than this ArrayList, the array
646: * element following the collection elements is set to null.
647: *
648: * @param contents
649: * the array
650: * @return an array of the elements from this ArrayList
651: *
652: * @exception ArrayStoreException
653: * when the type of an element in this ArrayList cannot be
654: * stored in the type of the specified array
655: */
656: @Override
657: @SuppressWarnings("unchecked")
658: public <T> T[] toArray(T[] contents) {
659: int size = lastIndex - firstIndex;
660: if (size > contents.length) {
661: Class<?> ct = contents.getClass().getComponentType();
662: contents = (T[]) Array.newInstance(ct, size);
663: }
664: System.arraycopy(array, firstIndex, contents, 0, size);
665: if (size < contents.length) {
666: contents[size] = null;
667: }
668: return contents;
669: }
670:
671: /**
672: * Sets the capacity of this ArrayList to be the same as the size.
673: *
674: * @see #size
675: */
676: public void trimToSize() {
677: int size = lastIndex - firstIndex;
678: E[] newArray = newElementArray(size);
679: System.arraycopy(array, firstIndex, newArray, 0, size);
680: array = newArray;
681: firstIndex = 0;
682: lastIndex = array.length;
683: modCount = 0;
684: }
685:
686: private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField(
687: "size", Integer.TYPE) }; //$NON-NLS-1$
688:
689: private void writeObject(ObjectOutputStream stream)
690: throws IOException {
691: ObjectOutputStream.PutField fields = stream.putFields();
692: fields.put("size", lastIndex - firstIndex); //$NON-NLS-1$
693: stream.writeFields();
694: stream.writeInt(array.length);
695: Iterator<?> it = iterator();
696: while (it.hasNext()) {
697: stream.writeObject(it.next());
698: }
699: }
700:
701: @SuppressWarnings("unchecked")
702: private void readObject(ObjectInputStream stream)
703: throws IOException, ClassNotFoundException {
704: ObjectInputStream.GetField fields = stream.readFields();
705: lastIndex = fields.get("size", 0); //$NON-NLS-1$
706: array = newElementArray(stream.readInt());
707: for (int i = 0; i < lastIndex; i++) {
708: array[i] = (E) stream.readObject();
709: }
710: }
711: }
|