Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Go

Idiom #159 Trie

Define a Trie data structure, where entries have an associated value.
(Not all nodes are entries)

type Trie struct {
	c        rune
	children map[rune]*Trie
	isEntry  bool
	value    V
}

Using type rune, multi-byte characters are correctly handled.
V is the type of the associated values.
struct Trie
{
    Rune c;
    Trie*[Rune] children;
    bool isEntry;
    bool value;
}
New implementation...
< > ⌨
programming-idioms.org 
type Trie struct {
	c        rune
	children map[rune]*Trie
	isEntry  bool
	value    V
}
struct Trie
{
    Rune c;
    Trie*[Rune] children;
    bool isEntry;
    bool value;
}
  type trie_p
     type(trie), pointer :: p => NULL()
  end type trie_p
  type trie
     class(*), allocatable :: value
     type(trie_p), dimension(:), allocatable :: nodes
  end type trie
data Trie v 
  = Branch Char (Map Char (Trie v))
  | Leaf Char v
local function New(base,new)
 return setmetatable(new,{__index=base})
end
local Trie={}
function Trie.New()
 return New(Trie,{
  children={},
  value=nil
 })
end
my $trie = Data::Trie->new;
class Trie:
   def __init__(self, prefix, value=None):
       self.prefix = prefix
       self.children = []
       self.value = value
struct Trie {
    val: String,
    nodes: Vec<Trie>
}