AbstractDictionary{I, T}

Abstract type for a dictionary between unique indices of type I to elements of type T.

At minimum, an AbstractDictionary must implement:

• getindex(::AbstractDictionary{I, T}, ::I) --> T
• isassigned(::AbstractDictionary{I}, ::I) --> Bool
• keys(::AbstractDictionary{I, T}) --> AbstractIndices{I}

If values can be set/mutated, then an AbstractDictionary should implement:

• issettable(::AbstractDictionary) (returning true)
• setindex!(dict::AbstractDictionary{I, T}, ::T, ::I} (returning dict)

If arbitrary indices can be added to or removed from the dictionary, implement:

• isinsertable(::AbstractDictionary) (returning true)
• insert!(dict::AbstractDictionary{I, T}, ::I, ::T} (returning dict)
• delete!(dict::AbstractDictionary{I, T}, ::I} (returning dict)

AbstractIndices{I} <: AbstractDictionary{I, I}

Abstract type for the unique keys of an AbstractDictionary. It is itself an AbstractDictionary for which getindex is idempotent, such that indices[i] = i. (This is a generalization of Base.Slice).

At minimum, an AbstractIndices{I} must implement:

• The iterate protocol, returning unique values of type I.
• in, such that in(i, indices) implies there is an element of indices which isequal to i.
• Either length, or override IteratorSize to SizeUnknown.

While an AbstractIndices object is a dictionary, the value corresponding to each index is fixed, so issettable(::AbstractIndices) = false and setindex! is never defined.

If arbitrary indices can be added or removed from the set, implement:

• isinsertable(::AbstractIndices) (returning true)
• insert!(indices::AbstractIndices{I}, ::I} (returning indices)
• delete!(indices::AbstractIndices{I}, ::I} (returning indices)

ArrayDictionary(indices, values)

Construct an ArrayDictionary <: AbstractDictionary from two arbitrary Julia iterables, one specifying the indices and one specifying the values. Lookup uses naive iteration.

If indices and values are Vectors, then the result is isinsertable and istokenizable, making simple and flexible dictionaries using naive search that may be optimal for small collections.

ArrayDictionary(indexable)

Construct a ArrayDictionary from an indexable container indexable with the same keys and values, equivalent to ArrayDictionary(keys(indexable), values(indexable)). Note that indexable may not be copied.

ArrayDictionary{I,T}()

Construct an ArrayDictionary from empty Vectors, with I and T default to Any.

ArrayDictionary(indices, undef::UndefInitializer)

Construct a ArrayDictionary from an iterable of indices, where the values are undefined/uninitialized.

ArrayIndices(iter)

Construct an ArrayIndices <: AbstractIndices from an arbitrary Julia iterable with unique elements. Lookup uses naive iteration.

ArrayIndices make simple and flexible indices using naive search that may be optimal for small collections. Larger collections are better handled by containers like Indices.

Dictionary(inds, values)
Dictionary{I}(inds, values)
Dictionary{I, T}(inds, values)

Construct a hash-based dictionary from two iterable inputs inds and values. The first value of inds will be the index for the first value of values. The input might not be copied.

Note: the values of inds must be distinct. Consider using dictionary(zip(inds, values)) if they are not. See also the index function.

Example

julia> Dictionary(["a", "b", "c"], [1, 2, 3]) 3-element Dictionary{String,Int64} "a" │ 1 "b" │ 2 "c" │ 3

julia> Dictionary{String, Float64}(["a", "b", "c"], [1, 2, 3]) 3-element Dictionary{String,Float6464} "a" │ 1.0 "b" │ 2.0 "c" │ 3.0

Dictionary(indexable)
Dictionary{I}(indexable)
Dictionary{I,T}(indexable)

Construct a hash-based dictionary from an indexable input indexable, equivalent to Dictionary(keys(indexable), values(indexable)). The input might not be copied.

