import java.util.*;

/**
 * ListOfObjects.java
 *
 *
 * Created: Fri Oct 08 09:45:58 1999
 *
 * @author Kenneth J. Goldman
 * 
 * This is an example implementation of list abstraction that uses a
 * doubly-linked list for its internal representation.
 * An Iterator is provided for efficiently traversing the list without
 * exposing the internal representation.
 * When an item is removed from the list, its ListItem is specially marked
 * so that iterators will skip over it.
 *
 */

public class ListOfObjects  {
  ListItem head;
  ListItem tail;
  int size;

  public ListOfObjects() {
    size = 0;
    head = new ListItem(null, null, null);
    tail = new ListItem(null, head, null);
    head.next = tail;
    tail.next = tail;
    head.prev = head;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public void addFirst(Object x) {
    ListItem added = new ListItem(x, head, head.next);
    head.next = added;
    added.next.prev = added;
    size++;
  }

  public void addLast(Object x) {
    ListItem added = new ListItem(x, tail.prev, tail);
    tail.prev = added;
    added.prev.next = added;
    size++;
  }

  public Object getFirst() {
    return head.next.data;
  }

  public Object getLast() {
    return tail.prev.data;
  }

  // could add a private method to insert after a specific item

  void remove(ListItem item) {
    if (item != head && item != tail && !item.removed) {
      item.prev.next = item.next;
      item.next.prev = item.prev;
      item.removed = true;
      size--;
    }
  }

  public Object removeFirst() {
    ListItem first = head.next;
    remove(first);
    return first.data;
  }

  public Object removeLast() {
    ListItem last = tail.prev;
    remove(last);
    return last.data;
  }

  public Iterator listIterator() {
    return new ListOfObjectsIterator();
  }

  public void clear() {
    Iterator elements = listIterator();
    while (elements.hasNext()) {
      elements.next();
      elements.remove();
    }
  }

  public boolean contains(Object x) {
    Iterator elements = listIterator();
    while (elements.hasNext()) {
      if (x.equals(elements.next()))
	return true;
    }
    return false;
  }

  public boolean removeFirstOccurrence(Object x) {
    Iterator elements = listIterator();
    while (elements.hasNext()) {
      if (x.equals(elements.next())) {
	elements.remove();
	return true;
      }
    }
    return false;
  }

  public String toString() {
    if (isEmpty())
      return "()";
    else
      return "(" + head.next + ")";
  }



  class ListItem {
    Object data;
    ListItem prev;
    ListItem next;
    boolean removed;
    ListItem(Object data, ListItem prev, ListItem next) {
      this.data = data;
      this.prev = prev;
      this.next = next;
      removed = false;
    }
    public String toString() {
      String result;
      if (data == null)
	result = "null";
      else
        result = data.toString();

      if (next != tail)
	result += (" " + next.toString()); 
      
      return result;
    }
  } // ListItem



  class ListOfObjectsIterator implements Iterator {
    ListItem current = head;

    void skipRemovedItems() {  // skips removed items following current one
      while (current.next.removed) {
	current = current.next;
      }
    }

    public boolean hasNext() {  // checks if a next non-removed item exists
      ListItem ptr = current;
      while (ptr.next.removed)
	ptr = ptr.next;
      return ptr.next != tail;
    }

    public Object next() {
      skipRemovedItems();       // skip the following removed items and
      current = current.next;   // then advance current
      if (current != tail)
	return current.data;
      else {
	return null;  // really should throw an exception
      }
    }

    public void remove() {
      ListOfObjects.this.remove(current);
    }
  } // ListOfObjectsIterator


  // A test program for the ListOfObjects class...
  public static void main(String args[]) {
    System.out.println("Testing ListOfObjects...");
    ListOfObjects list = new ListOfObjects();
    System.out.println("empty list: " + list);
    list.addFirst("b");
    list.addLast("c");
    list.addFirst("a");
    list.addLast("d");
    System.out.println("abcd? " + list);
    System.out.println("contains a? " + list.contains("a"));
    System.out.println("contains b? " + list.contains("b"));
    System.out.println("contains d? " + list.contains("d"));
    System.out.println("contains e? " + list.contains("e"));
    list.removeFirstOccurrence("c");
    System.out.println("after removing c: " + list);
    list.removeFirstOccurrence("a");
    System.out.println("after removing a: " + list);
    list.removeFirstOccurrence("f");
    System.out.println("after removing f: " + list);
    list.removeFirstOccurrence("d");
    System.out.println("after removing d: " + list);
    list.removeFirstOccurrence("b");
    System.out.println("after removing b: " + list);
    list.addFirst("b");
    list.addLast("c");
    list.addFirst("a");
    list.addLast("d");
    System.out.println("abcd? " + list);
    list.clear();
    System.out.println("after clearing: " + list);
    list.addFirst("b");
    list.addLast("c");
    list.addFirst("a");
    list.addLast("d");
    System.out.println("abcd? " + list);
    Iterator it1, it2, it3;
    it1 = list.listIterator();
    it2 = list.listIterator();
    it3 = list.listIterator();
    System.out.println("it1 is at " + it1.next());
    System.out.println("it1 is at " + it1.next());
    System.out.println("it2 is at " + it2.next());
    System.out.println("it2 is at " + it2.next());
    System.out.println("it2 is at " + it2.next());
    System.out.println("it3 is at " + it3.next());
    System.out.println("it1 is removing its current item ");
    it1.remove();
    System.out.println(list);
    System.out.println("it2 is removing its current item ");
    it2.remove();
    System.out.println(list);
    System.out.println("it3 is advancing directly to " + it3.next());
    System.out.println("it1 has next? " + it1.hasNext());
    System.out.println("it1 is advancing directly to " + it1.next());
    System.out.println("it1 has next? " + it1.hasNext());
    System.out.println("it2 is advancing directly to " + it2.next());
  }
  
} // ListOfObjects