# 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).