/**
 * Linked List class using recursion
 * @author Suzanne Balik, 23 Oct 2001
 */
public class RecursiveLinkedList {

  private Node head;
  
  public RecursiveLinkedList(){
    head = null;
  }
  
  public void clear() {
    head = null;
  }
  
  
  public void addToHead(int info) {
    head = new Node(info, head);
  }
  
  
  public void printInOrder(){
    printInOrderHelper(head);
  }
  
  private void printInOrderHelper(Node ref) {
  
    if (ref == null)
      return;
    else {
      System.out.println(ref.info);
      printInOrderHelper(ref.link);
    }
  }


  public void printInReverse(){
    printInReverseHelper(head);
  }
  
  private void printInReverseHelper(Node ref) {
  
    if (ref == null)
      return;
    else {
      printInReverseHelper(ref.link);
      System.out.println(ref.info);
    }
  } 
  
  
  public boolean find(int info) {
  
    return findHelper(info, head);
  }
  
  private boolean findHelper(int info, Node ref) {
  
    if (ref == null)
      return false;
    if (ref.info == info)
      return true;
    return findHelper(info, ref.link);
  }
  
  public int sum() {
  
    return sumHelper(head);
  }
  
  private int sumHelper(Node ref) {
  
    if (ref == null)
      return 0;
    return ref.info + sumHelper(ref.link);
  }
  
  public int min() {
  
    return minHelper(head);
    
  }
  
  private int minHelper(Node ref) throws EmptyListException {
  
    if (ref == null)
      throw new EmptyListException("List is empty!");
      
    if (ref.link == null)
      return ref.info;
      
    int min = minHelper(ref.link);
    if (min < ref.info)
      return min;
    else
      return ref.info;
  }
  
  
  public boolean isSorted() {
  
    return isSortedHelper(head);
    
  }
  
  private boolean isSortedHelper(Node ref) {
  
    if (ref == null)
      return true;
      
    if (ref.link == null)
      return true;
      
    if (ref.info > ref.link.info)
      return false;
      
    return isSortedHelper(ref.link);
  }
  
  
   
  public void remove(int info){
  
    head = removeHelper(info, head);
    
  }
  
  private Node removeHelper(int info, Node ref) {

    if (ref == null)
      return null;
  
    if (ref.info == info)
      return ref.link;
    
    ref.link = removeHelper(info, ref.link);
    return ref;
 }
    
  
  
  public String toString() {
    
    return "[" + toStringHelper(head) + "]";
  }
   
  private String toStringHelper(Node ref) {
  
    if (ref == null)
      return "";
      
    if (ref.link == null)
      return "" + ref.info;
      
    return ref.info + ", " + toStringHelper(ref.link);
  }
    
  
  public static void main (String[] args) {
  
  //Create a linked list
  RecursiveLinkedList list = new RecursiveLinkedList();
  
  
  //Add some integers to the list
  list.addToHead(5);
  list.addToHead(9);
  list.addToHead(4);
  list.addToHead(8);
  
  //Output the list using toString
  System.out.println(list);
  
  //Print the list in order
  System.out.println("\nPrint the list in order: ");
  list.printInOrder();
  
  //Print the list in reverse
  System.out.println("\nPrint the list in reverse: ");
  list.printInReverse();
  
  //Look for the numbers 1 - 10 in the list
  final int MAX = 10;
  for (int i = 1; i <= MAX; i++)
    System.out.println(i + " in the list?: " + list.find(i));
  
  //Find out if the list is sorted
  System.out.println("List sorted?: " + list.isSorted());
   
  //Get the sum of the numbers in the list
  System.out.println("Sum of numbers: " + list.sum());
  
  //Get the minimum value in the list
  System.out.println("Minimum value: " + list.min());
  
  //Remove the head node and output the list
  list.remove(8);
  System.out.println(list);
  
  //Get the sum of the numbers in the list
  System.out.println("Sum of numbers: " + list.sum());
  
  //Remove a node in the middle and output the list
  list.remove(9);
  System.out.println(list);
  
  //Get the sum of the numbers in the list
  System.out.println("Sum of numbers: " + list.sum());
  
  //Try to remove something that's not in the list and 
  //output the list
  list.remove(2);
  System.out.println(list);
  
  //Remove the last node  and output the list
  list.remove(5);
  System.out.println(list);
  
  //Get the sum of the numbers in the list
  System.out.println("Sum of numbers: " + list.sum());
  
  //Clear the list, print it, get the sum
  list.clear();
  System.out.println(list);
  System.out.println("Sum of numbers: " + list.sum());
  
  //Try to remove something from an empty list
  list.remove(6);
  
  //Add some integers to the list in sorted order
  list.addToHead(10);
  list.addToHead(9);
  list.addToHead(4);
  list.addToHead(3);
  list.addToHead(1);
  System.out.println(list);
  
  //Find out if the list is sorted
  System.out.println("List sorted?: " + list.isSorted());
  }
}