ternarytreap 1.0.2

  • Readme
  • Changelog
  • Example
  • Installing
  • 60

TernaryTreap #

Self balancing ternary tree designed for:

  • Autocompletion tasks - autocompleting textboxes etc.
  • Use as a generic, fast and memory efficient collection allowing prefixed based searching.
  • Includes class PrefixMatcher which suffices for most autocomplete cases.

Usage #

TL;DR #

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

// PrefixMatcher class is optimised for matching a prefix to a set of input strings.
  final PrefixMatcher matcher = PrefixMatcher(TernaryTreap.lowerCollapse)
    ..addAll(['cat', 'Cat', 'CAT', 'CanaRy', 'CANARY']);
print(matcher.match('can'));
(CanaRy, CANARY)

For more complex usage read on.

Most basic case #

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

This is useful for implementing autocompletion text boxes etc.

void main(List<String> args) {
  final TernaryTreap<String> ternaryTreap = TernaryTreap<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.values.flatten);
(CAT, Canary, cat, dog, zebra)
print(ternaryTreap.valuesByKeyPrefix('ca').flatten);
(cat)
print(ternaryTreap.toString());
-CAT
 CAT
Canary
Canary
cat
cat
dog
dog
zebra
zebra

Case insensitivity and other key mappings #

The above example matches strings exactly, i.e. keysByPrefix('ca') returns 'cat' but not 'CAT'.

To add case insensitivity or other mappings use a KeyMapping when constructing TernaryTree.

import 'package:ternarytreap/ternarytreap.dart';

void main(List<String> args) {
  final TernaryTreap<String> ternaryTreap =
      TernaryTreap<String>(keyMapping: 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.values.flatten);
(canary, cat, dog, zebra)
print(ternaryTreap.valuesByKeyPrefix('ca').flatten);
(canary, cat)
print(ternaryTreap.toString());
canary
canary
cat
cat
dog
dog
zebra
zebra

Some common KeyMapping options are supplied such as:

Create your own easily.

Attaching String Data to Retain Key->Input Mapping #

KeyMapping functions may represent an n to 1 relation from input strings to keys.

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> ternaryTreap2 =
      TernaryTreap<String>(keyMapping: TernaryTreap.lowercase)
        ..add('cat')
        ..add('Cat')
        ..add('CAT');

  print(ternaryTreap2.valuesByKeyPrefix('ca').flatten);
(cat)

To retain the original string you may attach it as data 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>(keyMapping: 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.flatten);
(canary, CanaRy, CANARY, cat, Cat, CAT)
print(ternaryTreap.valuesByKeyPrefix('cat').flatten);
(cat, Cat, CAT)
print(ternaryTreap.toString());
canary
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 to store an 'Animal' with name, description and a timestamp the following datatype may suffice:

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

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

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]
20
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]
60
Learn more about scoring.

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

  • Dart: 2.8.4
  • pana: 0.13.9+1

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.8.0
test ^1.6.0