Note: to construct a dictionary from Pairs use the dictionary function. See also the index function.

Examples

julia> Dictionary(Dict(:a=>1, :b=>2))
2-element Dictionary{Symbol,Int64}
 :a │ 1
 :b │ 2

julia> Dictionary(3:-1:1)
3-element Dictionary{Int64,Int64}
 1 │ 3
 2 │ 2
 3 │ 1 

Dictionary{I,T}(;sizehint = 8)

Construct an empty hash-based dictionary. I and T default to Any if not specified. A sizehint may be specified to set the initial size of the hash table, which may speed up subsequent insert! operations.

Example

julia> d = Dictionary{Int, Int}()
0-element Dictionary{Int64,Int64}

Dictionary(indices, undef::UndefInitializer)

Construct a Dictionary from an iterable of indices, where the values are undefined/uninitialized.

Example

julia> Dictionary{Int, Float64}([1,2,3], undef)
3-element Dictionary{Int64,Float64}
 1 │ 6.9220016379355e-310
 2 │ 6.9220016379426e-310
 3 │ 6.92200163794736e-310

Indices(iter)
Indices{I}(iter)

Construct a Indices with indices from iterable container iter.

Note that the elements of iter must be distinct/unique. Instead, the distinct function can be used for finding the unique elements.

Examples

julia> Indices([1,2,3])
3-element Indices{Int64}
 1
 2
 3

julia> Indices([1,2,3,3])
ERROR: IndexError("Indices are not unique (inputs at positions 3 and 4) - consider using the distinct function")
Stacktrace:
 [1] Indices{Int64}(::Array{Int64,1}) at /home/ferris/.julia/dev/Dictionaries/src/Indices.jl:92
 [2] Indices(::Array{Int64,1}) at /home/ferris/.julia/dev/Dictionaries/src/Indices.jl:53
 [3] top-level scope at REPL[12]:1

julia> distinct([1,2,3,3])
3-element Indices{Int64}
 1
 2
 3

IndicesTokens(indices)

Return a dictionary mapping from i ∈ indices to a valid token.

Tokenized(dict)

Return an indexable container mapping from the token ∈ tokens(dict) to the values of dict.

UnorderedDictionary(indexable)

Construct a UnorderedDictionary from an indexable container indexable with the same keys and values, equivalent to UnorderedDictionary(keys(indexable), values(indexable)). Note that indexable may not be copied.

UnorderedDictionary(indices, values)
UnorderedDictionary{I}(indices, values)
UnorderedDictionary{I, T}(indices, values)

Construct a UnorderedDictionary with indices from indices and values from values, matched in iteration order.

UnorderedDictionary{I, T}(indices, undef::UndefInitializer)

Construct a UnorderedDictionary with index type I and element type T. The container is initialized with keys that match the values of indices, but the values are uninitialized.

UnorderedDictionary{I, T}()

Construct an empty UnorderedDictionary with index type I and element type T. This type of dictionary uses hashes for fast lookup and insertion, and is both mutable and insertable. (See issettable and isinsertable). Unlike Dictionary, the order of elements is undefined (depending on the implementation of hash and the history of the collection).

UnorderedIndices(iter)
UnorderedIndices{I}(iter)

Construct a UnorderedIndices with indices from iterable container iter.

UnorderedIndices{I}()

Construct an empty UnorderedIndices with indices of type I. This container uses hashes for fast lookup, and is insertable. (See isinsertable). Unlike Indices, the order of elements is undefined (depending on the implementation of hash and the history of the collection).

copy(dict::AbstractDictionary)
copy(dict::AbstractDictionary, ::Type{T})

Create a shallow copy of the values and keys of dict. A new element type T can optionally be specified.

copy(inds::AbstractIndices)
copy(inds::AbstractIndices, I::Type)

Construct a shallow copy of inds, possibly specifying a new element type I. The output container is not guaranteed to be the same type as the input.

