swissdict for julia

dict.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

function _truncate_at_width_or_chars(str, width, chars="", truncmark="…")
    truncwidth = textwidth(truncmark)
    (width <= 0 || width < truncwidth) && return ""

    wid = truncidx = lastidx = 0
    for (idx, c) in pairs(str)
        lastidx = idx
        wid += textwidth(c)
        wid >= width - truncwidth && truncidx == 0 && (truncidx = lastidx)
        (wid >= width || c in chars) && break
    end

    lastidx != 0 && str[lastidx] in chars && (lastidx = prevind(str, lastidx))
    truncidx == 0 && (truncidx = lastidx)
    if lastidx < lastindex(str)
        return String(SubString(str, 1, truncidx) * truncmark)
    else
        return String(str)
    end
end

function show(io::IO, t::AbstractDict{K,V}) where V where K
    recur_io = IOContext(io, :SHOWN_SET => t,
                             :typeinfo => eltype(t))

    limit::Bool = get(io, :limit, false)
    # show in a Julia-syntax-like form: Dict(k=>v, ...)
    print(io, typeinfo_prefix(io, t))
    print(io, '(')
    if !isempty(t) && !show_circular(io, t)
        first = true
        n = 0
        for pair in t
            first || print(io, ',')
            first = false
            show(recur_io, pair)
            n+=1
            limit && n >= 10 && (print(io, "…"); break)
        end
    end
    print(io, ')')
end

# Dict
const _u8x16 = NTuple{16, VecElement{UInt8}}
"""
    Dict([itr])

`Dict{K,V}()` constructs a hash table with keys of type `K` and values of type `V`.
Keys are compared with [`isequal`](@ref) and hashed with [`hash`](@ref).

Given a single iterable argument, constructs a [`Dict`](@ref) whose key-value pairs
are taken from 2-tuples `(key,value)` generated by the argument.

# Examples
```jldoctest
julia> Dict([("A", 1), ("B", 2)])
Dict{String,Int64} with 2 entries:
  "B" => 2
  "A" => 1
```

Alternatively, a sequence of pair arguments may be passed.

```jldoctest
julia> Dict("A"=>1, "B"=>2)
Dict{String,Int64} with 2 entries:
  "B" => 2
  "A" => 1
```
"""
mutable struct Dict{K,V} <: AbstractDict{K,V}
    slots::Vector{_u8x16}
    keys::Vector{K}
    vals::Vector{V}
    nbfull::Int
    count::Int
    age::UInt
    idxfloor::Int  # an index <= the indices of all used slots

    function Dict{K,V}() where V where K
        new(fill(_expand16(0x00),1), Vector{K}(undef, 16), Vector{V}(undef, 16), 0, 0, 0, 1)
    end
    function Dict{K,V}(d::Dict{K,V}) where V where K
        new(copy(d.slots), copy(d.keys), copy(d.vals), d.nbfull, d.count, d.age,
            d.idxfloor)
    end
    function Dict{K, V}(slots, keys, vals, nbfull, count, age, idxfloor) where {K, V}
        new(slots, keys, vals, nbfull, count, age, idxfloor)
    end
end
function Dict{K,V}(kv) where V where K
    h = Dict{K,V}()
    if IteratorSize(typeof(kv)) !== SizeUnknown()
        sizehint!(h, length(kv))
    end
    for (k,v) in kv
        h[k] = v
    end
    return h
end
Dict{K,V}(p::Pair) where {K,V} = setindex!(Dict{K,V}(), p.second, p.first)
function Dict{K,V}(ps::Pair...) where V where K
    h = Dict{K,V}()
    sizehint!(h, length(ps))
    for p in ps
        h[p.first] = p.second
    end
    return h
end
# Note the constructors of WeakKeyDict mirror these here, keep in sync.
Dict() = Dict{Any,Any}()
Dict(kv::Tuple{}) = Dict()
copy(d::Dict) = Dict(d)

const AnyDict = Dict{Any,Any}

