ternarytreap 1.0.6

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

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

1.0.0 #

  • Initial version, created by Stagehand

1.0.1 #

  • Updated docs

1.0.2 #

  • Changed meta dependancy to cooperate with flutter_test

1.0.3 #

  • Updated doc links

1.0.4 #

  • Added new KeyMappings

1.0.5 #

  • Changed to multimap style interface

1.0.6 #

  • Fixed lint errors

example/README.md

Example #

A command line app is in example/bin:

  • Demonstrates the key -> data relationship using different key transforms.
  • Shows how to add a custom data type containing title, description and timestamp.
  • Shows how the [TernaryTreap] is built and balanced.

Usage: #

dart main.dart <KeyMapping> <preload>

KeyMapping Options: #

  • 0 - No key transform
  • 1 - Lowercase key transform
  • 2 - Collapse whitespace key transform
  • 3 - Lowercase and Collapse whitespace key transform

Preload #

The 'preload' option causes a list of words to be loaded at start to play with query function etc.

Examples: #

  • dart main.dart 0
  • dart main.dart 1
  • dart main.dart 2
  • dart main.dart 2 preload

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  ternarytreap: ^1.0.6

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

Alternatively, your editor might support pub get or flutter pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:ternarytreap/ternarytreap.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
0
Health:
Code health derived from static analysis. [more]
100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
100
Overall:
Weighted score of the above. [more]
50
Learn more about scoring.

We analyzed this package on Feb 12, 2020, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.7.1
  • pana: 0.13.5

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.5.0 <3.0.0
meta ^1.1.7 1.1.8
Dev dependencies
pedantic ^1.9.0
test ^1.6.0