Hello, world.

I find very useful and clean interface that provides SortedRange, but it was disappointing that it have binarySearch to answer does it .contains(value), but can't return the .indexOf(value). In my opinion it should be part of the interface.

--
Sincerely yours, Alexander Tankeev.

On 12/19/12 11:03 AM, Alexander Tankeev wrote:
> Hello, world.
>
> I find very useful and clean interface that provides SortedRange, but it
> was disappointing that it have binarySearch to answer does it
> .contains(value), but can't return the .indexOf(value). In my opinion it
> should be part of the interface.

What to return if there are several indexes for a value? That's why the more general lowerBound, upperBound, equalRange, and trisect are defined.

Andrei

On 12/19/2012 08:19 PM, Andrei Alexandrescu wrote:

>> I find very useful and clean interface that provides SortedRange, but it
>> was disappointing that it have binarySearch to answer does it
>> .contains(value), but can't return the .indexOf(value). In my opinion it
>> should be part of the interface.

> What to return if there are several indexes for a value? That's why the
> more general lowerBound, upperBound, equalRange, and trisect are defined.

Ok, and what if value isn't in Range at all? How lowerBound, upperBound, equalRange can help in such case?

auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 10, 11, 12, 14 ]);
auto p = a.lowerBound(7);
assert(equal(p, [0, 1, 2, 3, 4, 5]))

Sure I can do .contains(value) and then index is .lowerBound(value).length but it's 2 searches where 1 could be enough.

And what if you need all indexes of equal elements? Then you should do 3 searches where 1 could be enough.

On 12/19/12 11:45 AM, Alexander Tankeev wrote:
> On 12/19/2012 08:19 PM, Andrei Alexandrescu wrote:
>
>>> I find very useful and clean interface that provides SortedRange, but it
>>> was disappointing that it have binarySearch to answer does it
>>> .contains(value), but can't return the .indexOf(value). In my opinion it
>>> should be part of the interface.
>
>> What to return if there are several indexes for a value? That's why the
>> more general lowerBound, upperBound, equalRange, and trisect are defined.
>
> Ok, and what if value isn't in Range at all? How lowerBound, upperBound,
> equalRange can help in such case?
>
> auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 10, 11, 12, 14 ]);
> auto p = a.lowerBound(7);
> assert(equal(p, [0, 1, 2, 3, 4, 5]))

Take the length of the lower bound and compare it against the length of the sorted range.

auto firstIndex = p.length;
if (firstIndex < a.length) { ... found ... }

> Sure I can do .contains(value) and then index is
> .lowerBound(value).length but it's 2 searches where 1 could be enough.
>
> And what if you need all indexes of equal elements? Then you should do 3
> searches where 1 could be enough.

Use trisect for that.


Andrei

On Wednesday, 19 December 2012 at 17:57:45 UTC, Andrei Alexandrescu wrote:

>> And what if you need all indexes of equal elements? Then you should do 3
>> searches where 1 could be enough.
>
> Use trisect for that.
Ok, right. All cases can be checked by trisect. Thanks a lot.
No such element - equalRange.length == 0
All indexes - [lowerBound.length..lowerBound.length+equalRange.length]

> Andrei
Sincerely yours, Alexander.