X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=libjava%2Fjava%2Futil%2FLinkedList.java;fp=libjava%2Fjava%2Futil%2FLinkedList.java;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=d87e95a91c68ac8b067229a8286adbb7f58b0da2;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libjava/java/util/LinkedList.java b/libjava/java/util/LinkedList.java deleted file mode 100644 index d87e95a9..00000000 --- a/libjava/java/util/LinkedList.java +++ /dev/null @@ -1,956 +0,0 @@ -/* LinkedList.java -- Linked list implementation of the List interface - Copyright (C) 1998, 1999, 2000, 2001 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., 59 Temple Place, Suite 330, Boston, MA -02111-1307 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.Serializable; -import java.io.ObjectOutputStream; -import java.io.ObjectInputStream; -import java.io.IOException; -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.
- *
- * LinkedList is not synchronized, so if you need multi-threaded access,
- * consider using:
- * List l = Collections.synchronizedList(new LinkedList(...));
- *
- *
- * The iterators are fail-fast, meaning that any structural
- * modification, except for remove()
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 o == null ? e = null : o.equals(e)
.
- *
- * @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 o == null ? e = null : o.equals(e)
.
- *
- * @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 larger 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