Dict(ps::Pair{K,V}...) where {K,V} = Dict{K,V}(ps)
Dict(ps::Pair...)                  = Dict(ps)

function Dict(kv)
    try
        dict_with_eltype((K, V) -> Dict{K, V}, kv, eltype(kv))
    catch
        if !isiterable(typeof(kv)) || !all(x->isa(x,Union{Tuple,Pair}),kv)
            throw(ArgumentError("Dict(kv): kv needs to be an iterator of tuples or pairs"))
        else
            rethrow()
        end
    end
end

function grow_to!(dest::AbstractDict{K, V}, itr) where V where K
    y = iterate(itr)
    y === nothing && return dest
    ((k,v), st) = y
    dest2 = empty(dest, typeof(k), typeof(v))
    dest2[k] = v
    grow_to!(dest2, itr, st)
end

# this is a special case due to (1) allowing both Pairs and Tuples as elements,
# and (2) Pair being invariant. a bit annoying.
function grow_to!(dest::AbstractDict{K,V}, itr, st) where V where K
    y = iterate(itr, st)
    while y !== nothing
        (k,v), st = y
        if isa(k,K) && isa(v,V)
            dest[k] = v
        else
            new = empty(dest, promote_typejoin(K,typeof(k)), promote_typejoin(V,typeof(v)))
            merge!(new, dest)
            new[k] = v
            return grow_to!(new, itr, st)
        end
        y = iterate(itr, st)
    end
    return dest
end

empty(a::AbstractDict, ::Type{K}, ::Type{V}) where {K, V} = Dict{K, V}()

#hashindex(key, sz) = (((hash(key)%Int) & (sz-1)) + 1)::Int

##Simd utilities
@inline _expand16(u::UInt8) = ntuple(i->VecElement(u), Val(16))
_blsr(i::UInt32)= i & (i-Int32(1))

@inline _vcmp_eq(u::_u8x16, v::_u8x16) = Core.Intrinsics.llvmcall(("""
%cmp = icmp eq <16 x i8> %0, %1
%cmp16 = bitcast <16 x i1> %cmp to i16
%res = zext i16 %cmp16 to i32
ret i32 %res
"""), UInt32, Tuple{_u8x16,_u8x16}, u, v)

@inline _vcmp_le(u::_u8x16, v::_u8x16) = Core.Intrinsics.llvmcall(("""
%cmp = icmp ule <16 x i8> %0, %1
%cmp16 = bitcast <16 x i1> %cmp to i16
%res = zext i16 %cmp16 to i32
ret i32 %res
"""), UInt32, Tuple{_u8x16,_u8x16}, u, v)

@inline function _prefetchr(p::Ptr)
    p = reinterpret(UInt, p)
    if UInt === UInt64
        Core.Intrinsics.llvmcall(("declare void @llvm.prefetch(i8*, i32, i32, i32)", """
    %ptr = inttoptr i64 %0 to i8*
    call void @llvm.prefetch(i8* %ptr, i32 0, i32 3, i32 1)
    ret void
    """), Nothing, Tuple{UInt}, p)
    else
        Core.Intrinsics.llvmcall(("declare void @llvm.prefetch(i8*, i32, i32, i32)", """
    %ptr = inttoptr i32 %0 to i8*
    call void @llvm.prefetch(i8* %ptr, i32 0, i32 3, i32 1)
    ret void
    """), Nothing, Tuple{UInt}, p)
    end
end


@inline function _prefetchw(p::Ptr)
    p = reinterpret(UInt, p)
    if UInt === UInt64
        Core.Intrinsics.llvmcall(("declare void @llvm.prefetch(i8*, i32, i32, i32)", """
    %ptr = inttoptr i64 %0 to i8*
    call void @llvm.prefetch(i8* %ptr, i32 1, i32 3, i32 1)
    ret void
    """), Nothing, Tuple{UInt}, p)
    else
        Core.Intrinsics.llvmcall(("declare void @llvm.prefetch(i8*, i32, i32, i32)", """
    %ptr = inttoptr i32 %0 to i8*
    call void @llvm.prefetch(i8* %ptr, i32 1, i32 3, i32 1)
    ret void
    """), Nothing, Tuple{UInt}, p)
    end
