# TL;DR

For simple prefix matching within a set of strings use: PrefixMatcher with appropriate KeyMapping.

``````
final  PrefixMatcher matcher = PrefixMatcher(TernaryTreap.lowerCollapse)

``````
``````
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 : 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.

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 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>()

``````
``````
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)

}

``````
``````
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:

## 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)

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)

}

``````
``````
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,

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)

``````
``````
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.

## Libraries

ternarytreap
This library defines 2 Multimaps implemented as self balancing ternary trees allowing fast, memory efficient prefix searching over a set of String keys [...]