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

💡 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:

• 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"]);

🧱 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");

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