end


@inline function _hashtag(u::Unsigned)
    #extracts tag between 0x02 and 0xff from lower bits, rotates tag bits to front
    u = u % UInt
    tag = u % UInt8
    if UInt === UInt64
        hi = ((u>>8) | (u<<56)) % Int
    else
        hi = ((u>>8) | (u<<24)) % Int
    end
    tag = tag > 1 ? tag : tag+0x02
    return (hi, tag)
end

@propagate_inbounds function _slotget(slots::Vector{_u8x16}, i::Int)
    #@boundscheck 0 < i <= length(slots)*16 || throw(BoundsError(slots, 1 + (i-1)>>4)
    GC.@preserve slots begin
        return unsafe_load(convert(Ptr{UInt8}, pointer(slots)), i)
    end
end

@propagate_inbounds function _slotset!(slots::Vector{_u8x16},  v::UInt8, i::Int)
   # @boundscheck 0 < i <= length(slots)*16 || throw(BoundsError(slots, 1 + (i-1)>>4))
    GC.@preserve slots begin
        return unsafe_store!(convert(Ptr{UInt8}, pointer(slots)), v, i)
    end
end

@inline function _find_candidates(v::_u8x16, tag::UInt8)
    match = _vcmp_eq(v, _expand16(tag))
    return (match, v[16].value === 0x00)
end

@inline _find_free(v::_u8x16) = _vcmp_le(v, _expand16(UInt8(1)))

##Basic operations

# get the index where a key is stored, or -1 if not present
ht_keyindex(h::Dict, key) = ht_keyindex(h::Dict, key, _hashtag(hash(key))...)
function ht_keyindex(h::Dict, key, i0, tag)
    slots = h.slots
    keys = h.keys
    sz = length(slots)
    i = i0 & (sz-1)
    #_prefetchr(pointer(h.keys, i*16+1))
   # _prefetchr(pointer(h.vals, i*16+1))
    #Todo/discuss: _prefetchr(pointer(h.keys, i*16+9))?
    @inbounds while true
        msk = slots[i+1]
        cands, done = _find_candidates(msk, tag)
        while cands != 0
            off = trailing_zeros(cands)
            idx = i*16 + off + 1
            isequal(keys[idx], key) && return idx
            cands = _blsr(cands)
        end
        done && break
        i = (i+1) & (sz-1)
    end
    return -1
end

# get the index where a key is stored, or -pos if not present
# and the key would be inserted at pos
# This version is for use by setindex! and get!. It never rehashes.
ht_keyindex2!(h::Dict, key) = ht_keyindex2!(h, key, _hashtag(hash(key))...)
@inline function ht_keyindex2!(h::Dict, key, i0, tag)
    slots = h.slots
    keys = h.keys
    sz = length(slots)
    i = i0 & (sz-1)
    _prefetchw(pointer(h.keys, i*16+1))
    _prefetchw(pointer(h.vals, i*16+1))
    #Todo/discuss: _prefetchr(pointer(h.keys, i*16+9))?
    @inbounds while true
        msk = slots[i+1]
        cands, done = _find_candidates(msk, tag)
        while cands != 0
            off = trailing_zeros(cands)
            idx = i*16 + off + 1
            isequal(keys[idx], key) && return idx, tag
            cands = _blsr(cands)
        end
        done && break
        i = (i+1) & (sz-1)
    end
    i = i0 & (sz-1)
    @inbounds while true
        msk = slots[i+1]
        cands = _find_free(msk)
        if cands != 0
            off = trailing_zeros(cands)
            idx = i*16 + off + 1
            return -idx, tag
        end
        i = (i+1) & (sz-1)
    end
end

@propagate_inbounds function _setindex!(h::Dict, v, key, index, tag)
    h.keys[index] = key
    h.vals[index] = v
    h.count += 1
    h.age += 1
    so =  _slotget(h.slots, index)
    h.nbfull += (iszero(index & 0x0f) & (so==0x00))
    _slotset!(h.slots, tag, index)
    if index < h.idxfloor
        h.idxfloor = index
    end
    maybe_rehash_grow!(h)
