[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