D graph library -- update

[Dmitry Olshansky]

12-Jul-2013 02:23, 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?

Yup, but done in one step. I'd put it the other way around: simply put 
this is inserting an item into a sorted range => binary search + insert. 
An insertion sort is built around this operation performed repeatedly.

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

Append new value to values.

Then use 'values.length-1' (new length - 1 i.e. the old length) as an 
item to insert into sortedIndices.

The last step is to figure out what range to call lowerBound on - I'd 
say something like:

assumeSorted(sortedIndices.map!(x => values[x]))

then use that to find a suitable place to insert in sortedIndices.
>
> ... 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.
>


-- 
Dmitry Olshansky