end

function _delete!(h::Dict{K,V}, index) where {K,V}
    #Caller is responsible for maybe shrinking the Dict after the deletion.
    isbitstype(K) || isbitsunion(K) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.keys, index-1)
    isbitstype(V) || isbitsunion(V) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.vals, index-1)
    isboundary = iszero(index & 0x0f) #boundaries: 16, 32, ...
    @inbounds _slotset!(h.slots, ifelse(isboundary, 0x01, 0x00), index)
    h.count -= 1
    h.age += 1
    return h
end


#fast iteration over active slots.
function _iterslots(h::Dict, start::Int)
    i0 = ((start-1) & (length(h.keys)-1))>>4 + 1
    off = (start-1) & 0x0f
    @inbounds sl = _find_free(h.slots[i0>>4 + 1])
    sl = ((~sl & 0xffff)>>off) << off
    return _iterslots(h, (i0, sl))
end
function _iterslots(h::Dict, state)
    i, sl = state
    while iszero(sl)
        i += 1
        i <= length(h.slots) || return nothing
        @inbounds msk = h.slots[i]
        sl = _find_free(msk)
        sl = (~sl & 0xffff)
    end
    return ((i-1)*16 + trailing_zeros(sl) + 1, (i, _blsr(sl)))
end

#Dictionary resize logic:
#Guarantee 40% of buckets and 15% of entries free, and at least 25% of entries filled
#growth when > 85% entries full or > 60% buckets full, shrink when <25% entries full.
#>60% bucket full should be super rare outside of very bad hash collisions or
#super long-lived Dictionaries (expected 0.85^16 = 7% buckets full at 85% entries full).
#worst-case hysteresis: shrink at 25% vs grow at 30% if all hashes collide.
#expected hysteresis is 25% to 42.5%.
function maybe_rehash_grow!(h::Dict)
        sz = length(h.keys)
        if h.count > sz * 0.75 || (h.nbfull-1) * 10 > sz * 6
            rehash!(h, 2*sz)
        end
        nothing
    end

function maybe_rehash_shrink!(h::Dict)
#    sz = length(h.keys)
#    if h.count*4 < sz && sz > 16
#        rehash!(h, sz>>1)
#    end
    nothing
end

function _dictsizehint(sz)
    sz<= 16 && return 16
    nsz = _tablesz(sz)
    sz > 0.85*nsz ? 2*nsz : nsz
end

function sizehint!(d::Dict{T}, newsz) where T
    nsz = _dictsizehint(newsz)
    if newsz > nsz
        rehash!(d, nsz)
    end
    d
end


function rehash!(h::Dict{K,V}, newsz = length(h.keys)) where V where K
    olds = h.slots
    oldk = h.keys
    oldv = h.vals
    sz = length(oldk)
    newsz = _tablesz(newsz)
    newsz*0.95 > h.count || (newsz *= 2)
    h.age += 1
    h.idxfloor = 1
    if h.count == 0
        resize!(h.slots, newsz>>4)
        fill!(h.slots, _expand16(0x00))
        resize!(h.keys, newsz)
        resize!(h.vals, newsz)
        h.nbfull = 0
        return h
    end
    nssz = newsz>>4
    slots = fill(_expand16(0x00), nssz)
    keys = Vector{K}(undef, newsz)
    vals = Vector{V}(undef, newsz)
    age0 = h.age
    nbfull = 0
    is = _iterslots(h, 1)
    count = 0
    @inbounds while is !== nothing
        i, s = is
        k = oldk[i]
        v = oldv[i]
        i0, t = _hashtag(hash(k))
        i = i0 & (nssz-1)
        idx = 0
        while true
            msk = slots[i + 1]
            cands = _find_free(msk)
            if cands != 0
                off = trailing_zeros(cands)
                idx = i*16 + off + 1
                break
            end
            i = (i+1) & (nssz-1)
        end
        _slotset!(slots, t, idx)
        keys[idx] = k
        vals[idx] = v
        nbfull += iszero(idx & 0x0f)
        count += 1
        if h.age != age0
            return rehash!(h, newsz)
        end
        is = _iterslots(h, s)
    end
    h.slots = slots
    h.keys = keys
    h.vals = vals
    h.nbfull = nbfull
    @assert h.age == age0
    @assert h.count == count
    return h
