// 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!

#include <iostream>
#include <cstdlib>
#include <stdexcept>
#include <string>

using namespace std;

class Object {
public:
  virtual ~Object() {} // make sure that appropriate destructor will be called
  virtual string toString() const { return "Object"; }
  // any object can be converted to a string which can be printed to stream
};

using namespace std;

class IncomparableException: public logic_error
{
public:
	IncomparableException() : logic_error("Elements are not comparable.") {}
};


class Comparable : public Object
{ 
public:
  virtual int compareTo(Object* o) const throw(IncomparableException) = 0; 
  // pure virtual function:
  //   every proper class inheriting from Comparable has to provide
  //   definition for it
  // returned value (as in Java):
  //   -1 if *this < *o
  //    0 if *this == *o
  //    1 if *this > *o
};

class Integer : public Comparable
{
private:
  int value;
public: 
  Integer(int i) : value(i) {}
  string toString() const { 
    char c[10];
    itoa(value,c,10);
    return string(c);
  }
  int intValue() const { return value;}
  int compareTo(Object* o) const throw(IncomparableException)
  {
    Integer* other=dynamic_cast<Integer*>(o);
    // try to typecase the argument to pointer to Integer object
    // if not successful, other is set to NULL:
      
    if (other == NULL)
      // cannot compare different types
      throw IncomparableException();
      
    if (value < other->intValue())
      return -1;
    else if (value == other->intValue())
      return 0;
    else
      return 1;
  }
};

class Node { // do not modify this class
	Comparable* item;
	Node *next;
	
public:
	static int num_constructed;
  static int num_destructed;

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

	~Node() {
		num_destructed++;
	}
	  
	Comparable* getItem() {
		return item;
	} // end getItem

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

	Node* getNext() {
		return next;
	} // end getNext
}; // end class Node

int Node::num_constructed=0;
int Node::num_destructed=0;

	
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
}

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
}
	
Node* generateRandom(int size,long seed)
{
	srand(seed);
	Node* head=NULL;
	for (int i=0; i<size; i++)
		head=new Node(new Integer(rand()%100),head);
	return head;
}

int printSequence(Node* head)
// return the number of elements
{
	int count = 0;
	while (head != NULL) {
		count++;
		cout <<head->getItem()->toString()<<" ";
		head = head->getNext();
	}
	cout <<endl;		
	cout <<"Number of elements: "<<count<<endl;
	return count;
}

bool 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;
}

void dispose(Node* head) {
  while (head!=NULL) {
    delete head->getItem();
    Node* tmp=head;
    head = head->getNext();
    delete tmp;
  }
}

int main(int argn,char* args[]) { // do not modify
		
	if (argn<3) {
		cout <<"Specify two parameters: number_of items seed_to_random_generator"<<endl;
		return 0;
	}
	// generate sequence
	Node* sequence = generateRandom(atoi(args[1]),atoi(args[2]));
	// 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)
		cout <<"Warning: the resulting sequence has different number of elements!"<<endl;
		
	// test whether it's sorted
	if (!isSorted(sequence))
		cout <<"Warning: the resulting sequence is not sorted!"<<endl;
		
	// test that no new Node-s were created
	if (Node::num_constructed > ncon)
		cout <<"Warning: you have created new Node objects, which is not allowed!"<<endl;

	// test that no Node-s where lost
	if (Node::num_destructed > ndes)
		cout <<"Warning: you have lost some Node objects, which is not allowed!"<<endl;
		
  // deallocate the sequence
  dispose(sequence);
  
  // test that all Node-s have been deallocated
  // if not report "memory leak"		
  if (Node::num_constructed > Node::num_destructed)
    cout <<"Warning: there are at least "
         <<Node::num_constructed-Node::num_destructed
         <<" memory leaks in your program!"<<endl;
		
  cout <<"Done."<<endl;
  system("PAUSE");
  return 0;
}