Edit on GitHub

Tries.jl Documentation

Implemented of a Trie data structure. This is an associative data structure with keys of type NTuple{N,K} where N and values of type V.

Package Features

  • General trie data structure building on Dict.
  • Generalizes DataStructures Trie from AbstractString to arbitrary key types.
Note

Future versions might switch backend to Andy Ferris Dictionaries.jl.

Using Tries

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)
Pair{Tuple{Vararg{Symbol,N} where N},Any}

julia> x[:a,:b]
Trie{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]
Trie{Symbol,Any}:z => "added"
└─ :n => "n"

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

julia> x[:z]
Trie{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
ERROR: MethodError: no method matching (::Main.##ex-#429.var"#1#2")(::Tuple{}, ::Int64)
Closest candidates are:
  #1(::Any) at none:2

julia> x
Trie{Int64,Int64} => 0

julia> collect(keys(x))
1-element Array{Tuple{},1}:
 ()

Library Outline