ternarytreap 1.0.7

  • Readme
  • Changelog
  • Example
  • Installing
  • 60

TernaryTreap #

This library defines 2 Multimaps and a Set implemented as self balancing compact ternary trees allowing fast, memory efficient prefix and near neighbour searching over a set of String keys

  • TTMultiMapSet - Keys map to Set of Values
  • TTMultiMapList - Keys map to Sequence of Values
  • TTSet - A Set of Strings

Balancing is achieved via Treap algorithm where each node is assigned a random priority and tree rotation used to maintain heap ordering.

Usage #

Use as a generic multimap of arbitrary type. Key->Values relations are stored as either Set or List as below.

 final ttMultimapList = ternarytreap.TTMultiMapList<int>()
   ..add('zebra')
   ..addValues('zebra', [])
   ..add('zebra', 23)
   ..addValues('cat', [1, 2])
   ..addValues('canary', [3, 4])
   ..addValues('dog', [5, 6, 7, 9])
   ..addValues('cow', [4])
   ..addValues('donkey', [7, 5, 1])
   ..addValues('donkey', [6, 8, 3])
   ..add('goat', 7)
   ..add('pig', 3)
   ..addValues('horse', [9, 5, 8])
   ..add('rabbit')
   ..addValues('rat', [2, 3])
   ..add('sheep', 7)
   ..addValues('ape', [5, 6, 7])
   ..add('zonkey') // Yes it's a thing!
   ..add('dingo', 5)
   ..addValues('kangaroo', [4, 5, 7])
   ..add('chicken')
   ..add('hawk')
   ..add('crocodile', 5)
   ..addValues('cow', [3])
   ..addValues('zebra', [23, 24, 24, 25]);

Entries with keys starting with 'z'

 print(ttMultimapList.keysByPrefix('z'));
 print(ttMultimapList.entriesByKeyPrefix('z'));
 print(ttMultimapList.valuesByKeyPrefix('z'));
 (zebra, zonkey)
 (MapEntry(zebra: [23, 23, 24, 24, 25]), MapEntry(zonkey: []))
 (23, 23, 24, 24, 25)

Same data using Set for value storage. Repeated values are removed.

 final ttMultimapSet =
          ternarytreap.TTMultiMapSet<int>.from(ttMultimapList);

Entries with keys starting with 'z' with values.

 print(ttMultimapSet.entriesByKeyPrefix('z'));
 (MapEntry(zebra: {23, 24, 25}), MapEntry(zonkey: {}))

Near neighbour searching #

TTMultiMap supports near neighbour searching. Keys starting with 'cow' and maxPrefixEditDistance of 2. i.e.: cow, chicken, crocodile, canary, cat, dog, donkey, goat, hawk, horse, zonkey

 print(ttMultimapSet.keysByPrefix('cow', maxPrefixEditDistance: 2).join(', '));
 cow, chicken, crocodile, canary, cat, dog, donkey, goat, hawk, horse, zonkey

Case sensitivity and other key transformations #

Use key mappings to specify key transforms during all operations.

 final ttMultiMap = ternarytreap.TTMultiMapSet<String>(ternarytreap.lowercase)
   ..addKeys(['TeStInG', 'Cat', 'cAt', 'testinG', 'DOG', 'dog']);
 print(ttMultiMap.keys);
 (cat, dog, testing)

Depending on the KeyMapping this may result in 1 to many relationships between input string and key.

For example case insensitivity can be achieved by applying a lowercase mapping to all keys. If original strings are required than these must be stored as values.

 final keyValue = ternarytreap.TTMultiMapSet<String>(ternarytreap.lowercase)
   ..addKeyValues(['TeStInG', 'Cat', 'cAt', 'testinG', 'DOG', 'dog']);
 print(keyValue.entries);
 print(keyValue.valuesByKeyPrefix('CA'));
 (MapEntry(cat: {Cat, cAt}), MapEntry(dog: {DOG, dog}), MapEntry(testing: {TeStInG, testinG}))
 (Cat, cAt)

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

1.0.7 #

  • Added distance searching

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

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 11, 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
collection ^1.14.12 1.14.12
meta ^1.1.7 1.1.8
Dev dependencies
pedantic ^1.9.0
test ^1.6.0