// 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 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 testGetSequencesWithMostOccurrences_1() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur most often
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 0);
assertEquals(1, result.size());
List expected = new ArrayList();
expected.add("a");
ListAssert.assertEquals(expected, result.iterator().next());
}
@Test
public void testGetSequencesWithMostOccurrences_2() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur exactly once
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 1);
assertEquals(11, result.size());
List expected = new ArrayList();
expected.add("r");
expected.add("a");
expected.add("c");
// rac
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("c");
// ac
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// aca
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("c");
// c
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// ca
ListAssert.assertContains((List>) result, expected);
expected.add("d");
// cad
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("d");
// ad
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// ada
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("d");
// d
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// da
ListAssert.assertContains((List>) result, expected);
expected.add("b");
// dab
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_3() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur exactly twice
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 2);
assertEquals(7, result.size());
List expected = new ArrayList();
expected.add("a");
expected.add("b");
// ab
ListAssert.assertContains((List>) result, expected);
expected.add("r");
// abr
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("b");
// b
ListAssert.assertContains((List>) result, expected);
expected.add("r");
// br
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// bra
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("r");
// r
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// ra
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_4() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur exactly three times
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 3);
assertEquals(0, result.size());
}
@Test
public void testGetSequencesWithMostOccurrences_5() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur exactly four times
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 4);
assertEquals(0, result.size());
}
@Test
public void testGetSequencesWithMostOccurrences_6() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of one that occur exactly five times
Collection> result = fixture.getSequencesWithOccurrenceCount(1, 5);
assertEquals(1, result.size());
List expected = new ArrayList();
expected.add("a");
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_7() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of two that occur most often
Collection> result = fixture.getSequencesWithOccurrenceCount(2, 0);
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_8() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of two that occur exactly once
Collection> result = fixture.getSequencesWithOccurrenceCount(2, 1);
assertEquals(9, result.size());
List expected = new ArrayList();
expected.add("r");
expected.add("a");
expected.add("c");
// rac
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("c");
// ac
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// aca
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("c");
expected.add("a");
// ca
ListAssert.assertContains((List>) result, expected);
expected.add("d");
// cad
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("d");
// ad
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// ada
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("d");
expected.add("a");
// da
ListAssert.assertContains((List>) result, expected);
expected.add("b");
// dab
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_9() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of two that occur exactly twice
Collection> result = fixture.getSequencesWithOccurrenceCount(2, 2);
assertEquals(5, result.size());
List expected = new ArrayList();
expected.add("a");
expected.add("b");
// ab
ListAssert.assertContains((List>) result, expected);
expected.add("r");
// abr
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("b");
expected.add("r");
// br
ListAssert.assertContains((List>) result, expected);
expected.add("a");
// bra
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("r");
expected.add("a");
// ra
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_10() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of two that occur exactly three times
Collection> result = fixture.getSequencesWithOccurrenceCount(2, 3);
assertEquals(0, result.size());
}
@Test
public void testGetSequencesWithMostOccurrences_11() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of three that occur most often
Collection> result = fixture.getSequencesWithOccurrenceCount(3, 0);
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_12() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of three that occur exactly once
Collection> result = fixture.getSequencesWithOccurrenceCount(3, 1);
assertEquals(5, result.size());
List expected = new ArrayList();
expected.add("r");
expected.add("a");
expected.add("c");
// rac
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("c");
expected.add("a");
// aca
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("c");
expected.add("a");
expected.add("d");
// cad
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("a");
expected.add("d");
expected.add("a");
// ada
ListAssert.assertContains((List>) result, expected);
expected.clear();
expected.add("d");
expected.add("a");
expected.add("b");
// dab
ListAssert.assertContains((List>) result, expected);
}
@Test
public void testGetSequencesWithMostOccurrences_13() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of four that occur most often
Collection> result = fixture.getSequencesWithOccurrenceCount(4, 0);
// none of these exist, as the tree is only trained with sequences of length 3
assertEquals(0, result.size());
}
@Test
public void testGetSequencesWithMostOccurrences_14() throws Exception {
Trie fixture = new Trie();
fixture.train(sequence, 3);
// get all sequences with a minimal length of four that occur exactly once
Collection> result = fixture.getSequencesWithOccurrenceCount(4, 1);
// none of these exist, as the tree is only trained with sequences of length 3
assertEquals(0, result.size());
}
@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