[Issue 12763] New: std.range.SearchPolicy.binarySearch for InputRanges too

via Digitalmars-d-bugs digitalmars-d-bugs at puremagic.com
Sun May 18 01:15:07 PDT 2014


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 at puremagic.com
          Reporter: bearophile_hugs at 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.

--


More information about the Digitalmars-d-bugs mailing list