Sorted dict 1

Pull request for SortedDict and BalancedTree23 taking into account Kevin Squire's feedback from the past 12 days.
Kevin,

Just for your information, I am planning to carry out this suggestion with 
one small change: in the definition of Token, T will not be declared a 
subtype of Associative.  The reason is that I also need tokens for 
MultiMap and SortedSet, which are not subtypes of Associative.

I guess there is a vague plan to have an abstract type called Iterable in 
the future; in this case T could be a subtype of Iterable.

-- 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__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyNzA5MjMwNiwiZGF0YSI6eyJpZCI
> 6NDE3MzQ5Mjl9fQ==--f542033003b86edbabe4830283d024469412dc9f.gif]
> 
> 
>