www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - proposition to std.range: SortedRange.indexOf(value)

reply Alexander Tankeev <atankeev gmail.com> writes:
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.
Dec 19 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 19 2012
next sibling parent reply Alexander Tankeev <atankeev gmail.com> writes:
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.
Dec 19 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 19 2012
prev sibling parent "Alexander Tankeev" <atankeev gmail.com> writes:
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.

No such element - equalRange.length == 0 All indexes - [lowerBound.length..lowerBound.length+equalRange.length]
 Andrei

Dec 19 2012