import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;


/**
 * Test the MyLinkedList implementation of a (singly) linked-list.
 * The tests herein assume that the methods are implemented (successfully)
 * in the order listed.
 *
 * @author David Mutchler.
 *         Created October 12, 2008.
 */
public class MyLinkedListTest {

	private MyLinkedList<String> list;
	private List<String> testStrings;
	
	/**
	 * Does nothing; unused here.
	 *
	 * @throws java.lang.Exception
	 */
	@BeforeClass
	public static void setUpBeforeClass() throws Exception {
	}

	/**
	 * Does nothing; unused here.
	 *
	 * @throws java.lang.Exception
	 */
	@AfterClass
	public static void tearDownAfterClass() throws Exception {
	}

	/**
	 * Construct and add strings to a list to test
	 * and to a parallel ArrayList to use as an "oracle" for testing. 
	 *
	 * @throws java.lang.Exception
	 */
	@Before
	public void setUp() throws Exception {
		this.testStrings = new ArrayList<String>();
		
		this.testStrings.add("life's like this");
		this.testStrings.add("uh huh, uh huh");
		this.testStrings.add("chill out");
		this.testStrings.add("i like the way you are");
		this.testStrings.add("when we are driving in your car");
		this.testStrings.add("why did you have to go");
		this.testStrings.add("and make things so complicated?");
		this.testStrings.add("from Complicated, performed by Avril Lavigne");
		this.testStrings.add(null);	// tricky!
		this.testStrings.add("this is really the end");
		
		// list starts the same as testStrings
		
		this.list = new MyLinkedList<String>();
		
		for (String testString : this.testStrings) {
			this.list.add(testString);
		}
	}

	/**
	 * Does nothing; unused here.
	 *
	 * @throws java.lang.Exception
	 */
	@After
	public void tearDown() throws Exception {
	}

	/**
	 * Test method for {@link MyLinkedList#MyLinkedList()}.
	 */
	@Test
	public final void testMyLinkedList() {
		MyLinkedList<String> x = new MyLinkedList<String>();
		assertNotNull(x);
	}

	/**
	 * Test method for {@link MyLinkedList#add(java.lang.Object)}.
	 * Will NOT pass until SIZE is implemented.
	 */
	@Test
	public final void testAddE() {
		assertEquals(this.list.size(), this.testStrings.size());
	}

	/**
	 * Test method for {@link MyLinkedList#iterator()}.
	 */
	@Test
	public final void testIterator() {
		// Test that list and testStrings iterators behave the same
		Iterator<String> i = this.list.iterator();
		
		int k = 0;
		while (i.hasNext()) {
			String s = i.next();
			assertEquals(s, this.testStrings.get(k));
			++ k;
		}
	}

	/**
	 * Test method for {@link MyLinkedList#size()}.
	 */
	@Test
	public final void testSize() {
		assertEquals(this.list.size(), this.testStrings.size());
		
		MyLinkedList<String> smallList = new MyLinkedList<String>();
		assertEquals(smallList.size(), 0);
		
		smallList.add("new string in the list");
		assertEquals(smallList.size(), 1);
	}

	/**
	 * Test method for {@link MyLinkedList#clear()}.
	 */
	@Test
	public final void testClear() {
		assertEquals(this.list.size(), this.testStrings.size());
		
		this.list.clear();
		assertEquals(this.list.size(), 0);
	}

	/**
	 * Test method for {@link MyLinkedList#contains(java.lang.Object)}.
	 */
	@Test
	public final void testContains() {
		// Test that list contains all the strings in testStrings
		for (String testString : this.testStrings) {
			assertTrue(this.list.contains(testString));
		}
		
		// Test some boundary-case non-contains instances
		assertFalse(this.list.contains(""));
		assertFalse(this.list.contains("sdgdfd"));
		assertFalse(this.list.contains("\""));
		
		// Test that list contains all the strings in testStrings
		// even after testStrings is shuffled
		Collections.shuffle(this.testStrings);
		for (String testString : this.testStrings) {
			assertTrue(this.list.contains(testString));
		}
		
		// Test that list contains none of the strings in testStrings
		// after list is cleared
		this.list.clear();
		for (String testString : this.testStrings) {
			assertFalse(this.list.contains(testString));
		}
	}

	/**
	 * Test method for {@link MyLinkedList#get(int)}.
	 */
	@Test
	public final void testGet() {
		// Test that list contains all the strings in testStrings
		// at their proper places.  First test them in order (0, 1, ..)
		int k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Now test them in a mixed-up order
		assertEquals(this.list.get(3), this.testStrings.get(3));
		assertEquals(this.list.get(5), this.testStrings.get(5));
		assertEquals(this.list.get(3), this.testStrings.get(3));
		assertEquals(this.list.get(0), this.testStrings.get(0));
		assertEquals(this.list.get(this.list.size() - 1),
				this.testStrings.get(this.list.size() - 1));

		// Now test them in a reverse order
		Collections.reverse(this.testStrings);
		k = this.list.size() - 1;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			-- k;
		}
		
		// Test a few negative cases
		assertFalse(this.list.get(1).equals(""));
		assertFalse(this.list.get(1).equals(this.list.get(0)));
		
