TUPLE: trie value children ;
: <trie> ( -- trie ) f H{ } clone trie boa ;

: split-key ( str -- seq )
    dup length 3 / >integer group ;

: (trie-find) ( str trie -- value/f ? )
    over empty?
    [ value>> nip t ]
    [ [ unclip ]
      [ children>> ] bi* at dup
      [ (trie-find) ]
      [ nip f ] if
    ] if ; inline recursive

: trie-find ( str trie -- value/f ? )
    [ split-key ] dip (trie-find) ;

:: (trie-insert) ( trie key value  -- )
    key empty?
    [ trie value >>value drop ]
    [ key unclip :> ( ks k )
      trie children>> k swap at 
      [ ks value (trie-insert) ]  ! branch already present
      [ <trie> 
        [ k trie children>> set-at ]
        [ ks value (trie-insert) ] bi
      ] if* 
    ] if ; inline recursive

: trie-insert ( trie key value  -- )
    [ split-key ] dip (trie-insert) ;