diff options
Diffstat (limited to 'libjava/java/util/LinkedList.java')
| -rw-r--r-- | libjava/java/util/LinkedList.java | 958 |
1 files changed, 0 insertions, 958 deletions
diff --git a/libjava/java/util/LinkedList.java b/libjava/java/util/LinkedList.java deleted file mode 100644 index f611050df1d..00000000000 --- a/libjava/java/util/LinkedList.java +++ /dev/null @@ -1,958 +0,0 @@ -/* LinkedList.java -- Linked list implementation of the List interface - Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath 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 for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - - -package java.util; -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; -import java.io.Serializable; -import java.lang.reflect.Array; - -/** - * Linked list implementation of the List interface. In addition to the - * methods of the List interface, this class provides access to the first - * and last list elements in O(1) time for easy stack, queue, or double-ended - * queue (deque) creation. The list is doubly-linked, with traversal to a - * given index starting from the end closest to the element.<p> - * - * LinkedList is not synchronized, so if you need multi-threaded access, - * consider using:<br> - * <code>List l = Collections.synchronizedList(new LinkedList(...));</code> - * <p> - * - * The iterators are <i>fail-fast</i>, meaning that any structural - * modification, except for <code>remove()</code> called on the iterator - * itself, cause the iterator to throw a - * {@link ConcurrentModificationException} rather than exhibit - * non-deterministic behavior. - * - * @author Original author unknown - * @author Bryce McKinlay - * @author Eric Blake (ebb9@email.byu.edu) - * @see List - * @see ArrayList - * @see Vector - * @see Collections#synchronizedList(List) - * @since 1.2 - * @status missing javadoc, but complete to 1.4 - */ -public class LinkedList extends AbstractSequentialList - implements List, Cloneable, Serializable -{ - /** - * Compatible with JDK 1.2. - */ - private static final long serialVersionUID = 876323262645176354L; - - /** - * The first element in the list. - */ - transient Entry first; - - /** - * The last element in the list. - */ - transient Entry last; - - /** - * The current length of the list. - */ - transient int size = 0; - - /** - * Class to represent an entry in the list. Holds a single element. - */ - private static final class Entry - { - /** The element in the list. */ - Object data; - - /** The next list entry, null if this is last. */ - Entry next; - - /** The previous list entry, null if this is first. */ - Entry previous; - - /** - * Construct an entry. - * @param data the list element - */ - Entry(Object data) - { - this.data = data; - } - } // class Entry - - /** - * Obtain the Entry at a given position in a list. This method of course - * takes linear time, but it is intelligent enough to take the shorter of the - * paths to get to the Entry required. This implies that the first or last - * entry in the list is obtained in constant time, which is a very desirable - * property. - * For speed and flexibility, range checking is not done in this method: - * Incorrect values will be returned if (n < 0) or (n >= size). - * - * @param n the number of the entry to get - * @return the entry at position n - */ - // Package visible for use in nested classes. - Entry getEntry(int n) - { - Entry e; - if (n < size / 2) - { - e = first; - // n less than size/2, iterate from start - while (n-- > 0) - e = e.next; - } - else - { - e = last; - // n greater than size/2, iterate from end - while (++n < size) - e = e.previous; - } - return e; - } - - /** - * Remove an entry from the list. This will adjust size and deal with - * `first' and `last' appropriatly. - * - * @param e the entry to remove - */ - // Package visible for use in nested classes. - void removeEntry(Entry e) - { - modCount++; - size--; - if (size == 0) - first = last = null; - else - { - if (e == first) - { - first = e.next; - e.next.previous = null; - } - else if (e == last) - { - last = e.previous; - e.previous.next = null; - } - else - { - e.next.previous = e.previous; - e.previous.next = e.next; - } - } - } - - /** - * Checks that the index is in the range of possible elements (inclusive). - * - * @param index the index to check - * @throws IndexOutOfBoundsException if index < 0 || index > size - */ - private void checkBoundsInclusive(int index) - { - if (index < 0 || index > size) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" - + size); - } - - /** - * Checks that the index is in the range of existing elements (exclusive). - * - * @param index the index to check - * @throws IndexOutOfBoundsException if index < 0 || index >= size - */ - private void checkBoundsExclusive(int index) - { - if (index < 0 || index >= size) - throw new IndexOutOfBoundsException("Index: " + index + ", Size:" - + size); - } - - /** - * Create an empty linked list. - */ - public LinkedList() - { - } - - /** - * Create a linked list containing the elements, in order, of a given - * collection. - * - * @param c the collection to populate this list from - * @throws NullPointerException if c is null - */ - public LinkedList(Collection c) - { - addAll(c); - } - - /** - * Returns the first element in the list. - * - * @return the first list element - * @throws NoSuchElementException if the list is empty - */ - public Object getFirst() - { - if (size == 0) - throw new NoSuchElementException(); - return first.data; - } - - /** - * Returns the last element in the list. - * - * @return the last list element - * @throws NoSuchElementException if the list is empty - */ - public Object getLast() - { - if (size == 0) - throw new NoSuchElementException(); - return last.data; - } - - /** - * Remove and return the first element in the list. - * - * @return the former first element in the list - * @throws NoSuchElementException if the list is empty - */ - public Object removeFirst() - { - if (size == 0) - throw new NoSuchElementException(); - modCount++; - size--; - Object r = first.data; - - if (first.next != null) - first.next.previous = null; - else - last = null; - - first = first.next; - - return r; - } - - /** - * Remove and return the last element in the list. - * - * @return the former last element in the list - * @throws NoSuchElementException if the list is empty - */ - public Object removeLast() - { - if (size == 0) - throw new NoSuchElementException(); - modCount++; - size--; - Object r = last.data; - - if (last.previous != null) - last.previous.next = null; - else - first = null; - - last = last.previous; - - return r; - } - - /** - * Insert an element at the first of the list. - * - * @param o the element to insert - */ - public void addFirst(Object o) - { - Entry e = new Entry(o); - - modCount++; - if (size == 0) - first = last = e; - else - { - e.next = first; - first.previous = e; - first = e; - } - size++; - } - - /** - * Insert an element at the last of the list. - * - * @param o the element to insert - */ - public void addLast(Object o) - { - addLastEntry(new Entry(o)); - } - - /** - * Inserts an element at the end of the list. - * - * @param e the entry to add - */ - private void addLastEntry(Entry e) - { - modCount++; - if (size == 0) - first = last = e; - else - { - e.previous = last; - last.next = e; - last = e; - } - size++; - } - - /** - * Returns true if the list contains the given object. Comparison is done by - * <code>o == null ? e = null : o.equals(e)</code>. - * - * @param o the element to look for - * @return true if it is found - */ - public boolean contains(Object o) - { - Entry e = first; - while (e != null) - { - if (equals(o, e.data)) - return true; - e = e.next; - } - return false; - } - - /** - * Returns the size of the list. - * - * @return the list size - */ - public int size() - { - return size; - } - - /** - * Adds an element to the end of the list. - * - * @param e the entry to add - * @return true, as it always succeeds - */ - public boolean add(Object o) - { - addLastEntry(new Entry(o)); - return true; - } - - /** - * Removes the entry at the lowest index in the list that matches the given - * object, comparing by <code>o == null ? e = null : o.equals(e)</code>. - * - * @param o the object to remove - * @return true if an instance of the object was removed - */ - public boolean remove(Object o) - { - Entry e = first; - while (e != null) - { - if (equals(o, e.data)) - { - removeEntry(e); - return true; - } - e = e.next; - } - return false; - } - - /** - * Append the elements of the collection in iteration order to the end of - * this list. If this list is modified externally (for example, if this - * list is the collection), behavior is unspecified. - * - * @param c the collection to append - * @return true if the list was modified - * @throws NullPointerException if c is null - */ - public boolean addAll(Collection c) - { - return addAll(size, c); - } - - /** - * Insert the elements of the collection in iteration order at the given - * index of this list. If this list is modified externally (for example, - * if this list is the collection), behavior is unspecified. - * - * @param c the collection to append - * @return true if the list was modified - * @throws NullPointerException if c is null - * @throws IndexOutOfBoundsException if index < 0 || index > size() - */ - public boolean addAll(int index, Collection c) - { - checkBoundsInclusive(index); - int csize = c.size(); - - if (csize == 0) - return false; - - Iterator itr = c.iterator(); - - // Get the entries just before and after index. If index is at the start - // of the list, BEFORE is null. If index is at the end of the list, AFTER - // is null. If the list is empty, both are null. - Entry after = null; - Entry before = null; - if (index != size) - { - after = getEntry(index); - before = after.previous; - } - else - before = last; - - // Create the first new entry. We do not yet set the link from `before' - // to the first entry, in order to deal with the case where (c == this). - // [Actually, we don't have to handle this case to fufill the - // contract for addAll(), but Sun's implementation appears to.] - Entry e = new Entry(itr.next()); - e.previous = before; - Entry prev = e; - Entry firstNew = e; - - // Create and link all the remaining entries. - for (int pos = 1; pos < csize; pos++) - { - e = new Entry(itr.next()); - e.previous = prev; - prev.next = e; - prev = e; - } - - // Link the new chain of entries into the list. - modCount++; - size += csize; - prev.next = after; - if (after != null) - after.previous = e; - else - last = e; - - if (before != null) - before.next = firstNew; - else - first = firstNew; - return true; - } - - /** - * Remove all elements from this list. - */ - public void clear() - { - if (size > 0) - { - modCount++; - first = null; - last = null; - size = 0; - } - } - - /** - * Return the element at index. - * - * @param index the place to look - * @return the element at index - * @throws IndexOutOfBoundsException if index < 0 || index >= size() - */ - public Object get(int index) - { - checkBoundsExclusive(index); - return getEntry(index).data; - } - - /** - * Replace the element at the given location in the list. - * - * @param index which index to change - * @param o the new element - * @return the prior element - * @throws IndexOutOfBoundsException if index < 0 || index >= size() - */ - public Object set(int index, Object o) - { - checkBoundsExclusive(index); - Entry e = getEntry(index); - Object old = e.data; - e.data = o; - return old; - } - - /** - * Inserts an element in the given position in the list. - * - * @param index where to insert the element - * @param o the element to insert - * @throws IndexOutOfBoundsException if index < 0 || index > size() - */ - public void add(int index, Object o) - { - checkBoundsInclusive(index); - Entry e = new Entry(o); - - if (index < size) - { - modCount++; - Entry after = getEntry(index); - e.next = after; - e.previous = after.previous; - if (after.previous == null) - first = e; - else - after.previous.next = e; - after.previous = e; - size++; - } - else - addLastEntry(e); - } - - /** - * Removes the element at the given position from the list. - * - * @param index the location of the element to remove - * @return the removed element - * @throws IndexOutOfBoundsException if index < 0 || index > size() - */ - public Object remove(int index) - { - checkBoundsExclusive(index); - Entry e = getEntry(index); - removeEntry(e); - return e.data; - } - - /** - * Returns the first index where the element is located in the list, or -1. - * - * @param o the element to look for - * @return its position, or -1 if not found - */ - public int indexOf(Object o) - { - int index = 0; - Entry e = first; - while (e != null) - { - if (equals(o, e.data)) - return index; - index++; - e = e.next; - } - return -1; - } - - /** - * Returns the last index where the element is located in the list, or -1. - * - * @param o the element to look for - * @return its position, or -1 if not found - */ - public int lastIndexOf(Object o) - { - int index = size - 1; - Entry e = last; - while (e != null) - { - if (equals(o, e.data)) - return index; - index--; - e = e.previous; - } - return -1; - } - - /** - * Obtain a ListIterator over this list, starting at a given index. The - * ListIterator returned by this method supports the add, remove and set - * methods. - * - * @param index the index of the element to be returned by the first call to - * next(), or size() to be initially positioned at the end of the list - * @throws IndexOutOfBoundsException if index < 0 || index > size() - */ - public ListIterator listIterator(int index) - { - checkBoundsInclusive(index); - return new LinkedListItr(index); - } - - /** - * Create a shallow copy of this LinkedList (the elements are not cloned). - * - * @return an object of the same class as this object, containing the - * same elements in the same order - */ - public Object clone() - { - LinkedList copy = null; - try - { - copy = (LinkedList) super.clone(); - } - catch (CloneNotSupportedException ex) - { - } - copy.clear(); - copy.addAll(this); - return copy; - } - - /** - * Returns an array which contains the elements of the list in order. - * - * @return an array containing the list elements - */ - public Object[] toArray() - { - Object[] array = new Object[size]; - Entry e = first; - for (int i = 0; i < size; i++) - { - array[i] = e.data; - e = e.next; - } - return array; - } - - /** - * Returns an Array whose component type is the runtime component type of - * the passed-in Array. The returned Array is populated with all of the - * elements in this LinkedList. If the passed-in Array is not large enough - * to store all of the elements in this List, a new Array will be created - * and returned; if the passed-in Array is <i>larger</i> than the size - * of this List, then size() index will be set to null. - * - * @param a the passed-in Array - * @return an array representation of this list - * @throws ArrayStoreException if the runtime type of a does not allow - * an element in this list - * @throws NullPointerException if a is null - */ - public Object[] toArray(Object[] a) - { - if (a.length < size) - a = (Object[]) Array.newInstance(a.getClass().getComponentType(), size); - else if (a.length > size) - a[size] = null; - Entry e = first; - for (int i = 0; i < size; i++) - { - a[i] = e.data; - e = e.next; - } - return a; - } - - /** - * Serializes this object to the given stream. - * - * @param s the stream to write to - * @throws IOException if the underlying stream fails - * @serialData the size of the list (int), followed by all the elements - * (Object) in proper order - */ - private void writeObject(ObjectOutputStream s) throws IOException - { - s.defaultWriteObject(); - s.writeInt(size); - Entry e = first; - while (e != null) - { - s.writeObject(e.data); - e = e.next; - } - } - - /** - * Deserializes this object from the given stream. - * - * @param s the stream to read from - * @throws ClassNotFoundException if the underlying stream fails - * @throws IOException if the underlying stream fails - * @serialData the size of the list (int), followed by all the elements - * (Object) in proper order - */ - private void readObject(ObjectInputStream s) - throws IOException, ClassNotFoundException - { - s.defaultReadObject(); - int i = s.readInt(); - while (--i >= 0) - addLastEntry(new Entry(s.readObject())); - } - - /** - * A ListIterator over the list. This class keeps track of its - * position in the list and the two list entries it is between. - * - * @author Original author unknown - * @author Eric Blake (ebb9@email.byu.edu) - */ - private final class LinkedListItr implements ListIterator - { - /** Number of modifications we know about. */ - private int knownMod = modCount; - - /** Entry that will be returned by next(). */ - private Entry next; - - /** Entry that will be returned by previous(). */ - private Entry previous; - - /** Entry that will be affected by remove() or set(). */ - private Entry lastReturned; - - /** Index of `next'. */ - private int position; - - /** - * Initialize the iterator. - * - * @param index the initial index - */ - LinkedListItr(int index) - { - if (index == size) - { - next = null; - previous = last; - } - else - { - next = getEntry(index); - previous = next.previous; - } - position = index; - } - - /** - * Checks for iterator consistency. - * - * @throws ConcurrentModificationException if the list was modified - */ - private void checkMod() - { - if (knownMod != modCount) - throw new ConcurrentModificationException(); - } - - /** - * Returns the index of the next element. - * - * @return the next index - * @throws ConcurrentModificationException if the list was modified - */ - public int nextIndex() - { - checkMod(); - return position; - } - - /** - * Returns the index of the previous element. - * - * @return the previous index - * @throws ConcurrentModificationException if the list was modified - */ - public int previousIndex() - { - checkMod(); - return position - 1; - } - - /** - * Returns true if more elements exist via next. - * - * @return true if next will succeed - * @throws ConcurrentModificationException if the list was modified - */ - public boolean hasNext() - { - checkMod(); - return (next != null); - } - - /** - * Returns true if more elements exist via previous. - * - * @return true if previous will succeed - * @throws ConcurrentModificationException if the list was modified - */ - public boolean hasPrevious() - { - checkMod(); - return (previous != null); - } - - /** - * Returns the next element. - * - * @return the next element - * @throws ConcurrentModificationException if the list was modified - * @throws NoSuchElementException if there is no next - */ - public Object next() - { - checkMod(); - if (next == null) - throw new NoSuchElementException(); - position++; - lastReturned = previous = next; - next = lastReturned.next; - return lastReturned.data; - } - - /** - * Returns the previous element. - * - * @return the previous element - * @throws ConcurrentModificationException if the list was modified - * @throws NoSuchElementException if there is no previous - */ - public Object previous() - { - checkMod(); - if (previous == null) - throw new NoSuchElementException(); - position--; - lastReturned = next = previous; - previous = lastReturned.previous; - return lastReturned.data; - } - - /** - * Remove the most recently returned element from the list. - * - * @throws ConcurrentModificationException if the list was modified - * @throws IllegalStateException if there was no last element - */ - public void remove() - { - checkMod(); - if (lastReturned == null) - throw new IllegalStateException(); - - // Adjust the position to before the removed element, if the element - // being removed is behind the cursor. - if (lastReturned == previous) - position--; - - next = lastReturned.next; - previous = lastReturned.previous; - removeEntry(lastReturned); - knownMod++; - - lastReturned = null; - } - - /** - * Adds an element between the previous and next, and advance to the next. - * - * @param o the element to add - * @throws ConcurrentModificationException if the list was modified - */ - public void add(Object o) - { - checkMod(); - modCount++; - knownMod++; - size++; - position++; - Entry e = new Entry(o); - e.previous = previous; - e.next = next; - - if (previous != null) - previous.next = e; - else - first = e; - - if (next != null) - next.previous = e; - else - last = e; - - previous = e; - lastReturned = null; - } - - /** - * Changes the contents of the element most recently returned. - * - * @param o the new element - * @throws ConcurrentModificationException if the list was modified - * @throws IllegalStateException if there was no last element - */ - public void set(Object o) - { - checkMod(); - if (lastReturned == null) - throw new IllegalStateException(); - lastReturned.data = o; - } - } // class LinkedListItr -} |