/*
 * List.java
 * 
 * Login: 
 * 
 * This class creates Objects that can represent a List of Strings.
 */
public class List {

	private ListNode myHead;
	private int mySize;

	/*
	 * Constructor for List objects
	 */
	public List() {
		this.myHead = null;
		this.mySize = 0;
	}

	/***************************************************
	 * private ListNode class
	 ***************************************************/
	/*
	 * This class represents the internal structure of a List, created out of
	 * pairs modeled after Racket lists.
	 */
	private static class ListNode {

		// Instance variables modeled after Racket lists
		private String myFirst;
		private ListNode myRest;

		/*
		 * Constructor for ListNodes
		 */
		private ListNode(String first, ListNode rest) {
			this.myFirst = first;
			this.myRest = rest;
		}

		/*
		 * Create a ListNode with no reference to a second ListNode
		 */
		private ListNode(String first) {
			// An additional use of the keyword "this" is to call a constructor
			// with a different set of arguments. Must appear as the first line
			// of code within the constructor.
			this(first, null);
		}
	}

	/***************************************************
	 * List Methods
	 ***************************************************/
	/*
	 * isEmpty()
	 * 
	 * @return true if the List contains no ListNodes
	 */
	public boolean isEmpty() {
		return this.myHead == null;
		// also could have checked that size = 0;
	}

	/*
	 * toString()
	 * 
	 * @return a String representation of the contents of the List
	 */
	public String toString() {
		String rtn = "( ";
		for (ListNode node = this.myHead; node != null; node = node.myRest) {
			rtn = rtn + node.myFirst + " ";
		}
		return rtn + ")";
	}

	/*
	 * size()
	 * 
	 * @return the number of ListNodes in the List.
	 */
	public int size() {
		return this.mySize;
	}

	/*
	 * mySizeConsistent()
	 * 
	 * @return true if the number of ListNodes in the list is consistent with
	 * the value of the variable mySize.
	 */
	public boolean mySizeConsistent() {
		int count = 0;
		ListNode node = this.myHead;
		while (node != null) {
			count++;
			node = node.myRest;
		}
		return count == this.mySize;
	}

	/*
	 * length()
	 * 
	 * Without using the mySize instance variable, length calculates the length
	 * of the List.
	 */
	public int length() {
		int count = 0;
		for (ListNode node = this.myHead; node != null; node = node.myRest) {
			count++;
		}
		return count;
	}

	// a second version of length
	public int length2() {
		int count = 0;
		ListNode node = this.myHead;
		while (node != null) {
			count++;
			node = node.myRest;
		}
		return count;
	}

	/*
	 * contains(String obj)
	 * 
	 * @param an Object to look for in the List.
	 * 
	 * @return true if the value of myFirst in one of the ListNodes in this List
	 * is equal to the method input (using the method equals to determine
	 * equality)
	 */
	public boolean contains(String str) {
		for (ListNode node = this.myHead; node != null; node = node.myRest) {
			if (str.equals(node.myFirst)) {
				return true;
			}
		}
		return false;
	}

	/*
	 * get(int pos)
	 * 
	 * @param the desired index in the List.
	 * 
	 * @return the value of myFirst from the ListNode at that requested position
	 * in the List.
	 */
	public String get(int pos) {
		if (pos < 0) {
			throw new IllegalArgumentException(
					"Argument to get must be at least 0.");
		}
		if (pos >= this.size()) {
			throw new IllegalArgumentException("Argument to get is too large.");
		}
		int k = 0;
		for (ListNode node = this.myHead; node != null; node = node.myRest) {
			if (k == pos) {
				return node.myFirst;
			}
			k++;
		}
		return null;
	}

	/*
	 * addToFront(String str)
	 * 
	 * @param str is a new String to be inserted at the front of the list
	 * 
	 * This should modify the List and does not return anything.
	 */
	public void addToFront(String str) {
		this.mySize++;
		this.myHead = new ListNode(str, this.myHead);
	}

	/*
	 * addToFront(ListNode node)
	 * 
	 * @param node which is a ListNode to be inserted as the first element in
	 * the current List.
	 * 
	 * This should modify the List and does not return anything.
	 */
	public void addToFront(ListNode node) {
		this.mySize++;
		node.myRest = this.myHead;
		this.myHead = node;
	}

	/*
	 * equals(Object obj)
	 * 
	 * @param obj is an Object to compare the List to.
	 * 
	 * @return a boolean, which will be true if calling toString on the input
	 * Object produces an identical String to the String returned when calling
	 * toString on the current List (this) and false otherwise
	 */
	public boolean equals(Object obj) {
		// if obj is not of type List, they are not equal
		if (!(obj instanceof List)) {
			return false;
		}

		// We know that obj is of type List.
		// Create a reference to it for easy access.
		List list2 = (List) obj;

		// if the two lists are different sizes, they are not equal
		if (this.mySize != list2.mySize) {
			return false;
		}
		// compare element by element
		ListNode node1 = this.myHead;
		ListNode node2 = list2.myHead;
		for (int i = 0; i < this.mySize; i++) {
			if (!node1.myFirst.equals(node2.myFirst)) {
				return false;
			}
			node1 = node1.myRest;
			node2 = node2.myRest;
		}

		// if we haven't returned false by this point, return true
		return true;
	}

