import java.util.Collection;
import java.util.List;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.LinkedList;
import java.util.Stack;
// All the wordy "import"'s above can be replaced with a simple
// import java.util.*;

public class Lab9 extends JPFalt {
	/**
	 * Data for test cases.
	 */
	Person p1 = new Person("Alice", 1);
	Person p2 = new Person("Bob", 2);
	Person p3 = new Person("Chris", 3);
	Person p4 = new Person("Diana", 4);
	Person p5 = new Person("Ella", 5);
	
	/** 
	 * Create a test suite 
	 */
	public static void main(String[] args) {
		new Lab9();
	}
	
	/**
	 * Class constructor
	 */
	public Lab9() {
	}
	
	/**
	 * Test the Java standard LinkedList class
	 */
	public void testStandardLinkedList(){
		testHeader("Java standard LinkedList class");
		// prepare data for test, adding data using Collection interface
		Collection colStandard = new LinkedList();
		colStandard.add(p1);
		colStandard.add(p2);
		colStandard.add(p3);
		colStandard.add(p4);
		colStandard.add(p5);
		
		// Now, actually test
		// First, check the size
		expected("size = 5");
		actual("size = " + colStandard.size());
		
		// Then, check to contents of all elements
		expected(p1.toString());
		expected(p2.toString());
		expected(p3.toString());
		expected(p4.toString());
		expected(p5.toString());
		for(Iterator it = colStandard.iterator();it.hasNext();){
			Object o = it.next();
			actual(o.toString());
		}
	}
	
	/**
	 * Test MyLinkedList class
	 */
	/*public void testMyLinkedList(){
		testHeader("MyLinkedList class");
		// prepare data for test, adding data using Collection interface
		Collection colMy = new MyLinkedList();
		colMy.add(p1);
		colMy.add(p2);
		colMy.add(p3);
		colMy.add(p4);
		colMy.add(p5);
		
		// Now, actually test
		// First, check the size
		expected("size = 5");
		actual("size = " + colMy.size());
		
		// Then, check to contents of all elements
		expected(p1.toString());
		expected(p2.toString());
		expected(p3.toString());
		expected(p4.toString());
		expected(p5.toString());
		for(Iterator it = colMy.iterator();it.hasNext();){
			Object o = it.next();
			actual(o.toString());
		}
	}*/
	
	/**
	 *  Test MyStack class
	 *
	 */
	public void testMyStack(){
		MyStack mySt = new MyStack();
		mySt.push(p1);
		mySt.push(p2);
		mySt.push(p3);
		mySt.push(p4);
		mySt.push(p5);
		
		testHeader("pop()");
		expected(p5);
		actual(mySt.pop());
		
		testHeader("peek()");
		expected(p4);
		actual(mySt.peek());
		
		testHeader("peek(2)");
		expected(p2);
		actual(mySt.peek(2));
		
		testHeader("peek(3)");
		expected(p1);
		actual(mySt.peek(3));
				
		testHeader("peek(10)");
		expected("EmptyStackException");
		actual(mySt.peek(10));
	}

	/**
	 * Test the ListIterator of standard LinkedList class
	 */
	public void testListIteratorOfStandard(){
		testHeader("ListIterator of standard LinkedList");
		// prepare data for test, adding data using Collection interface
		Collection colStandard = new LinkedList();
		colStandard.add(p1);
		colStandard.add(p2);
		colStandard.add(p3);
		
		// Now, actually test
		expected("size = 3");
		actual("size = " + colStandard.size());
		
		ListIterator lit = ((List)colStandard).listIterator();
		testHeader("Go forward from beginning to end");
		expected(p1.toString());
		expected(p2.toString());
		expected(p3.toString());
		while(lit.hasNext()){
			Object o = lit.next();
			actual(o.toString());
		}
		
		testHeader("Now backward from end to beginning");
		expected(p3.toString());
		expected(p2.toString());
		expected(p1.toString());
		while(lit.hasPrevious()){
			Object o = lit.previous();
			actual(o.toString());
		}
	}
	