end

"""
    empty!(collection) -> collection

Remove all elements from a `collection`.

# Examples
```jldoctest
julia> A = Dict("a" => 1, "b" => 2)
Dict{String,Int64} with 2 entries:
  "b" => 2
  "a" => 1

julia> empty!(A);

julia> A
Dict{String,Int64} with 0 entries
```
"""
function empty!(h::Dict{K,V}) where V where K
    fill!(h.slots, _expand16(0x00))
    sz = length(h.keys)
    empty!(h.keys)
    empty!(h.vals)
    resize!(h.keys, sz)
    resize!(h.vals, sz)
    h.nbfull = 0
    h.count = 0
    h.age += 1
    h.idxfloor = 1
    return h
end

function setindex!(h::Dict{K,V}, v0, key0) where V where K
    key = convert(K, key0)
    if !isequal(key, key0)
        throw(ArgumentError("$(limitrepr(key0)) is not a valid key for type $K"))
    end
    setindex!(h, v0, key)
end

function setindex!(h::Dict{K,V}, v0, key::K) where V where K
    v = convert(V, v0)
    index, tag = ht_keyindex2!(h, key)

    if index > 0
        h.age += 1
        @inbounds h.keys[index] = key
        @inbounds h.vals[index] = v
    else
        @inbounds _setindex!(h, v, key, -index, tag)
    end

    return h
end

"""
    get!(collection, key, default)

Return the value stored for the given key, or if no mapping for the key is present, store
`key => default`, and return `default`.

# Examples
```jldoctest
julia> d = Dict("a"=>1, "b"=>2, "c"=>3);

julia> get!(d, "a", 5)
1

julia> get!(d, "d", 4)
4

julia> d
Dict{String,Int64} with 4 entries:
  "c" => 3
  "b" => 2
  "a" => 1
  "d" => 4
```
"""
get!(collection, key, default)

get!(h::Dict{K,V}, key0, default) where {K,V} = get!(()->default, h, key0)

"""
    get!(f::Function, collection, key)

Return the value stored for the given key, or if no mapping for the key is present, store
`key => f()`, and return `f()`.

This is intended to be called using `do` block syntax:
```julia
get!(Dict, key) do
    # default value calculated here
    time()
end
```
"""
get!(f::Function, collection, key)

function get!(default::Callable, h::Dict{K,V}, key0) where V where K
    key = convert(K, key0)
    if !isequal(key, key0)
        throw(ArgumentError("$(limitrepr(key0)) is not a valid key for type $K"))
    end
    return get!(default, h, key)
end

function get!(default::Callable, h::Dict{K,V}, key::K) where V where K
    index, tag = ht_keyindex2!(h, key)

    index > 0 && return h.vals[index]

    age0 = h.age
    v = convert(V, default())
    if h.age != age0
        index, tag = ht_keyindex2!(h, key)
    end
    if index > 0
        h.age += 1
        @inbounds h.keys[index] = key
        @inbounds h.vals[index] = v
    else
        @inbounds _setindex!(h, v, key, -index, tag)
    end
    return v
end

# NOTE: this macro is trivial, and should
#       therefore not be exported as-is: it's for internal use only.
macro get!(h, key0, default)
    return quote
        get!(()->$(esc(default)), $(esc(h)), $(esc(key0)))
    end
end


function getindex(h::Dict{K,V}, key) where V where K
    index = ht_keyindex(h, key)
    @inbounds return (index < 0) ? throw(KeyError(key)) : h.vals[index]::V
end

