Sorted dict 1

Pull request for SortedDict and BalancedTree23 taking into account Kevin Squire's feedback from the past 12 days.
Thanks for the updates, Steve. I'll try to provide more detailed responses
to your other messages at some point, although it might not be until next
week.

On Wednesday, October 8, 2014, StephenVavasis <notifications@github.com>
wrote:

> In src/sortedDict.jl:
>
> > +    bt1 = BalancedTree23{K,D,Ord}(o)
> > +    for pr in d
> > +        insert!(bt1, pr[1], pr[2], false)
> > +    end
> > +    SortedDict(bt1)
> > +end
> > +
> > +
> > +
> > +## An SDToken is a small structure for iterating
> > +## over the items in a sorted dict order.  It is
> > +## a wrapper around an (SortedDict,Int) pair; the int is the index
> > +## of the current item in t.data.  An iterator
> > +## should never point to a deleted item.  An iterator
> > +## that points to the before-start item (=1)
> > +## or the after-end item (=2) cannot be  dereferenced.
>
> Kevin, There is some issue in Julia with parametric typealias creating
> subtypes. I have posted it as issue 8625:
> https://github.com/JuliaLang/julia/issues/8625 As a consequence of this
> issue, I will have to put in many apparently unnecessary parameter
> specifications {K,D,Ord} into sortedDict.jl even though I took them all out
> in the last round of revision at your suggestion. If this issue gets
> resolved, then I guess later I can remove them again. Unfortunately, this
> issue will needlessly clutter the code.
> … <#148f086e2e8b2424_>
> -- Steve
> On Tue, 23 Sep 2014, Kevin Squire wrote: In src/sortedDict.jl: > + bt1 =
> BalancedTree23{K,D,Ord}(o) > + for pr in d > + insert!(bt1, pr[1], pr[2],
> false) > + end > + SortedDict(bt1) > +end > + > + > + > +## An SDToken is a
> small structure for iterating > +## over the items in a sorted dict order.
> It is > +## a wrapper around an (SortedDict,Int) pair; the int is the index
> > +## of the current item in t.data. An iterator > +## should never point
> to a deleted item. An iterator > +## that points to the before-start item
> (=1) > +## or the after-end item (=2) cannot be dereferenced.
> Organizationally, I think it would be nice to have all token related
> functions grouped together, probably in a separate file, and possibly in
> their own Tokens submodule. The notion of a token could then be generalized
> to apply to hash-based dictionaries. Not everything would apply, of course,
> but it would make it easier to, e.g., delete items without hashing the key
> twice. The implementation could look something like this: module Tokens #
> modules and types can't have the same name in Julia abstract AbstractToken
> abstract AbstractSemiToken immutable SemiToken <: AbstractSemiToken
> address::Int end immutable Token{T<:Associative, S<:AbstractSemiToken} m::T
> address::S end typealias SDToken Token{SortedDict, SemiToken} ... This
> would also allow encapsulation and simplification of some of the names
> below--e.g., validtoken and findtoken would become Tokens.valid and
> Tokens.find, respectively. What do you think? — Reply to this email
> directly or view it
> onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyNzA5MjMwNiwiZGF0YSI6eyJpZCI6NDE3MzQ5Mjl9fQ==--f5
> 42033003b86edbabe4830283d024469412dc9f.gif]
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/JuliaLang/DataStructures.jl/pull/53/files#r18593269>.
>