Implement Base.Iterator interface for branch and prune routine

[gwater]

Hi, I found this package really useful so I thought I'd propose this feature:

It splits the branch_and_prune() routine up so it can be inspected at every iteration by implementing the Base.Iterator interface. A few other packages like DifferentialEquations.jl (for Integrators) and ProximalAlogrithms.jl use similar approaches. Iterators can be used to visualize the algorithms and probably other nifty things.

The changes have negligible impact on speed and memory. In fact, they remove a minor type instability from branch_and_prune() by making the type of outputs predictable. The existing API is unchanged, but a new type RootSearch is exported which implements the appropriate Iterator methods. (Introducing a type to indicate the search strategy might also be useful for #22.)

[codecov-io]

Codecov Report

Merging #60 into master will increase coverage by 1.97%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master      #60      +/-   ##
==========================================
+ Coverage   44.34%   46.31%   +1.97%     
==========================================
  Files           9        9              
  Lines         327      339      +12     
==========================================
+ Hits          145      157      +12     
  Misses        182      182

Impacted Files	Coverage Δ
src/roots.jl	85.24% <100%> (+3.61%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update beb47c1...5f2af1d. Read the comment docs.

[dpsanders]

Hi, this is great, thanks a lot!

Could you please add an example and a test of how to use the iterator interface?

[gwater]

Thanks, I added a simple use case to examples/roots.jl. However, I'm not sure what test case we need: The Iterator methods are almost completely covered by existing unit tests (through branch_and_prune()). We could use InterfaceTesting.jl to be really thorough but it seems they haven't caught up with julia 0.6 yet.

[gwater]

I came up with some simple test cases for the previously uncovered methods (which immediately uncovered bugs in each one.)

[dpsanders]

I like the idea of introducing a type for the search strategy. I guess that's for a different PR? Or would you like to include it here?

[gwater]

I think the different search strategies should be dealt with in a seperate PR because they have a lot more impact on users than this mostly "under the hood" change. There will probably need to be some discussion about defaults, etc.

[dpsanders]

I wonder if we could / should introduce the ability to call a callback function to facilitate interacting with the root search? In any case, I think this is good to merge.

Many thanks!

[gwater]

Regarding, the callback function I'm of two minds: On one hand it would be very easy to implement and there would be no cost. On the other hand effectively using it would require detailed knowledge of the internals; in which case one could just do what I did in the example and the callback would be superfluous.

[gwater]

It might be useful to expose some specific break conditions though:

• a maximum number of iterations
• a maximum number of intervals / memory limit (#59 )

It should be quite easy to include these in the revised branch_and_prune().

[dpsanders]

Thanks. I'm curious what your particular use case is?

[gwater]

Sure, I've hinted at this a few times: I think it would be cool to visualize intervals splitting and vanishing/shrinking. I'm working on an eigenvalue problem for a delay differential equation and I'd like to give people an impression of the algorithm used to solve it.