Re: How to use lowerBound and upperBound effectively?

[A. Bressan via Digitalmars-d-learn]

On Tuesday, 2 July 2019 at 17:07:25 UTC, Ali Çehreli wrote:

On 07/02/2019 02:27 AM, A. Bressan wrote:

> contrary to C++, lowerBound and
> upperBound give the same piece of information because they
return
> complementary sub-ranges.

I don't understand the specific problem but can 'trisect' be 
useful?


  https://dlang.org/library/std/range/sorted_range.trisect.html

Ali


I try to clarify the problem, sorry for not being clearer.

Given a value 'v', 'std::lower_bound' returns an iterator 
pointing to the first element 'a' for which 'a'std::upper_bound' returns an iterator to the first element 'a' 
between a pair of iterators for which 'a<=v' is false. Thus the 
two C++ functions find a different point.


The D function 'lowerBound' returns a range containing all 
elements 'first element '>=v' by using length.
'upperBound' returns a range containing all elements '>=v'. Again 
it is possible to recover the position of the first element '>=v' 
by subtracting the length of the returned range from the original 
length.
Thus 'lowerBound' and 'upperBound' provide the same piece of 
information: the position of the first element '>=v'. I need the 
position of the first element '>v'.


v=5
data  [1,2,3,4,5,5,6,7,8,9]
std::lower_bound   ^
std::upper_bound   ^
lowerBound ___
upperBound ___


My current solution is to reverse the range and the ordering so 
that I can pin-point the correct location.


v=5
data  [9,8,7,6,5,5,4,3,2,1]
std::lower_bound   ^
std::upper_bound   ^
lowerBound ___
upperBound ___

My question is motivated by the fact that the search policies 
(except the linear scan)  are variants of the bisection method 
https://en.wikipedia.org/wiki/Bisection_method
and can find both the first element '>=v' or the first element 
'>v' by changing the predicate '>=' for '>'. It seems to me that 
there must be a simpler way and that I am overlooking something.


The 'trisect' method, provides both the position of first element 
'>=v' and that of  the first element '>v'. So it provides more 
than what I need, but it is nicer to read and maybe faster than 
my solution.


Thanks

Andrea

How to use lowerBound and upperBound effectively?

[A. Bressan via Digitalmars-d-learn]

Hi, I am translating the following C++ code to D and I have some 
trouble to achieve it using ranges.


#include 
#include 

typedef std::vector::const_iterator iter;
std::pair getSubVector(iter beg, iter end, int val, 
int shift)

{
return {std::upper_bound(beg,end,val)-shift,end};
}

My best result is the following convoluted code, is there a 
better way?


auto getSubVector(T)(const ref T vec, int val, int shift)
if (isInstanceOf!(SortedRange, T))
{
auto 
begin=vec.length-assumeSorted!"a>b"(retro(vec)).lowerBound().length-shift;

return vec[begin..$];
}

The difficulty I have is that, contrary to C++, lowerBound and 
upperBound give the same piece of information because they return 
complementary sub-ranges.
To get the elements that are equal to val outside of the 
upperBound I need to reverse the range.


I tried to use lowerBound on a range sorted by "a<=b", but it 
triggers an error that does not seem to be relevant to binary 
search strategies:


std/algorithm/sorting.d(178): Predicate for isSorted is not 
antisymmetric. Both pred(a, b) and pred(b, a) are true for 
certain values.

shifted lowerBound with ranges

[A. Bressan via Digitalmars-d-learn]

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));
}
}