TernaryTreap<V> class

A self balancing Ternary search tree.

Specification

TernaryTreapSet and TernaryTreapList multimaps are functions:

  • f : K ↦ ℘ (V)
  • g : KV ∪ V

such that

  • K is the set of all Keys
  • V is the set of all Values
  • ℕ is the set of Natural numbers
  • ℘ (V) is the powerset of V
  • V is the set of all functions ℕ ↦ V
  • V contains the empty function ∅ ↦ V

The codomain of f and g include the empty set and empty sequence respectively. This allows Keys to be stored without Values, useful when you require only a set of Keys for prefix searching purposes.

Often it is desirable to define equivalences between Key strings, for example case insensitivity.

For example the key 'it' may map to 'IT', 'It' or 'it'.

This is achieved via a KeyMapping, defined as the surjection:

  • m : KL ⊆ K

such that:

  • m(m(x)) = m(x), i.e. m must be idempotent, repeated applications do not change the result.

For example:

  • m(x) = x : Default identity function, preserve all input keys.
  • m(x) = lowercase(x) : Convert keys to lowercase.

TernaryTreap Multimaps are composite functions with KeyMapping parameter m.

  • TernaryTreapSetm(x) = fm(x)
  • TernaryTreapListm(x) = gm(x)

Usage

Most basic case

Insert keys and later return those starting with a given prefix.

