001: /*
002: * Copyright 2007 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package sun.awt.util;
027:
028: import java.util.AbstractSequentialList;
029: import java.util.Collection;
030: import java.util.ConcurrentModificationException;
031: import java.util.Deque;
032: import java.util.Iterator;
033: import java.util.List;
034: import java.util.ListIterator;
035: import java.util.NoSuchElementException;
036:
037: /**
038: * Linked list implementation of the <tt>List</tt> interface. Implements all
039: * optional list operations, and permits all elements (including
040: * <tt>null</tt>). In addition to implementing the <tt>List</tt> interface,
041: * the <tt>IdentityLinkedList</tt> class provides uniformly named methods to
042: * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
043: * beginning and end of the list. These operations allow linked lists to be
044: * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
045: * double-ended queue}. <p>
046: *
047: * The class implements the <tt>Deque</tt> interface, providing
048: * first-in-first-out queue operations for <tt>add</tt>,
049: * <tt>poll</tt>, along with other stack and deque operations.<p>
050: *
051: * All of the operations perform as could be expected for a doubly-linked
052: * list. Operations that index into the list will traverse the list from
053: * the beginning or the end, whichever is closer to the specified index.<p>
054: *
055: * <p><strong>Note that this implementation is not synchronized.</strong>
056: * If multiple threads access a linked list concurrently, and at least
057: * one of the threads modifies the list structurally, it <i>must</i> be
058: * synchronized externally. (A structural modification is any operation
059: * that adds or deletes one or more elements; merely setting the value of
060: * an element is not a structural modification.) This is typically
061: * accomplished by synchronizing on some object that naturally
062: * encapsulates the list.
063: *
064: * If no such object exists, the list should be "wrapped" using the
065: * {@link Collections#synchronizedList Collections.synchronizedList}
066: * method. This is best done at creation time, to prevent accidental
067: * unsynchronized access to the list:<pre>
068: * List list = Collections.synchronizedList(new IdentityLinkedList(...));</pre>
069: *
070: * <p>The iterators returned by this class's <tt>iterator</tt> and
071: * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
072: * structurally modified at any time after the iterator is created, in
073: * any way except through the Iterator's own <tt>remove</tt> or
074: * <tt>add</tt> methods, the iterator will throw a {@link
075: * ConcurrentModificationException}. Thus, in the face of concurrent
076: * modification, the iterator fails quickly and cleanly, rather than
077: * risking arbitrary, non-deterministic behavior at an undetermined
078: * time in the future.
079: *
080: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
081: * as it is, generally speaking, impossible to make any hard guarantees in the
082: * presence of unsynchronized concurrent modification. Fail-fast iterators
083: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
084: * Therefore, it would be wrong to write a program that depended on this
085: * exception for its correctness: <i>the fail-fast behavior of iterators
086: * should be used only to detect bugs.</i>
087: */
088:
089: public class IdentityLinkedList<E> extends AbstractSequentialList<E>
090: implements List<E>, Deque<E> {
091: private transient Entry<E> header = new Entry<E>(null, null, null);
092: private transient int size = 0;
093:
094: /**
095: * Constructs an empty list.
096: */
097: public IdentityLinkedList() {
098: header.next = header.previous = header;
099: }
100:
101: /**
102: * Constructs a list containing the elements of the specified
103: * collection, in the order they are returned by the collection's
104: * iterator.
105: *
106: * @param c the collection whose elements are to be placed into this list
107: * @throws NullPointerException if the specified collection is null
108: */
109: public IdentityLinkedList(Collection<? extends E> c) {
110: this ();
111: addAll(c);
112: }
113:
114: /**
115: * Returns the first element in this list.
116: *
117: * @return the first element in this list
118: * @throws NoSuchElementException if this list is empty
119: */
120: public E getFirst() {
121: if (size == 0)
122: throw new NoSuchElementException();
123:
124: return header.next.element;
125: }
126:
127: /**
128: * Returns the last element in this list.
129: *
130: * @return the last element in this list
131: * @throws NoSuchElementException if this list is empty
132: */
133: public E getLast() {
134: if (size == 0)
135: throw new NoSuchElementException();
136:
137: return header.previous.element;
138: }
139:
140: /**
141: * Removes and returns the first element from this list.
142: *
143: * @return the first element from this list
144: * @throws NoSuchElementException if this list is empty
145: */
146: public E removeFirst() {
147: return remove(header.next);
148: }
149:
150: /**
151: * Removes and returns the last element from this list.
152: *
153: * @return the last element from this list
154: * @throws NoSuchElementException if this list is empty
155: */
156: public E removeLast() {
157: return remove(header.previous);
158: }
159:
160: /**
161: * Inserts the specified element at the beginning of this list.
162: *
163: * @param e the element to add
164: */
165: public void addFirst(E e) {
166: addBefore(e, header.next);
167: }
168:
169: /**
170: * Appends the specified element to the end of this list.
171: *
172: * <p>This method is equivalent to {@link #add}.
173: *
174: * @param e the element to add
175: */
176: public void addLast(E e) {
177: addBefore(e, header);
178: }
179:
180: /**
181: * Returns <tt>true</tt> if this list contains the specified element.
182: * More formally, returns <tt>true</tt> if and only if this list contains
183: * at least one element <tt>e</tt> such that
184: * <tt>(o==null ? e==null : o == e)</tt>.
185: *
186: * @param o element whose presence in this list is to be tested
187: * @return <tt>true</tt> if this list contains the specified element
188: */
189: public boolean contains(Object o) {
190: return indexOf(o) != -1;
191: }
192:
193: /**
194: * Returns the number of elements in this list.
195: *
196: * @return the number of elements in this list
197: */
198: public int size() {
199: return size;
200: }
201:
202: /**
203: * Appends the specified element to the end of this list.
204: *
205: * <p>This method is equivalent to {@link #addLast}.
206: *
207: * @param e element to be appended to this list
208: * @return <tt>true</tt> (as specified by {@link Collection#add})
209: */
210: public boolean add(E e) {
211: addBefore(e, header);
212: return true;
213: }
214:
215: /**
216: * Removes the first occurrence of the specified element from this list,
217: * if it is present. If this list does not contain the element, it is
218: * unchanged. More formally, removes the element with the lowest index
219: * <tt>i</tt> such that <tt>get(i)==o</tt>
220: * (if such an element exists). Returns <tt>true</tt> if this list
221: * contained the specified element (or equivalently, if this list
222: * changed as a result of the call).
223: *
224: * @param o element to be removed from this list, if present
225: * @return <tt>true</tt> if this list contained the specified element
226: */
227: public boolean remove(Object o) {
228: for (Entry<E> e = header.next; e != header; e = e.next) {
229: if (o == e.element) {
230: remove(e);
231: return true;
232: }
233: }
234: return false;
235: }
236:
237: /**
238: * Appends all of the elements in the specified collection to the end of
239: * this list, in the order that they are returned by the specified
240: * collection's iterator. The behavior of this operation is undefined if
241: * the specified collection is modified while the operation is in
242: * progress. (Note that this will occur if the specified collection is
243: * this list, and it's nonempty.)
244: *
245: * @param c collection containing elements to be added to this list
246: * @return <tt>true</tt> if this list changed as a result of the call
247: * @throws NullPointerException if the specified collection is null
248: */
249: public boolean addAll(Collection<? extends E> c) {
250: return addAll(size, c);
251: }
252:
253: /**
254: * Inserts all of the elements in the specified collection into this
255: * list, starting at the specified position. Shifts the element
256: * currently at that position (if any) and any subsequent elements to
257: * the right (increases their indices). The new elements will appear
258: * in the list in the order that they are returned by the
259: * specified collection's iterator.
260: *
261: * @param index index at which to insert the first element
262: * from the specified collection
263: * @param c collection containing elements to be added to this list
264: * @return <tt>true</tt> if this list changed as a result of the call
265: * @throws IndexOutOfBoundsException {@inheritDoc}
266: * @throws NullPointerException if the specified collection is null
267: */
268: public boolean addAll(int index, Collection<? extends E> c) {
269: if (index < 0 || index > size)
270: throw new IndexOutOfBoundsException("Index: " + index
271: + ", Size: " + size);
272: Object[] a = c.toArray();
273: int numNew = a.length;
274: if (numNew == 0)
275: return false;
276: modCount++;
277:
278: Entry<E> successor = (index == size ? header : entry(index));
279: Entry<E> predecessor = successor.previous;
280: for (int i = 0; i < numNew; i++) {
281: Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
282: predecessor.next = e;
283: predecessor = e;
284: }
285: successor.previous = predecessor;
286:
287: size += numNew;
288: return true;
289: }
290:
291: /**
292: * Removes all of the elements from this list.
293: */
294: public void clear() {
295: Entry<E> e = header.next;
296: while (e != header) {
297: Entry<E> next = e.next;
298: e.next = e.previous = null;
299: e.element = null;
300: e = next;
301: }
302: header.next = header.previous = header;
303: size = 0;
304: modCount++;
305: }
306:
307: // Positional Access Operations
308:
309: /**
310: * Returns the element at the specified position in this list.
311: *
312: * @param index index of the element to return
313: * @return the element at the specified position in this list
314: * @throws IndexOutOfBoundsException {@inheritDoc}
315: */
316: public E get(int index) {
317: return entry(index).element;
318: }
319:
320: /**
321: * Replaces the element at the specified position in this list with the
322: * specified element.
323: *
324: * @param index index of the element to replace
325: * @param element element to be stored at the specified position
326: * @return the element previously at the specified position
327: * @throws IndexOutOfBoundsException {@inheritDoc}
328: */
329: public E set(int index, E element) {
330: Entry<E> e = entry(index);
331: E oldVal = e.element;
332: e.element = element;
333: return oldVal;
334: }
335:
336: /**
337: * Inserts the specified element at the specified position in this list.
338: * Shifts the element currently at that position (if any) and any
339: * subsequent elements to the right (adds one to their indices).
340: *
341: * @param index index at which the specified element is to be inserted
342: * @param element element to be inserted
343: * @throws IndexOutOfBoundsException {@inheritDoc}
344: */
345: public void add(int index, E element) {
346: addBefore(element, (index == size ? header : entry(index)));
347: }
348:
349: /**
350: * Removes the element at the specified position in this list. Shifts any
351: * subsequent elements to the left (subtracts one from their indices).
352: * Returns the element that was removed from the list.
353: *
354: * @param index the index of the element to be removed
355: * @return the element previously at the specified position
356: * @throws IndexOutOfBoundsException {@inheritDoc}
357: */
358: public E remove(int index) {
359: return remove(entry(index));
360: }
361:
362: /**
363: * Returns the indexed entry.
364: */
365: private Entry<E> entry(int index) {
366: if (index < 0 || index >= size)
367: throw new IndexOutOfBoundsException("Index: " + index
368: + ", Size: " + size);
369: Entry<E> e = header;
370: if (index < (size >> 1)) {
371: for (int i = 0; i <= index; i++)
372: e = e.next;
373: } else {
374: for (int i = size; i > index; i--)
375: e = e.previous;
376: }
377: return e;
378: }
379:
380: // Search Operations
381:
382: /**
383: * Returns the index of the first occurrence of the specified element
384: * in this list, or -1 if this list does not contain the element.
385: * More formally, returns the lowest index <tt>i</tt> such that
386: * <tt>get(i)==o</tt>,
387: * or -1 if there is no such index.
388: *
389: * @param o element to search for
390: * @return the index of the first occurrence of the specified element in
391: * this list, or -1 if this list does not contain the element
392: */
393: public int indexOf(Object o) {
394: int index = 0;
395: for (Entry e = header.next; e != header; e = e.next) {
396: if (o == e.element) {
397: return index;
398: }
399: index++;
400: }
401: return -1;
402: }
403:
404: /**
405: * Returns the index of the last occurrence of the specified element
406: * in this list, or -1 if this list does not contain the element.
407: * More formally, returns the highest index <tt>i</tt> such that
408: * <tt>get(i)==o</tt>,
409: * or -1 if there is no such index.
410: *
411: * @param o element to search for
412: * @return the index of the last occurrence of the specified element in
413: * this list, or -1 if this list does not contain the element
414: */
415: public int lastIndexOf(Object o) {
416: int index = size;
417: for (Entry e = header.previous; e != header; e = e.previous) {
418: index--;
419: if (o == e.element) {
420: return index;
421: }
422: }
423: return -1;
424: }
425:
426: // Queue operations.
427:
428: /**
429: * Retrieves, but does not remove, the head (first element) of this list.
430: * @return the head of this list, or <tt>null</tt> if this list is empty
431: * @since 1.5
432: */
433: public E peek() {
434: if (size == 0)
435: return null;
436: return getFirst();
437: }
438:
439: /**
440: * Retrieves, but does not remove, the head (first element) of this list.
441: * @return the head of this list
442: * @throws NoSuchElementException if this list is empty
443: * @since 1.5
444: */
445: public E element() {
446: return getFirst();
447: }
448:
449: /**
450: * Retrieves and removes the head (first element) of this list
451: * @return the head of this list, or <tt>null</tt> if this list is empty
452: * @since 1.5
453: */
454: public E poll() {
455: if (size == 0)
456: return null;
457: return removeFirst();
458: }
459:
460: /**
461: * Retrieves and removes the head (first element) of this list.
462: *
463: * @return the head of this list
464: * @throws NoSuchElementException if this list is empty
465: * @since 1.5
466: */
467: public E remove() {
468: return removeFirst();
469: }
470:
471: /**
472: * Adds the specified element as the tail (last element) of this list.
473: *
474: * @param e the element to add
475: * @return <tt>true</tt> (as specified by {@link Queue#offer})
476: * @since 1.5
477: */
478: public boolean offer(E e) {
479: return add(e);
480: }
481:
482: // Deque operations
483: /**
484: * Inserts the specified element at the front of this list.
485: *
486: * @param e the element to insert
487: * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
488: * @since 1.6
489: */
490: public boolean offerFirst(E e) {
491: addFirst(e);
492: return true;
493: }
494:
495: /**
496: * Inserts the specified element at the end of this list.
497: *
498: * @param e the element to insert
499: * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
500: * @since 1.6
501: */
502: public boolean offerLast(E e) {
503: addLast(e);
504: return true;
505: }
506:
507: /**
508: * Retrieves, but does not remove, the first element of this list,
509: * or returns <tt>null</tt> if this list is empty.
510: *
511: * @return the first element of this list, or <tt>null</tt>
512: * if this list is empty
513: * @since 1.6
514: */
515: public E peekFirst() {
516: if (size == 0)
517: return null;
518: return getFirst();
519: }
520:
521: /**
522: * Retrieves, but does not remove, the last element of this list,
523: * or returns <tt>null</tt> if this list is empty.
524: *
525: * @return the last element of this list, or <tt>null</tt>
526: * if this list is empty
527: * @since 1.6
528: */
529: public E peekLast() {
530: if (size == 0)
531: return null;
532: return getLast();
533: }
534:
535: /**
536: * Retrieves and removes the first element of this list,
537: * or returns <tt>null</tt> if this list is empty.
538: *
539: * @return the first element of this list, or <tt>null</tt> if
540: * this list is empty
541: * @since 1.6
542: */
543: public E pollFirst() {
544: if (size == 0)
545: return null;
546: return removeFirst();
547: }
548:
549: /**
550: * Retrieves and removes the last element of this list,
551: * or returns <tt>null</tt> if this list is empty.
552: *
553: * @return the last element of this list, or <tt>null</tt> if
554: * this list is empty
555: * @since 1.6
556: */
557: public E pollLast() {
558: if (size == 0)
559: return null;
560: return removeLast();
561: }
562:
563: /**
564: * Pushes an element onto the stack represented by this list. In other
565: * words, inserts the element at the front of this list.
566: *
567: * <p>This method is equivalent to {@link #addFirst}.
568: *
569: * @param e the element to push
570: * @since 1.6
571: */
572: public void push(E e) {
573: addFirst(e);
574: }
575:
576: /**
577: * Pops an element from the stack represented by this list. In other
578: * words, removes and returns the first element of this list.
579: *
580: * <p>This method is equivalent to {@link #removeFirst()}.
581: *
582: * @return the element at the front of this list (which is the top
583: * of the stack represented by this list)
584: * @throws NoSuchElementException if this list is empty
585: * @since 1.6
586: */
587: public E pop() {
588: return removeFirst();
589: }
590:
591: /**
592: * Removes the first occurrence of the specified element in this
593: * list (when traversing the list from head to tail). If the list
594: * does not contain the element, it is unchanged.
595: *
596: * @param o element to be removed from this list, if present
597: * @return <tt>true</tt> if the list contained the specified element
598: * @since 1.6
599: */
600: public boolean removeFirstOccurrence(Object o) {
601: return remove(o);
602: }
603:
604: /**
605: * Removes the last occurrence of the specified element in this
606: * list (when traversing the list from head to tail). If the list
607: * does not contain the element, it is unchanged.
608: *
609: * @param o element to be removed from this list, if present
610: * @return <tt>true</tt> if the list contained the specified element
611: * @since 1.6
612: */
613: public boolean removeLastOccurrence(Object o) {
614: for (Entry<E> e = header.previous; e != header; e = e.previous) {
615: if (o == e.element) {
616: remove(e);
617: return true;
618: }
619: }
620: return false;
621: }
622:
623: /**
624: * Returns a list-iterator of the elements in this list (in proper
625: * sequence), starting at the specified position in the list.
626: * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
627: *
628: * The list-iterator is <i>fail-fast</i>: if the list is structurally
629: * modified at any time after the Iterator is created, in any way except
630: * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
631: * methods, the list-iterator will throw a
632: * <tt>ConcurrentModificationException</tt>. Thus, in the face of
633: * concurrent modification, the iterator fails quickly and cleanly, rather
634: * than risking arbitrary, non-deterministic behavior at an undetermined
635: * time in the future.
636: *
637: * @param index index of the first element to be returned from the
638: * list-iterator (by a call to <tt>next</tt>)
639: * @return a ListIterator of the elements in this list (in proper
640: * sequence), starting at the specified position in the list
641: * @throws IndexOutOfBoundsException {@inheritDoc}
642: * @see List#listIterator(int)
643: */
644: public ListIterator<E> listIterator(int index) {
645: return new ListItr(index);
646: }
647:
648: private class ListItr implements ListIterator<E> {
649: private Entry<E> lastReturned = header;
650: private Entry<E> next;
651: private int nextIndex;
652: private int expectedModCount = modCount;
653:
654: ListItr(int index) {
655: if (index < 0 || index > size)
656: throw new IndexOutOfBoundsException("Index: " + index
657: + ", Size: " + size);
658: if (index < (size >> 1)) {
659: next = header.next;
660: for (nextIndex = 0; nextIndex < index; nextIndex++)
661: next = next.next;
662: } else {
663: next = header;
664: for (nextIndex = size; nextIndex > index; nextIndex--)
665: next = next.previous;
666: }
667: }
668:
669: public boolean hasNext() {
670: return nextIndex != size;
671: }
672:
673: public E next() {
674: checkForComodification();
675: if (nextIndex == size)
676: throw new NoSuchElementException();
677:
678: lastReturned = next;
679: next = next.next;
680: nextIndex++;
681: return lastReturned.element;
682: }
683:
684: public boolean hasPrevious() {
685: return nextIndex != 0;
686: }
687:
688: public E previous() {
689: if (nextIndex == 0)
690: throw new NoSuchElementException();
691:
692: lastReturned = next = next.previous;
693: nextIndex--;
694: checkForComodification();
695: return lastReturned.element;
696: }
697:
698: public int nextIndex() {
699: return nextIndex;
700: }
701:
702: public int previousIndex() {
703: return nextIndex - 1;
704: }
705:
706: public void remove() {
707: checkForComodification();
708: Entry<E> lastNext = lastReturned.next;
709: try {
710: IdentityLinkedList.this .remove(lastReturned);
711: } catch (NoSuchElementException e) {
712: throw new IllegalStateException();
713: }
714: if (next == lastReturned)
715: next = lastNext;
716: else
717: nextIndex--;
718: lastReturned = header;
719: expectedModCount++;
720: }
721:
722: public void set(E e) {
723: if (lastReturned == header)
724: throw new IllegalStateException();
725: checkForComodification();
726: lastReturned.element = e;
727: }
728:
729: public void add(E e) {
730: checkForComodification();
731: lastReturned = header;
732: addBefore(e, next);
733: nextIndex++;
734: expectedModCount++;
735: }
736:
737: final void checkForComodification() {
738: if (modCount != expectedModCount)
739: throw new ConcurrentModificationException();
740: }
741: }
742:
743: private static class Entry<E> {
744: E element;
745: Entry<E> next;
746: Entry<E> previous;
747:
748: Entry(E element, Entry<E> next, Entry<E> previous) {
749: this .element = element;
750: this .next = next;
751: this .previous = previous;
752: }
753: }
754:
755: private Entry<E> addBefore(E e, Entry<E> entry) {
756: Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
757: newEntry.previous.next = newEntry;
758: newEntry.next.previous = newEntry;
759: size++;
760: modCount++;
761: return newEntry;
762: }
763:
764: private E remove(Entry<E> e) {
765: if (e == header)
766: throw new NoSuchElementException();
767:
768: E result = e.element;
769: e.previous.next = e.next;
770: e.next.previous = e.previous;
771: e.next = e.previous = null;
772: e.element = null;
773: size--;
774: modCount++;
775: return result;
776: }
777:
778: /**
779: * @since 1.6
780: */
781: public Iterator<E> descendingIterator() {
782: return new DescendingIterator();
783: }
784:
785: /** Adapter to provide descending iterators via ListItr.previous */
786: private class DescendingIterator implements Iterator {
787: final ListItr itr = new ListItr(size());
788:
789: public boolean hasNext() {
790: return itr.hasPrevious();
791: }
792:
793: public E next() {
794: return itr.previous();
795: }
796:
797: public void remove() {
798: itr.remove();
799: }
800: }
801:
802: /**
803: * Returns an array containing all of the elements in this list
804: * in proper sequence (from first to last element).
805: *
806: * <p>The returned array will be "safe" in that no references to it are
807: * maintained by this list. (In other words, this method must allocate
808: * a new array). The caller is thus free to modify the returned array.
809: *
810: * <p>This method acts as bridge between array-based and collection-based
811: * APIs.
812: *
813: * @return an array containing all of the elements in this list
814: * in proper sequence
815: */
816: public Object[] toArray() {
817: Object[] result = new Object[size];
818: int i = 0;
819: for (Entry<E> e = header.next; e != header; e = e.next)
820: result[i++] = e.element;
821: return result;
822: }
823:
824: /**
825: * Returns an array containing all of the elements in this list in
826: * proper sequence (from first to last element); the runtime type of
827: * the returned array is that of the specified array. If the list fits
828: * in the specified array, it is returned therein. Otherwise, a new
829: * array is allocated with the runtime type of the specified array and
830: * the size of this list.
831: *
832: * <p>If the list fits in the specified array with room to spare (i.e.,
833: * the array has more elements than the list), the element in the array
834: * immediately following the end of the list is set to <tt>null</tt>.
835: * (This is useful in determining the length of the list <i>only</i> if
836: * the caller knows that the list does not contain any null elements.)
837: *
838: * <p>Like the {@link #toArray()} method, this method acts as bridge between
839: * array-based and collection-based APIs. Further, this method allows
840: * precise control over the runtime type of the output array, and may,
841: * under certain circumstances, be used to save allocation costs.
842: *
843: * <p>Suppose <tt>x</tt> is a list known to contain only strings.
844: * The following code can be used to dump the list into a newly
845: * allocated array of <tt>String</tt>:
846: *
847: * <pre>
848: * String[] y = x.toArray(new String[0]);</pre>
849: *
850: * Note that <tt>toArray(new Object[0])</tt> is identical in function to
851: * <tt>toArray()</tt>.
852: *
853: * @param a the array into which the elements of the list are to
854: * be stored, if it is big enough; otherwise, a new array of the
855: * same runtime type is allocated for this purpose.
856: * @return an array containing the elements of the list
857: * @throws ArrayStoreException if the runtime type of the specified array
858: * is not a supertype of the runtime type of every element in
859: * this list
860: * @throws NullPointerException if the specified array is null
861: */
862: public <T> T[] toArray(T[] a) {
863: if (a.length < size)
864: a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
865: .getComponentType(), size);
866: int i = 0;
867: Object[] result = a;
868: for (Entry<E> e = header.next; e != header; e = e.next)
869: result[i++] = e.element;
870:
871: if (a.length > size)
872: a[size] = null;
873:
874: return a;
875: }
876: }
|