package com.googlecode.gaal.suffix.impl;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.util.Iterator;
import org.junit.Before;
import org.junit.Test;
import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.data.impl.ArraySequence;
import com.googlecode.gaal.suffix.api.IntervalTree.Interval;
import com.googlecode.gaal.suffix.api.LinearizedSuffixTree;
import com.googlecode.gaal.suffix.api.LinearizedSuffixTree.BinaryInterval;
import com.googlecode.gaal.suffix.impl.LinearizedSuffixTreeImpl;
import com.googlecode.gaal.suffix.impl.EnhancedSuffixArrayImplTest.IntervalImpl;
public class LinearizedSuffixTreeImplTest {
// caggtcagtcacggtatca#
private static final int[] text = { 2, 1, 3, 3, 4, 2, 1, 3, 4, 2, 1, 2, 3, 3, 4, 1, 4, 2, 1, 5 };
private static final String[] alphabet = { null, "a", "c", "g", "t", "#" };
private static final int[] suffixTable = { 10, 1, 6, 15, 18, 9, 0, 5, 17, 11, 12, 2, 13, 7, 3, 14, 8, 4, 16, 19 };
private static final int[] prefixTable = { 18, 1, 9, 13, 4, 19, 8, 2, 10, 14, 17, 12, 7, 16, 6, 3, 11, 15, 5, 0 };
private static final int[] sLcpTable = { -1, 1, 2, 1, 1, 0, 2, 3, 2, 1, 0, 3, 1, 2, 4, 0, 1, 3, 3, 0 };
private static final int[] pLcpTable = { -1, 2, 3, 4, 1, 0, 1, 1, 2, 3, 0, 3, 1, 1, 2, 0, 1, 2, 3, 0 };
private static final int[] sExtendedLcpTable = { 0, 6, 10, 5, 6, 2, 11, 15, 10, 5, 1, 15, 5, 10, 20, 0, 5, 16, 15,
1 };
private static final int[] pExtendedLcpTable = { 0, 10, 15, 20, 5, 2, 6, 5, 10, 15, 1, 15, 6, 5, 10, 0, 5, 10, 15,
1 };
private static final int[] sNewChildTable = { 15, 2, 1, 4, 3, 9, 7, 6, 8, 5, 12, 11, 13, 14, 10, 19, 18, 17, 16, 0 };
private static final int[] pNewChildTable = { 15, 2, 3, 1, 4, 7, 6, 8, 9, 5, 13, 11, 12, 14, 10, 19, 17, 18, 16, 0 };
private static final IntervalImpl[] preOrder = { new IntervalImpl(0, 19, 0), new IntervalImpl(0, 14, 0),
new IntervalImpl(0, 9, 0), new IntervalImpl(0, 4, 1), new IntervalImpl(0, 2, 1),
new IntervalImpl(0, 0, -1), new IntervalImpl(1, 2, 2), new IntervalImpl(1, 1, -1),
new IntervalImpl(2, 2, -1), new IntervalImpl(3, 4, 1), new IntervalImpl(3, 3, -1),
new IntervalImpl(4, 4, -1), new IntervalImpl(5, 9, 1), new IntervalImpl(5, 8, 2),
new IntervalImpl(5, 7, 2), new IntervalImpl(5, 5, -1), new IntervalImpl(6, 7, 3),
new IntervalImpl(6, 6, -1), new IntervalImpl(7, 7, -1), new IntervalImpl(8, 8, -1),
new IntervalImpl(9, 9, -1), new IntervalImpl(10, 14, 1), new IntervalImpl(10, 11, 3),
new IntervalImpl(10, 10, -1), new IntervalImpl(11, 11, -1), new IntervalImpl(12, 14, 2),
new IntervalImpl(12, 12, -1), new IntervalImpl(13, 14, 4), new IntervalImpl(13, 13, -1),
new IntervalImpl(14, 14, -1), new IntervalImpl(15, 19, 0), new IntervalImpl(15, 18, 1),
new IntervalImpl(15, 15, -1), new IntervalImpl(16, 18, 3), new IntervalImpl(16, 17, 3),
new IntervalImpl(16, 16, -1), new IntervalImpl(17, 17, -1), new IntervalImpl(18, 18, -1),
new IntervalImpl(19, 19, -1) };
private LinearizedSuffixTree lst;
private LinearizedSuffixTree lpt;
@Before
public void setUp() throws Exception {
IntSequence sequence = new ArraySequence(text);
lst = new LinearizedSuffixTreeImpl(sequence, alphabet.length - 1);
lpt = new LinearizedSuffixTreeImpl(sequence.reverse(), alphabet.length - 1);
}
@Test
public void testGetExtendedLcpTable() {
assertArrayEquals(sExtendedLcpTable, lst.getExtendedLcpTable());
assertArrayEquals(pExtendedLcpTable, lpt.getExtendedLcpTable());
}
@Test
public void testGetNewChildTable() {
assertArrayEquals(sNewChildTable, lst.getChildTable());
assertArrayEquals(pNewChildTable, lpt.getChildTable());
}
@Test
public void testGetTop() {
Interval top = lst.top();
assertTrue(top.left() == 0);
assertTrue(top.right() == text.length - 1);
assertTrue(top.lcp() == 0);
}
@Test
public void testGetSuffixTable() {
assertArrayEquals(suffixTable, lst.getSuffixTable());
assertArrayEquals(prefixTable, lpt.getSuffixTable());
}
@Test
public void testGetLcpTable() {
assertArrayEquals(sLcpTable, lst.getLcpTable());
assertArrayEquals(pLcpTable, lpt.getLcpTable());
}
@Test
public void testAlpabetSize() {
assertTrue(lst.alphabetSize() == alphabet.length - 1);
}
@Test
public void testTraversePreOrder() {
Iterator<BinaryInterval> iterator = lst.preorderIterator();
int i = 0;
while (iterator.hasNext()) {
Interval node = iterator.next();
IntervalImpl ref = preOrder[i++];
if (!ref.equals(node)) {
System.err.println(ref + " != " + node);
fail("node mismatch");
} else {
System.out.println(ref + " == " + node);
}
}
assertTrue(i == preOrder.length);
}
@Test
public void testSearch() {
IntSequence pattern;
Interval interval;
pattern = new ArraySequence(new int[] { 3, 4 });
interval = lst.search(pattern);
System.out.printf("%s\t->%s\n", interval, interval.label());
assertTrue(seqEquals(interval.label(), pattern));
pattern = new ArraySequence(new int[] { 3, 4, 2, 1 });
interval = lst.search(pattern);
System.out.printf("%s\t->%s\n", interval, interval.label());
assertTrue(seqEquals(interval.label(), pattern));
pattern = new ArraySequence(new int[] { 3, 4, 1 });
interval = lst.search(pattern);
assertNull(interval);
}
@Test
public void testLongestSearch() {
int[] patternToFind = { 2, 1, 4 };
int[] expectedArray = {2, 1};
IntSequence pattern = new ArraySequence(patternToFind);
IntSequence expected = new ArraySequence(expectedArray);
System.out.println("Looking for : " + pattern);
System.out.println("Expected: " + expected);
Interval result = lst.longestSearch(pattern);
System.out.println("Longest found: " + result.label());
assertEquals(expected, result.label());
}
private boolean seqEquals(IntSequence sequence, IntSequence other) {
if (sequence.size() != other.size())
return false;
for (int i = 0; i < sequence.size(); i++) {
if (sequence.get(i) != other.get(i))
return false;
}
return true;
}
}