feat(bisect): lift the binary search's speculation to Search
Previously, midpoint returned an iterator of next nodes to search, which is meant to support speculative searching. This was implemented only for the basic binary search. It could be tedious and error-prone to implement speculation by one's self, so it would be preferable if the library could do it instead. This commit lifts the speculation out of the binary search and into Search.
Now, midpoint returns a single next node to search, which is substantially easier for implementors (for example, the implementation of binary search is now simply picking and returning the midpoint node).
This commit fixes an arguable bug in the binary search implementation, where it didn't quite go in breadth-first order, and also incidentally implements breadth-first ordering for the linear search (assuming that the input nodes are originally given in topological order).
Stack:
feat(bisect): lift the binary search's speculation to
SearchPreviously,
midpointreturned an iterator of next nodes to search, which is meant to support speculative searching. This was implemented only for the basic binary search. It could be tedious and error-prone to implement speculation by one's self, so it would be preferable if the library could do it instead. This commit lifts the speculation out of the binary search and intoSearch.Now,
midpointreturns a single next node to search, which is substantially easier for implementors (for example, the implementation of binary search is now simply picking and returning the midpoint node).This commit fixes an arguable bug in the binary search implementation, where it didn't quite go in breadth-first order, and also incidentally implements breadth-first ordering for the linear search (assuming that the input nodes are originally given in topological order).