copy(inds::AbstractIndices)
copy(inds::AbstractIndices, ::Type{I})

Create a shallow copy of the indices, optionally changing the element type.

(Note that copy on a dictionary does not copy its indices).

delete!(indices::AbstractIndices, i)

Delete the index i from indices. An error is thrown if i does not exist.

delete!(dict::AbstractDictionary, i)

Delete the index i from dict. An error is thrown if i does not exist.

See also unset!, insert!.

empty(inds::AbstractIndices, I::Type, T::Type)
empty(dict::AbstractDictionary, I::Type, T::Type)

Return an empty, insertable AbstractDictionary of with indices of type I and elements of type T (even when the first argument is are indices). The default container is Dictionary{I}, but the output may depend on the first argument.

empty(dict::AbstractDictionary)

Return an empty, insertable AbstractDictionary with indices of type keytype(dict) and elements of type eltype(inds).

empty(inds::AbstractIndices, I::Type)
empty(dict::AbstractDictionary, I::Type)

Return an empty, insertable AbstractIndices of element type I (even when the first argument is a dictionary). The default container is Indices{I}, but the output may depend on the first argument.

empty(inds::AbstractIndices)

Return an empty, insertable AbstractIndices of element type eltype(inds).

fill(value, d::AbstractDictionary, [T = typeof(value)])

Construct a new issettable dictionary with identical keys as d and all elements initialized to value.

An element type can optionally be provided, which can be useful for constructing containers that accept different types of values, for example fill(d, missing, Union{Missing, Bool}).

get!(dict::AbstractDictionary, i, default)

Return the value dict[i] if index i exists. Otherwise, a new index i is inserted and set to default, which is returned.

See also get, set!.

get!(f::Union{Function, Type}, dict::AbstractDictionary, i)

Return the value dict[i] if index i exists. Otherwise, a new index i is inserted and set to the value f(), which is returned.

insert!(dict::AbstractDictionary, i, value)

Insert the value at new index i into dict. An error is thrown if index i already exists.

Hint: Use setindex! to update an existing value, and set! to perform an "upsert" (update-or-insert) operation.

insert!(indices::AbstractIndices, i)

Insert the new index i into indices. An error is thrown if i already exists.

pairs(dict::AbstractDictionary)

Return a new dictionary, wrapping dict, that shares the same keys but containing key-value pairs.

Example

julia> dict = Dictionary(["a", "b", "c"], [1, 2, 3])
3-element Dictionary{String,Int64}
 "c" │ 3
 "b" │ 2
 "a" │ 1

julia> pairs(dict)
3-element Dictionaries.PairDictionary{String,Int64,Dictionary{String,Int64}}
 "c" │ "c" => 3
 "b" │ "b" => 2
 "a" │ "a" => 1

similar(d::AbstractDictionary, [T=eltype(d)])

Construct a new issettable dictionary with identical keys as d and an element type of T. The initial values are uninitialized/undefined.

sort!(dict::AbstractDictionary; kwargs...)

Modify dict so that it is sorted by its values. The kwargs are the usual ordering options supported by sort. Note that this only works on supported types.

See also sort, sortkeys! and sortpairs!.

sort(dict::AbstractDictionary; kwargs...)

Return a copy of dict sorted by its values. The kwargs are the usual ordering options supported by sort.

See also sort!, sortkeys and sortpairs.

deletetoken!(dict, token)

Remove the slot of the dictionary at token.

See also gettoken and gettoken!.

dictionary(iter)

Construct a new AbstractDictionary from an iterable iter of key-value Pairs (or other iterables of two elements, such as a two-tuples). The default container type is Dictionary. If duplicate keys are detected, the first encountered value is retained.

See also the index function.

Examples

julia> dictionary(["a"=>1, "b"=>2, "c"=>3])
3-element Dictionary{String,Int64}
 "a" │ 1
 "b" │ 2
 "c" │ 3

