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