retrieval 1.0.1 retrieval: ^1.0.1 copied to clipboard
A trie data structure Dart implementation — useful for autocomplete.
A trie data structure Dart implementation — useful for autocomplete.
Features #
- 🔍 Tries are useful for type-ahead, autocomplete and other search problems
- ⚡ Has a simple API for storing text
- 🚀 Has an API to map strings to objects to handle a variety of problems
- 🎯 This library is built in modern Dart code, with sound null-safety
- 💙 Written in pure Dart, this library is usable in all Flutter platforms
Usage #
Trie #
Example
import 'package:retrieval/trie.dart';
void main() {
final trie = Trie();
// Insert a word into trie with trie.insert().
trie.insert('crikey');
trie.insert('crocodile');
// Check for existence of words.
print(trie.has('crikey')); // true
print(trie.has('ghost')); // false
// Find matching words by prefix.
print(trie.find('cr')); // ['crocodile', 'crikey']
print(trie.find('crikey')); // ['crikey']
print(trie.find('ghost')); // []
}
API Reference
Import the Trie
class via:
import 'package:retrieval/trie.dart';
Create a new Trie
with:
final trie = Trie();
Add a word to the trie
with the insert
method:
trie.insert('crikey');
Check if a word is in the trie
with the has
method:
trie.has('crikey');
Find all words with a given prefix with the find
method:
trie.find('cr');
All words that start with 'cr'
will be returned in a list of strings.
Key-Value Trie #
While the Trie
class covers the majority of use-cases, the KeyValueTrie
class allows you to map strings to objects. When retrieving from the KeyValueTrie
, you search for string prefixes and get back the associated values.
Example
import 'package:retrieval/key_value_trie.dart';
void main() {
// Use a key-value trie to associate each word with a value.
final keyValueTrie = KeyValueTrie<String>(); // Values of type String.
keyValueTrie.insert('trophy', '🏆');
keyValueTrie.insert('train', '🚆');
// When finding matching words by prefix, the associated value is returned.
print(keyValueTrie.find('tr')); // ['🚆', '🏆']
print(keyValueTrie.find('trophy')); // ['🏆']
print(keyValueTrie.find('trie')); // []
}
API Reference
Import the KeyValueTrie
class via:
import 'package:retrieval/key_value_trie.dart';
Create a new KeyValueTrie
, declaring the type of values stored within <>
, with:
final keyValueTrie = KeyValueTrie<String>();
Add a word and its associated value to the keyValueTrie
with the insert
method:
keyValueTrie.insert('trophy', '🏆');
Check if a word is in the keyValueTrie
with the has
method:
trie.has('trophy');
Find all values associated with a word's given prefix with the find
method:
trie.find('tr');
What is a trie? #
Trie with words of
DART
,DASH
,DASHI
,DARE
andAPP
.
A trie is a search tree data structure. In this implementation, each character is a node in the trie, for example, after inserting the word DART
, nodes of D
, A
, R
and T
are created.
In the trie, words with the same prefix are in the same subtree. For example, since DART
and DASH
both have a prefix of DA
, they can be found by searching from the A
node (that's below the D
node). This property makes finding words in a trie, by prefix, easy!