package de.ugoe.cs.eventbench.models;

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

import junitx.framework.ListAssert;

import org.junit.*;
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 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("a");
		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());
	}

	@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");
	}

	@After
	public void tearDown()
		throws Exception {
		// Add additional tear down code here
	}

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