ternarytreap 1.0.5 ternarytreap: ^1.0.5 copied to clipboard
Self balancing ternary tree. Optimised for autocompletion tasks. A generic Map with fast prefix searching on keys.
TL;DR #
For simple prefix matching within a set of strings use: PrefixMatcher with appropriate KeyMapping.
final PrefixMatcher matcher = PrefixMatcher(TernaryTreap.lowerCollapse)
..addAll(['cat', 'Cat', 'CAT', 'CanaRy', 'CANARY']);
print(matcher.match('can'));
(CanaRy, CANARY)
TernaryTreap #
This library defines 2 Multimaps implemented as self balancing ternary trees allowing fast, memory efficient prefix searching over a set of String keys
- TernaryTreapSet - Keys map to Set of Values
- TernaryTreapList - Keys map to Sequence of Values
Balancing is achieved via Treap algorithm where each node is assigned a random priority and tree rotation used to maintain heap ordering.
Specification #
TernaryTreap Set and List multimaps are functions:
- f : K ↦ ℘ (V)
- g : K ↦ Vℕ ∪ 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.
This is achieved via a KeyMapping, defined as the surjection:
- m : K↠ L ⊆ 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 keys.
-
m(x) = lowercase(x). Convert keys to lowercase.
TernaryTreap Multimaps are composite functions with KeyMapping parameter m.
- TernaryTreapSetm(x) = f ∘ m(x)
- TernaryTreapListm(x) = g ∘ m(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('zebra')
..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
Some common KeyMapping
options are supplied such as:
Create your own easily.
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}
Features and bugs #
Please file feature requests and bugs at the issue tracker.