rantree.jl

abstract UTree{T}

immutable UTreeBranch{T} <: UTree{T}
    left::UTree{T}
    right::UTree{T}
end

immutable UTreeLeaf{T} <: UTree{T}
    v::T
end


islead(u::Uint128) = (u >> 127) != 0
islead(u::Uint64) = (u >> 63) != 0
islead(u::Uint32) = (u >> 31) != 0
islead(u::Uint16) = (u >> 15) != 0
islead(u::Uint8) = (u >> 7) != 0

import Base.getindex, Base.rand, Base.show

getindex{T}(t::UTreeBranch{T},u) = islead(u) ?  getindex(t.right, u << 1) : getindex(t.left, u << 1)

getindex{T}(t::UTreeLeaf{T},u) = t.v

function additem{T}(t::UTreeLeaf{T},r::T,u) 
    if u == 0
        return UTreeLeaf(r)
    elseif islead(u)
        return UTreeBranch(t,additem(t,r,u << 1))        
    else
        return UTreeBranch(additem(t,r,u << 1),UTreeLeaf(r))
    end
end

function additem{T}(t::UTreeBranch{T},r::T,u) 
    if u == 0
        return UTreeLeaf(r)
    elseif islead(u)
        return UTreeBranch(t.left,additem(t.right,r,u << 1))        
    else
        return UTreeBranch(additem(t.left,r,u << 1),UTreeLeaf(r))
    end
end


function utree(probs,labels)
    n = length(probs)
    t = UTreeLeaf(labels[1])
    u = uint64(round(probs[1]*2.0^64))
    for i = 2:n
        t = additem(t, labels[i],u)
        u += uint64(round(probs[i]*2.0^64))
    end
    t
end

rand{T}(t::UTree{T}) = t[rand(Uint64)]

show{T}(io::IO, t::UTree{T}) = show(io,typeof(t))

n = 100_000
probs = fill(1/n,n)
labels = 1:n
t = utree(probs,labels)

@time for i = 1:100; t = utree(probs,labels); end