www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - The return of std.algorithm.find

reply RazvanN <razvan.nitu1305 gmail.com> writes:
The find function which receives an input haystack and a needle 
returns the haystack advanced to the first occurrence of the 
needle. For normal ranges this is fine, but for
sorted ranges (aka SortedRange) it is a bit odd. For example:

find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 
7]. This is in terms with the general policy of the find 
function, but is weird. Since we know the range is sorted, 
shouldn't the result be [1, 2, 4]?
Nov 15 2016
next sibling parent reply drug <drug2004 bk.ru> writes:
15.11.2016 12:43, RazvanN пишет:

 The find function which receives an input haystack and a needle returns
 the haystack advanced to the first occurrence of the needle. For normal
 ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 7]. This
 is in terms with the general policy of the find function, but is weird.
 Since we know the range is sorted, shouldn't the result be [1, 2, 4]?


I don't think so. You could use findSplit, it returns three ranges [1, 
2], [4], [5, 6, 7].
Nov 15 2016
parent reply drug <drug2004 bk.ru> writes:
15.11.2016 12:48, drug пишет:

 15.11.2016 12:43, RazvanN пишет:

 The find function which receives an input haystack and a needle returns
 the haystack advanced to the first occurrence of the needle. For normal
 ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 7]. This
 is in terms with the general policy of the find function, but is weird.
 Since we know the range is sorted, shouldn't the result be [1, 2, 4]?


 I don't think so. You could use findSplit, it returns three ranges [1,
 2], [4], [5, 6, 7].


See also SortedRange.trisect
Nov 15 2016
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/15/2016 01:50 AM, drug wrote:

 15.11.2016 12:48, drug пишет:

 15.11.2016 12:43, RazvanN пишет:

 The find function which receives an input haystack and a needle returns
 the haystack advanced to the first occurrence of the needle. For normal
 ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 7]. This
 is in terms with the general policy of the find function, but is weird.
 Since we know the range is sorted, shouldn't the result be [1, 2, 4]?


 I don't think so. You could use findSplit, it returns three ranges [1,
 2], [4], [5, 6, 7].


 See also SortedRange.trisect


Indeed. This is what I was typing:

import std.stdio;
import std.range;

void main() {
     auto r = assumeSorted([1, 2, 4, 5, 6, 7]);
     auto found = r.trisect(4);

     auto desired = chain(found[0], found[1]);
     writeln(desired);
}

Prints

[1, 2, 4]

Ali
Nov 15 2016
prev sibling next sibling parent reply RazvanN <razvan.nitu1305 gmail.com> writes:
On Tuesday, 15 November 2016 at 09:43:27 UTC, RazvanN wrote:

 The find function which receives an input haystack and a needle 
 returns the haystack advanced to the first occurrence of the 
 needle. For normal ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 
 7]. This is in terms with the general policy of the find 
 function, but is weird. Since we know the range is sorted, 
 shouldn't the result be [1, 2, 4]?


The whole function is find!"a <= b"(assumeSorted([1, 2, 4, 5, 6, 
7]), 4). And the result is
the whole range [1, 2, 4, 5, 6, 7].
Nov 15 2016
next sibling parent drug <drug2004 bk.ru> writes:
15.11.2016 12:50, RazvanN пишет:

 On Tuesday, 15 November 2016 at 09:43:27 UTC, RazvanN wrote:

 The find function which receives an input haystack and a needle
 returns the haystack advanced to the first occurrence of the needle.
 For normal ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 7].
 This is in terms with the general policy of the find function, but is
 weird. Since we know the range is sorted, shouldn't the result be [1,
 2, 4]?


 The whole function is find!"a <= b"(assumeSorted([1, 2, 4, 5, 6, 7]),
 4). And the result is
 the whole range [1, 2, 4, 5, 6, 7].


IIRC find!"a <= b" will return the first element that is less or equal 
to needle, so this will be the whole range. To find all elements of 
SortedRange that are less or equal to needle you need to use 
SortedRange.lowerBound
Nov 15 2016
prev sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 15 November 2016 at 09:50:40 UTC, RazvanN wrote:

 On Tuesday, 15 November 2016 at 09:43:27 UTC, RazvanN wrote:

 The find function which receives an input haystack and a 
 needle returns the haystack advanced to the first occurrence 
 of the needle. For normal ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 
 7]. This is in terms with the general policy of the find 
 function, but is weird. Since we know the range is sorted, 
 shouldn't the result be [1, 2, 4]?


 The whole function is find!"a <= b"(assumeSorted([1, 2, 4, 5, 
 6, 7]), 4). And the result is
 the whole range [1, 2, 4, 5, 6, 7].


Are you sure you don't want filter ?
Nov 15 2016
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/15/16 4:43 AM, RazvanN wrote:

 The find function which receives an input haystack and a needle returns
 the haystack advanced to the first occurrence of the needle. For normal
 ranges this is fine, but for
 sorted ranges (aka SortedRange) it is a bit odd. For example:

 find(assumeSorted[1, 2, 4, 5, 6, 7], 4) would return [4, 5, 6, 7]. This
 is in terms with the general policy of the find function, but is weird.
 Since we know the range is sorted, shouldn't the result be [1, 2, 4]?


A sorted range provides better mechanisms to find values as members of 
SortedRange. Don't use find(assumeSorted(...)), as it's still a linear 
search.

-Steve
Nov 15 2016