	/*
	 * add(String str)
	 * 
	 * @param str is a String to add to the end of the List.
	 * 
	 * This should modify the List and does not return anything. If this List is
	 * empty, it should add the String to the front of the List. If the List is
	 * not empty, it should search to find the last ListNode in the List and
	 * that ListNode's variable myRest should reference a new ListNode with the
	 * input argument (str) set as myFirst.
	 */
	public void add(String str) {
		// TODO write the method add
	}

	/*
	 * appendInPlace(List list2)
	 * 
	 * @param list2 is a List to be appended to the end of this List. If this
	 * List is empty, the List's myHead instance variable should refer to the
	 * first ListNode in the List list2. If this List is not empty, it should
	 * find the last ListNode in this List and its myRest instance variable
	 * should reference the first ListNode in list2.
	 * 
	 * This does not return anything and should modify this List, but should not
	 * modify list2.
	 */
	public void appendInPlace(List list2) {
		// TODO write the method appendInPlace
	}

	/*
	 * makeFromArray(String[] strArr)
	 * 
	 * @param strArr is an array of Strings.
	 * 
	 * @return a List of the same size as the input strArr and with the content
	 * from strArr in the order they appear in strArr.
	 * 
	 * This method is labeled as STATIC! This means you don't need an object of
	 * the class to call this method. Because it is a static method, you will
	 * not have access to a _this_ reference like you would in a non-static
	 * method. You can call this method by typing List.makeFromArray(x). We also
	 * could have made this a constructor that took in an String[].
	 * 
	 * You should use addToFront to add elements to your List. addToFront takes
	 * constant time, so this will allow you to add all of the elements to your
	 * List in O(N) time, where N is the length of the String[] strArr.
	 */
	public static List makeFromArray(String[] strArr) {
		// TODO write the method makeFromArray
		return null;
	}

	/*
	 * makeEquivalentArray()
	 * 
	 * @param none.
	 * 
	 * @return an String[] with the contents from the List in the same order in
	 * which they appear in the List.
	 * 
	 * It should not modify the List.
	 */
	public String[] makeEquivalentArray() {
		// TODO write the method makeEquivalentArray
		return null;
	}

	/*
	 * reverse()
	 * 
	 * @return none
	 * 
	 * This method should reverse the contents of the List without creating any
	 * new ListNode Objects or any new List Objects and without creating an
	 * Array or other structures. You can create references to Objects, but you
	 * can't call new. This type of restriction is called doing something
	 * "in place" because it does not require any additional Objects to be
	 * created.
	 * 
	 * However, you will need a few ListNode references. We recommend creating
	 * ListNode references to refer to the previous, current, and next ListNode.
	 * 
	 * You might find it helpful to use a while loop like this:
	 * 
	 * while (current != null)
	 * 
	 * where current is a ListNode reference.
	 * 
	 * You should draw out on paper how each of the references will change each
	 * time through your loop.
	 */
	public void reverse() {
		// TODO write the method reverse
	}

	/*
	 * split()
	 * 
	 * @return a new List that contains the second half of the elements in the
	 * original List.
	 * 
	 * The current list (this) should be modified to now only have a list of
	 * half the length.
	 * 
	 * If the current list (this) has only 1 element, the List should be
	 * unmodified and should return an empty List.
	 * 
	 * If the current list (this) has an odd number of elements, the current
	 * List should have one more element than the List that is returned.
	 */
	public List split() {
		// TODO Write split
		return null;
	}

	/*
	 * removeFirst()
	 * 
	 * @return the ListNode that was previously the first ListNode in the List.
	 * 
	 * This should modify the List to remove the first element in the List. The
	 * List should be unchanged if this is called on an empty List.
	 */
	public ListNode removeFirst() {
		// TODO write removeFirst
		return null;
	}

	/*
	 * merge(List list2)
	 * 
	 * @param list2 is an already sorted List to be merged with the current List
	 * (this).
	 * 
	 * The method should modify the current List to contain the merged
	 * combination of the current List (this) and the input List (list2).
	 * 
	 * The method merge should only be called on a List that is already in
	 * sorted order.
	 * 
	 * You will find Java's compareTo method helpful. Find information about
	 * String's compareTo here:
	 * http://docs.oracle.com/javase/6/docs/api/java/lang
	 * /String.html#compareTo(java.lang.String) You can also look at the
	 * examples in BSTNode.java
	 * 
	 * You may make an extra List Object, but you may not create any new
	 * ListNode Objects
	 * 
	 * You may find the method removeFirst() and addToFront(ListNode node)
	 * helpful.
	 * 
	 * This method will modify this and list2. When completed, list2 should be
	 * empty and the current List (this) should contain all elements in sorted
	 * order
	 */
	public void merge(List list2) {
		// TODO Write merge
	}

	/*
	 * mergeSort()
	 * 
	 * The method mergeSort should use split() and merge(List list2) to execute
	 * merge sort on a List.
	 * 
	 * This method will modify the List.
	 */
	public void mergeSort() {
		// TODO Write mergeSort
	}

	/*
	 * This is the method that will run when you click the green go button in
	 * Eclipse. We recommend that you call your methods here for additional
	 * debugging.
	 */
	public static void main(String[] args) {
		List myList = new List();
		myList.add("a");
		myList.add("b");
		myList.add("c");

		System.out.println(myList.length());
	}

}