Sorted Containers

Added sorted containers to DataStructures, testing, and documentation.
Replaced README.md with README.rst
[Note to David Sanders: If you send me your email address, I can directly
cc you on my messages sent to github.  My email address is
vavasis@uwaterloo.ca.]

Kevin,

I can certain rename "index".  "Reference" is probably already overused in
Julia (e.g., see newgroup postings about 'call-by-reference'), but "token"
is good.  Other choices could be "address" or "handle".  Let me know which
of these (token, address, handle) you like best.

With regard to removing the index functionality from SortedDict, I'm not
seeing what is the rationale.  It doesn't simplify the code review since
the heavy-duty functions in balancedTree won't change.  It is not clear to
me why users would ever want to replace a SortedDict with a Dict in a
drop-in manner.  They wouldn't opt for the extra complexity of setting up
a SortedDict in the first place unless they already needed the extra
functionality of iterating in sorted order.

Furthermore, removing index functionality from SortedDict now and
postponing it until later has the disadvantage that someone who needs this
functionality may incorporate the 'base class' BalancedTree into his/her
code instead of waiting for us to get it into SortedDict.  This would be
bad because we want to be able to arbitrarily change the base class (e.g.,
switch BalancedTree to LLRB trees if someone wants to write that) while
leaving the interface class SortedDict stable.

-- Steve



On Mon, 1 Sep 2014, Kevin Squire wrote:

> 
> In README.rst:
> 
> > +the address of a specific (key,value) pair (in the case of SortedDict
> > +and MultiMap) or key (in the case of Sorted Set) and can be
> > +dereferenced in O(1) time.  (For readers familiar with C++ standard
> > +containers, this notion of index is similar to the C++ iterator.  The
> > +main difference is that indices in this package are array subscripts and
> > +cannot be dereferenced without knowledge of the container, whereas C++ iterators
> > +are essentially memory addresses that can be dereferenced by themselves.)
> > +An index can be advanced or regressed via the functions 
> > +``advance_ind`` and ``regress_ind``.  There are two special values that
> > +the index may take: the *before-start* value and the *past-end* value.  These special
> > +values act as lower and upper bounds
> > +on the actual data.  The before-start index can be advanced,
> > +while the past-end index can be regressed.  A dereferencing operation on either
> > +leads to an error.  In the current release, an index is stored
> > +as an integer.
> > +
> 
> Some thoughts about indices:
>
>  1.
>
>     In Julia, index already refers to
>
>     a. the location of an element in an array (which also happens to correspond to the rank when
>     iterating)
>     b. more generally for collections, the value in brackets that is passed to getindex and
>     setindex! (e.g., a[19], d["key"], etc.)
>
>     While your use of index is related to both, it isn't really either one. Would you consider
>     using a different term to indicate a reference to a node, e.g., node_ref or token?
>
>     I would prefer something like token, because in theory, this interface could also apply to the
>     existing Dict implementation, which doesn't have nodes.
>
>  2.
>
>     My preconceived hope about (and preference for) a SortedDict implementation was that it could
>     follow the existing Associative/Dict interface exactly, making it drop-in exchangeable for any
>     Dict, with changes only in behavior (e.g., the keys would be sorted) and performance (e.g.,
>     lookup is O(log N)). As soon as a user starts using an index/token however, the reverse is no
>     longer true--Dicts are no longer a drop in replacement for SortedDicts (ignoring the sorting
>     part, of course).
>
>     Maybe that's not a big deal, and I can certainly see the value in having the indexes(tokens).
>     My preference, however, would be to separate out the indexing into another pull request (at
>     least for SortedDict--BalancedTrees can certainly keep that functionality). After this
>     implementation gets accepted, the indexing could be submitted, and we can explore implementing
>     the index/token functionality for hash-based dictionaries, so that the implementations can
>     stay compatible. Thoughts?
> 
> —
> Reply to this email directly or view it onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyNTE3OTM0MSwiZGF0YSI6eyJpZCI6
> NDA1Mjk5MDR9fQ==--4bd4d049e967b3be7e0c41a30304acd1ba630bc6.gif]
> 
> 
>