// UPDATED: Jun 28, 2006 at 8.45am

// Implement methods MergeSort and Merge in the following code.
// Do not modify or add any other methods.
// Run the program with parameter: number_of elements random_seed.
// Make sure that when you run the program it will not generate any warnings.
// Each warning will make you loose points for the implementation!

import java.util.Random;

public class a4 {

	public static class Node { // do not modify this class
	  private Comparable item;
	  private Node next;
	  public static int num_constructed=0;
	  public static int num_destructed=0;

	  public Node(Comparable newItem) {
	    item = newItem;
	    next = null;
	    num_constructed++;
	  } // end constructor

	  public Node(Comparable newItem, Node nextNode) {
	    item = newItem;
	    next = nextNode;
	    num_constructed++;
	  } // end constructor

	  public void finalize() {
	  	num_destructed++;
	  }
	  
	  public Comparable getItem() {
	    return item;
	  } // end getItem

	  public void setNext(Node nextNode) {
	    next = nextNode;
	  } // end setNext

	  public Node getNext() {
	    return next;
	  } // end getNext
	} // end class Node
	
	public static Node MergeSort(Node head)
	// the method is passed a reference to the head of linked list containing a sequence of objects
	// the method should return a head of a linked list containing the same nodes
	// but ordered using the method compareTo() on the objects
	// the method MergeSort can call itself and can call method Merge (see bellow)
	{
		// supply your code
	}

	public static Node Merge(Node head1, Node head2)
	// the method is passed two references to the heads of sorted linked lists
	// the method should return a head of new linked list which is sorted
	// and contains all nodes from the original two sorted linked lists
	{
		// supply your code
	}
	
	public static Node generateRandom(int size,long seed)
	{
		Random generator = new Random(seed);
		Node head=null;
		for (int i=0; i<size; i++)
			head=new Node(new Integer(generator.nextInt(100)),head);
		return head;
	}

	private static int printSequence(Node head)
	// return the number of elements
	{
		int count = 0;
		while (head != null) {
			count++;
			System.out.print(head.getItem()+" ");
			head = head.getNext();
		}
		System.out.println();		
		System.out.println("Number of elements: "+count);
		return count;
	}

	private static boolean isSorted(Node head) {
		if (head==null)
			return true;
		while (head.getNext()!=null) {
			if (head.getItem().compareTo(head.getNext().getItem()) > 0)
				return false;
			head = head.getNext();
		}
		
		return true;
	}

	public static void main(String[] args) { // do not modify
		
		if (args.length<2) {
			System.out.println("Specify two parameters: number_of items seed_to_random_generator");
			return;
		}
		// generate sequence
		Node sequence = generateRandom(Integer.parseInt(args[0]),
																	 Integer.parseInt(args[1]));
		// remember the number of Nodes
		int ncon = Node.num_constructed;
		int ndes = Node.num_destructed;
		
		// print the sequence
		int nelements = printSequence(sequence);
		
		// sort sequence
		sequence=MergeSort(sequence);
		
		// print the sequence and test whether the number of elements didn't change
		if (printSequence(sequence) != nelements)
			System.out.println("Warning: the resulting sequence has different number of elements!");
		
		// test whether it's sorted
		if (!isSorted(sequence))
			System.out.println("Warning: the resulting sequence is not sorted!");
		
		// test that no new Node-s were created
		if (Node.num_constructed > ncon)
			System.out.println("Warning: you have created new Node objects, which is not allowed!");

		// force garbage collection
		Runtime R=Runtime.getRuntime();
		R.gc();
		
		// test that no Node-s where lost
		if (Node.num_destructed > ndes)
			System.out.println("Warning: you have lost some Node objects, which is not allowed!");
		
		System.out.println("Done.");
	}

}