Sorted Containers

Added sorted containers to DataStructures, testing, and documentation.
Replaced README.md with README.rst
Kevin,

I'm working through your proposed updates and making most of them.  In the 
case of possibly unneeded functions, I got rid of is_ind_past_end and 
is_ind_before_start, since is_ind_past_end(m,i) can be rephrased easily as 
i == past_end(m).

With regard to why one needs advance_ind: this function is at the heart of 
all the loop constructs.  You might suppose that since one has the loop 
constructs, one does not need advance_ind, but there are certainly cases 
where the user wants fine control over advancing indices.  See, for 
example, the code for "isequal(m1,m2)" in SortedDict.jl.  The function 
past_end(m) is needed because the termination test for a loop that 
advances over indices is i==past_end(m).  The container also uses the 
past_end index in other context (key missing, for example).

With regard to regress_ind and before_start, these seem less useful; 
indeed, I've never used the corresponding functions in C++.  But I guess 
someone might want to move backwards through a container, and there's no 
easy way to get this functionality with the other functions offered.

-- Steve





On Mon, 25 Aug 2014, Kevin Squire wrote:

> 
> In README.rst:
> 
> > +Complexity of sorted containers
> > +---------------------------------
> > +
> > +In the list of functions below, the complexity of the various
> > +operations is given.  For example, O(log *n*) means that the function
> > +requires a number of operations
> > +logarithmic in *n*, where *n* is the current size 
> > +(number of items) of the
> > +container at the time of the function call.  Note that comparing
> > +two keys is considered one 'operation' in this context, even though
> > +there are settings where comparing two keys could be expensive.
> > +
> > +
> > +---------------------------------
> > +Navigating the containers
> > +---------------------------------
> 
> Okay, there were fewer than I thought. That said, I'm wondering if all of these need to be
> exported/documented? Particularly, it's unclear how useful is_ind_past_end, before_start,
> is_ind_before_start, advance_ind, and regress_ind are (in Julia). Can you offer some
> justification/use case (beyond their existence in C++)?
> 
> —
> Reply to this email directly or view it onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyNDY1MDM3MiwiZGF0YSI6eyJpZCI6
> NDA1Mjk5MDR9fQ==--5b4d76fefb215b69190139646ae894f737a25ce2.gif]
> 
> 
>