Skip to content
This repository
tree: c9969589bf
Fetching contributors…

Cannot retrieve contributors at this time

file 69 lines (60 sloc) 1.478 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

type Trie{T}
    value::T
    children::Dict{Char,Trie{T}}
    is_key::Bool

    function Trie()
        self = new()
        self.children = Dict{Char,Trie{T}}()
        self.is_key = false
        self
    end
end

Trie() = Trie{Any}()

function assign{T}(t::Trie{T}, val::T, key::String)
    node = t
    for char in key
        if !has(node.children, char)
            node.children[char] = Trie{T}()
        end
        node = node.children[char]
    end
    node.is_key = true
    node.value = val
end

function subtrie(t::Trie, prefix::String)
    node = t
    for char in prefix
        if !has(node.children, char)
            return nothing
        else
            node = node.children[char]
        end
    end
    node
end

function has(t::Trie, key::String)
    node = subtrie(t, key)
    node != nothing && node.is_key
end

get(t::Trie, key::String) = get(t, key, nothing)
function get(t::Trie, key::String, notfound)
    node = subtrie(t, key)
    if node != nothing && node.is_key
        return node.value
    end
    notfound
end

function keys(t::Trie, prefix::String, found)
    if t.is_key
        push(found, prefix)
    end
    for (char,child) in t.children
        keys(child, strcat(prefix,char), found)
    end
end
keys(t::Trie, prefix::String) = (found=String[]; keys(t, prefix, found); found)
keys(t::Trie) = keys(t, "")

function keys_with_prefix(t::Trie, prefix::String)
    st = subtrie(t, prefix)
    st != nothing ? keys(st,prefix) : []
end
Something went wrong with that request. Please try again.