diff -r 3392f250c784 -r ecbd252fd3a7 emul/compact/src/main/java/java/util/LinkedList.java
--- a/emul/compact/src/main/java/java/util/LinkedList.java Fri Mar 22 16:59:47 2013 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1100 +0,0 @@
-/*
- * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util;
-
-/**
- * Doubly-linked list implementation of the {@code List} and {@code Deque}
- * interfaces. Implements all optional list operations, and permits all
- * elements (including {@code null}).
- *
- *
All of the operations perform as could be expected for a doubly-linked
- * list. Operations that index into the list will traverse the list from
- * the beginning or the end, whichever is closer to the specified index.
- *
- *
Note that this implementation is not synchronized.
- * If multiple threads access a linked list concurrently, and at least
- * one of the threads modifies the list structurally, it must be
- * synchronized externally. (A structural modification is any operation
- * that adds or deletes one or more elements; merely setting the value of
- * an element is not a structural modification.) This is typically
- * accomplished by synchronizing on some object that naturally
- * encapsulates the list.
- *
- * If no such object exists, the list should be "wrapped" using the
- * {@link Collections#synchronizedList Collections.synchronizedList}
- * method. This is best done at creation time, to prevent accidental
- * unsynchronized access to the list:
- * List list = Collections.synchronizedList(new LinkedList(...));
- *
- * The iterators returned by this class's {@code iterator} and
- * {@code listIterator} methods are fail-fast: if the list is
- * structurally modified at any time after the iterator is created, in
- * any way except through the Iterator's own {@code remove} or
- * {@code add} methods, the iterator will throw a {@link
- * ConcurrentModificationException}. Thus, in the face of concurrent
- * modification, the iterator fails quickly and cleanly, rather than
- * risking arbitrary, non-deterministic behavior at an undetermined
- * time in the future.
- *
- *
Note that the fail-fast behavior of an iterator cannot be guaranteed
- * as it is, generally speaking, impossible to make any hard guarantees in the
- * presence of unsynchronized concurrent modification. Fail-fast iterators
- * throw {@code ConcurrentModificationException} on a best-effort basis.
- * Therefore, it would be wrong to write a program that depended on this
- * exception for its correctness: the fail-fast behavior of iterators
- * should be used only to detect bugs.
- *
- *
This class is a member of the
- *
- * Java Collections Framework.
- *
- * @author Josh Bloch
- * @see List
- * @see ArrayList
- * @since 1.2
- * @param the type of elements held in this collection
- */
-
-public class LinkedList
- extends AbstractSequentialList
- implements List, Deque, Cloneable, java.io.Serializable
-{
- transient int size = 0;
-
- /**
- * Pointer to first node.
- * Invariant: (first == null && last == null) ||
- * (first.prev == null && first.item != null)
- */
- transient Node first;
-
- /**
- * Pointer to last node.
- * Invariant: (first == null && last == null) ||
- * (last.next == null && last.item != null)
- */
- transient Node last;
-
- /**
- * Constructs an empty list.
- */
- public LinkedList() {
- }
-
- /**
- * Constructs a list containing the elements of the specified
- * collection, in the order they are returned by the collection's
- * iterator.
- *
- * @param c the collection whose elements are to be placed into this list
- * @throws NullPointerException if the specified collection is null
- */
- public LinkedList(Collection extends E> c) {
- this();
- addAll(c);
- }
-
- /**
- * Links e as first element.
- */
- private void linkFirst(E e) {
- final Node f = first;
- final Node newNode = new Node<>(null, e, f);
- first = newNode;
- if (f == null)
- last = newNode;
- else
- f.prev = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Links e as last element.
- */
- void linkLast(E e) {
- final Node l = last;
- final Node newNode = new Node<>(l, e, null);
- last = newNode;
- if (l == null)
- first = newNode;
- else
- l.next = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Inserts element e before non-null Node succ.
- */
- void linkBefore(E e, Node succ) {
- // assert succ != null;
- final Node pred = succ.prev;
- final Node newNode = new Node<>(pred, e, succ);
- succ.prev = newNode;
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Unlinks non-null first node f.
- */
- private E unlinkFirst(Node f) {
- // assert f == first && f != null;
- final E element = f.item;
- final Node next = f.next;
- f.item = null;
- f.next = null; // help GC
- first = next;
- if (next == null)
- last = null;
- else
- next.prev = null;
- size--;
- modCount++;
- return element;
- }
-
- /**
- * Unlinks non-null last node l.
- */
- private E unlinkLast(Node l) {
- // assert l == last && l != null;
- final E element = l.item;
- final Node prev = l.prev;
- l.item = null;
- l.prev = null; // help GC
- last = prev;
- if (prev == null)
- first = null;
- else
- prev.next = null;
- size--;
- modCount++;
- return element;
- }
-
- /**
- * Unlinks non-null node x.
- */
- E unlink(Node x) {
- // assert x != null;
- final E element = x.item;
- final Node next = x.next;
- final Node prev = x.prev;
-
- if (prev == null) {
- first = next;
- } else {
- prev.next = next;
- x.prev = null;
- }
-
- if (next == null) {
- last = prev;
- } else {
- next.prev = prev;
- x.next = null;
- }
-
- x.item = null;
- size--;
- modCount++;
- return element;
- }
-
- /**
- * Returns the first element in this list.
- *
- * @return the first element in this list
- * @throws NoSuchElementException if this list is empty
- */
- public E getFirst() {
- final Node f = first;
- if (f == null)
- throw new NoSuchElementException();
- return f.item;
- }
-
- /**
- * Returns the last element in this list.
- *
- * @return the last element in this list
- * @throws NoSuchElementException if this list is empty
- */
- public E getLast() {
- final Node l = last;
- if (l == null)
- throw new NoSuchElementException();
- return l.item;
- }
-
- /**
- * Removes and returns the first element from this list.
- *
- * @return the first element from this list
- * @throws NoSuchElementException if this list is empty
- */
- public E removeFirst() {
- final Node f = first;
- if (f == null)
- throw new NoSuchElementException();
- return unlinkFirst(f);
- }
-
- /**
- * Removes and returns the last element from this list.
- *
- * @return the last element from this list
- * @throws NoSuchElementException if this list is empty
- */
- public E removeLast() {
- final Node l = last;
- if (l == null)
- throw new NoSuchElementException();
- return unlinkLast(l);
- }
-
- /**
- * Inserts the specified element at the beginning of this list.
- *
- * @param e the element to add
- */
- public void addFirst(E e) {
- linkFirst(e);
- }
-
- /**
- * Appends the specified element to the end of this list.
- *
- * This method is equivalent to {@link #add}.
- *
- * @param e the element to add
- */
- public void addLast(E e) {
- linkLast(e);
- }
-
- /**
- * Returns {@code true} if this list contains the specified element.
- * More formally, returns {@code true} if and only if this list contains
- * at least one element {@code e} such that
- * (o==null ? e==null : o.equals(e)).
- *
- * @param o element whose presence in this list is to be tested
- * @return {@code true} if this list contains the specified element
- */
- public boolean contains(Object o) {
- return indexOf(o) != -1;
- }
-
- /**
- * Returns the number of elements in this list.
- *
- * @return the number of elements in this list
- */
- public int size() {
- return size;
- }
-
- /**
- * Appends the specified element to the end of this list.
- *
- *
This method is equivalent to {@link #addLast}.
- *
- * @param e element to be appended to this list
- * @return {@code true} (as specified by {@link Collection#add})
- */
- public boolean add(E e) {
- linkLast(e);
- return true;
- }
-
- /**
- * Removes the first occurrence of the specified element from this list,
- * if it is present. If this list does not contain the element, it is
- * unchanged. More formally, removes the element with the lowest index
- * {@code i} such that
- * (o==null ? get(i)==null : o.equals(get(i)))
- * (if such an element exists). Returns {@code true} if this list
- * contained the specified element (or equivalently, if this list
- * changed as a result of the call).
- *
- * @param o element to be removed from this list, if present
- * @return {@code true} if this list contained the specified element
- */
- public boolean remove(Object o) {
- if (o == null) {
- for (Node x = first; x != null; x = x.next) {
- if (x.item == null) {
- unlink(x);
- return true;
- }
- }
- } else {
- for (Node x = first; x != null; x = x.next) {
- if (o.equals(x.item)) {
- unlink(x);
- return true;
- }
- }
- }
- return false;
- }
-
- /**
- * Appends all of the elements in the specified collection to the end of
- * this list, in the order that they are returned by the specified
- * collection's iterator. The behavior of this operation is undefined if
- * the specified collection is modified while the operation is in
- * progress. (Note that this will occur if the specified collection is
- * this list, and it's nonempty.)
- *
- * @param c collection containing elements to be added to this list
- * @return {@code true} if this list changed as a result of the call
- * @throws NullPointerException if the specified collection is null
- */
- public boolean addAll(Collection extends E> c) {
- return addAll(size, c);
- }
-
- /**
- * Inserts all of the elements in the specified collection into this
- * list, starting at the specified position. Shifts the element
- * currently at that position (if any) and any subsequent elements to
- * the right (increases their indices). The new elements will appear
- * in the list in the order that they are returned by the
- * specified collection's iterator.
- *
- * @param index index at which to insert the first element
- * from the specified collection
- * @param c collection containing elements to be added to this list
- * @return {@code true} if this list changed as a result of the call
- * @throws IndexOutOfBoundsException {@inheritDoc}
- * @throws NullPointerException if the specified collection is null
- */
- public boolean addAll(int index, Collection extends E> c) {
- checkPositionIndex(index);
-
- Object[] a = c.toArray();
- int numNew = a.length;
- if (numNew == 0)
- return false;
-
- Node pred, succ;
- if (index == size) {
- succ = null;
- pred = last;
- } else {
- succ = node(index);
- pred = succ.prev;
- }
-
- for (Object o : a) {
- @SuppressWarnings("unchecked") E e = (E) o;
- Node newNode = new Node<>(pred, e, null);
- if (pred == null)
- first = newNode;
- else
- pred.next = newNode;
- pred = newNode;
- }
-
- if (succ == null) {
- last = pred;
- } else {
- pred.next = succ;
- succ.prev = pred;
- }
-
- size += numNew;
- modCount++;
- return true;
- }
-
- /**
- * Removes all of the elements from this list.
- * The list will be empty after this call returns.
- */
- public void clear() {
- // Clearing all of the links between nodes is "unnecessary", but:
- // - helps a generational GC if the discarded nodes inhabit
- // more than one generation
- // - is sure to free memory even if there is a reachable Iterator
- for (Node x = first; x != null; ) {
- Node next = x.next;
- x.item = null;
- x.next = null;
- x.prev = null;
- x = next;
- }
- first = last = null;
- size = 0;
- modCount++;
- }
-
-
- // Positional Access Operations
-
- /**
- * Returns the element at the specified position in this list.
- *
- * @param index index of the element to return
- * @return the element at the specified position in this list
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public E get(int index) {
- checkElementIndex(index);
- return node(index).item;
- }
-
- /**
- * Replaces the element at the specified position in this list with the
- * specified element.
- *
- * @param index index of the element to replace
- * @param element element to be stored at the specified position
- * @return the element previously at the specified position
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public E set(int index, E element) {
- checkElementIndex(index);
- Node x = node(index);
- E oldVal = x.item;
- x.item = element;
- return oldVal;
- }
-
- /**
- * Inserts the specified element at the specified position in this list.
- * Shifts the element currently at that position (if any) and any
- * subsequent elements to the right (adds one to their indices).
- *
- * @param index index at which the specified element is to be inserted
- * @param element element to be inserted
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public void add(int index, E element) {
- checkPositionIndex(index);
-
- if (index == size)
- linkLast(element);
- else
- linkBefore(element, node(index));
- }
-
- /**
- * Removes the element at the specified position in this list. Shifts any
- * subsequent elements to the left (subtracts one from their indices).
- * Returns the element that was removed from the list.
- *
- * @param index the index of the element to be removed
- * @return the element previously at the specified position
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public E remove(int index) {
- checkElementIndex(index);
- return unlink(node(index));
- }
-
- /**
- * Tells if the argument is the index of an existing element.
- */
- private boolean isElementIndex(int index) {
- return index >= 0 && index < size;
- }
-
- /**
- * Tells if the argument is the index of a valid position for an
- * iterator or an add operation.
- */
- private boolean isPositionIndex(int index) {
- return index >= 0 && index <= size;
- }
-
- /**
- * Constructs an IndexOutOfBoundsException detail message.
- * Of the many possible refactorings of the error handling code,
- * this "outlining" performs best with both server and client VMs.
- */
- private String outOfBoundsMsg(int index) {
- return "Index: "+index+", Size: "+size;
- }
-
- private void checkElementIndex(int index) {
- if (!isElementIndex(index))
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- private void checkPositionIndex(int index) {
- if (!isPositionIndex(index))
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- /**
- * Returns the (non-null) Node at the specified element index.
- */
- Node node(int index) {
- // assert isElementIndex(index);
-
- if (index < (size >> 1)) {
- Node x = first;
- for (int i = 0; i < index; i++)
- x = x.next;
- return x;
- } else {
- Node x = last;
- for (int i = size - 1; i > index; i--)
- x = x.prev;
- return x;
- }
- }
-
- // Search Operations
-
- /**
- * Returns the index of the first occurrence of the specified element
- * in this list, or -1 if this list does not contain the element.
- * More formally, returns the lowest index {@code i} such that
- * (o==null ? get(i)==null : o.equals(get(i))),
- * or -1 if there is no such index.
- *
- * @param o element to search for
- * @return the index of the first occurrence of the specified element in
- * this list, or -1 if this list does not contain the element
- */
- public int indexOf(Object o) {
- int index = 0;
- if (o == null) {
- for (Node x = first; x != null; x = x.next) {
- if (x.item == null)
- return index;
- index++;
- }
- } else {
- for (Node x = first; x != null; x = x.next) {
- if (o.equals(x.item))
- return index;
- index++;
- }
- }
- return -1;
- }
-
- /**
- * Returns the index of the last occurrence of the specified element
- * in this list, or -1 if this list does not contain the element.
- * More formally, returns the highest index {@code i} such that
- * (o==null ? get(i)==null : o.equals(get(i))),
- * or -1 if there is no such index.
- *
- * @param o element to search for
- * @return the index of the last occurrence of the specified element in
- * this list, or -1 if this list does not contain the element
- */
- public int lastIndexOf(Object o) {
- int index = size;
- if (o == null) {
- for (Node x = last; x != null; x = x.prev) {
- index--;
- if (x.item == null)
- return index;
- }
- } else {
- for (Node x = last; x != null; x = x.prev) {
- index--;
- if (o.equals(x.item))
- return index;
- }
- }
- return -1;
- }
-
- // Queue operations.
-
- /**
- * Retrieves, but does not remove, the head (first element) of this list.
- *
- * @return the head of this list, or {@code null} if this list is empty
- * @since 1.5
- */
- public E peek() {
- final Node f = first;
- return (f == null) ? null : f.item;
- }
-
- /**
- * Retrieves, but does not remove, the head (first element) of this list.
- *
- * @return the head of this list
- * @throws NoSuchElementException if this list is empty
- * @since 1.5
- */
- public E element() {
- return getFirst();
- }
-
- /**
- * Retrieves and removes the head (first element) of this list.
- *
- * @return the head of this list, or {@code null} if this list is empty
- * @since 1.5
- */
- public E poll() {
- final Node f = first;
- return (f == null) ? null : unlinkFirst(f);
- }
-
- /**
- * Retrieves and removes the head (first element) of this list.
- *
- * @return the head of this list
- * @throws NoSuchElementException if this list is empty
- * @since 1.5
- */
- public E remove() {
- return removeFirst();
- }
-
- /**
- * Adds the specified element as the tail (last element) of this list.
- *
- * @param e the element to add
- * @return {@code true} (as specified by {@link Queue#offer})
- * @since 1.5
- */
- public boolean offer(E e) {
- return add(e);
- }
-
- // Deque operations
- /**
- * Inserts the specified element at the front of this list.
- *
- * @param e the element to insert
- * @return {@code true} (as specified by {@link Deque#offerFirst})
- * @since 1.6
- */
- public boolean offerFirst(E e) {
- addFirst(e);
- return true;
- }
-
- /**
- * Inserts the specified element at the end of this list.
- *
- * @param e the element to insert
- * @return {@code true} (as specified by {@link Deque#offerLast})
- * @since 1.6
- */
- public boolean offerLast(E e) {
- addLast(e);
- return true;
- }
-
- /**
- * Retrieves, but does not remove, the first element of this list,
- * or returns {@code null} if this list is empty.
- *
- * @return the first element of this list, or {@code null}
- * if this list is empty
- * @since 1.6
- */
- public E peekFirst() {
- final Node f = first;
- return (f == null) ? null : f.item;
- }
-
- /**
- * Retrieves, but does not remove, the last element of this list,
- * or returns {@code null} if this list is empty.
- *
- * @return the last element of this list, or {@code null}
- * if this list is empty
- * @since 1.6
- */
- public E peekLast() {
- final Node l = last;
- return (l == null) ? null : l.item;
- }
-
- /**
- * Retrieves and removes the first element of this list,
- * or returns {@code null} if this list is empty.
- *
- * @return the first element of this list, or {@code null} if
- * this list is empty
- * @since 1.6
- */
- public E pollFirst() {
- final Node f = first;
- return (f == null) ? null : unlinkFirst(f);
- }
-
- /**
- * Retrieves and removes the last element of this list,
- * or returns {@code null} if this list is empty.
- *
- * @return the last element of this list, or {@code null} if
- * this list is empty
- * @since 1.6
- */
- public E pollLast() {
- final Node l = last;
- return (l == null) ? null : unlinkLast(l);
- }
-
- /**
- * Pushes an element onto the stack represented by this list. In other
- * words, inserts the element at the front of this list.
- *
- * This method is equivalent to {@link #addFirst}.
- *
- * @param e the element to push
- * @since 1.6
- */
- public void push(E e) {
- addFirst(e);
- }
-
- /**
- * Pops an element from the stack represented by this list. In other
- * words, removes and returns the first element of this list.
- *
- *
This method is equivalent to {@link #removeFirst()}.
- *
- * @return the element at the front of this list (which is the top
- * of the stack represented by this list)
- * @throws NoSuchElementException if this list is empty
- * @since 1.6
- */
- public E pop() {
- return removeFirst();
- }
-
- /**
- * Removes the first occurrence of the specified element in this
- * list (when traversing the list from head to tail). If the list
- * does not contain the element, it is unchanged.
- *
- * @param o element to be removed from this list, if present
- * @return {@code true} if the list contained the specified element
- * @since 1.6
- */
- public boolean removeFirstOccurrence(Object o) {
- return remove(o);
- }
-
- /**
- * Removes the last occurrence of the specified element in this
- * list (when traversing the list from head to tail). If the list
- * does not contain the element, it is unchanged.
- *
- * @param o element to be removed from this list, if present
- * @return {@code true} if the list contained the specified element
- * @since 1.6
- */
- public boolean removeLastOccurrence(Object o) {
- if (o == null) {
- for (Node x = last; x != null; x = x.prev) {
- if (x.item == null) {
- unlink(x);
- return true;
- }
- }
- } else {
- for (Node x = last; x != null; x = x.prev) {
- if (o.equals(x.item)) {
- unlink(x);
- return true;
- }
- }
- }
- return false;
- }
-
- /**
- * Returns a list-iterator of the elements in this list (in proper
- * sequence), starting at the specified position in the list.
- * Obeys the general contract of {@code List.listIterator(int)}.
- *
- * The list-iterator is fail-fast: if the list is structurally
- * modified at any time after the Iterator is created, in any way except
- * through the list-iterator's own {@code remove} or {@code add}
- * methods, the list-iterator will throw a
- * {@code ConcurrentModificationException}. Thus, in the face of
- * concurrent modification, the iterator fails quickly and cleanly, rather
- * than risking arbitrary, non-deterministic behavior at an undetermined
- * time in the future.
- *
- * @param index index of the first element to be returned from the
- * list-iterator (by a call to {@code next})
- * @return a ListIterator of the elements in this list (in proper
- * sequence), starting at the specified position in the list
- * @throws IndexOutOfBoundsException {@inheritDoc}
- * @see List#listIterator(int)
- */
- public ListIterator listIterator(int index) {
- checkPositionIndex(index);
- return new ListItr(index);
- }
-
- private class ListItr implements ListIterator {
- private Node lastReturned = null;
- private Node next;
- private int nextIndex;
- private int expectedModCount = modCount;
-
- ListItr(int index) {
- // assert isPositionIndex(index);
- next = (index == size) ? null : node(index);
- nextIndex = index;
- }
-
- public boolean hasNext() {
- return nextIndex < size;
- }
-
- public E next() {
- checkForComodification();
- if (!hasNext())
- throw new NoSuchElementException();
-
- lastReturned = next;
- next = next.next;
- nextIndex++;
- return lastReturned.item;
- }
-
- public boolean hasPrevious() {
- return nextIndex > 0;
- }
-
- public E previous() {
- checkForComodification();
- if (!hasPrevious())
- throw new NoSuchElementException();
-
- lastReturned = next = (next == null) ? last : next.prev;
- nextIndex--;
- return lastReturned.item;
- }
-
- public int nextIndex() {
- return nextIndex;
- }
-
- public int previousIndex() {
- return nextIndex - 1;
- }
-
- public void remove() {
- checkForComodification();
- if (lastReturned == null)
- throw new IllegalStateException();
-
- Node lastNext = lastReturned.next;
- unlink(lastReturned);
- if (next == lastReturned)
- next = lastNext;
- else
- nextIndex--;
- lastReturned = null;
- expectedModCount++;
- }
-
- public void set(E e) {
- if (lastReturned == null)
- throw new IllegalStateException();
- checkForComodification();
- lastReturned.item = e;
- }
-
- public void add(E e) {
- checkForComodification();
- lastReturned = null;
- if (next == null)
- linkLast(e);
- else
- linkBefore(e, next);
- nextIndex++;
- expectedModCount++;
- }
-
- final void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
- }
-
- private static class Node {
- E item;
- Node next;
- Node prev;
-
- Node(Node prev, E element, Node next) {
- this.item = element;
- this.next = next;
- this.prev = prev;
- }
- }
-
- /**
- * @since 1.6
- */
- public Iterator descendingIterator() {
- return new DescendingIterator();
- }
-
- /**
- * Adapter to provide descending iterators via ListItr.previous
- */
- private class DescendingIterator implements Iterator {
- private final ListItr itr = new ListItr(size());
- public boolean hasNext() {
- return itr.hasPrevious();
- }
- public E next() {
- return itr.previous();
- }
- public void remove() {
- itr.remove();
- }
- }
-
- @SuppressWarnings("unchecked")
- private LinkedList superClone() {
- try {
- return (LinkedList) super.clone();
- } catch (CloneNotSupportedException e) {
- throw new InternalError();
- }
- }
-
- /**
- * Returns a shallow copy of this {@code LinkedList}. (The elements
- * themselves are not cloned.)
- *
- * @return a shallow copy of this {@code LinkedList} instance
- */
- public Object clone() {
- LinkedList clone = superClone();
-
- // Put clone into "virgin" state
- clone.first = clone.last = null;
- clone.size = 0;
- clone.modCount = 0;
-
- // Initialize clone with our elements
- for (Node x = first; x != null; x = x.next)
- clone.add(x.item);
-
- return clone;
- }
-
- /**
- * Returns an array containing all of the elements in this list
- * in proper sequence (from first to last element).
- *
- * The returned array will be "safe" in that no references to it are
- * maintained by this list. (In other words, this method must allocate
- * a new array). The caller is thus free to modify the returned array.
- *
- *
This method acts as bridge between array-based and collection-based
- * APIs.
- *
- * @return an array containing all of the elements in this list
- * in proper sequence
- */
- public Object[] toArray() {
- Object[] result = new Object[size];
- int i = 0;
- for (Node x = first; x != null; x = x.next)
- result[i++] = x.item;
- return result;
- }
-
- /**
- * Returns an array containing all of the elements in this list in
- * proper sequence (from first to last element); the runtime type of
- * the returned array is that of the specified array. If the list fits
- * in the specified array, it is returned therein. Otherwise, a new
- * array is allocated with the runtime type of the specified array and
- * the size of this list.
- *
- * If the list fits in the specified array with room to spare (i.e.,
- * the array has more elements than the list), the element in the array
- * immediately following the end of the list is set to {@code null}.
- * (This is useful in determining the length of the list only if
- * the caller knows that the list does not contain any null elements.)
- *
- *
Like the {@link #toArray()} method, this method acts as bridge between
- * array-based and collection-based APIs. Further, this method allows
- * precise control over the runtime type of the output array, and may,
- * under certain circumstances, be used to save allocation costs.
- *
- *
Suppose {@code x} is a list known to contain only strings.
- * The following code can be used to dump the list into a newly
- * allocated array of {@code String}:
- *
- *
- * String[] y = x.toArray(new String[0]);
- *
- * Note that {@code toArray(new Object[0])} is identical in function to
- * {@code toArray()}.
- *
- * @param a the array into which the elements of the list are to
- * be stored, if it is big enough; otherwise, a new array of the
- * same runtime type is allocated for this purpose.
- * @return an array containing the elements of the list
- * @throws ArrayStoreException if the runtime type of the specified array
- * is not a supertype of the runtime type of every element in
- * this list
- * @throws NullPointerException if the specified array is null
- */
- @SuppressWarnings("unchecked")
- public T[] toArray(T[] a) {
- if (a.length < size)
- a = (T[])java.lang.reflect.Array.newInstance(
- a.getClass().getComponentType(), size);
- int i = 0;
- Object[] result = a;
- for (Node x = first; x != null; x = x.next)
- result[i++] = x.item;
-
- if (a.length > size)
- a[size] = null;
-
- return a;
- }
-
- private static final long serialVersionUID = 876323262645176354L;
-
-}