julia> dictionary(["a"=>1, "b"=>2, "c"=>3, "a"=>4])
3-element Dictionary{String,Int64}
 "a" │ 1
 "b" │ 2
 "c" │ 3

julia> dictionary(zip(["a","b","c"], [1,2,3]))
3-element Dictionary{String,Int64}
 "a" │ 1
 "b" │ 2
 "c" │ 3

distinct(itr)

Collect the distinct elements of iterator itr into a new collection. Similar to Base.unique, except returning a set (Indices) instead of an array.

Example

julia> distinct([1,2,3,3])
3-element Indices{Int64}
 1
 2
 3

gettoken!(dict, i)

Return the tuple (hadindex, token), where hadindex is true if i previously existed in dict, or false otherwise (in which case dict was mutated to insert a slot for the new index i). The token may be used to retrieve a value using the gettokenvalue or set a corresponding value via the settokenvalue!.

See also gettoken and deletetoken!.

gettoken(dict, i)

Return the tuple (hasindex, token), where hasindex is true if i exists in dict. The token can be used to retrieve a value using the gettokenvalue function. You can check if a token is assigned to a valid Julia object (i.e. not #undef) via istokenassigned.

Settable (i.e. mutable) dictionaries allow you to set a corresponding value via the settokenvalue! function (see the issettable trait).

Insertable dictionaries provide the gettoken! function (see the isinsertable trait).

index(f, iter)

Return a dictionary associating the values x of iterable collection iter with the key f(x). If keys are repeated, only the first is kept. Somewhat similar to unique(f, iter)

See also the dictionary function.

Examples

julia> index(first, ["Alice", "Bob", "Charlie"])
3-element Dictionary{Char,String}
 'A' │ "Alice"
 'B' │ "Bob"
 'C' │ "Charlie"

julia> index(iseven, 1:10)
2-element Dictionary{Bool,Int64}
 false │ 1
  true │ 2

isdictequal(d1, d2)

Determine if two dictionaries are equivalent. Dictionaries d1 and d2 are equivalent if issetequal(keys(d1), keys(d2)) and for each key i, d1[i] == d2[i].

Example

julia> isdictequal(Dictionary(['a','b'],[1,2]), Dictionary(['b','a'],[2,1]))
true

julia> isdictequal(Dictionary(['a','b'],[1,2]), Dictionary(['b','a'],[2,3]))
false

julia> isdictequal(Dictionary(['a','b'],[1,2]), Dictionary(['b','a'],[2,missing]))
missing

isinsertable(dict::AbstractDictionary)

Return true if dict supports the insertable interface, or false otherwise. The primary functions dict needs to implement for the insertable interface are:

• insert!(dict, i, value) - add a new value at index i (will error if index exists)
• delete!(dict, i) - remove element at index i (will error if index does not exist)

Functions get!, set! and unset! are also provided for common operations where you are not sure if an index exists or not. New insertable dictionaries are primarily generated via the empty function.

See also issettable and istokenizable.

isinsertable(indices::AbstractIndices)

Return true if indices supports the insertable interface, or false otherwise. The primary functions a map needs to implement for the insertable interface are:

• insert!(indices, i) - add new index i to indices (will error if index exists)
• delete!(indices, i) - remove an existing index i from indices (will error if index does not exist).

Functions set! and unset! are also provided for common operations where you are not sure if an index exists or not. New insertable indices are primarily generated via the empty function.

issettable(dict::AbstractDictionary)

Return true if the dictionary dict obeys the settable interface, or false otherwise.

A mutable dictionary is one where the values can be modified (but not necessarily the indices). The mutable interface requires the dictionary to implement:

• setindex!(dict::AbstractDictionary{I, T}, value::I, index::T)

New settable dictionaries are primarily created through the similar function (for uninitialized values), as well as fill, zeros, ones, trues and falses (for initialized values).

See also isinsertable.

istokenizable(indices::AbstractIndices)

Return true if the indices indices obeys the token interface, or false otherwise.

A token is a more efficient way of referring to an element of indices. Using tokens may help avoid multiple index lookups for a single operation.

A tokenizable indices must implement:

• tokentype(indices) --> T::Type
• iteratetoken(indices, s...) iterates the tokens of indices, like iterate
• gettoken(indices, i) --> (hasindex::Bool, token)
• gettokenvalue(indices, token) returning the value of the index at token

An isinsertable tokenizable indices must implement

• gettoken!(indices, i) --> (hadtoken::Bool, token)

• deletetoken!(indices, token) --> indices

  istokenizable(dict::AbstractDictionary)

Return true if the dictionary dict obeys the token interface, or false otherwise.

A token is a more efficient way of referring to an element of dict. Using tokens may help avoid multiple index lookups for a single operation.

An tokenizable dictionary must implement:

• keys(dict) must be istokenizable and share tokens with dict
• gettokenvalue(dict, token) returning the dictionary value at token
• istokenassigned(dict, token) --> Bool

An issettable tokenizable dictionary must implement:

• settokenvalue!(dict, token)

An isinsertable tokenizable dictionary must implement:

• gettoken!(dict, i) --> (hadtoken::Bool, token)
• deletetoken!(dict, token) --> dict

set!(dict::AbstractDictionary, i, value)

Update or insert the value at index i into dict. Sometimes referred to as an "upsert" operation.

Hint: Use setindex! to exclusively update an existing value, and insert! to exclusively insert a new value. See also get!.

set!(indices::AbstractIndices, i)

Insert a new value i into indices if it doesn't exist, or do nothing otherwise.

setwith!(f, dict::AbstractDictionary, i, value)

Update the value at i with the function f (f(dict[i], value)) or insert value.

Hint: Use mergewith! to merge Dictionarys together.

sharetokens(dict1, dict2)

Return true if dict1 and dict2 obviously share tokens, using a test which can be performed quickly (e.g. O(1) rather than O(N)). Return false otherwise.

Note: the test may not be precise, this defaults to tokens(dict1) === tokens(dict2).

sortkeys!(dict::AbstractDictionary; kwargs...)

Modify dict so that it is sorted by keys(dict). The kwargs are the usual ordering options supported by sort. Note that this only works on supported types.

See also sortkeys, sort! and sortpairs!.

sortkeys(dict::AbstractDictionary; kwargs...)

Return a copy of dict sorted by keys(dict). The kwargs are the usual ordering options supported by sort.

See also sortkeys!, sort and sortpairs.

sortpairs!(dict::AbstractDictionary; kwargs...)

Modify dict so that it is sorted by pairs(dict). The kwargs are the usual ordering options supported by sort.

See also sortpairs,sort! and sortkeys!.

sortpairs(dict::AbstractDictionary; kwargs...)

Return a copy of dict sorted by pairs(dict). The kwargs are the usual ordering options supported by sort.

See also sortpairs!,sort and sortkeys.

tokenized(dict::AbstractDictionary)

For istokenizable dictionary dict, return a container that supports getindex(dict, token) and isassigned(dict, token), where token ∈ tokens(dict).

If issettable(dict) then the result should also support setindex!(dict, value, token).

Note: the output is not necessarily an AbstractDictionary.

tokens(dict::AbstractDictionary)

Return a new dictionary mapping from the keys of dict to a "token". The token can be used to fetch a value with gettokenvalue. For mutable containers, the token can be used to overwrite a value with settokenvalue!.

tokentype(dict)

Return the type of the tokens retrieved via gettoken for dictionary dict, for dictionaries that are istokenizable.

unset!(indices::AbstractIndices, i)

Delete the index i from indices if it exists, or do nothing otherwise.

unset!(dict::AbstractDictionary, i)

Delete the index i from dict if it exists, or do nothing otherwise.

See also delete!, set!.