ternarytreap

Description:

ternarytreap

TernaryTreap #
This library defines 2 Multimaps and a Set implemented as self balancing compact ternary trees allowing fast, memory efficient prefix and near neighbour searching over a set of String keys

TTMultiMapSet - Keys map to Set of Values
TTMultiMapList - Keys map to Sequence of Values
TTSet - A Set of Strings

Balancing is achieved via Treap algorithm where each node is assigned a random priority and tree rotation used to maintain heap ordering.
Usage #
Use as a generic multimap of arbitrary type.
Key->Values relations are stored as either Set or List as below.
final ttMultimapList = ternarytreap.TTMultiMapList<int>()
..add('zebra')
..addValues('zebra', [])
..add('zebra', 23)
..addValues('cat', [1, 2])
..addValues('canary', [3, 4])
..addValues('dog', [5, 6, 7, 9])
..addValues('cow', [4])
..addValues('donkey', [7, 5, 1])
..addValues('donkey', [6, 8, 3])
..add('goat', 7)
..add('pig', 3)
..addValues('horse', [9, 5, 8])
..add('rabbit')
..addValues('rat', [2, 3])
..add('sheep', 7)
..addValues('ape', [5, 6, 7])
..add('zonkey') // Yes it's a thing!
..add('dingo', 5)
..addValues('kangaroo', [4, 5, 7])
..add('chicken')
..add('hawk')
..add('crocodile', 5)
..addValues('cow', [3])
..addValues('zebra', [23, 24, 24, 25]);
copied to clipboard
Entries with keys starting with 'z'
print(ttMultimapList.keysByPrefix('z'));
print(ttMultimapList.entriesByKeyPrefix('z'));
print(ttMultimapList.valuesByKeyPrefix('z'));
copied to clipboard
(zebra, zonkey)
(MapEntry(zebra: [23, 23, 24, 24, 25]), MapEntry(zonkey: []))
(23, 23, 24, 24, 25)
copied to clipboard
Same data using Set for value storage. Repeated values are removed.
final ttMultimapSet =
ternarytreap.TTMultiMapSet<int>.from(ttMultimapList);
copied to clipboard
Entries with keys starting with 'z' with values.
print(ttMultimapSet.entriesByKeyPrefix('z'));
copied to clipboard
(MapEntry(zebra: {23, 24, 25}), MapEntry(zonkey: {}))
copied to clipboard
Near neighbour searching #
TTMultiMap supports near neighbour searching.
Keys starting with 'cow' and maxPrefixEditDistance of 2.
i.e.:
cow, chicken, crocodile,
canary, cat, dog,
donkey, goat, hawk,
horse, zonkey
print(ttMultimapSet.keysByPrefix('cow', maxPrefixEditDistance: 2).join(', '));
copied to clipboard
cow, chicken, crocodile, canary, cat, dog, donkey, goat, hawk, horse, zonkey

copied to clipboard
Case sensitivity and other key transformations #
Use key mappings to specify key transforms during all operations.
final ttMultiMap = ternarytreap.TTMultiMapSet<String>(ternarytreap.lowercase)
..addKeys(['TeStInG', 'Cat', 'cAt', 'testinG', 'DOG', 'dog']);
print(ttMultiMap.keys);
copied to clipboard
(cat, dog, testing)
copied to clipboard
Depending on the KeyMapping this may result in 1 to many relationships
between input string and key.
For example case insensitivity can be achieved by applying a lowercase
mapping to all keys. If original strings are required than these must
be stored as values.
final keyValue = ternarytreap.TTMultiMapSet<String>(ternarytreap.lowercase)
..addKeyValues(['TeStInG', 'Cat', 'cAt', 'testinG', 'DOG', 'dog']);
print(keyValue.entries);
print(keyValue.valuesByKeyPrefix('CA'));
copied to clipboard
(MapEntry(cat: {Cat, cAt}), MapEntry(dog: {DOG, dog}), MapEntry(testing: {TeStInG, testinG}))
(Cat, cAt)
copied to clipboard
Features and bugs #
Please file feature requests and bugs at the issue tracker.