Skip to content

Instantly share code, notes, and snippets.

@ajs
Created November 3, 2016 17:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ajs/094bed75488a8450747f0e53cd50c1dd to your computer and use it in GitHub Desktop.
Save ajs/094bed75488a8450747f0e53cd50c1dd to your computer and use it in GitHub Desktop.
A Trie in perl 6 that can generate a sequence of pairs representing the shortest unique prefix over a set of input words
class ArgTrie is Hash {
# A simple Trie that builds a tree from input words (command-line arguments)
# and can generate a list of unique prefixes mapped to the full words.
has $.count is rw = 0;
method gist() { "\{ count={self.count.gist} {self.pairs.gist} \}" }
method insert(Str $word) {
my $letter = $word.substr(0,1);
self.{$letter} = ArgTrie.new if $letter.chars and not self.{$letter}:exists;
self.{$letter}.insert($word.substr(1)) if $word.chars > 0;
self.count++;
}
method unique() {
gather do {
for self.pairs -> $pair {
for $pair.value.unique -> $u {
take (self.count > 1 ?? $pair.key ~ $u.key !! '') => ($pair.key ~ $u.value);
}
}
if self.count > [+] self.values.map: {.count} {
take '' => '';
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment