Edit on GitHub

Public Interface

Documentation for Tries.jl's public interface.

Tries — Module

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.

source
Tries.Trie — Type
Trie{K,T}()

Construct an empty Trie{K,T} with root value missing.

source
Trie{K,T}(value)

Construct an empty Trie{K,T} with root value is value.

source
Trie(values::Vararg{Pair{NTuple{N,K},T} where N}) where {K,T}
Trie(values::Vararg{Pair{Vector{K},T}}) where {K,T}
Trie(values::Vararg{Pair{NTuple{N,K},<:Any} where N}) where {K}
Trie(values::Base.Generator)

Construct a Trie{K,T} and populate it with r[k...]=v.

julia> 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> Trie((:a,)=>"a", (:a,:b)=>"c", (:a,:c,:d)=>"z", (:a,:b,:d)=>"y")
Trie{Symbol,String}
└─ :a => "a"
   ├─ :b => "c"
   │  └─ :d => "y"
   └─ :c
      └─ :d => "z"

See also setindex!.

source
Base.get — Function
Base.get(x::Trie)
Base.get(x::SubTrie)

Return value::Union{Missing,valtype(x)} of x.

source
Base.get(x::Trie,k)

Returns subtrie(x,k).value.

See also subtrie

source
Base.show — Function
Base.show(x::Trie)
Base.show(x::SubTrie)

Display x with AbstractTrees.print_tree.

source
Base.keytype — Function
Base.keytype(::Type{Trie{K,V}}) where {K,V}
Base.keytype(::Trie{K,V}) where {K,V}

Returns NTuple{N,K} where N.

Note

eltype(keytype(Trie{K,V})) == K

source
Base.eltype — Function
Base.eltype(::Type{<:AbstractTrie{K,V}}) where {K,V}
Base.etype(::AbstractTrie{K,V}) where {K,V}

Returns Pair{Tuple{Vararg{K,N} where N},Union{Missing,V}} for iterate and collect.

source
Base.haskey — Function
Base.haskey(x::AbstractTrie,path)

Returns true iif x has nodes along path.

source
Tries.subtrie — Function
subtrie(x::Trie{K,T},path...)

Return a subtree at path.

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

julia> subtrie(a, :a, :b)
SubTrie{Symbol,String} @ :a, :b => "c"
└─ :d => "y"

julia> subtrie(a, :a, :d, :b)
ERROR: KeyError: key (:d, :b) not found
Stacktrace:
 [1] (::Tries.var"#41#42")(::Tuple{Symbol,Symbol,Symbol}, ::Int64) at /home/gregor/dev/julia/Tries/src/Tries.jl:334
 [2] subtrie(::Tries.var"#41#42", ::Trie{Symbol,String}, ::Symbol, ::Vararg{Symbol,N} where N) at /home/gregor/dev/julia/Tries/src/Tries.jl:386
 [3] subtrie(::Trie{Symbol,String}, ::Symbol, ::Symbol, ::Vararg{Symbol,N} where N) at /home/gregor/dev/julia/Tries/src/Tries.jl:334
 [4] top-level scope at REPL[12]:1
source
subtrie(::Nothing,x::Trie{K,T},path...)

Return a subtree at path, or nothing, if path does not exist in x. Does not modify x.

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

julia> subtrie(nothing, a, :a, :d)
source
subtrie(notfound::Function,x::Trie{K,T},path...)

Return a subtree at path, or notfound(path,error_index), if path does not exist in x (default (path,i)->throw(KeyError(path[i:end]))). Does not modify x.

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


julia> subtrie((x...) -> x, a, :a, :d)
((:a, :d), 2)
Note

check

source
Tries.subtrie! — Function
subtrie!(x::Trie,path...)

Return a subtree at path. Nodes missing in x along path are created and populated with values missing.

source
subtrie!(f::Function,x::Trie,path...)

Return a subtree at path. Nodes missing in x along path are created and populated with values f(path, key).

julia> a = Trie{Int,Int}(0)
Trie{Int64,Int64} => 0

julia> subtrie!((path,key)->length(p)+1, a, 4,3,2,1)
SubTrie{Int64,Int64} @ 4, 3, 2, 1 => 4

julia> a
Trie{Int64,Int64} => 0
└─ 4 => 1
   └─ 3 => 2
      └─ 2 => 3
         └─ 1 => 4
source
Base.getindex — Function
Base.getindex(x::Trie{K,T}, path...) where {K,T}

Get SubTrie at path.

See also SubTrie.

source
Base.getindex(x::SubTrie, path...)

Get SubTrie at (x.path...,path...).

See also SubTrie.

source
Base.setindex! — Function
Base.setindex!(x::Trie{K,T}, v::T, path...) where {K,T}

Set value at path to `v and return previous value or missing.

Note

To retrieve last value you need to call setindex! explicitly.

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

julia> x[:a,:b,:z]="node added"
"node added"

julia> setindex!(x,"value set",:a,:c)
Trie{Symbol,String}
└─ :d => "z"


julia> x
Trie{Symbol,String}
└─ :a => "a"
   ├─ :b => "c"
   │  ├─ :d => "y"
   │  └─ :z => "node added"
   └─ :c => "value set"
      └─ :d => "z"

See also subtrie!

source
Base.values — Function
Base.values(x::Union{Trie,SubTrie})

Generator returning values as second fields from pairs(x).

See also pairs

source
Base.keys — Function
Base.keys(x::AbstractTrie)

Generator returning paths as first fields from pairs(x).

See also pairs

source