Sorted dict 1

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

There is something going on here with Julia types that I'm not 
understanding.  Here are some declarations in my code:


abstract AbstractSemiToken
immutable IntSemiToken <: AbstractSemiToken
     address::Int
end
immutable Token{T, S <: AbstractSemiToken}
     container::T
     semitoken::S
end
typealias SDSemiToken IntSemiToken
typealias SDToken Token{SortedDict, SDSemiToken}

Recall that SortedDict is a parametrized type with three parameters, K, D, 
Ord.  Now, here is the peculiarity:  I have a method called 'status' 
(formally 'validtoken') like this:

status(i::SDToken) =  < etc >

But Julia cannot find 'status' when the test function invokes it.  The 
following code

     @assert(status(ii) == 3)
     h = assemble(m1, semi(ii))
     println("typeof(ii) = ", typeof(ii))
     println("typeof(h) = ", typeof(h))
     println("methods of status() = ", methods(status))
     @assert(status(h) == 3)


generates the following printout and error message:

typeof(ii) = Token{SortedDict{K,D,Ord<:Ordering},IntSemiToken}
typeof(h) = Token{SortedDict{Int64,Float64,ForwardOrdering},IntSemiToken}
methods of status() = # 1 method for generic function "status":
status(i::Token{SortedDict{K,D,Ord<:Ordering},IntSemiToken}) at 
c:\Users\vavasis
\Documents\.julia\v0.4\DataStructures\src\sortedDict.jl:501
ERROR: `status` has no method matching 
status(::Token{SortedDict{Int64,Float64,ForwardOrdering},IntSemiToken})

This is very strange, right?  Why does the type of ii have dummy 
parameters K,D,Ord in its signature?  (These are parameters in the 
declaration of SortedDict and not real types.)  And why is status() able 
to match ii but not h?  Is it a bug in the type system or something that I 
don't understand about parameters?

I am able to fix this error if I go through my code and reparametrize 
EVERY declaration (e.g., replace status(i::SDToken) by 
status{K,D,Ord<:Ordering}(i::SDToken{K,D,Ord})).  But this shouldn't be 
necessary and it also makes the code harder to read.

-- 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]
> 
> 
>