ternarytreap 1.0.6

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.

• TernaryTreapSet_m(x) = f ∘ m(x)
• TernaryTreapList_m(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:

• lowerCase

• collapseWhitespace

• lowerCollapse

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.