/**
 * An incomplete implementation of a reverse sorted list.
 * Items are stored in an order opposite to that of their natural ordering.
 * Natural order is determined by Comparable's compareTo method.
 * (In other words, items are stored from greatest-to-least rather than
 * in the normal least-to-greatest order.)
 */
public class ReverseSortedList<E extends Comparable<E>> {

  private Node<E> head;
  // Only need ONE instance variable here.
  //
  // Original version had curr and str declared here.  However, they
  // only needed to be used within the body of a single method at a time.
  // It is much better to make them local variables so that they don't
  // incorrectly retain data between method calls.


  /** Adds an element to the appropriate location in this List. */

// If you had trouble with this one, trace through on paper how this code works.
// Add a node to an empty list, at the start of an existing list, at the end of
// an existing list, and somewhere in the middle of an existing list.

  //VERSION 1: As described in 08B lecture
  public void add(E item) {
    Node<E> before = null;
    Node<E> curr = this.head;
    while (curr != null && curr.getData().compareTo(item) > 0) {
      //go past all items greater than the item we're adding
      before = curr;
      curr = curr.getNext();
    }
    //now found where we want to add
    if (before == null) {
      //must be at very start of list, so need to update head pointer
      head = new Node<E>(item, curr);  //curr may be null here, which is fine
    }else {
      before.setNext(new Node<E>(item, curr));
    }
  }

/*
  //VERSION 2: Deal with empty list and insertion at head before the loop
  public void add(E item) {
    if (this.head == null || item.compareTo(this.head.getData()) > 0) {
      //list is empty or item goes before current head
      this.head = new Node<E>(item, this.head);
    }else {
      Node<E> before = this.head;
      Node<E> curr = this.head.getNext();
      //rather than use a before pointer, will just look at node after seek
      while (curr != null && curr.getData().compareTo(item) > 0) {
        //go past all items greater than item we're adding
        before = before.getNext();
        curr = curr.getNext();
      }
      //item now goes between before and curr
      //(curr may be null if it is the last item in list)
      before.setNext(new Node<E>(item, curr));
    }
  }
*/
/*
  //VERSION 3: Use only before pointer (renamed seek here) without needing curr
  public void add(E item) {
    if (this.head == null || item.compareTo(this.head.getData()) > 0) {
      //list is empty or item goes before current head
      this.head = new Node<E>(item, this.head);
    }else {
      Node<E> seek = this.head;
      //rather than use a before pointer, will just look at node after seek
      while (seek.getNext() != null &&
             seek.getNext().getData().compareTo(item) > 0) {
        //go past all items greater than item we're adding
        seek = seek.getNext();
      }
      //item now goes between seek and seek.getNext()
      //(seek.getNext() may be null if seek is last item in list)
      //Long version of node insertion (rather than 1-liner format used above)
      Node<E> toAdd = new Node<E>(item);
      toAdd.setNext(seek.getNext());
      seek.setNext(toAdd);
    }
  }
*/


  @Override
  public String toString() {
    String str = "";     //should be a local variable, not an instance variable
    Node<E> curr = head;
    while (curr != null) {
      str += curr.getData() + " ";
      curr = curr.getNext();
    }
    return str;
  }


  public static void main(String[] args) {
    ReverseSortedList<String> names = new ReverseSortedList<String>();
    names.add("Doug");
    names.add("Abe");
    names.add("Chris");
    names.add("Ben");
    names.add("Fred");
    System.out.println("[Fred Doug Chris Ben Abe ] =?= [" + names + "]");

    ReverseSortedList<Integer> nums = new ReverseSortedList<Integer>();
    nums.add(5);
    nums.add(7);
    nums.add(2);
    nums.add(8);
    nums.add(6);
    System.out.println("[8 7 6 5 2 ] =?= [" + nums + "]");

    System.out.println(nums);  //Should still be: 8 7 6 5 2
    System.out.println(nums);  //Should still be: 8 7 6 5 2
  }
}