D graph library -- update

[Joseph Rushton Wakeling]

On 07/11/2013 10:43 PM, Dmitry Olshansky wrote:
> In such a case if inserting exactly one element into a sorted range you may want
> to special case it to lowerbound + insert.
> E.g. something like this:
> 
> auto idx = sortedRange.lowerbound(val).length;
> //insert should be called on array backing that sortedRange
> insert(sortedRange, idx, val);

... which would basically correspond to an insertion sort, right?

I'm quite tired on reading this so will have to think it over fresh tomorrow.
What I'm not certain of is how to tweak it given that actually here we have two
arrays:

    size_t[] values;  // doesn't change, but we've added a new value at the end
    size_t[] sortedIndices; // indices 0 .. values.length, sorted according
                            // to values[i]

... so, it's sortedIndices that we need to sort, but according to the
corresponding entries in the array of values.

Anyway, thanks for the thought -- lowerbound() is a function I've never used
before so it wouldn't have occurred to me.