"""
    get(collection, key, default)

Return the value stored for the given key, or the given default value if no mapping for the
key is present.

# Examples
```jldoctest
julia> d = Dict("a"=>1, "b"=>2);

julia> get(d, "a", 3)
1

julia> get(d, "c", 3)
3
```
"""
get(collection, key, default)

function get(h::Dict{K,V}, key, default) where V where K
    index = ht_keyindex(h, key)
    @inbounds return (index < 0) ? default : h.vals[index]::V
end

"""
    get(f::Function, collection, key)

Return the value stored for the given key, or if no mapping for the key is present, return
`f()`.  Use [`get!`](@ref) to also store the default value in the Dictionary.

This is intended to be called using `do` block syntax

```julia
get(Dict, key) do
    # default value calculated here
    time()
end
```
"""
get(::Function, collection, key)

function get(default::Callable, h::Dict{K,V}, key) where V where K
    index = ht_keyindex(h, key)
    @inbounds return (index < 0) ? default() : h.vals[index]::V
end

"""
    haskey(collection, key) -> Bool

Determine whether a collection has a mapping for a given `key`.

# Examples
```jldoctest
julia> D = Dict('a'=>2, 'b'=>3)
Dict{Char,Int64} with 2 entries:
  'a' => 2
  'b' => 3

julia> haskey(D, 'a')
true

julia> haskey(D, 'c')
false
```
"""
haskey(h::Dict, key) = (ht_keyindex(h, key) > 0)
in(key, v::KeySet{<:Any, <:Dict}) = (ht_keyindex(v.dict, key) > 0)

"""
    getkey(collection, key, default)

Return the key matching argument `key` if one exists in `collection`, otherwise return `default`.

# Examples
```jldoctest
julia> D = Dict('a'=>2, 'b'=>3)
Dict{Char,Int64} with 2 entries:
  'a' => 2
  'b' => 3

julia> getkey(D, 'a', 1)
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)

julia> getkey(D, 'd', 'a')
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
```
"""
function getkey(h::Dict{K,V}, key, default) where V where K
    index = ht_keyindex(h, key)
    @inbounds return (index<0) ? default : h.keys[index]::K
end

function _pop!(h::Dict, index)
    @inbounds val = h.vals[index]
    _delete!(h, index)
    maybe_rehash_shrink!(h)
    return val
end

function pop!(h::Dict, key)
    index = ht_keyindex(h, key)
    return index > 0 ? _pop!(h, index) : throw(KeyError(key))
end

"""
    pop!(collection, key[, default])

Delete and return the mapping for `key` if it exists in `collection`, otherwise return
`default`, or throw an error if `default` is not specified.

# Examples
```jldoctest
julia> d = Dict("a"=>1, "b"=>2, "c"=>3);

julia> pop!(d, "a")
1

julia> pop!(d, "d")
ERROR: KeyError: key "d" not found
Stacktrace:
[...]

julia> pop!(d, "e", 4)
4
```
"""
pop!(collection, key, default)

function pop!(h::Dict, key, default)
    index = ht_keyindex(h, key)
    return index > 0 ? _pop!(h, index) : default
end

function pop!(h::Dict)
    isempty(h) && throw(ArgumentError("Dict must be non-empty"))
    is = _iterslots(h, h.idxfloor)
    @assert is !== nothing
    idx, s = is
    @inbounds key = h.keys[idx]
    @inbounds val = h.vals[idx]
    _delete!(h, idx)
    h.idxfloor = idx
    key => val
end


"""
    delete!(collection, key)

Delete the mapping for the given key in a collection, and return the collection.

# Examples
```jldoctest
julia> d = Dict("a"=>1, "b"=>2)
Dict{String,Int64} with 2 entries:
  "b" => 2
  "a" => 1

julia> delete!(d, "b")
Dict{String,Int64} with 1 entry:
  "a" => 1
```
"""
delete!(collection, key)

function delete!(h::Dict, key)
    index = ht_keyindex(h, key)
    if index > 0
        _delete!(h, index)
    end
    maybe_rehash_shrink!(h)
    return h
end


isempty(t::Dict) = (t.count == 0)
length(t::Dict) = t.count

