SequenceSet

Data Structure

Sequence Set is an Apache Kahadb class. We use SequenceSet to track range of long values. It is a Linked List consisting sequence ranges.

Add 9-12 sequence

If the new sequence finds an adjacent sequence either to the first or last of the sequence value, the sequence grows. Internally it adds a sequence of value 9 and then increments the last value from 9 to 12.

Add 14-17 sequence

Since 14 > 12 (head node’s last value), it adds after the head node.

Add 4-7 sequence

Since 4 < 9 (head node’s first value), it adds before head node and replaces it as head.

Add 8-10 sequence

Adds 8 first. Since 8 is adjacent to the head node’s last value (7), it simply grows the head’s last value to 8 so head node’s sequence value becomes 4-8. Also, now it finds the next sequence adjacent to head, so the sequence grows further to 12.

Add 15-16 sequence

15 and 16 are already contained by the node 14-17 so the structure remains as it is.

Class Diagram

Unit test

    public void testSequenceSet() {
        SequenceSet sequenceSet = new SequenceSet();
        sequenceSet.add(new Sequence(9, 12));
        assertEquals(1, sequenceSet.size());

        sequenceSet.add(new Sequence(14, 17));
        assertEquals(2, sequenceSet.size());

        sequenceSet.add(new Sequence(4, 7));
        assertEquals(3, sequenceSet.size());

        sequenceSet.add(new Sequence(8, 10));
        assertEquals(2, sequenceSet.size());

        sequenceSet.add(new Sequence(15, 16));
        assertEquals(2, sequenceSet.size());
    }