Sorted Containers

Added sorted containers to DataStructures, testing, and documentation.
Replaced README.md with README.rst
On Mon, Sep 1, 2014 at 3:29 AM, Kevin Squire <notifications@github.com>
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?
>
>
+1 for a `SortedDict` that is a drop-in replacement for `Dict`.

However, in the research application for which I need a sorted associative
container, I do indeed use a lot of the C++ `map` functionality, including
`lower_bound` and decrementing iterators, so +1 for also having these
available, even though they do not make sense for a hash-based `Dict`.

By the way, it is becoming increasingly difficult to read this discussion
on GitHub. Is there anything that can be done about this?