Giter VIP home page Giter VIP logo

tries.jl's Introduction

Tries

Dev Build Status Codecov

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

tries.jl's People

Contributors

gkappler avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.