Creating implementation for idiom 159 : Trie

Idiom

# 159 Trie

Created by

Lead paragraph

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

New implementation

Language

Imports

Code

Documentation URL

Original attribution URL

Online runnable demo

Username

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations

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

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

Demo

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

use Data::Trie qw();

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>
}

Preview