shifted lowerBound with ranges

A. Bressan invalid at nospam.donotuse
Sun Jun 23 17:38:47 UTC 2019


Hi, I am trying to convert some pointer based C++ code to ranges.

Given a sorted list of numbers w and a value v, I want to extract 
a sublist containing
exactly s numbers <=v and all numbers >v.

The following code "works", but it is ugly:
-the result of shiftedLowerBound is not a slice of the original 
array and it has a different type
-if the operation is repeated with increasing v the search 
algorithm cannot use the result of the previous computation.

I looked at the code of std.range and it seems that the result 
can be achieved by using the function getTransitionIndex of 
SortedRange, but it is private. Am I overlooking something that 
makes it possible to achieve my goal using the range interface?

-----------------------------------------

import std.stdio;
import std.range;
import std.algorithm;

auto shiftedLowerBound(W,V)(W w, V v, long s )
{
     auto ws=assumeSorted(w);
     auto pps=ws.trisect(v);
     long k=pps[1].length-s;
     return chain( (pps[0])[$+min(k,0)..$], (pps[1])[max(k,0)..$], 
pps[2] );
}

void main()
{
     long[] 
w=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15,15,15,16,17,18,19,20,21];
     long[] vs=[10,15];
     int s=6;
     foreach(v;vs)
     {
         writeln(w.shiftedLowerBound(v,s));
     }
}


More information about the Digitalmars-d-learn mailing list