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