/**
 * Ordered Linked List class
 * @author Suzanne Balik, 10 Apr 2002
 * Added copy and merge methods
 */

public class OrderedList {

  private Node head;
  
  public OrderedList(){
    head = null;
  }
  
  public void clear() {
    head = null;
  }
  
  public boolean isEmpty() {
    if (head == null) 
      return true;
    else
      return false;
  }
  
  public void insert(int info) {
  
    //Case 1 - The list is empty - create a head node and put info there
    if (isEmpty()) {
      head = new Node(info);
      return;
    }
    
    //Case 2 - Insert info before head node
    if (info < head.info) {
      head = new Node(info, head);
      return;
    }
    
    //Case 3 - Insert info in middle of list
    Node prev = head;
    Node curr = head.link;
    while (curr != null) {
      if (info < curr.info) {
        prev.link = new Node(info,curr);
	return;
      }
      else {
        prev = curr;
	curr = curr.link;
      }
    } 
      //Case 4 - Insert info at end of list
      prev.link = new Node(info);
      return;
  }
  
  public void remove(int info) {

    //Case 1 - The list is empty or info < head node's info
    if (isEmpty() || info < head.info)
      return;
    
    //Case 2 - The head node contains info - move head to the next node  
    if (head.info == info) {
      head = head.link;
      return;
    }
    
    //Case 3 - One of the other nodes contains info - link around the node
    Node prev = head;
    Node curr = head.link;
    //Keep looking as long as info > current node's info
    while(curr != null && info >= curr.info) {
      if (curr.info == info) {
        prev.link = curr.link;
	return;
      }
      else {
        prev = curr;
	curr = curr.link;
      }
    }
    
    //Case 4 - The list does not contain info - just return
    return;
  }
  
  //Create a copy of a list starting with a given Node
  private Node copy(Node ref) {
    if (ref == null)
      return null;
    else {
      Node retval = new Node(ref.info);
      Node prev = retval;
      ref = ref.link;
      while (ref != null) {
        prev.link = new Node(ref.info);
	prev = prev.link;
	ref = ref.link;
      }
      return retval;
    }
  } 
  
  
  
  //Merge a copy of the Nodes in the Other list with this list
  public void merge(OrderedList other) {
   if (other.head == null)
      return;
   if (isEmpty()) {
      head = copy(other.head);
      return;
   }
   Node prev;
   Node curr;
   Node tmp = other.head;
   if (other.head.info < head.info) {
      head = new Node(other.head.info, head);
      tmp = other.head.link;
   }
   prev = head;
   curr = head.link;
   while (curr != null && tmp != null) {
      if (tmp.info < curr.info) {
         prev.link = new Node(tmp.info,curr);
	 prev = prev.link;
	 tmp = tmp.link;
      }
      else {
         prev = curr;
	 curr = curr.link;
      }
   }
   if (tmp != null)
      prev.link = copy(tmp);
   return;
}
  
  
  
  public String toString() {
    String s = "[";
    Node tmp = head;
    while (tmp != null) {
      s += tmp.info;
      if (tmp.link != null)
        s += ", ";
      tmp = tmp.link;
    }
    s += "]";
    return s;
  }
  
  
  
  public static void main (String[] args) {
  
  //Create a linked list
  OrderedList list = new OrderedList();
  
  //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
  OrderedList other = new OrderedList();
  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);
  }
}