// file OrderedList.java
//  Singly linked list with header.


class GOrderedListA <T extends Comparable<T>>  {
   private T value;
   private GOrderedListA<T> next;

// Note: No setValue() method or setNext() methods are provided, 
// since those could require reordering the list.
  
   public T getValue() {
       return value; }

   public GOrderedListA<T> getNext() {
       return next; }

// If X is in the list, returns the previous node.
// If X is not in the list, returns the node for the greatest element less 
// than  X.

   public GOrderedListA<T> searchBefore(T x) { // Locate node containing x
       GOrderedListA<T> n = this;
       while (true) {
          if (n.next==null) return n;
          if (n.next.value.compareTo(x) >= 0) return n;
          n = n.next;
         } 
      }

// Is element x in the list. Note the use of the left to right evaluation of 
// && (if the condition n.net != null is false, then the conjunction returns
// false without evaluating n.next.value.equals(x).

   public boolean inList(T x) {
       GOrderedListA<T> n = searchBefore(x);
       return n.next != null && n.next.value.equals(x); }

// Adds x to the ordered list, if it is not already there.
   public void add(T x) {
       GOrderedListA<T> n = searchBefore(x);
       if (n.next == null || !(n.next.value.equals(x))) {
           GOrderedListA<T> newNode = new GOrderedListA<T>();
           newNode.value = x;
           newNode.next = n.next;
           n.next = newNode;
         }
     }
       
// Deletes x from the ordered list, if it is there.

   public void delete(T x) {
       GOrderedListA<T> n = searchBefore(x);
       if (n.next != null && n.next.value.equals(x))
          n.next = n.next.next;
      }



   public String toString() {
          GOrderedListA<T> a = next;
          String s = "[";
          while (a != null) {
             s = s + a.value.toString() + " ";
             a = a.next;
           }
         return s+ "]";
         }

   public static void main(String[] args) {
      GOrderedListA<MyString> l = new GOrderedListA<MyString>();
      l.add(new MyString("How"));
      l.add(new MyString("much"));
      l.add(new MyString("wood"));
      l.add(new MyString("could"));
      l.add(new MyString("a"));
      l.add(new MyString("woodchuck"));
      l.add(new MyString("chuck"));
      System.out.println(l.toString());
      l.delete(new MyString("wood"));
      System.out.println(l.toString());
}
}