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 TrieTest
contains tests for the class {@link Trie}
.
*
* @author Steffen Herbold
* @version 1.0
*/
public class TrieTest {
List sequence;
Collection 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 result = new Trie();
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 fixture = new Trie();
List seq = new ArrayList();
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 fixture = new Trie();
fixture.add(new ArrayList());
assertEquals(0, fixture.getNumSymbols());
}
@Test
public void testAdd_3()
throws Exception {
Trie fixture = new Trie();
fixture.add(null);
assertEquals(0, fixture.getNumSymbols());
}
@Test
public void testFind_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List findSequence = new ArrayList();
findSequence.add("a");
findSequence.add("b");
findSequence.add("r");
TrieNode expected = fixture.getChild("a").getChild("b").getChild("r");
TrieNode result = fixture.find(findSequence);
assertEquals(expected, result);
}
@Test
public void testFind_2()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List findSequence = new ArrayList();
findSequence.add("c");
findSequence.add("a");
TrieNode expected = fixture.getChild("c").getChild("a");
TrieNode result = fixture.find(findSequence);
assertEquals(expected, result);
}
@Test
public void testFind_3()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List findSequence = new ArrayList();
TrieNode result = fixture.find(findSequence);
assertTrue(result.isRoot());
}
@Test
public void testFind_4()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
TrieNode result = fixture.find(null);
assertTrue(result.isRoot());
}
@Test
public void testGetChildCreate_1()
throws Exception {
Trie fixture = new Trie();
String symbol = "a";
TrieNode 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 fixture = new Trie();
fixture.getChildCreate(null);
}
@Test
public void testGetContextSuffix_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List context = new ArrayList();
context.add("a");
context.add("a");
context.add("b");
List expected = new ArrayList();
expected.add("a");
expected.add("b");
List result = fixture.getContextSuffix(context);
ListAssert.assertEquals(expected, result);
}
@Test
public void testGetContextSuffix_2()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List context = new ArrayList();
context.add("a");
context.add("a");
context.add("b");
context.add("r");
List expected = new ArrayList();
expected.add("b");
expected.add("r");
List result = fixture.getContextSuffix(context);
ListAssert.assertEquals(expected, result);
}
@Test
public void testGetContextSuffix_3()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List context = new ArrayList();
context.add("a");
context.add("a");
context.add("b");
context.add("x");
List expected = new ArrayList();
List result = fixture.getContextSuffix(context);
ListAssert.assertEquals(expected, result);
}
@Test
public void testGetContextSuffix_4()
throws Exception {
Trie fixture = new Trie();
List result = fixture.getContextSuffix(null);
// add additional test code here
assertNotNull(result);
assertEquals(0, result.size());
}
@Test
public void testGetContextSuffix_5()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List context = new ArrayList();
context.add("a");
context.add("a");
context.add("b");
List expected = new ArrayList();
expected.add("a");
expected.add("b");
List result = fixture.getContextSuffix(context);
ListAssert.assertEquals(expected, result);
}
@Test
public void testGetCount_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("a");
int result = fixture.getCount(subSequence);
assertEquals(5, result);
}
@Test
public void testGetCount_2()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("a");
subSequence.add("b");
int result = fixture.getCount(subSequence);
assertEquals(2, result);
}
@Test
public void testGetCount_3()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("x");
int result = fixture.getCount(subSequence);
assertEquals(0, result);
}
@Test
public void testGetCount_4()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
int result = fixture.getCount(subSequence, "a");
assertEquals(5, result);
}
@Test
public void testGetCount_5()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("a");
subSequence.add("b");
int result = fixture.getCount(subSequence, "r");
assertEquals(2, result);
}
@Test
public void testGetCount_6()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
int result = fixture.getCount(subSequence, "x");
assertEquals(0, result);
}
@Test
public void testGetFollowingSymbols_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("a");
Collection expected = new ArrayList();
expected.add("b");
expected.add("c");
expected.add("d");
Collection result = fixture.getFollowingSymbols(subSequence);
assertCollectionContent(expected, result);
}
@Test
public void testGetFollowingSymbols_2()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("a");
subSequence.add("b");
subSequence.add("r");
Collection result = fixture.getFollowingSymbols(subSequence);
assertEquals(0, result.size());
}
@Test
public void testGetFollowingSymbols_3()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List subSequence = new ArrayList();
subSequence.add("x");
Collection result = fixture.getFollowingSymbols(subSequence);
assertEquals(0, result.size());
}
@Test
public void testGetNumLeafAncestors_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
int result = fixture.getNumLeafAncestors();
assertEquals(7, result);
}
@Test
public void testGetNumLeafs_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
int result = fixture.getNumLeafs();
assertEquals(7, result);
}
@Test
public void testGetNumSymbols_1()
throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
int result = fixture.getNumSymbols();
assertEquals(5, result);
}
@Test
public void testTrain_1()
throws Exception {
Trie fixture = new Trie();
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 root = fixture.find(new ArrayList());
TrieNode root_a = root.getChild("a");
TrieNode root_a_a = root_a.getChild("a");
TrieNode root_a_b = root_a.getChild("b");
TrieNode root_a_b_a = root_a_b.getChild("a");
TrieNode root_a_b_b = root_a_b.getChild("b");
TrieNode root_a_b_c = root_a_b.getChild("c");
TrieNode root_a_b_d = root_a_b.getChild("d");
TrieNode root_a_b_r = root_a_b.getChild("r");
TrieNode root_a_c = root_a.getChild("c");
TrieNode root_a_c_a = root_a_c.getChild("a");
TrieNode root_a_c_b = root_a_c.getChild("b");
TrieNode root_a_c_c = root_a_c.getChild("c");
TrieNode root_a_c_d = root_a_c.getChild("d");
TrieNode root_a_c_r = root_a_c.getChild("r");
TrieNode root_a_d = root_a.getChild("d");
TrieNode root_a_d_a = root_a_d.getChild("a");
TrieNode root_a_d_b = root_a_d.getChild("b");
TrieNode root_a_d_c = root_a_d.getChild("c");
TrieNode root_a_d_d = root_a_d.getChild("d");
TrieNode root_a_d_r = root_a_d.getChild("r");
TrieNode root_a_r = root_a.getChild("r");
TrieNode root_b = root.getChild("b");
TrieNode root_b_a = root_b.getChild("a");
TrieNode root_b_b = root_b.getChild("b");
TrieNode root_b_c = root_b.getChild("c");
TrieNode root_b_d = root_b.getChild("d");
TrieNode root_b_r = root_b.getChild("r");
TrieNode root_b_r_a = root_b_r.getChild("a");
TrieNode root_b_r_b = root_b_r.getChild("b");
TrieNode root_b_r_c = root_b_r.getChild("c");
TrieNode root_b_r_d = root_b_r.getChild("d");
TrieNode root_b_r_r = root_b_r.getChild("r");
TrieNode root_c = root.getChild("c");
TrieNode root_c_a = root_c.getChild("a");
TrieNode root_c_a_a = root_c_a.getChild("a");
TrieNode root_c_a_b = root_c_a.getChild("b");
TrieNode root_c_a_c = root_c_a.getChild("c");
TrieNode root_c_a_d = root_c_a.getChild("d");
TrieNode root_c_a_r = root_c_a.getChild("r");
TrieNode root_c_b = root_c.getChild("b");
TrieNode root_c_c = root_c.getChild("c");
TrieNode root_c_d = root_c.getChild("d");
TrieNode root_c_r = root_c.getChild("r");
TrieNode root_d = root.getChild("d");
TrieNode root_d_a = root_d.getChild("a");
TrieNode root_d_a_a = root_d_a.getChild("a");
TrieNode root_d_a_b = root_d_a.getChild("b");
TrieNode root_d_a_c = root_d_a.getChild("c");
TrieNode root_d_a_d = root_d_a.getChild("d");
TrieNode root_d_a_r = root_d_a.getChild("r");
TrieNode root_d_b = root_d.getChild("b");
TrieNode root_d_c = root_d.getChild("c");
TrieNode root_d_d = root_d.getChild("d");
TrieNode root_d_r = root_d.getChild("r");
TrieNode root_r = root.getChild("r");
TrieNode root_r_a = root_r.getChild("a");
TrieNode root_r_a_a = root_r_a.getChild("a");
TrieNode root_r_a_b = root_r_a.getChild("b");
TrieNode root_r_a_c = root_r_a.getChild("c");
TrieNode root_r_a_d = root_r_a.getChild("d");
TrieNode root_r_a_r = root_r_a.getChild("r");
TrieNode root_r_b = root_r.getChild("b");
TrieNode root_r_c = root_r.getChild("c");
TrieNode root_r_d = root_r.getChild("d");
TrieNode 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 fixture = new Trie();
int maxOrder = 0;
fixture.train(sequence, maxOrder);
assertTrue(fixture.getKnownSymbols().isEmpty());
}
@Test
public void testTrain_3()
throws Exception {
Trie