package de.ugoe.cs.eventbench.models;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import de.ugoe.cs.eventbench.data.Event;
import org.junit.*;
import static org.junit.Assert.*;
/**
* The class TrieBasedModelTest
contains tests for the class {@link TrieBasedModel}
.
*
* @author Steffen Herbold
* @version 1.0
*/
public class TrieBasedModelTest {
List> sequence;
Collection> symbols;
private void assertTrieStructure(Trie> trie, int numSequences) {
TrieNode> root = trie.find(null);
TrieNode> root_a = root.getChild(new Event("a"));
TrieNode> root_a_a = root_a.getChild(new Event("a"));
TrieNode> root_a_b = root_a.getChild(new Event("b"));
TrieNode> root_a_b_a = root_a_b.getChild(new Event("a"));
TrieNode> root_a_b_b = root_a_b.getChild(new Event("b"));
TrieNode> root_a_b_c = root_a_b.getChild(new Event("c"));
TrieNode> root_a_b_d = root_a_b.getChild(new Event("d"));
TrieNode> root_a_b_r = root_a_b.getChild(new Event("r"));
TrieNode> root_a_c = root_a.getChild(new Event("c"));
TrieNode> root_a_c_a = root_a_c.getChild(new Event("a"));
TrieNode> root_a_c_b = root_a_c.getChild(new Event("b"));
TrieNode> root_a_c_c = root_a_c.getChild(new Event("c"));
TrieNode> root_a_c_d = root_a_c.getChild(new Event("d"));
TrieNode> root_a_c_r = root_a_c.getChild(new Event("r"));
TrieNode> root_a_d = root_a.getChild(new Event("d"));
TrieNode> root_a_d_a = root_a_d.getChild(new Event("a"));
TrieNode> root_a_d_b = root_a_d.getChild(new Event("b"));
TrieNode> root_a_d_c = root_a_d.getChild(new Event("c"));
TrieNode> root_a_d_d = root_a_d.getChild(new Event("d"));
TrieNode> root_a_d_r = root_a_d.getChild(new Event("r"));
TrieNode> root_a_r = root_a.getChild(new Event("r"));
TrieNode> root_b = root.getChild(new Event("b"));
TrieNode> root_b_a = root_b.getChild(new Event("a"));
TrieNode> root_b_b = root_b.getChild(new Event("b"));
TrieNode> root_b_c = root_b.getChild(new Event("c"));
TrieNode> root_b_d = root_b.getChild(new Event("d"));
TrieNode> root_b_r = root_b.getChild(new Event("r"));
TrieNode> root_b_r_a = root_b_r.getChild(new Event("a"));
TrieNode> root_b_r_b = root_b_r.getChild(new Event("b"));
TrieNode> root_b_r_c = root_b_r.getChild(new Event("c"));
TrieNode> root_b_r_d = root_b_r.getChild(new Event("d"));
TrieNode> root_b_r_r = root_b_r.getChild(new Event("r"));
TrieNode> root_c = root.getChild(new Event("c"));
TrieNode> root_c_a = root_c.getChild(new Event("a"));
TrieNode> root_c_a_a = root_c_a.getChild(new Event("a"));
TrieNode> root_c_a_b = root_c_a.getChild(new Event("b"));
TrieNode> root_c_a_c = root_c_a.getChild(new Event("c"));
TrieNode> root_c_a_d = root_c_a.getChild(new Event("d"));
TrieNode> root_c_a_r = root_c_a.getChild(new Event("r"));
TrieNode> root_c_b = root_c.getChild(new Event("b"));
TrieNode> root_c_c = root_c.getChild(new Event("c"));
TrieNode> root_c_d = root_c.getChild(new Event("d"));
TrieNode> root_c_r = root_c.getChild(new Event("r"));
TrieNode> root_d = root.getChild(new Event("d"));
TrieNode> root_d_a = root_d.getChild(new Event("a"));
TrieNode> root_d_a_a = root_d_a.getChild(new Event("a"));
TrieNode> root_d_a_b = root_d_a.getChild(new Event("b"));
TrieNode> root_d_a_c = root_d_a.getChild(new Event("c"));
TrieNode> root_d_a_d = root_d_a.getChild(new Event("d"));
TrieNode> root_d_a_r = root_d_a.getChild(new Event("r"));
TrieNode> root_d_b = root_d.getChild(new Event("b"));
TrieNode> root_d_c = root_d.getChild(new Event("c"));
TrieNode> root_d_d = root_d.getChild(new Event("d"));
TrieNode> root_d_r = root_d.getChild(new Event("r"));
TrieNode> root_r = root.getChild(new Event("r"));
TrieNode> root_r_a = root_r.getChild(new Event("a"));
TrieNode> root_r_a_a = root_r_a.getChild(new Event("a"));
TrieNode> root_r_a_b = root_r_a.getChild(new Event("b"));
TrieNode> root_r_a_c = root_r_a.getChild(new Event("c"));
TrieNode> root_r_a_d = root_r_a.getChild(new Event("d"));
TrieNode> root_r_a_r = root_r_a.getChild(new Event("r"));
TrieNode> root_r_a_end = root_r_a.getChild(Event.ENDEVENT);
TrieNode> root_r_b = root_r.getChild(new Event("b"));
TrieNode> root_r_c = root_r.getChild(new Event("c"));
TrieNode> root_r_d = root_r.getChild(new Event("d"));
TrieNode> root_r_r = root_r.getChild(new Event("r"));
TrieNode> root_start = root.getChild(Event.STARTEVENT);
TrieNode> root_start_a = root_start.getChild(new Event("a"));
TrieNode> root_start_a_a = root_start_a.getChild(new Event("a"));
TrieNode> root_start_a_b = root_start_a.getChild(new Event("b"));
TrieNode> root_start_a_c = root_start_a.getChild(new Event("c"));
TrieNode> root_start_a_d = root_start_a.getChild(new Event("d"));
TrieNode> root_start_a_r = root_start_a.getChild(new Event("r"));
TrieNode> root_start_b = root_start.getChild(new Event("b"));
TrieNode> root_start_c = root_start.getChild(new Event("c"));
TrieNode> root_start_d = root_start.getChild(new Event("d"));
TrieNode> root_start_r = root_start.getChild(new Event("r"));
assertEquals(numSequences*5, root_a.getCount());
assertNull(root_a_a);
assertEquals(numSequences*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(numSequences*2, root_a_b_r.getCount());
assertEquals(numSequences*1, root_a_c.getCount());
assertEquals(numSequences*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(numSequences*1, root_a_d.getCount());
assertEquals(numSequences*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(numSequences*2, root_b.getCount());
assertNull(root_b_a);
assertNull(root_b_b);
assertNull(root_b_c);
assertNull(root_b_d);
assertEquals(numSequences*2, root_b_r.getCount());
assertEquals(numSequences*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(numSequences*1, root_c.getCount());
assertEquals(numSequences*1, root_c_a.getCount());
assertNull(root_c_a_a);
assertNull(root_c_a_b);
assertNull(root_c_a_c);
assertEquals(numSequences*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(numSequences*1, root_d.getCount());
assertEquals(numSequences*1, root_d_a.getCount());
assertNull(root_d_a_a);
assertEquals(numSequences*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(numSequences*2, root_r.getCount());
assertEquals(numSequences*2, root_r_a.getCount());
assertNull(root_r_a_a);
assertNull(root_r_a_b);
assertEquals(numSequences*1, root_r_a_c.getCount());
assertNull(root_r_a_d);
assertNull(root_r_a_r);
assertEquals(numSequences*1, root_r_a_end.getCount());
assertNull(root_r_b);
assertNull(root_r_c);
assertNull(root_r_d);
assertNull(root_r_r);
assertEquals(numSequences*1, root_start.getCount());
assertEquals(numSequences*1, root_start_a.getCount());
assertNull(root_start_a_a);
assertEquals(numSequences*1, root_start_a_b.getCount());
assertNull(root_start_a_c);
assertNull(root_start_a_d);
assertNull(root_start_a_r);
assertNull(root_start_b);
assertNull(root_start_c);
assertNull(root_start_d);
assertNull(root_start_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());
assertTrue(root_r_a_end.isLeaf());
}
private static void assertCollectionContent(Collection> c1, Collection> c2) {
assertEquals(c1.size(), c2.size());
for( Object obj : c1 ) {
assertTrue(c2.contains(obj));
}
}
@Test
public void testGenerateSequences_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int length = 2;
Collection>> expected = new HashSet>>();
ArrayList> list;
list = new ArrayList>();
list.add(new Event("a"));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList>();
list.add(new Event("a"));
list.add(new Event("b"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("a"));
list.add(new Event("c"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("a"));
list.add(new Event("d"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("b"));
list.add(new Event("r"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("c"));
list.add(new Event("a"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("d"));
list.add(new Event("a"));
expected.add(list);
list = new ArrayList>();
list.add(new Event("r"));
list.add(new Event("a"));
expected.add(list);
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
expected.add(list);
Collection>> result = fixture.generateSequences(length);
assertCollectionContent(expected, result);
}
@Test
public void testGenerateSequences_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int length = 3;
Collection>> expected = new HashSet>>();
ArrayList> list;
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(new Event("b"));
expected.add(list);
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(new Event("c"));
expected.add(list);
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(new Event("d"));
expected.add(list);
Collection>> result = fixture.generateSequences(length, true);
assertCollectionContent(expected, result);
}
@Test( expected = java.security.InvalidParameterException.class )
public void testGenerateSequences_3()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int length = 0;
fixture.generateSequences(length, false);
}
@Test
public void testGenerateValidSequences_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int length = 5;
Collection>> expected = new HashSet>>();
ArrayList> list;
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(new Event("c"));
list.add(new Event("a"));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList>();
list.add(Event.STARTEVENT);
list.add(new Event("a"));
list.add(new Event("d"));
list.add(new Event("a"));
list.add(Event.ENDEVENT);
expected.add(list);
Collection>> result = fixture.generateValidSequences(length);
assertCollectionContent(expected, result);
}
@Test(expected = java.security.InvalidParameterException.class )
public void testGenerateValidSequences_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int length = 0;
fixture.generateValidSequences(length);
}
@Test
public void testGetEvents_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
Collection extends Event>> result = fixture.getEvents();
assertCollectionContent(symbols, result);
}
@Test
public void testGetEvents_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection extends Event>> result = fixture.getEvents();
assertCollectionContent(new HashSet>(), result);
}
@Test
public void testGetNumFOMStates_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int result = fixture.getNumFOMStates();
assertEquals(10, result);
}
@Test
public void testGetNumFOMStates_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());;
int result = fixture.getNumFOMStates();
assertEquals(0, result);
}
@Test
public void testGetNumSymbols_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int result = fixture.getNumSymbols();
assertEquals(7, result);
}
@Test
public void testGetNumSymbols_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
int result = fixture.getNumSymbols();
assertEquals(0, result);
}
@Test
public void testGetNumTransitions_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
int result = fixture.getNumTransitions();
assertEquals(11, result);
}
@Test
public void testGetNumTransitions_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
int result = fixture.getNumTransitions();
assertEquals(0, result);
}
@Test
public void testTrain_1 ()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
assertCollectionContent(symbols, fixture.getEvents());
assertTrieStructure(fixture.trie, 1); }
@Test
public void testTrain_2 ()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
sequences.add(sequence);
fixture.train(sequences);
assertCollectionContent(symbols, fixture.getEvents());
assertTrieStructure(fixture.trie, 2);
}
@Test
public void testUpdate_1()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = new ArrayList>>();
sequences.add(sequence);
fixture.train(sequences);
fixture.update(sequences);
assertCollectionContent(symbols, fixture.getEvents());
assertTrieStructure(fixture.trie, 2);
}
@Test
public void testUpdate_2()
throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder, new Random());
Collection>> sequences = null;
fixture.trie = null;
fixture.update(sequences);
assertNull(fixture.trie);
}
@Before
public void setUp()
throws Exception {
sequence = new ArrayList>();
sequence.add(new Event("a"));
sequence.add(new Event("b"));
sequence.add(new Event("r"));
sequence.add(new Event("a"));
sequence.add(new Event("c"));
sequence.add(new Event("a"));
sequence.add(new Event("d"));
sequence.add(new Event("a"));
sequence.add(new Event("b"));
sequence.add(new Event("r"));
sequence.add(new Event("a"));
symbols = new HashSet>();
symbols.add(new Event("a"));
symbols.add(new Event("b"));
symbols.add(new Event("c"));
symbols.add(new Event