package de.ugoe.cs.quest.usageprofiles;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;

import junitx.framework.ListAssert;

import org.junit.*;

import de.ugoe.cs.quest.usageprofiles.Trie;
import de.ugoe.cs.quest.usageprofiles.TrieNode;
import de.ugoe.cs.quest.usageprofiles.Trie.Edge;
import de.ugoe.cs.quest.usageprofiles.Trie.TrieVertex;
import static org.junit.Assert.*;

/**
 * The class <code>TrieTest</code> contains tests for the class
 * <code>{@link Trie}</code>.
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class TrieTest {

	List<String> sequence;
	Collection<String> symbols;

	private static void assertCollectionContent(Collection<?> c1,
			Collection<?> c2) {
		assertEquals(c1.size(), c2.size());
		for (Object obj : c1) {
			assertTrue(c2.contains(obj));
		}
	}

	@Test
	public void testTrie_1() throws Exception {

		Trie<String> result = new Trie<String>();

		assertNotNull(result);
		assertEquals(0, result.getNumLeafs());
		assertEquals(0, result.getNumSymbols());
		assertEquals(0, result.getNumLeafAncestors());
		assertTrue(result.getKnownSymbols().isEmpty());
	}

	@Test
	public void testTrie_2() throws Exception {
		Trie<String> trie1 = new Trie<String>();
		trie1.train(sequence, 3);

		Trie<String> result = new Trie<String>(trie1);

		assertEquals(trie1, result);
		assertNotSame(trie1, result);
	}

	@Test(expected = java.security.InvalidParameterException.class)
	public void testTrie_3() throws Exception {
		new Trie<String>(null);
	}

	@Test
	public void testAdd_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		List<String> seq = new ArrayList<String>();
		seq.add("a");
		seq.add("b");

		fixture.add(seq);

		assertEquals(1, fixture.getChild("a").getCount());
		assertEquals(1, fixture.getChild("a").getChild("b").getCount());
		assertNull(fixture.getChild("b"));
	}

	@Test
	public void testAdd_2() throws Exception {
		Trie<String> fixture = new Trie<String>();

		fixture.add(new ArrayList<String>());

		assertEquals(0, fixture.getNumSymbols());
	}

	@Test
	public void testAdd_3() throws Exception {
		Trie<String> fixture = new Trie<String>();

		fixture.add(null);

		assertEquals(0, fixture.getNumSymbols());
	}

	@Test
	public void testFind_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> findSequence = new ArrayList<String>();
		findSequence.add("a");
		findSequence.add("b");
		findSequence.add("r");
		TrieNode<String> expected = fixture.getChild("a").getChild("b")
				.getChild("r");

		TrieNode<String> result = fixture.find(findSequence);

		assertEquals(expected, result);
	}

	@Test
	public void testFind_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> findSequence = new ArrayList<String>();
		findSequence.add("c");
		findSequence.add("a");
		TrieNode<String> expected = fixture.getChild("c").getChild("a");

		TrieNode<String> result = fixture.find(findSequence);

		assertEquals(expected, result);
	}

	@Test
	public void testFind_3() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> findSequence = new ArrayList<String>();

		TrieNode<String> result = fixture.find(findSequence);

		assertTrue(result.isRoot());
	}

	@Test
	public void testFind_4() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);

		TrieNode<String> result = fixture.find(null);

		assertTrue(result.isRoot());
	}

	@Test
	public void testGetChildCreate_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		String symbol = "a";

		TrieNode<String> result = fixture.getChildCreate(symbol);

		assertEquals(symbol, result.getSymbol());
		assertEquals(0, result.getCount());
		assertTrue(result.isLeaf());
	}

	@Test(expected = java.security.InvalidParameterException.class)
	public void testGetChildCreate_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.getChildCreate(null);
	}

	@Test
	public void testGetContextSuffix_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> context = new ArrayList<String>();
		context.add("a");
		context.add("a");
		context.add("b");
		List<String> expected = new ArrayList<String>();
		expected.add("a");
		expected.add("b");

		List<String> result = fixture.getContextSuffix(context);

		ListAssert.assertEquals(expected, result);
	}

	@Test
	public void testGetContextSuffix_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> context = new ArrayList<String>();
		context.add("a");
		context.add("a");
		context.add("b");
		context.add("r");
		List<String> expected = new ArrayList<String>();
		expected.add("b");
		expected.add("r");

		List<String> result = fixture.getContextSuffix(context);

		ListAssert.assertEquals(expected, result);
	}

	@Test
	public void testGetContextSuffix_3() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> context = new ArrayList<String>();
		context.add("a");
		context.add("a");
		context.add("b");
		context.add("x");
		List<String> expected = new ArrayList<String>();

		List<String> result = fixture.getContextSuffix(context);

		ListAssert.assertEquals(expected, result);
	}

	@Test
	public void testGetContextSuffix_4() throws Exception {
		Trie<String> fixture = new Trie<String>();

		List<String> result = fixture.getContextSuffix(null);

		// add additional test code here
		assertNotNull(result);
		assertEquals(0, result.size());
	}

	@Test
	public void testGetContextSuffix_5() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> context = new ArrayList<String>();
		context.add("a");
		context.add("a");
		context.add("b");
		List<String> expected = new ArrayList<String>();
		expected.add("a");
		expected.add("b");

		List<String> result = fixture.getContextSuffix(context);

		ListAssert.assertEquals(expected, result);
	}

	@Test
	public void testGetCount_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("a");

		int result = fixture.getCount(subSequence);

		assertEquals(5, result);
	}

	@Test
	public void testGetCount_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("a");
		subSequence.add("b");

		int result = fixture.getCount(subSequence);

		assertEquals(2, result);
	}

	@Test
	public void testGetCount_3() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("x");

		int result = fixture.getCount(subSequence);

		assertEquals(0, result);
	}

	@Test
	public void testGetCount_4() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();

		int result = fixture.getCount(subSequence, "a");

		assertEquals(5, result);
	}

	@Test
	public void testGetCount_5() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("a");
		subSequence.add("b");

		int result = fixture.getCount(subSequence, "r");

		assertEquals(2, result);
	}

	@Test
	public void testGetCount_6() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();

		int result = fixture.getCount(subSequence, "x");

		assertEquals(0, result);
	}

	@Test
	public void testGetFollowingSymbols_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("a");
		Collection<String> expected = new ArrayList<String>();
		expected.add("b");
		expected.add("c");
		expected.add("d");

		Collection<String> result = fixture.getFollowingSymbols(subSequence);

		assertCollectionContent(expected, result);
	}

	@Test
	public void testGetFollowingSymbols_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("a");
		subSequence.add("b");
		subSequence.add("r");

		Collection<String> result = fixture.getFollowingSymbols(subSequence);

		assertEquals(0, result.size());
	}

	@Test
	public void testGetFollowingSymbols_3() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);
		List<String> subSequence = new ArrayList<String>();
		subSequence.add("x");

		Collection<String> result = fixture.getFollowingSymbols(subSequence);

		assertEquals(0, result.size());
	}

	@Test
	public void testGetNumLeafAncestors_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);

		int result = fixture.getNumLeafAncestors();

		assertEquals(7, result);
	}

	@Test
	public void testGetNumLeafs_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);

		int result = fixture.getNumLeafs();

		assertEquals(7, result);
	}

	@Test
	public void testGetNumSymbols_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);

		int result = fixture.getNumSymbols();

		assertEquals(5, result);
	}

	@Test
	public void testTrain_1() throws Exception {
		Trie<String> fixture = new Trie<String>();
		int maxOrder = 3;

		fixture.train(sequence, maxOrder);

		// check if symbols are correct
		assertCollectionContent(symbols, fixture.getKnownSymbols());

		// check if counters are correct and only the correct nodes exist
		TrieNode<String> root = fixture.find(new ArrayList<String>());
		TrieNode<String> root_a = root.getChild("a");
		TrieNode<String> root_a_a = root_a.getChild("a");
		TrieNode<String> root_a_b = root_a.getChild("b");
		TrieNode<String> root_a_b_a = root_a_b.getChild("a");
		TrieNode<String> root_a_b_b = root_a_b.getChild("b");
		TrieNode<String> root_a_b_c = root_a_b.getChild("c");
		TrieNode<String> root_a_b_d = root_a_b.getChild("d");
		TrieNode<String> root_a_b_r = root_a_b.getChild("r");
		TrieNode<String> root_a_c = root_a.getChild("c");
		TrieNode<String> root_a_c_a = root_a_c.getChild("a");
		TrieNode<String> root_a_c_b = root_a_c.getChild("b");
		TrieNode<String> root_a_c_c = root_a_c.getChild("c");
		TrieNode<String> root_a_c_d = root_a_c.getChild("d");
		TrieNode<String> root_a_c_r = root_a_c.getChild("r");
		TrieNode<String> root_a_d = root_a.getChild("d");
		TrieNode<String> root_a_d_a = root_a_d.getChild("a");
		TrieNode<String> root_a_d_b = root_a_d.getChild("b");
		TrieNode<String> root_a_d_c = root_a_d.getChild("c");
		TrieNode<String> root_a_d_d = root_a_d.getChild("d");
		TrieNode<String> root_a_d_r = root_a_d.getChild("r");
		TrieNode<String> root_a_r = root_a.getChild("r");
		TrieNode<String> root_b = root.getChild("b");
		TrieNode<String> root_b_a = root_b.getChild("a");
		TrieNode<String> root_b_b = root_b.getChild("b");
		TrieNode<String> root_b_c = root_b.getChild("c");
		TrieNode<String> root_b_d = root_b.getChild("d");
		TrieNode<String> root_b_r = root_b.getChild("r");
		TrieNode<String> root_b_r_a = root_b_r.getChild("a");
		TrieNode<String> root_b_r_b = root_b_r.getChild("b");
		TrieNode<String> root_b_r_c = root_b_r.getChild("c");
		TrieNode<String> root_b_r_d = root_b_r.getChild("d");
		TrieNode<String> root_b_r_r = root_b_r.getChild("r");
		TrieNode<String> root_c = root.getChild("c");
		TrieNode<String> root_c_a = root_c.getChild("a");
		TrieNode<String> root_c_a_a = root_c_a.getChild("a");
		TrieNode<String> root_c_a_b = root_c_a.getChild("b");
		TrieNode<String> root_c_a_c = root_c_a.getChild("c");
		TrieNode<String> root_c_a_d = root_c_a.getChild("d");
		TrieNode<String> root_c_a_r = root_c_a.getChild("r");
		TrieNode<String> root_c_b = root_c.getChild("b");
		TrieNode<String> root_c_c = root_c.getChild("c");
		TrieNode<String> root_c_d = root_c.getChild("d");
		TrieNode<String> root_c_r = root_c.getChild("r");
		TrieNode<String> root_d = root.getChild("d");
		TrieNode<String> root_d_a = root_d.getChild("a");
		TrieNode<String> root_d_a_a = root_d_a.getChild("a");
		TrieNode<String> root_d_a_b = root_d_a.getChild("b");
		TrieNode<String> root_d_a_c = root_d_a.getChild("c");
		TrieNode<String> root_d_a_d = root_d_a.getChild("d");
		TrieNode<String> root_d_a_r = root_d_a.getChild("r");
		TrieNode<String> root_d_b = root_d.getChild("b");
		TrieNode<String> root_d_c = root_d.getChild("c");
		TrieNode<String> root_d_d = root_d.getChild("d");
		TrieNode<String> root_d_r = root_d.getChild("r");
		TrieNode<String> root_r = root.getChild("r");
		TrieNode<String> root_r_a = root_r.getChild("a");
		TrieNode<String> root_r_a_a = root_r_a.getChild("a");
		TrieNode<String> root_r_a_b = root_r_a.getChild("b");
		TrieNode<String> root_r_a_c = root_r_a.getChild("c");
		TrieNode<String> root_r_a_d = root_r_a.getChild("d");
		TrieNode<String> root_r_a_r = root_r_a.getChild("r");
		TrieNode<String> root_r_b = root_r.getChild("b");
		TrieNode<String> root_r_c = root_r.getChild("c");
		TrieNode<String> root_r_d = root_r.getChild("d");
		TrieNode<String> root_r_r = root_r.getChild("r");

		assertEquals(5, root_a.getCount());
		assertNull(root_a_a);
		assertEquals(2, root_a_b.getCount());
		assertNull(root_a_b_a);
		assertNull(root_a_b_b);
		assertNull(root_a_b_c);
		assertNull(root_a_b_d);
		assertEquals(2, root_a_b_r.getCount());
		assertEquals(1, root_a_c.getCount());
		assertEquals(1, root_a_c_a.getCount());
		assertNull(root_a_c_b);
		assertNull(root_a_c_c);
		assertNull(root_a_c_d);
		assertNull(root_a_c_r);
		assertEquals(1, root_a_d.getCount());
		assertEquals(1, root_a_d_a.getCount());
		assertNull(root_a_d_b);
		assertNull(root_a_d_c);
		assertNull(root_a_d_d);
		assertNull(root_a_d_r);
		assertNull(root_a_r);

		assertEquals(2, root_b.getCount());
		assertNull(root_b_a);
		assertNull(root_b_b);
		assertNull(root_b_c);
		assertNull(root_b_d);
		assertEquals(2, root_b_r.getCount());
		assertEquals(2, root_b_r_a.getCount());
		assertNull(root_b_r_b);
		assertNull(root_b_r_c);
		assertNull(root_b_r_d);
		assertNull(root_b_r_r);

		assertEquals(1, root_c.getCount());
		assertEquals(1, root_c_a.getCount());
		assertNull(root_c_a_a);
		assertNull(root_c_a_b);
		assertNull(root_c_a_c);
		assertEquals(1, root_c_a_d.getCount());
		assertNull(root_c_a_r);
		assertNull(root_c_b);
		assertNull(root_c_c);
		assertNull(root_c_d);
		assertNull(root_c_r);

		assertEquals(1, root_d.getCount());
		assertEquals(1, root_d_a.getCount());
		assertNull(root_d_a_a);
		assertEquals(1, root_d_a_b.getCount());
		assertNull(root_d_a_c);
		assertNull(root_d_a_d);
		assertNull(root_d_a_r);
		assertNull(root_d_b);
		assertNull(root_d_c);
		assertNull(root_d_d);
		assertNull(root_d_r);

		assertEquals(2, root_r.getCount());
		assertEquals(2, root_r_a.getCount());
		assertNull(root_r_a_a);
		assertNull(root_r_a_b);
		assertEquals(1, root_r_a_c.getCount());
		assertNull(root_r_a_d);
		assertNull(root_r_a_r);
		assertNull(root_r_b);
		assertNull(root_r_c);
		assertNull(root_r_d);
		assertNull(root_r_r);

		// check if leafs are really leafs
		assertTrue(root_a_b_r.isLeaf());
		assertTrue(root_a_c_a.isLeaf());
		assertTrue(root_a_d_a.isLeaf());
		assertTrue(root_b_r_a.isLeaf());
		assertTrue(root_c_a_d.isLeaf());
		assertTrue(root_d_a_b.isLeaf());
		assertTrue(root_r_a_c.isLeaf());
	}

	@Test
	public void testTrain_2() throws Exception {
		Trie<String> fixture = new Trie<String>();
		int maxOrder = 0;

		fixture.train(sequence, maxOrder);

		assertTrue(fixture.getKnownSymbols().isEmpty());
	}

	@Test
	public void testTrain_3() throws Exception {
		Trie<Object> fixture = new Trie<Object>();
		List<Object> sequence = new ArrayList<Object>();
		int maxOrder = 1;

		fixture.train(sequence, maxOrder);

		assertTrue(fixture.getKnownSymbols().isEmpty());
	}

	@Test
	public void testTrain_4() throws Exception {
		Trie<String> fixture = new Trie<String>();
		List<String> sequence = new ArrayList<String>();
		sequence.add("a");
		sequence.add("b");
		int maxOrder = 3;

		fixture.train(sequence, maxOrder);

		assertCollectionContent(sequence, fixture.getKnownSymbols());
		TrieNode<String> root = fixture.find(new ArrayList<String>());
		TrieNode<String> root_a = root.getChild("a");
		TrieNode<String> root_a_a = root_a.getChild("a");
		TrieNode<String> root_a_b = root_a.getChild("b");
		TrieNode<String> root_b = root.getChild("b");
		TrieNode<String> root_b_a = root_b.getChild("a");
		TrieNode<String> root_b_b = root_b.getChild("b");

		assertEquals(1, root_a.getCount());
		assertNull(root_a_a);
		assertEquals(1, root_a_b.getCount());
		assertEquals(1, root_b.getCount());
		assertNull(root_b_a);
		assertNull(root_b_b);

		assertTrue(root_a_b.isLeaf());
		assertTrue(root_b.isLeaf());
	}

	@Test
	public void testEdgeEdge_1() throws Exception {
		Edge result = new Edge();

		assertNotNull(result);
	}

	@Test
	public void testTrieVertexTrieVertex_1() throws Exception {
		String id = "idString";

		TrieVertex result = new TrieVertex(id);

		assertNotNull(result);
	}

	@Test
	public void testTrieVertexToString_1() throws Exception {
		String id = "idString";
		TrieVertex fixture = new TrieVertex(id);

		String result = fixture.toString();

		assertEquals(id, result);
	}

	@Test
	public void testEquals_1() throws Exception {
		Trie<String> trieOther = new Trie<String>();
		Trie<String> fixture = new Trie<String>();

		boolean result = fixture.equals(trieOther);

		assertEquals(true, result);
	}

	@Test
	public void testEquals_2() throws Exception {
		Trie<String> trieOther = new Trie<String>();
		trieOther.train(sequence, 2);
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 2);

		boolean result = fixture.equals(trieOther);

		assertEquals(true, result);
	}

	@Test
	public void testEquals_3() throws Exception {
		Trie<String> trieOther = new Trie<String>();
		trieOther.train(sequence, 2);
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 3);

		boolean result = fixture.equals(trieOther);

		assertEquals(false, result);
	}

	@Test
	public void testEquals_4() throws Exception {
		Trie<String> trieOther = new Trie<String>();
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 2);

		boolean result = fixture.equals(trieOther);

		assertEquals(false, result);
	}

	@Test
	public void testEquals_5() throws Exception {
		Trie<String> trieOther = new Trie<String>();
		trieOther.train(sequence, 2);
		Trie<String> fixture = new Trie<String>();

		boolean result = fixture.equals(trieOther);

		assertEquals(false, result);
	}

	@Test
	public void testEquals_6() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 2);

		boolean result = fixture.equals(fixture);

		assertEquals(true, result);
	}

	@Test
	public void testEquals_7() throws Exception {
		Trie<String> fixture = new Trie<String>();
		fixture.train(sequence, 2);

		boolean result = fixture.equals(null);

		assertEquals(false, result);
	}

	@Before
	public void setUp() throws Exception {
		sequence = new ArrayList<String>();
		sequence.add("a");
		sequence.add("b");
		sequence.add("r");
		sequence.add("a");
		sequence.add("c");
		sequence.add("a");
		sequence.add("d");
		sequence.add("a");
		sequence.add("b");
		sequence.add("r");
		sequence.add("a");

		symbols = new HashSet<String>();
		symbols.add("a");
		symbols.add("b");
		symbols.add("c");
		symbols.add("d");
		symbols.add("r");
	}

	public static void main(String[] args) {
		new org.junit.runner.JUnitCore().run(TrieTest.class);
	}
}