itrie

Description:

itrie

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
💡 How to use

Constructors
Iterable
Mutations (Immutable)
Getters


🛠️ Properties

Immutable
Stack safe
(Space) Efficient


📃 Versioning
😀 Support
👀 License

💻 Installation #
# pubspec.yaml
dependencies:
itrie: ^0.0.1
copied to clipboard
💡 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)]);
copied to clipboard
Iterable #
ITrie extends Iterable.
This means that you have access to all the methods
available in the Iterable API:

map
fold
every
iterator
And more 🚀

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"]);
copied to clipboard

🧱 ITrie is immutable
These methods return a new copy of the original ITrie
without modifying the original ITrie

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");
copied to clipboard
🛠️ 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);
copied to clipboard

✅ Immutability in ITrie uses a technique called Path copying: this makes ITrie 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.