JuliaLang/julia — pull request #4038 by kmsquire (2013-08-13 01:58:26+00:00)
Title: WIP: OrderedDict redux

This is yet another redo of OrderedDict.

Unlike previous versions, this version grafts ordering onto the current Dict infrastructure directly, with no impact to the performance of unordered dicts.

```julia
julia> a = OrderedDict{String, Int}()
Dict{String,Int64,Int64}()

julia> for i = 1:5
a[randstring(3)] = i
end

julia> a
["0MO"=>1,"91h"=>2,"XtG"=>3,"iYN"=>4,"BH5"=>5]

julia> b = (String=>Int)[]
Dict{String,Int64,Nothing}()

julia> for i = 1:5
b[randstring(3)] = i
end

julia> b
["UiE"=>5,"IWn"=>1,"Un0"=>2,"17V"=>4,"PCQ"=>3]

julia> a = OrderedSet(5,4,3,2,1)
Set{Int64,Int64}(5,4,3,2,1)

julia> a = Set(1,2,3,4,5)
Set{Int64,Nothing}(5,4,2,3,1)
```

Features:
* adds two arrays to Dict which maintain the ordering and the mapping to hashmap key/value locations in the hashmap.
* uses element type Nothing for these arrays for unordered dicts (see https://github.com/JuliaLang/julia/commit/42ce80651e310da4593faeec2378c8d378208fa5)
* adds ordered versions of `Dict` functions, reusing `Dict` code where possible.
* type abuse: `OrderedDict{K,V}()` type constructor returns a `Dict{K,V,Ordered}`
* this lets us call `OrderedDict{K,V}()`, and also have `OrderedDict()` outer constructors
* ditto with `OrderedSet{K}`
* `(K=>V)[]` creates a `Dict{K,V,Unordered}`

Downsides:
* Requires specifying `Ordered` or `Unordered` when calling the main `Dict` or `Set` constructor explicitly

---------

Comments:
* Type parameterization
* Passing `Unordered` as a type parameter to the `Dict`/`Set` constructors is annoying. For Dict, `(K=>V)` is a good alternative; there's nothing like that for `Set`
* Alternative: could create an `UnorderedDict()` or `UnorderedSet`, which is the same amount of typing.
* Request: @JeffBezanson is it possible to defaults for unspecified type parameters?
* Another remote possibility: deprecate `{}` for `Any[]`, and reserve `{}` for Set notation?
* Type system abuse
* `Base.Order.Reverse` can return `Order.Forward` (but only under rare circumstances)
* Would prefer to use an alias as a constructor, but see #3427.

I'm actually less concerned about the type abuse than the extra type parameter to `Dict`/`Set`. Any thoughts/suggestions welcome.