	/**
	 * Test the ListIterator of MyLinkedList class
	 */
	/*public void testListIteratorOfMyLinkedList(){
		testHeader("ListIterator of MyLinkedList");
		// prepare data for test, adding data using Collection interface
		Collection colMy = new MyLinkedList();
		colMy.add(p1);
		colMy.add(p2);
		colMy.add(p3);
		
		// Now, actually test
		expected("size = 3");
		actual("size = " + colMy.size());
		
		ListIterator lit = ((List)colMy).listIterator();
		testHeader("Go forward from beginning to end");
		expected(p1.toString());
		expected(p2.toString());
		expected(p3.toString());
		while(lit.hasNext()){
			Object o = lit.next();
			actual(o.toString());
		}
		
		testHeader("Now backward from end to beginning");
		expected(p3.toString());
		expected(p2.toString());
		expected(p1.toString());
		while(lit.hasPrevious()){
			Object o = lit.previous();
			actual(o.toString());
		}
	}*/
}

class MyLinkedList
{
	/**
	 * The inner class representing each node of the list
	 */
	class ListNode{
		Object data;
		ListNode next;
		ListNode(Object data, ListNode next){
			this.data = data;
			this.next = next;
		}
	}
	/**
	 * The pointer to the beginning of the list.
	 * header.next actually points to the first node of the list
	 */
	ListNode header = new ListNode(null, null);
	
	/**
	 * lastNode points to the last node of the list
	 * At first, when the list is empty, it points to the header
	 */
	ListNode lastNode = header;
	
	/**
	 * The variable keeping track of the size of the list
	 */
	int size = 0;

	/**
	 * Appends the specified element to the end of this list.
	 *
	 * @param o element to be appended to this list.
	 * @return true (as per the general contract of
	 * Collection.add).
	 */
	public boolean add(Object o){
		// create a node containing the new data
		ListNode newnode = new ListNode(o, null);
		// and append it to the end of the list
		this.lastNode.next = newnode;
		this.lastNode = newnode;
		
		// update the size of the list
		this.size++;
		
		return true;
	}
					
	/**
	 * The inner class representing the iterator over this collection
	 */
	class MyLLIterator implements Iterator {
		ListNode current_pointer;
		MyLLIterator(){
			// At first, set the current position to the beginning of the list
			this.current_pointer = header.next;
		}
		/**
		 * For what hasNext() is supposed to do, look at the specification
		 * of Iterator interface.
		 */
		public boolean hasNext(){
			// TODO: you need to re-implement the body of this method.
			// At present, it is just a dummy
			return true;
		}

		/**
		 * For what next() is supposed to do, look at the specification of
		 * Iterator interface.
		 * @return The method should return the data object, not the ListNode object
		 */
		public Object next(){
			// TODO: you need to re-implement the body of this method
			// At present, it is just a dummy
			return null;
		}
		public void remove(){
			// For this lab assignment, don't worry about this method.
			// Do nothing !
		}
	}
}

class MyStack extends Stack {
	/** The stack used for storing temporary data */
	Stack tmpStack = new Stack();

	/**
	 * Looks at the object at some depth from the top of stack, w/o removing it from stack
	 * @param depth: the number specified how deep to peek inside the stack
	 * @return the object at that depth.
	 */
	Object peek(int depth){
		//TODO: you need to re-implement the body of this method
		// At present, it is just a dummy
		return null;
	}
}

class Person {
	String name;
	int    ID;
	
	/**
	 * Construct a person.
	 */
	Person(String name, int ID) {
		this.name = name;
		this.ID = ID;
	}
	
	/**
	 * Convert this person to a string.
	 */
	public String toString() {
		return "new " + getClass().getName() + "(" +
			this.name + ", " +
			this.ID + ")";
	}
	
	public boolean equals(Object o){
		if(o instanceof Person){
			Person other = (Person)o;
			return (other.name.compareTo(this.name) == 0)
					&& (other.ID == this.ID);
		}
		else return false;
	}
}