package de.ugoe.cs.quest.usageprofiles;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import de.ugoe.cs.quest.eventcore.Event;
import de.ugoe.cs.quest.usageprofiles.Trie;
import de.ugoe.cs.quest.usageprofiles.TrieBasedModel;
import de.ugoe.cs.quest.usageprofiles.TrieNode;
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 testTrieBasedModel_1() throws Exception {
int markovOrder = 2;
Random r = new Random();
MockTrieBasedModel result = new MockTrieBasedModel(markovOrder, r);
assertNotNull(result);
assertEquals(markovOrder + 1, result.trieOrder);
assertEquals(r, result.r);
}
@Test(expected = java.security.InvalidParameterException.class)
public void testTrieBasedModel_2() throws Exception {
int markovOrder = -1;
Random r = new Random();
new MockTrieBasedModel(markovOrder, r);
}
@Test(expected = java.security.InvalidParameterException.class)
public void testTrieBasedModel_3() throws Exception {
int markovOrder = 2;
Random r = null;
new MockTrieBasedModel(markovOrder, r);
}
@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(expected = java.security.InvalidParameterException.class)
public void testTrain_3() throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
new Random());
Collection>> sequences = null;
fixture.train(sequences);
}
@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(expected = java.security.InvalidParameterException.class)
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);
}
@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