• via Digitalmars-d-bugs (35/40) May 18 2014 https://issues.dlang.org/show_bug.cgi?id=12763

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=12763

          Issue ID: 12763
           Summary: std.range.SearchPolicy.binarySearch for InputRanges
                    too
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

void main() {
    import std.stdio, std.algorithm, std.range;
    auto odds = 30.iota.filter!q{ a % 2 }.assumeSorted;
    odds.upperBound(12).writeln;
}



DMD 2.066alpha gives:

C:\dmd2\src\phobos\std\range.d(8613,9): Error: static assert  "Specify
SearchPolicy.linear explicitly for SortedRange!(FilterResult!(unaryFun,
Result), "a < b")"
temp.d(4,20):        instantiated from here: upperBound!(cast(SearchPolicy)3,
int)



The code compiles and works if I add SearchPolicy.linear:


void main() {
    import std.stdio, std.algorithm, std.range;
    auto odds = 30.iota.filter!q{ a % 2 }.assumeSorted;
    odds.upperBound!(SearchPolicy.linear)(12).writeln;
}



But monarch_dodra said:

 for a sorted linked list (or forward iterators in general), 
 you can find the result with O(N) *walk* iterations, but still 
 only O(log(N)) *comparison* iterations.

 It's not used in phobos (as far as I know of anyways). It *could* 
 be implemented in SortedRange's BinaryFind though.


I think it's worth supporting SearchPolicy.binarySearch (that is the default
one for upperBound) for InputRanges too.

--