/**
 * Ordered Linked List class using recursion
 * @author Suzanne Balik, 10 Apr 2002
 * Added copy and merge methods
 */
public class RecursiveOrderedList {

  private Node head;
  
  public RecursiveOrderedList(){
    head = null;
  }
  
  public void clear() {
    head = null;
  }
  
  public boolean isEmpty() {
    if (head == null) 
      return true;
    else
      return false;
  }
  
  public void insert(int info) {
  
    head = insertHelper(info, head);
  }
  
  private Node insertHelper(int info, Node ref) {
  
    if (ref == null)
      return new Node(info);
      
    if (info < ref.info)
      return new Node(info, ref);
      
    ref.link = insertHelper(info, ref.link);
    return ref;
  }
    
  
  public void remove(int info) {

    head = removeHelper(info, head);

  }
  
  private Node removeHelper(int info, Node ref) {
  
    if (ref == null)
      return null;
      
    if (info == ref.info)
      return ref.link;
      
    if (info < ref.info)
      return ref;
      
    ref.link = removeHelper(info, ref.link);
    return ref;
  }
  
  //Create a copy of a list starting with a given Node
  private Node copy(Node ref) {
    if (ref == null)
      return null;
    else
      return new Node(ref.info, copy(ref.link));
  }
  
  //Merge a copy of the Nodes in the Other list with this list
  public void merge(RecursiveOrderedList other) {

   head = mergeHelper(head, other.head);
  }

  private Node mergeHelper(Node ref, Node other) {

   if (ref == null && other == null)
      return null;
   if (ref == null)
      return copy(other);
   if (other == null)
      return ref;
   if (other.info < ref.info)
      return new Node(other.info, mergeHelper(ref, other.link));
      
   ref.link = mergeHelper(ref.link, other);
   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
  RecursiveOrderedList list = new RecursiveOrderedList();
  
  //Check if the list is empty
  System.out.println("List empty? " + list.isEmpty());
  
  //Insert some integers into the list
  list.insert(5);
  list.insert(2);
  list.insert(4);
  list.insert(9);
  
  //Check if the list is empty
  System.out.println("List empty? " + list.isEmpty());
  
  //Output the list
  System.out.println(list);
  
  //Try to remove something that's not in the list and output the list
  list.remove(1);
  System.out.println(list);
  
  
  //Remove the head node and output the list
  list.remove(2);
  System.out.println(list);
  
  //Remove a node in the middle and output the list
  list.remove(5);
  System.out.println(list);
  
  //Try to remove something that's not in the list and output the list
  list.remove(7);
  System.out.println(list);
  
  //Try to remove something that's not in the list and output the list
  list.remove(10);
  System.out.println(list);
  
  
  
  //Clear the list - list should be empty
  list.clear();
  System.out.println("List empty? " + list.isEmpty());
  
  //Insert some integers into the list
  list.insert(5);
  list.insert(2);
  list.insert(4);
  list.insert(9);
  System.out.println(list);
  
  //Create an other list and insert some integers into it
  RecursiveOrderedList other = new RecursiveOrderedList();
  other.insert(5);
  other.insert(7);
  other.insert(8);
  other.insert(1);
  System.out.println(other);
  
  //Merge list with other list and output
  list.merge(other);
  System.out.println(list);
  System.out.println(other);
  }
}