// 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 junitx.framework.ListAssert;
import org.junit.*;
import de.ugoe.cs.autoquest.usageprofiles.Trie;
import de.ugoe.cs.autoquest.usageprofiles.TrieNode;
import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge;
import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex;
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 testTrie_2() throws Exception {
Trie trie1 = new Trie();
trie1.train(sequence, 3);
Trie result = new Trie(trie1);
assertEquals(trie1, result);
assertNotSame(trie1, result);
}
@Test(expected = java.lang.IllegalArgumentException.class)
public void testTrie_3() throws Exception {
new Trie((SymbolComparator) null);
}
@Test(expected = java.lang.IllegalArgumentException.class)
public void testTrie_4() throws Exception {
new Trie((Trie) null);
}
@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.lang.IllegalArgumentException.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 testGetSequencesWithMostOccurrences_1() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
List expected = new ArrayList();
expected.add("a");
Collection> result = fixture.getSequencesWithMostOccurrences(1);
assertEquals(1, result.size());
ListAssert.assertEquals(expected, result.iterator().next());
}
@Test
public void testGetSequencesWithMostOccurrences_2() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
Collection> result = fixture.getSequencesWithMostOccurrences(2);
assertEquals(5, result.size());
List expected = new ArrayList();
expected.add("a");
expected.add("b");
ListAssert.assertContains((List>) result, expected);
expected.add("r");
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("b");
expected.add("r");
ListAssert.assertContains((List>) result, expected);
expected.add("a");
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("r");
expected.add("a");
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_3() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
Collection> result = fixture.getSequencesWithMostOccurrences(3);
assertEquals(2, result.size());
List expected = new ArrayList();
expected.add("a");
expected.add("b");
expected.add("r");
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("b");
expected.add("r");
expected.add("a");
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_4() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
Collection> result = fixture.getSequencesWithMostOccurrences(4);
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