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.