		// Test IndexOutOfBoundsException
		try {
			this.list.get(-1);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.get(-100);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.get(this.testStrings.size());
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.get(10000);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		this.list.clear();
		try {
			this.list.get(0);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
	}

	/**
	 * Test method for {@link MyLinkedList#isEmpty()}.
	 */
	@Test
	public final void testIsEmpty() {
		// Test that the list begins non-empty
		assertFalse(this.list.isEmpty());
		assertFalse(this.list.isEmpty());

		// Test that the list is empty after it is cleared
		this.list.clear();
		assertTrue(this.list.isEmpty());
		assertTrue(this.list.isEmpty());

		// Test a new small list -- size 0, then 1, then cleared back to 0
		MyLinkedList<String> smallList = new MyLinkedList<String>();
		assertTrue(smallList.isEmpty());
		
		smallList.add("");
		assertFalse(smallList.isEmpty());
		
		smallList.clear();
		assertTrue(smallList.isEmpty());
		assertTrue(smallList.isEmpty());
	}

	/**
	 * Test method for {@link MyLinkedList#remove(int)}.
	 */
	@Test
	public final void testRemoveInt() {
		// Test remove from middle
		this.testStrings.remove(this.testStrings.size() / 2);
		this.list.remove(this.list.size() / 2);

		int k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test remove from end
		this.testStrings.remove(this.testStrings.size() - 1);
		this.list.remove(this.list.size() - 1);

		k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test remove from beginning
		this.testStrings.remove(0);
		this.list.remove(0);

		k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test remove from beginning, repeatedly.
		int size = this.testStrings.size();
		for (int j = 0; j < size; ++j) {
			this.testStrings.remove(0);
			this.list.remove(0);

			k = 0;
			for (String testString : this.testStrings) {
				assertEquals(this.list.get(k), testString);
				++ k;
			}
		}
		assertTrue(this.list.size() == 0);
		assertTrue(this.list.isEmpty());
		
		// Test IndexOutOfBoundsException
		try {
			this.setUp();
		} catch (Exception e) {
			// Shouldn't get here!
		}

		try {
			this.list.remove(-1);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.remove(-100);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.remove(this.testStrings.size());
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.remove(10000);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		this.list.clear();
		try {
			this.list.remove(0);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
	}

	/**
	 * Test method for {@link MyLinkedList#add(int, java.lang.Object)}.
	 */
	@Test
	public final void testAddIntE() {
		// Test add in middle
		this.testStrings.add(this.testStrings.size() / 2, "new middle");
		this.list.add(this.list.size() / 2, "new middle");

		int k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test add to end
		this.testStrings.add(this.testStrings.size(), "new end");
		this.list.add(this.list.size(), "new end");

		k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test add at beginning
		this.testStrings.add(0, "new beginning");
		this.list.add(0, "new beginning");

		k = 0;
		for (String testString : this.testStrings) {
			assertEquals(this.list.get(k), testString);
			++ k;
		}
		
		// Test IndexOutOfBoundsException
		try {
			this.setUp();
		} catch (Exception e) {
			// Shouldn't get here!
		}

		try {
			this.list.add(-1, null);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.add(-100, "huh");
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.add(this.testStrings.size() + 1, "");
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		try {
			this.list.add(10000, null);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
		
		this.list.clear();
		try {
			this.list.add(-1, null);
			assertTrue(false);	// fail if you get here
		} catch (IndexOutOfBoundsException e) {
			// supposed to get here
		}
	}

	/**
	 * Test method for {@link MyLinkedList#set(int, java.lang.Object)}.
	 */
	@Test
	public final void testSet() {
		// Set each element to "", testing as you go
		for (int k = this.testStrings.size() - 1; k >= 0; --k) {
			assertEquals(this.list.get(k), this.testStrings.get(k));
			
			this.testStrings.set(k, k + "");
			assertFalse(this.testStrings.get(k).equals(this.list.get(k)));
			
			this.list.set(k, k + "");
			assertEquals(this.list.get(k), this.testStrings.get(k));
		}
	}

	/**
	 * Test method for {@link MyLinkedList#toArray()}.
	 */
	@Test
	public final void testToArray() {
		// Test that the returned array has the right elements
		Object[] listToArray = this.list.toArray();
		
		int k = 0;
		for (String testString : this.testStrings) {
			assertEquals(listToArray[k], testString);
			++ k;
		}
		
		// Test that the returned array has the right size
		assertEquals(listToArray.length, this.list.size());
	}

	/**
	 * Test method for {@link MyLinkedList#toArray(T[])}.
	 */
	@Test
	public final void testToArrayTArray() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#subList(int, int)}.
	 */
	@Test
	public final void testSubList() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#indexOf(java.lang.Object)}.
	 */
	@Test
	public final void testIndexOf() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#addAll(java.util.Collection)}.
	 */
	@Test
	public final void testAddAllCollectionOfQextendsE() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#addAll(int, java.util.Collection)}.
	 */
	@Test
	public final void testAddAllIntCollectionOfQextendsE() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#containsAll(java.util.Collection)}.
	 */
	@Test
	public final void testContainsAll() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#lastIndexOf(java.lang.Object)}.
	 */
	@Test
	public final void testLastIndexOf() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#listIterator()}.
	 */
	@Test
	public final void testListIterator() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#listIterator(int)}.
	 */
	@Test
	public final void testListIteratorInt() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#remove(java.lang.Object)}.
	 */
	@Test
	public final void testRemoveObject() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#removeAll(java.util.Collection)}.
	 */
	@Test
	public final void testRemoveAll() {
		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link MyLinkedList#retainAll(java.util.Collection)}.
	 */
	@Test
	public final void testRetainAll() {
		fail("Not yet implemented"); // TODO
	}

}