TTMultiMap<V> class abstract

A Multimap with prefix and near neighbour searching capability across keys.

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 keyValues = ['TeStInG', 'Cat', 'cAt', 'testinG', 'DOG', 'dog'];
final ttMultiMap = ternarytreap.TTMultiMapSet<String>.fromIterables(
     keyValues, keyValues, ternarytreap.lowercase);
print(ttMultiMap.entries);
print(ttMultiMap.valuesByKeyPrefix('CA'));

(MapEntry(cat: {Cat, cAt}), MapEntry(dog: {DOG, dog}), MapEntry(testing: {TeStInG, testinG}))
(Cat, cAt)

Implementation

A TTMultiMap is a self balancing compact ternary tree.

               +---+   Graph with 3 keys,
               | C |   each associated with
               +-+-+   different number of
                 |     value objects:
                 |
               +-+-+   CAN: no value
  +------------+U 5|   CUP: 2 value objects
  |            +-+-+   CUT: 1 value object
+-+-+            |
|A 3|            |     * Numbers represent priorities.
|N  |          +-+-+   * Non branching middle children are collapsed.
+-+-+          |P 8+-------------+
               +-+-+             |
                 |             +-+-+
                 |             |T 2|
         +------+++------+     +-+-+
         | Value | Value |       |
         +------+-+------+       |
                             +---+---+
                             | Value |
                             +-------+

Each Node stores:

A list of characters Node.runes such that Ternary Tree invarient is maintained: Node.runes.left.first < Node.runes.first & Node.runes.right.first > Node.runes.first
An integer priority value Node.priority such that Treap invarient:

(Node.left.priority < Node.priority) &&
(Node.right.priority < Node.priority)

is maintained.

Non branching middle nodes are collapsed into single node making this a compact trie.

Note: Key nodes with empty Value collections all share a common empty collection object.

Implementers

Constructors

TTMultiMap()

Properties

entries → Iterable<MapEntry<String, Iterable<V>>>: Iterates through TTMultiMap as MapEntry objects.
no setter
hashCode → int: The hash code for this object.
no setterinherited
isEmpty → bool: Returns true if there are no keys in the TTMultiMap.
no setter
isNotEmpty → bool: Returns true if there is at least one key in the TTMultiMap.
no setter
keyMapping → KeyMapping: The KeyMapping in use by this TTMultiMap. Is applied to all incoming keys.
no setter
keys → TTIterable<String>: Return Iterable view of keys
no setter
length → int: The number of keys in the TTMultiMap.
no setter
runtimeType → Type: A representation of the runtime type of the object.
no setterinherited
values → Iterable<V>: Return Iterable view of values
no setter

Methods

add(String key, V value) → bool: Insert a key and value association.
addAll(TTMultiMap<V> other) → void: Add all key/value pairs from other.
addEntries(Iterable<MapEntry<String, Iterable<V>>> entries) → void: Adds all associations contained in entries to this TTMultiMap.
addKey(String key) → bool: Add key to collection.
addKeys(Iterable<String> keys) → void: Add each key in keys.
addValues(String key, Iterable<V> values) → void: Add all values to specified key
asMap() → Map<String, Iterable<V>>: Return a view of this TTMultiMap as a Map
clear() → void: Removes all data from the TTMultiMap.
contains(String key, V value) → bool: Returns whether this TTMultiMap contains an association between keyMapping(key) and value.
containsKey(String key) → bool: Returns whether this TTMultiMap contains key.
containsValue(V value) → bool: Returns whether this TTMultiMap contains value at least once.
entriesByKeyPrefix(String prefix, {int maxPrefixEditDistance = 0}) → TTIterable<MapEntry<String, Iterable<V>>>: Iterates through TTMultiMap as MapEntry objects such that only keys prefixed by keyMapping(prefix) are included.
forEach(void f(String key, V value)) → void: Applies f to each key/value pair of the TTMultiMap
forEachKey(void f(String key, Iterable<V> values)) → void: Applies f to each key/value pair of the TTMultiMap where key matches specified key.
forEachKeyPrefixedBy(String prefix, void f(String key, Iterable<V> values), {int maxPrefixEditDistance = 0}) → void: Applies f to each key/value pair of the TTMultiMap where key is prefixed by prefix.
keysByPrefix(String prefix, {int maxPrefixEditDistance = 0}) → TTIterable<String>: Iterates through TTMultiMap keys such that only keys prefixed by keyMapping(prefix) are included.
longestCommonKeyPrefixByKeyPrefix(String prefix) → String: Find the longest common key prefix for all keys prefixed by prefix.
lookup(String key, V value) → V?: If TTMultiMap contains specified (key, value) pair then return stored value.
noSuchMethod(Invocation invocation) → dynamic: Invoked when a nonexistent method or property is accessed.
inherited
remove(String key, V value) → bool: Removes the association between the given key and value.
removeKey(String key) → Iterable<V>?: Removes key and all associated values.
removeValues(String key) → Iterable<V>?: Removes all values associated with key. The key remains present, mapped to an empty iterable.
sizeOf([int valueSizeInBytes = 0]) → int: Return approximate size of tree in bytes
toJson({bool includeValues = true, dynamic valueToEncodable(V value)}) → Map<String, dynamic>: Return Json representation of TTMultiMap.
toString({String paddingChar = '-'}) → String: Generate a string representation of this TTMultiMap.
override
valuesByKeyPrefix(String prefix, {int maxPrefixEditDistance = 0}) → TTIterable<V>: Iterates through TTMultiMap values for each key such that only keys prefixed by keyMapping(prefix) are included.

Operators

operator ==(Object other) → bool: The equality operator.
inherited
operator [](String key) → Iterable<V>?: Return Iterable of values for specified key.
operator []=(String key, Iterable<V> values) → void: Set Iterable of values corresponding to key.