void  main(List<String> args) {

final  TernaryTreap<String> ternaryTreap = TernaryTreapSet<String>()
..add('cat')
..add('Canary')
..add('dog')
..add('zebr
..add('CAT');

print(ternaryTreap.keys);
(CAT, Canary, cat, dog, zebra)
print(ternaryTreap.keysByPrefix('ca'));
(cat)
print(ternaryTreap.toString());
-CAT
Canary
cat
dog
zebra

Case insensitivity and other key mappings

The above example matches strings exactly, i.e. keysByPrefix('ca') returns 'cat' but not 'CAT'. This is because the default identity KeyMapping: m(x) = x is used. This can be overridden by specifying a KeyMapping during construction. For example to achieve case insensitivity:

import  'package:ternarytreap/ternarytreap.dart';
void  main(List<String> args) {
final  TernaryTreap<String> ternaryTreap =
TernaryTreapSet<String>(TernaryTreap.lowercase)
..add('cat')
..add('Canary')
..add('dog')
..add('zebra')
..add('CAT');
}

print(ternaryTreap.keys);
(canary, cat, dog, zebra)
print(ternaryTreap.keysByPrefix('ca'));
(canary, cat)
print(ternaryTreap.toString());
canary
cat
dog
zebra

Attaching String Data to Retain Key->Input Mapping

When a KeyMapping such as lowercase maps multiple inputs to the same key the original input strings are lost. In the example below this results in input strings 'CAT' and 'Cat' being lost.

final  TernaryTreap<String> ternaryTreap =
TernaryTreapSet<String>(TernaryTreap.lowercase)
..add('cat')
..add('Cat')
..add('CAT');
print(ternaryTreap.keysByPrefix('ca'));
(cat)

To retain the original string you may attach it as a Value during insertion. These strings may now be recovered during subsequent queries.

import  'package:ternarytreap/ternarytreap.dart';
void  main(List<String> args) {
final  TernaryTreap<String> ternaryTreap =
TernaryTreap<String>(TernaryTreap.lowercase)
..add('cat', 'cat')
..add('Cat', 'Cat')
..add('CAT', 'CAT')
..add('CanaRy', 'CanaRy')
..add('CANARY', 'CANARY');
}
print(ternaryTreap.keys);
(canary, cat)
print(ternaryTreap.keysByPrefix('ca'));
(canary, cat)
print(ternaryTreap.values);
(canary, CanaRy, CANARY, cat, Cat, CAT)
print(ternaryTreap.valuesByKeyPrefix('cat'));
(cat, Cat, CAT)
print(ternaryTreap.toString());
canary
CanaRy
CANARY
cat
cat
Cat
CAT

Attaching Complex data Types

Sometimes it is useful to associate input strings with more complex datatypes. For example the following datatype stores an 'Animal' with name, description and a timestamp

import  'package:ternarytreap/ternarytreap.dart';

// An example of a data object, takes a name and description,
// and adds a timestamp.
class  Animal {
Animal(this.name, this.description)
: timestamp = DateTime.now().millisecondsSinceEpoch.toString();

// name - will be set to original input string pre KeyMapping
final  String name;

final  String description;

final  String timestamp;

Return String value.

@returns String repesenting object.
@override
String  toString() => <String, dynamic>{
'name': name,
'description': description,
'timestamp': timestamp,
}.toString();
}

void  main(List<String> args) {
final  TernaryTreap<Animal> ternaryTreap =
TernaryTreap<Animal>(TernaryTreap.lowerCollapse)
..add('Cat', Animal('Cat', 'Purrs'))
..add('Canary', Animal('Canary', 'Yellow'))
..add('Dog', Animal('Dog', 'Friend'))
..add('Zebra', Animal('Zebra', 'Stripes'))
..add('CAT', Animal('CAT', 'Scan'));
print(ternaryTreap.keys);
(canary, cat, dog, zebra)
print(ternaryTreap.keysByPrefix('ca'));
(canary, cat)
print(ternaryTreap.values);
({name: Canary, description: Yellow, timestamp: 1574730578753},
{name: Cat, description: Purrs, timestamp: 1574730578735},
{name: CAT, description: Scan, timestamp: 1574730578754},
{name: Dog, description: Friend, timestamp: 1574730578754},
{name: Zebra, description: Stripes, timestamp: 1574730578754})
print(ternaryTreap.valuesByKeyPrefix('ca'));
({name: Canary, description: Yellow, timestamp: 1574730578753},
{name: Cat, description: Purrs, timestamp: 1574730578735},
{name: CAT, description: Scan, timestamp: 1574730578754})
print(ternaryTreap.toString());
canary
{name: Canary, description: Yellow, timestamp: 1574730578753}
cat
{name: Cat, description: Purrs, timestamp: 1574730578735}
{name: CAT, description: Scan, timestamp: 1574730578754}
dog
{name: Dog, description: Friend, timestamp: 1574730578754}
zebra
{name: Zebra, description: Stripes, timestamp: 1574730578754}

Structure

A TernaryTreap is a tree of Nodes.

               +---+   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.
+-+-+          +-+-+
  |            |P 8+-------------+
+-+-+          +-+-+             |
| N |            |             +-+-+
+---+            |             |T 2|
         +------+++------+     +-+-+
         | Value | Value |       |
         +------+-+------+       |
                             +---+---+
                             | Value |
                             +-------+

Each Node stores:

  • A character Node.codeUnit such that Ternary Tree invarient is maintained.
  • An integer priority value Node.priority such that Treap invarient:
(Node.left.priority > Node.priority) &&
(Node.right.priority > Node.priority)

is maintained.

Constructors

TernaryTreap()

Properties

depth → int
The maximum node depth of the TernaryTreap. [...]
read-only
entries → Iterable<MapEntry<String, Iterable<V>>>
Iterates through TernaryTreap as MapEntry objects. [...]
read-only
isEmpty → bool
Returns true if there are no keys in the TernaryTreap.
read-only
isNotEmpty → bool
Returns true if there is at least one key in the TernaryTreap.
read-only
keys → Iterable<String>
Return Iterable view of keys
read-only
length → int
The number of keys in the TernaryTreap.
read-only
values → Iterable<V>
Return Iterable view of values [...]
read-only
hashCode → int
The hash code for this object.
read-only, inherited
runtimeType → Type
A representation of the runtime type of the object.
read-only, inherited

Methods

add(String key, [V value]) → void
Insert a key and optional value. [...]
addAll(TernaryTreap<V> other) → void
Adds all associations of other to this TernaryTreap. [...]
addValues(String key, Iterable<V> values) → void
Add all values to specified key [...]
asMap() → Map<String, Iterable<V>>
Return a view of this TernaryTreap as a Map
clear() → void
Removes all data from the TernaryTreap.
contains(Object key, Object value) → bool
Returns whether this TernaryTreap contains an association between [key[] and value.
containsKey(Object key) → bool
Returns whether this TernaryTreap contains key.
containsValue(Object value) → bool
Returns whether this TernaryTreap contains value at least once.
entriesByKeyPrefix(String prefix) → Iterable<MapEntry<String, Iterable<V>>>
Iterates through TernaryTreap as MapEntry objects such that only keys prefixed by mapKey(prefix) are included. [...]
forEach(void f(String key, V value)) → void
Applies f to each key/value pair of the TernaryTreap [...]
forEachKey(void f(String key, Iterable<V> values)) → void
Applies f to each key/value pair of the TernaryTreap where key matches specified key. [...]
forEachKeyPrefixedBy(String prefix, void f(String key, Iterable<V> values)) → void
Applies f to each key/value pair of the TernaryTreap where key is prefixed by prefix (after KeyMapping applied). [...]
keysByPrefix(String prefix) → Iterable<String>
Returns Iterable collection of each key of the TernaryTreap where key is prefixed by mapKey(prefix). [...]
mapKey(String key) → String
Return key transformed by any KeyMapping specified during construction. [...]
remove(Object key, V value) → bool
Removes the association between the given key and value. [...]
removeKey(Object key) → Iterable<V>
Removes key and all associated values. [...]
removeValues(Object key) → Iterable<V>
Removes all values associated with key. [...]
toString([String paddingChar = '-']) → String
Generate a string representation of this TernaryTreap. Requires that values be json encodable. [...]
valuesByKeyPrefix(String prefix) → Iterable<V>
Return Iterable view of values where key is prefixed by mapKey(prefix). [...]
noSuchMethod(Invocation invocation) → dynamic
Invoked when a non-existent method or property is accessed.
inherited

Operators

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

Static Methods

collapseWhitespace(String str) → String
Transform str such that: [...]
joinSingleLetters(String str) → String
Transform str such that adjacent single Letters separated by whitespace are joined together. For example: [...]
lowercase(String str) → String
Transform str such that all characters are lowercase. [...]
lowerCollapse(String str) → String
Transform str with both lowercase and collapseWhitespace. [...]
nonLetterToSpace(String str) → String
Transform str such that each non letter character is replaced by a space character. [...]
uppercase(String str) → String
Transform str such that all characters are uppercase. [...]