Skip to content
a character trie data structure backed by
C Other Makefile
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.


Type Name Latest commit message Commit time
Failed to load latest commit information.

Build Status


Algorithm::Trie::libdatrie - a character keyed trie using the datrie library.


use Algorithm::Trie::libdatrie;

my Trie $t .= new: 'a'..'z', 'A'..'Z';
my @words = <pool prize preview prepare produce progress>;
for @words.kv -> $data, $word {
  $ $word, $data );
$data = $t.retrieve($word);
my $iter = $t.iterator;
while $ {
  $key = $iter.key;
  $data = $iter.value;


More documentation and maybe a few more features and tests are planned. For now the tests are probably the best documentation.


Algorithm::Trie::libdatrie is an implementation of a character keyed trie using the datrie library.

As the author of the datrie library states:

Trie is a kind of digital search tree, an efficient indexing method with O(1) time complexity for searching. Comparably as efficient as hashing, trie also provides flexibility on incremental matching and key spelling manipulation. This makes it ideal for lexical analyzers, as well as spelling dictionaries. This library is an implementation of double-array structure for representing trie, as proposed by Junichi Aoe. The details of the implementation can be found at

Classes and Methods


multi method new(**@ranges) returns Trie
multi method new(Str $file) returns Trie
method save(Str $file) returns Bool
method is-dirty() returns Bool
method store(Str $key, Int $data) returns Bool
method store-if-absent(Str $key, Int $data) returns Bool
method retrieve(Str $key) returns Int
method delete(Str $key) returns Bool
method root() returns TrieState
method iterator() returns TrieIterator
method free()
/* NYI
sub enum_func(Str $key, Int $value, Pointer[void] $stash) returns Bool { * }
method enumerate(&enum_func, Pointer[void] $stash) returns Bool
  • new

    my Trie $t .= new: 'a'..'z', 'A'..'Z', '0'..'9';

The set of characters used in keys has a maximum size of 255. The characters themselves may be any unicode character who's code will fit in a 32 bit uint. The new function will map the input ranges into 0..254 internally.

my Trie $t .= new: $file;

A Trie may be loaded from a $file created by the save method.

  • root, iterator

These methods return objects of class TrieState and TrieIterator that are positioned at the root of the Trie.

  • the rest

Should be mostly self-explanatory. See the tests.


A TrieState object is used to walk through the Trie character by character. A TrieState object may also be used to create a TrieIterator in order to iterate over the nodes beneath the TrieStat's current position.

method clone() returns TrieState
method rewind()
method walk(Str $c where *.chars == 1) returns Bool
method is-walkable(Str $c where *.chars == 1) returns Bool
method walkable-chars() returns Array[Str]
method is-terminal() returns Bool
method is-single() returns Bool
method is-leaf() returns Bool
method value() returns Int
method free()


A TrieIterator can be created from the Trie directly via $trie.iterator or from a TrieState via$trie-state).

method new(TrieState $state) returns TrieIterator
method next() returns Bool
method key() returns Str
method value() returns Int
method free()


The datrie library:

Wikipedia entry for: Trie




Copyright 2015 zengargoyle

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.

You can’t perform that action at this time.