/**
 * An IntList is a list of ints.
 */
public class IntList {
	private ConsCell start; // first in the list or null
/**
 * Construct a new IntList given its first ConsCell.
 * @param s the first ConsCell in the list or null
*/
	public IntList(ConsCell s) {
		start = s;
	}

/**
 * Cons the given element h onto us and return the resulting IntList.
 * @param h the head int for the new list
 * @return the IntList with head h and us for a tail
*/	
	public IntList cons(int h) {
		return new IntList (new ConsCell(h,start));
	}

/** 
 * Get our length.
 * @return our int lenth
*/
	public int length() {
		if (start == null)
			return 0;
		else
			return start.length();
	}

/**
 * Print ourself to System.out
 *
*/
	public void print() {
		System.out.print("[");
		ConsCell a = start;
		while (a != null) {
			System.out.print(a.getHead());
			a = a.getTail();
			if (a != null) System.out.print(",");
		}
		System.out.println("]");
	}

/**
 * Check the list to see if it contains a value
 * @param n integer we want to check for
 * @return If we found the integer or not
*/
	public boolean contains(int n) {
		ConsCell a = start;
		while (a != null) {
			if (n == a.getHead())
				return true;
			a = a.getTail();
		}
		return false;
	}

/**
 * Compare two lists to see if they are identical
 * @param y List to compare with
 * @return If the two lists are the same
*/
	public boolean equals(IntList y) {
		ConsCell a = start;
		ConsCell b = y.start;

		if (this.length() != y.length())
			return false;

		while (a != null || b != null) {
			if (a.getHead() != b.getHead())
				return false;
			
			a = a.getTail();
			b = b.getTail();
		}
		return true;
	}
/**
 * append two lists into a newly created third list
 * @param y list to append
 * @return this list and y appended into a new list
*/
	public IntList append(IntList y) {
		IntList newlist = new IntList(null);
	
		ConsCell a = reverse().start;

		IntList yrev=y.reverse();
		ConsCell b = yrev.start;
		
		while (b != null) {
			newlist = newlist.cons(b.getHead());
			b = b.getTail();
		}

		while (a != null) {
			newlist = newlist.cons(a.getHead());
			a = a.getTail();
		}
	
		return newlist;
	}

/**
 * Append two lists together recursively
 * @param y The list to append
 * @return The newly created list
*/
	public IntList appendRec(IntList y) {
		IntList newlist = new IntList(null);

		newlist = appendRecHelper(newlist, y.start);
		newlist = appendRecHelper(newlist, start);

		return newlist;
	}

/**
 * Helper function for AppendRec
 * @param newlist The list to append to
 * @param c The cell to append to the list
 * @return The newly created list
*/ 
	private IntList appendRecHelper(IntList newlist, ConsCell c) {
		if (c.getTail() != null)
			newlist = appendRecHelper(newlist, c.getTail());

		return newlist.cons(c.getHead());
	}

/**
 * reverse the contents of a list and store it in a new IntList
 * @return a new IntList
*/
	public IntList reverse() {
		IntList newlist = new IntList(null);
		ConsCell a = start;

		while (a != null) {
			newlist = newlist.cons(a.getHead());
			a = a.getTail();
		}
		
		return newlist;
	}

/**
 * reverseMe flips the list around without making a new copy
 * SideEffect: Reverses the list
*/
	public void reverseME() {
		/* The next two lines reverse it my creating a new instance  but have been
			commented out to perform a recursive version that doesn't create any
			new ConCells
		IntList newlist = this.reverse();
		this.start = newlist.start;
		*/
		reverseRec(null,start);
	}

/**
 * reverseRec recursively flips a IntList
 * SideEffect: Reverse the list
*/
	private void reverseRec(ConsCell a, ConsCell b) {
		if (b.getTail() != null)
			reverseRec(b, b.getTail());
		else
			this.start=b;

		b.setTail(a);
	}

/**
 * Create a new IntList by sorting the list from smallest to largest
 * @return A new list sorted from smallest to largest
*/
public IntList sort() {
	IntList newlist = this.reverse(); // We just want to make a copy so this is as good of a way 
	return mergesort(newlist);
}
	
/** Sorts the IntList from smallest to largest via merge sort algorithm
 * SideEffect: Sorts the list
*/
	public void sortME() {
	}

/** 
 * Merge sort algorithm method. Split the list in half and recursively call itself until
 * the entire list is essentially single units. Then recombine them in order
 * @param l The list to sort
 * @return The list sorted from least to greatest
*/
private IntList mergesort(IntList l)
{	
	if (l.length() <= 1)
		return l;

	IntList left = new IntList(null);
	IntList right = new IntList(null);

	int m = l.length() / 2;
	
	ConsCell p = l.start;
	int i = 0;
	while (p != null) {
		if (i < m) 
			left = left.cons(p.getHead());
		else 
			right = right.cons(p.getHead());

		p=p.getTail();
		i++;
	}

	left = mergesort(left);
	right = mergesort(right);

	return merge(left, right);
}

/**
 * mergesort helper function. This is where the list is actually sorted
 * @param left the left half of the list
 * @param right the right half of the list
 * @return The combined sorted list
*/
private IntList merge(IntList left, IntList right) {
	IntList result = new IntList(null);

	ConsCell l = left.start;
	ConsCell r = right.start;

	left.print();
	right.print();
	
	while (l != null && r != null) {
		if (l.getHead() >= r.getHead()) {
			result = result.cons(l.getHead());
			l=l.getTail();
		}
		else {
			result = result.cons(r.getHead());
			r=r.getTail();
 		}
	}

	while (r != null) {
		result = result.cons(r.getHead());
		r=r.getTail();
	}
	while (l != null) {
		result = result.cons(l.getHead());
		l=l.getTail();
	}


	System.out.println("result: "); result.print();
	return result;
}
}