# Concurrent::Trie A lock-free trie (Text Retrieval) data structure, safe for concurrent use. ## Synopsis use Concurrent::Trie; my $trie = Concurrent::Trie.new; say $trie.contains('brie'); # False say so $trie; # False say $trie.elems; # 0 $trie.insert('brie'); say $trie.contains('brie'); # True say so $trie; # True say $trie.elems; # 1 $trie.insert('babybel'); $trie.insert('gorgonzola'); say $trie.elems; # 3 say $trie.entries(); # (gorgonzola babybel brie) say $trie.entries('b'); # (babybel brie) ## Overview A trie stores strings as a tree, with each level in the tree representing a character in the string (so the tree's maximum depth is equal to the number of characters in the longest entry). A trie is especially useful for prefix searches, where all entries with a given prefix are required, since this is obtained simply by walking the tree according to the prefix, and then visiting all nodes below that point to find entries. This is a lock-free trie. Checking if the trie contains a particular string never blocks. Iterating the entries never blocks either, and will provide a snapshot of all the entries at the time the `entries` method was called. An insertion uses optimistic concurrency control, building an updated tree and then trying to commit it. This offers a global progress bound: if one thread fails to insert, it's because another thread did a successful insert. This data structure is well suited to auto-complete style features in concurrent applications, where new entries and lookups may occur when, for example, processing web requests in parallel. ## Methods ### insert(Str $value --> Nil) Inserts the passed string value into the trie. ### contains(Str $value --> Bool) Checks if the passed string value is in the trie. Returns `True` if so, and `False` otherwise. ### entries($prefix = '' --> Seq) Returns a lazy iterator of all entries in the trie with the specified prefix. If no prefix is passed, the default is the empty prefix, meaning that a call like `$trie.entries()` will iterate all entries in the trie. The order of the results is not defined. The results will be a snapshot of what was in the trie at the point `entries` was called; additions after that point will not be in the `entries` list. ### elems(--> Int) Gets the number of entries in the trie. The data structure maintains a count, making this O(1) (as opposed to `$trie.entries.elems`, which would be O(n)). ### Bool() Returns `True` if the number of entries in the trie is non-zero, and `False` otherwise.