@propagate_inbounds function iterate(h::Dict, state = h.idxfloor)
    is = _iterslots(h, state)
    is === nothing && return nothing
    i, s = is
    @inbounds p = h.keys[i] => h.vals[i]
    return (p, s)
end

@propagate_inbounds function iterate(v::Union{KeySet{<:Any, <:Dict}, ValueIterator{<:Dict}}, state=v.dict.idxfloor)
    is = _iterslots(v.dict, state)
    is === nothing && return nothing
    i, s = is
    return (v isa KeySet ? v.dict.keys[i] : v.dict.vals[i], s)
end

function filter!(pred, h::Dict{K,V}) where {K,V}
    h.count == 0 && return h
    is = _iterslots(v, h.idxfloor)
    while is !== nothing
        i, s = is
        @inbounds k = h.keys[i]
        @inbounds v = h.vals[i]
        if !pred(Pair{K,V}(k,v))
            _delete!(h, i)
        end
    end
    maybe_rehash_shrink!(h)
    h
end

struct ImmutableDict{K,V} <: AbstractDict{K,V}
    parent::ImmutableDict{K,V}
    key::K
    value::V
    ImmutableDict{K,V}() where {K,V} = new() # represents an empty Dictionary
    ImmutableDict{K,V}(key, value) where {K,V} = (empty = new(); new(empty, key, value))
    ImmutableDict{K,V}(parent::ImmutableDict, key, value) where {K,V} = new(parent, key, value)
end

"""
    ImmutableDict

ImmutableDict is a Dictionary implemented as an immutable linked list,
which is optimal for small Dictionaries that are constructed over many individual insertions
Note that it is not possible to remove a value, although it can be partially overridden and hidden
by inserting a new value with the same key

    ImmutableDict(KV::Pair)

Create a new entry in the Immutable Dictionary for the key => value pair

 - use `(key => value) in Dict` to see if this particular combination is in the properties set
 - use `get(Dict, key, default)` to retrieve the most recent value for a particular key

"""
ImmutableDict
ImmutableDict(KV::Pair{K,V}) where {K,V} = ImmutableDict{K,V}(KV[1], KV[2])
ImmutableDict(t::ImmutableDict{K,V}, KV::Pair) where {K,V} = ImmutableDict{K,V}(t, KV[1], KV[2])

function in(key_value::Pair, Dict::ImmutableDict, valcmp=(==))
    key, value = key_value
    while isdefined(Dict, :parent)
        if Dict.key == key
            valcmp(value, Dict.value) && return true
        end
        Dict = Dict.parent
    end
    return false
end

function haskey(Dict::ImmutableDict, key)
    while isdefined(Dict, :parent)
        Dict.key == key && return true
        Dict = Dict.parent
    end
    return false
end

function getindex(Dict::ImmutableDict, key)
    while isdefined(Dict, :parent)
        Dict.key == key && return Dict.value
        Dict = Dict.parent
    end
    throw(KeyError(key))
end
function get(Dict::ImmutableDict, key, default)
    while isdefined(Dict, :parent)
        Dict.key == key && return Dict.value
        Dict = Dict.parent
    end
    return default
end

# this actually defines reverse iteration (e.g. it should not be used for merge/copy/filter type operations)
function iterate(d::ImmutableDict{K,V}, t=d) where {K, V}
    !isdefined(t, :parent) && return nothing
    (Pair{K,V}(t.key, t.value), t.parent)
end
length(t::ImmutableDict) = count(x->true, t)
isempty(t::ImmutableDict) = !isdefined(t, :parent)
empty(::ImmutableDict, ::Type{K}, ::Type{V}) where {K, V} = ImmutableDict{K,V}()

_similar_for(c::Dict, ::Type{Pair{K,V}}, itr, isz) where {K, V} = empty(c, K, V)
_similar_for(c::AbstractDict, ::Type{T}, itr, isz) where {T} =
    throw(ArgumentError("for AbstractDicts, similar requires an element type of Pair;\n  if calling map, consider a comprehension instead"))