Tries

Trie is a small package providing a tree-like data structure implemented on a Dict backend and using AbstractTrees for printing and traversal. Trie generalizes DataStructures.Trie from AbstractString keys to arbitrary NTuple{N,K} where N key types.

Some design decisions for a trie::Trie{K,V} regarding keytype and getindex might change in future versions based on discussions with the community. :

• getindex(trie, ks::K...) and setindex!(trie, v, ks::K...) consider Trie as sparse representation of an object with values::Union{V,Missing} referenced by any finite N-dimensional key ks::NTuple{N,K} where N.
• keytype(trie) currently is K, should it be ks::NTuple{N,K} where N?
• Future versions might switch backend to Andy Ferris Dictionaries.jl. Contributions, thoughts and suggestions very welcome!

julia> using Tries

julia> x=Trie((:a,)=>"a",
              (:a,:b)=>"c",
       	   (:a,:c,:d)=>"z",
       	   (:a,:b,:d)=>1)
Trie{Symbol,Any}
└─ :a => "a"
   ├─ :b => "c"
   │  └─ :d => 1
   └─ :c
      └─ :d => "z"

julia> eltype(x)
Any

julia> x[:a,:b]
SubTrie{Symbol,Any} @ :a, :b => "c"
└─ :d => 1

julia> x[:a,:b].path
(:a, :b)

julia> get(x[:a,:b])
"c"

julia> get(x[:a][:b,:d])
1

julia> #
       get(x,[:a,:b])
"c"

julia> x[:z]="added"
"added"

julia> get(x[:z])
"added"

julia> x[:z,:n]="n"
"n"

julia> x[:z]
SubTrie{Symbol,Any} @ :z => "added"
└─ :n => "n"

julia> x[:z,:n]="m"
"m"

julia> x[:z]
SubTrie{Symbol,Any} @ :z => "added"
└─ :n => "m"

julia> x
Trie{Symbol,Any}
├─ :a => "a"
│  ├─ :b => "c"
│  │  └─ :d => 1
│  └─ :c
│     └─ :d => "z"
└─ :z => "added"
   └─ :n => "m"

julia> using Tries
julia> x=Trie{Int,Int}(0)
Trie{Int64,Int64} => 0
julia> subtrie!(x, 1,2,3,4,5) do x
x[end]+1
end
SubTrie{Int64,Int64} @ 1, 2, 3, 4, 5 => 6
julia> x
Trie{Int64,Int64} => 0
└─ 1 => 2
└─ 2 => 3
└─ 3 => 4
└─ 4 => 5
└─ 5 => 6
⋮
julia> collect(keys(x))
6-element Array{Tuple{Vararg{Int64,N} where N},1}:
()
(1,)
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 3, 4, 5)

Tries is used in CombinedParsers.jl for fast prefix tree matching (see docs).