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]);
Entries with keys starting with 'z'
print(ttMultimapList.keysByPrefix('z'));
print(ttMultimapList.entriesByKeyPrefix('z'));
print(ttMultimapList.valuesByKeyPrefix('z'));
(zebra, zonkey)
(MapEntry(zebra: [23, 23, 24, 24, 25]), MapEntry(zonkey: []))
(23, 23, 24, 24, 25)
Same data using Set for value storage. Repeated values are removed.
final ttMultimapSet =
ternarytreap.TTMultiMapSet<int>.from(ttMultimapList);
Entries with keys starting with 'z' with values.
print(ttMultimapSet.entriesByKeyPrefix('z'));
(MapEntry(zebra: {23, 24, 25}), MapEntry(zonkey: {}))
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(', '));
cow, chicken, crocodile, canary, cat, dog, donkey, goat, hawk, horse, zonkey
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);
(cat, dog, testing)
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'));
(MapEntry(cat: {Cat, cAt}), MapEntry(dog: {DOG, dog}), MapEntry(testing: {TeStInG, testinG}))
(Cat, cAt)
Features and bugs
Please file feature requests and bugs at the issue tracker.
Libraries
- 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