LinkedList.java

/* LinkedList.java -- Linked list implementation of the List interface
   Copyright (C) 1998, 1999, 2000 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.

As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */


package java.util;
import java.io.Serializable;
import java.io.ObjectOutputStream;
import java.io.ObjectInputStream;
import java.io.IOException;
import java.lang.reflect.Array;

// TO DO:
// ~ Doc comment for the class.
// ~ Doc comments for the non-list methods.
// ~ other general implementation notes.

/**
 * Linked list implementation of the List interface.
 */
public class LinkedList extends AbstractSequentialList
  implements List, Cloneable, Serializable
{
  static final long serialVersionUID = 876323262645176354L;

  /**
   * An Entry containing the head (in the next field) and the tail (in the
   * previous field) of the list. The data field is null. If the list is empty,
   * both the head and the tail point to ends itself.
   */
  transient Entry first;
  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 class Entry
  {
    Object data;
    Entry next;
    Entry previous;
    
    Entry(Object data)
    {
      this.data = data;
    }
  }
  
  /**
   * 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.
   */
  private 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. It does not effect modCount, that is 
   *  the responsibility of the caller. */
  private void removeEntry(Entry e)
  {
    if (size == 1)
      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;
	  }
      }
    size--;
  }

  /**
   * Create an empty linked list.
   */
  public LinkedList()
  {
    super();
  }

  /**
   * Create a linked list containing the elements, in order, of a given
   * collection.
   *
   * @param c the collection to populate this list from.
   */
  public LinkedList(Collection c)
  {
    super();
    // Note: addAll could be made slightly faster, but not enough so to justify
    // re-implementing it from scratch. It is just a matter of a relatively
    // small constant factor.
    addAll(c);
  }

  public Object getFirst()
  {
    if (size == 0)
      throw new NoSuchElementException();
    return first.data;
  }

  public Object getLast()
  {
    if (size == 0)
      throw new NoSuchElementException();
    return last.data;
  }

  public Object removeFirst()
  {
    if (size == 0)
      throw new NoSuchElementException();
    size--;
    modCount++;
    Object r = first.data;
    
    if (first.next != null)
      first.next.previous = null;
    else
      last = null;

    first = first.next;
    
    return r;
  }

  public Object removeLast()
  {
    if (size == 0)
      throw new NoSuchElementException();
    size--;
    modCount++;
    Object r = last.data;
    
    if (last.previous != null)
      last.previous.next = null;
    else
      first = null;
    
    last = last.previous;
    
    return r;
  }

  public void addFirst(Object o)
  {
    modCount++;
    Entry e = new Entry(o);
    
    if (size == 0)
      first = last = e;
    else
      {
	e.next = first;
        first.previous = e;
	first = e;
      }    
    size++;
  }

  public void addLast(Object o)
  {
    modCount++;
    addLastEntry(new Entry(o));
  }
  
  private void addLastEntry(Entry e)
  {
    if (size == 0)
      first = last = e;
    else
      {
	e.previous = last;
        last.next = e;
	last = e;
      }
    size++;
  }

  public boolean contains(Object o)
  {
    Entry e = first;
    while (e != null)
      {
        if (e.data == null ? o == null : o.equals(e.data))
	  return true;
        e = e.next;
      }
    return false;
  }

  public int size()
  {
    return size;
  }
  
  public boolean add(Object o)
  {
    modCount++;
    addLastEntry(new Entry(o));
    return true;
  }
  
  public boolean remove(Object o)
  {
    modCount++;
    Entry e = first;
    while (e != null)
      {
        if (e.data == null ? o == null : o.equals(e.data))
	  {
	    removeEntry(e);
	    return true;
	  }
        e = e.next;
      }
    return false;
  }

  public boolean addAll(Collection c)
  {
    return addAll(size, c);
  }
  
  public boolean addAll(int index, Collection c)
  {
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    modCount++;
    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 thelist, 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.
    prev.next = after;
    if (after != null)
      after.previous = e;
    else
      last = e;
    
    if (before != null)
      before.next = firstNew;
    else
      first = firstNew;
    
    size += csize;
    return true;
  }

  public void clear()
  {
    modCount++;
    first = null;
    last = null;
    size = 0;
  }

  public Object get(int index)
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    Entry e = getEntry(index);
    return e.data;
  }
  
  public Object set(int index, Object o)
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    Entry e = getEntry(index);
    Object old = e.data;
    e.data = o;
    return old;
  }

  public void add(int index, Object o)
  {
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    modCount++;
    addEntry(index, new Entry(o));    
  }
  
  private void addEntry(int index, Entry e)
  {
    if (index < size)
      {
	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);
  }
  
  public Object remove(int index)
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    modCount++;
    Entry e = getEntry(index);
    removeEntry(e);
    return e.data;
  }
  
  public int indexOf(Object o)
  {
    int index = 0;
    Entry e = first;
    while (e != null)
      {
        if (e.data == null ? o == null : o.equals(e.data))
	  return index;
	++index;
        e = e.next;
      }
    return -1;
  }
  
  public int lastIndexOf(Object o)
  {
    int index = size - 1;
    Entry e = last;
    while (e != null)
      {
        if (e.data == null ? o == null : o.equals(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.
   * @exception IndexOutOfBoundsException if index < 0 || index > size().
   */
  public ListIterator listIterator(int index)
  {
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    return new LinkedListItr(index);
  }

  /**
   * Create a shallow copy of this LinkedList.
   * @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.size = 0;
    copy.addAll(this);
    return copy;
  }
  
  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;
  }
  
  public Object[] toArray(Object[] array)
  {
    if (array.length < size)
      array = (Object[]) Array.newInstance(array.getClass().getComponentType(), 
        				   size);
    else if (array.length > size)
      array[size] = null;
    Entry e = first;
    for (int i = 0; i < size; i++)
      {
        array[i] = e.data;
        e = e.next;
      }
    return array;  
  }

  /**
   * Serialize an object to a stream.
   * @serialdata the size of the list (int), followed by all the elements
   * (Object) in proper order.
   */
  private void writeObject(ObjectOutputStream s) throws IOException
  {
    s.writeInt(size);
    Iterator itr = iterator();
    for (int i = 0; i < size; i++)
      s.writeObject(itr.next());
  }

  /**
   * Deserialize an object from a stream.
   * @serialdata the size of the list (int), followed by all the elements
   * (Object) in proper order.
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    int serialSize = s.readInt();
    for (int i = 0; i < serialSize; i++)
      addLastEntry(new Entry(s.readObject()));
  }
  
  /** A ListIterator over the list. This class keeps track of its
   * position in the list, the size of the list, and the two list
   * entries it is between.  This enables it to be used identically
   * for both the list itself and a sublist of the list.
   */
  class LinkedListItr implements ListIterator
  {
    int knownMod;
    Entry next;         // entry that will be returned by next().
    Entry previous;     // entry that will be returned by previous().
    Entry lastReturned; // entry that will be affected by remove() or set().
    int position;       // index of `next'.

    /**
     * Create a new Iter starting at a given Entry within the list, at a given
     * position, in a list of given size.
     */
    LinkedListItr(int index)
    {
      if (index == size)
        {
          next = null;
	  previous = last;
	}
      else
        {
          next = getEntry(index);
	  previous = next.previous;
	}
      position = index;
      knownMod = modCount;
    }

    private void checkMod()
    {
      if (knownMod != modCount)
	throw new ConcurrentModificationException();
    }

    public int nextIndex()
    {
      checkMod();
      return position;
    }

    public int previousIndex()
    {
      checkMod();
      return position - 1;
    }

    public boolean hasNext()
    {
      checkMod();
      return (next != null);
    }

    public boolean hasPrevious()
    {
      checkMod();
      return (previous != null);
    }

    public Object next()
    {
      checkMod();
      if (next == null)
	throw new NoSuchElementException();
      position++;
      lastReturned = previous = next;
      next = lastReturned.next;
      return lastReturned.data;
    }

    public Object previous()
    {
      checkMod();
      if (previous == null)
	throw new NoSuchElementException();
      position--;
      lastReturned = next = previous;
      previous = lastReturned.previous;
      return lastReturned.data;
    }

    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;
      modCount++;
      knownMod++;
      removeEntry(lastReturned);
      
      lastReturned = null;
    }

    public void add(Object o)
    {
      checkMod();
      modCount++;
      knownMod++;
      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;
	  next = next.next;
	}
      else
	last = e;

      previous = e;
      size++;
      position++;
      lastReturned = null;
    }

    public void set(Object o)
    {
      checkMod();
      if (lastReturned == null)
	throw new IllegalStateException();
      lastReturned.data = o;
    }
  }  // class LinkedListItr  
}