ITrie
Efficient, immutable and stack safe implementation of a Trie
data structure in dart.
Trie
is ideal for autocomplete, text search, spell checking, and generally when working with string and prefixes.
💻 Installation
# pubspec.yaml
dependencies:
itrie: ^0.0.1
💡 How to use
The package export a single ITrie
class.
Constructors
An ITrie
can be created from any Iterable
or using the empty
constructor:
/// Empty [ITrie] with [int] values
final empty = ITrie<int>.empty();
final copy = empty.insert("key", 10);
/// From [Iterable] containing a record of `(String, T)`
final fromIterable = ITrie.fromIterable([("key", 10)]);
Iterable
ITrie
extends Iterable
.
This means that you have access to all the methods available in the Iterable API:
Mutations (Immutable)
Methods to add/remove/modify key/value inside ITrie
:
final itrie = ITrie<int>.empty();
final insert = itrie.insert("key", 10);
final remove = itrie.remove("key");
final modify = itrie.modify("key", (value) => value + 1);
final insertMany = itrie.insertMany([("key2", 20)]);
final removeMany = itrie.removeMany(["key"]);
🧱
ITrie
is immutableThese methods return a new copy of the original
ITrie
without modifying the originalITrie
Getters
Methods to extract key/value based on key
and prefix
:
final itrie = ITrie<int>.empty();
final getV = itrie.get("key");
final longestPrefixOf = itrie.longestPrefixOf("keys");
final withPrefix = itrie.withPrefix("ke");
final keysWithPrefix = itrie.keysWithPrefix("ke");
final valuesWithPrefix = itrie.valuesWithPrefix("ke");
final keys = itrie.keys;
final values = itrie.values;
final length = itrie.length;
final has = itrie.has("key");
🛠️ Properties
Immutable
The main difference between other trie implementations is that ITrie
is immutable.
Every mutation (e.g. insert
, delete
, modify
) returns a new instance of ITrie
instead of modifying the original ITrie
in-place.
final itrie = ITrie<int>.empty();
final newITrie = itrie.insert("key", 10); /// 👈 `insert` returns a new [ITrie]
expect(itrie.length, 0); /// 👈 Original `itrie` is not modified
expect(newITrie.length, 1);
✅ Immutability in
ITrie
uses a technique called Path copying: this makesITrie
efficient since it does not require to copy the full data structure with every mutation
Stack safe
ITrie
does not use recursion. No matter how many operations or elements it contains, ITrie
will never cause stack overflow issues.
(Space) Efficient
ITrie
is implemented internally as a Ternary Search Trie. This data structure allows for any alphabet size (any String
) and it is also more space efficient compared to other trie implementations.
📃 Versioning
- v0.0.1 - 22 January 2024
😀 Support
If you are interested in my work you can subscribe to my newsletter.
For more frequent updates you can also follow me on my Twitter.
👀 License
MIT License, see the LICENSE.md file for details.