// 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); } }