// Copyright 2012 Georg-August-Universität Göttingen, Germany
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package de.ugoe.cs.autoquest.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.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.eventcore.StringEventType;
import de.ugoe.cs.autoquest.usageprofiles.MockTrieBasedModel;
import de.ugoe.cs.autoquest.usageprofiles.Trie;
import de.ugoe.cs.autoquest.usageprofiles.TrieBasedModel;
import de.ugoe.cs.autoquest.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(new StringEventType("a")));
TrieNode root_a_a = root_a.getChild(new Event(new StringEventType("a")));
TrieNode root_a_b = root_a.getChild(new Event(new StringEventType("b")));
TrieNode root_a_b_a = root_a_b
.getChild(new Event(new StringEventType("a")));
TrieNode root_a_b_b = root_a_b
.getChild(new Event(new StringEventType("b")));
TrieNode root_a_b_c = root_a_b
.getChild(new Event(new StringEventType("c")));
TrieNode root_a_b_d = root_a_b
.getChild(new Event(new StringEventType("d")));
TrieNode root_a_b_r = root_a_b
.getChild(new Event(new StringEventType("r")));
TrieNode root_a_c = root_a.getChild(new Event(new StringEventType("c")));
TrieNode root_a_c_a = root_a_c
.getChild(new Event(new StringEventType("a")));
TrieNode root_a_c_b = root_a_c
.getChild(new Event(new StringEventType("b")));
TrieNode root_a_c_c = root_a_c
.getChild(new Event(new StringEventType("c")));
TrieNode root_a_c_d = root_a_c
.getChild(new Event(new StringEventType("d")));
TrieNode root_a_c_r = root_a_c
.getChild(new Event(new StringEventType("r")));
TrieNode root_a_d = root_a.getChild(new Event(new StringEventType("d")));
TrieNode root_a_d_a = root_a_d
.getChild(new Event(new StringEventType("a")));
TrieNode root_a_d_b = root_a_d
.getChild(new Event(new StringEventType("b")));
TrieNode root_a_d_c = root_a_d
.getChild(new Event(new StringEventType("c")));
TrieNode root_a_d_d = root_a_d
.getChild(new Event(new StringEventType("d")));
TrieNode root_a_d_r = root_a_d
.getChild(new Event(new StringEventType("r")));
TrieNode root_a_r = root_a.getChild(new Event(new StringEventType("r")));
TrieNode root_b = root.getChild(new Event(new StringEventType("b")));
TrieNode root_b_a = root_b.getChild(new Event(new StringEventType("a")));
TrieNode root_b_b = root_b.getChild(new Event(new StringEventType("b")));
TrieNode root_b_c = root_b.getChild(new Event(new StringEventType("c")));
TrieNode root_b_d = root_b.getChild(new Event(new StringEventType("d")));
TrieNode root_b_r = root_b.getChild(new Event(new StringEventType("r")));
TrieNode root_b_r_a = root_b_r
.getChild(new Event(new StringEventType("a")));
TrieNode root_b_r_b = root_b_r
.getChild(new Event(new StringEventType("b")));
TrieNode root_b_r_c = root_b_r
.getChild(new Event(new StringEventType("c")));
TrieNode root_b_r_d = root_b_r
.getChild(new Event(new StringEventType("d")));
TrieNode root_b_r_r = root_b_r
.getChild(new Event(new StringEventType("r")));
TrieNode root_c = root.getChild(new Event(new StringEventType("c")));
TrieNode root_c_a = root_c.getChild(new Event(new StringEventType("a")));
TrieNode root_c_a_a = root_c_a
.getChild(new Event(new StringEventType("a")));
TrieNode root_c_a_b = root_c_a
.getChild(new Event(new StringEventType("b")));
TrieNode root_c_a_c = root_c_a
.getChild(new Event(new StringEventType("c")));
TrieNode root_c_a_d = root_c_a
.getChild(new Event(new StringEventType("d")));
TrieNode root_c_a_r = root_c_a
.getChild(new Event(new StringEventType("r")));
TrieNode root_c_b = root_c.getChild(new Event(new StringEventType("b")));
TrieNode root_c_c = root_c.getChild(new Event(new StringEventType("c")));
TrieNode root_c_d = root_c.getChild(new Event(new StringEventType("d")));
TrieNode root_c_r = root_c.getChild(new Event(new StringEventType("r")));
TrieNode root_d = root.getChild(new Event(new StringEventType("d")));
TrieNode root_d_a = root_d.getChild(new Event(new StringEventType("a")));
TrieNode root_d_a_a = root_d_a
.getChild(new Event(new StringEventType("a")));
TrieNode root_d_a_b = root_d_a
.getChild(new Event(new StringEventType("b")));
TrieNode root_d_a_c = root_d_a
.getChild(new Event(new StringEventType("c")));
TrieNode root_d_a_d = root_d_a
.getChild(new Event(new StringEventType("d")));
TrieNode root_d_a_r = root_d_a
.getChild(new Event(new StringEventType("r")));
TrieNode root_d_b = root_d.getChild(new Event(new StringEventType("b")));
TrieNode root_d_c = root_d.getChild(new Event(new StringEventType("c")));
TrieNode root_d_d = root_d.getChild(new Event(new StringEventType("d")));
TrieNode root_d_r = root_d.getChild(new Event(new StringEventType("r")));
TrieNode root_r = root.getChild(new Event(new StringEventType("r")));
TrieNode root_r_a = root_r.getChild(new Event(new StringEventType("a")));
TrieNode root_r_a_a = root_r_a
.getChild(new Event(new StringEventType("a")));
TrieNode root_r_a_b = root_r_a
.getChild(new Event(new StringEventType("b")));
TrieNode root_r_a_c = root_r_a
.getChild(new Event(new StringEventType("c")));
TrieNode root_r_a_d = root_r_a
.getChild(new Event(new StringEventType("d")));
TrieNode root_r_a_r = root_r_a
.getChild(new Event(new StringEventType("r")));
TrieNode root_r_a_end = root_r_a.getChild(Event.ENDEVENT);
TrieNode root_r_b = root_r.getChild(new Event(new StringEventType("b")));
TrieNode root_r_c = root_r.getChild(new Event(new StringEventType("c")));
TrieNode root_r_d = root_r.getChild(new Event(new StringEventType("d")));
TrieNode root_r_r = root_r.getChild(new Event(new StringEventType("r")));
TrieNode root_start = root.getChild(Event.STARTEVENT);
TrieNode root_start_a = root_start
.getChild(new Event(new StringEventType("a")));
TrieNode root_start_a_a = root_start_a
.getChild(new Event(new StringEventType("a")));
TrieNode root_start_a_b = root_start_a
.getChild(new Event(new StringEventType("b")));
TrieNode root_start_a_c = root_start_a
.getChild(new Event(new StringEventType("c")));
TrieNode root_start_a_d = root_start_a
.getChild(new Event(new StringEventType("d")));
TrieNode root_start_a_r = root_start_a
.getChild(new Event(new StringEventType("r")));
TrieNode root_start_b = root_start
.getChild(new Event(new StringEventType("b")));
TrieNode root_start_c = root_start
.getChild(new Event(new StringEventType("c")));
TrieNode root_start_d = root_start
.getChild(new Event(new StringEventType("d")));
TrieNode root_start_r = root_start
.getChild(new Event(new StringEventType("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.lang.IllegalArgumentException.class)
public void testTrieBasedModel_2() throws Exception {
int markovOrder = -1;
Random r = new Random();
new MockTrieBasedModel(markovOrder, r);
}
@Test(expected = java.lang.IllegalArgumentException.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(new StringEventType("a")));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("b")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("c")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("d")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("b")));
list.add(new Event(new StringEventType("r")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("c")));
list.add(new Event(new StringEventType("a")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("d")));
list.add(new Event(new StringEventType("a")));
expected.add(list);
list = new ArrayList();
list.add(new Event(new StringEventType("r")));
list.add(new Event(new StringEventType("a")));
expected.add(list);
list = new ArrayList();
list.add(Event.STARTEVENT);
list.add(new Event(new StringEventType("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(new StringEventType("a")));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList();
list.add(Event.STARTEVENT);
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("b")));
expected.add(list);
list = new ArrayList();
list.add(Event.STARTEVENT);
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("c")));
expected.add(list);
list = new ArrayList();
list.add(Event.STARTEVENT);
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("d")));
expected.add(list);
Collection> result = fixture
.generateSequences(length, true);
assertCollectionContent(expected, result);
}
@Test(expected = java.lang.IllegalArgumentException.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(new StringEventType("a")));
list.add(new Event(new StringEventType("c")));
list.add(new Event(new StringEventType("a")));
list.add(Event.ENDEVENT);
expected.add(list);
list = new ArrayList();
list.add(Event.STARTEVENT);
list.add(new Event(new StringEventType("a")));
list.add(new Event(new StringEventType("d")));
list.add(new Event(new StringEventType("a")));
list.add(Event.ENDEVENT);
expected.add(list);
Collection> result = fixture
.generateValidSequences(length);
assertCollectionContent(expected, result);
}
@Test(expected = java.lang.IllegalArgumentException.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 result = fixture.getEvents();
assertCollectionContent(symbols, result);
}
@Test
public void testGetEvents_2() throws Exception {
int markovOrder = 2;
MockTrieBasedModel fixture = new MockTrieBasedModel(markovOrder,
new Random());
Collection 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.lang.IllegalArgumentException.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.lang.IllegalArgumentException.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(new StringEventType("a")));
sequence.add(new Event(new StringEventType("b")));
sequence.add(new Event(new StringEventType("r")));
sequence.add(new Event(new StringEventType("a")));
sequence.add(new Event(new StringEventType("c")));
sequence.add(new Event(new StringEventType("a")));
sequence.add(new Event(new StringEventType("d")));
sequence.add(new Event(new StringEventType("a")));
sequence.add(new Event(new StringEventType("b")));
sequence.add(new Event(new StringEventType("r")));
sequence.add(new Event(new StringEventType("a")));
symbols = new HashSet();
symbols.add(new Event(new StringEventType("a")));
symbols.add(new Event(new StringEventType("b")));
symbols.add(new Event(new StringEventType("c")));
symbols.add(new Event(new StringEventType("d")));
symbols.add(new Event(new StringEventType("r")));
symbols.add(Event.STARTEVENT);
symbols.add(Event.ENDEVENT);
}
public static void main(String[] args) {
new org.junit.runner.JUnitCore().run(TrieBasedModelTest.class);
}
}