src/iterate.rs

/*!
Tools for separating the computational steps of an iterative algorithm from stopping rules
and reporting.

The computational step is to be implemented as a closure. That closure gets passed a `state`
parameter that implements an [`if_verbose`][AlgIteratorState::if_verbose] method that is to
be called to determine whether function values or other potentially costly things need to be
calculated on that iteration. The parameter of [`if_verbose`][AlgIteratorState::if_verbose] is
another closure that does the necessary computation.

## Simple example

```rust
# use alg_tools::types::*;
# use alg_tools::iterate::*;
let mut iter = AlgIteratorOptions{
    max_iter : 100,
    verbose_iter : Verbose::Every(10),
    .. Default::default()
};
let mut x = 1 as float;
# let mut iter_clone = iter.clone();
iter.iterate(|state|{
    // This is our computational step
    x = x + x.sqrt();
    state.if_verbose(||{
        // return current value when requested
        return x
     })
});
// or alternatively (avoiding problems with moves)
# iter = iter_clone;
for state in iter.iter() {
    // This is our computational step
    x = x + x.sqrt();
    state.if_verbose(||{
        // return current value when requested
        return x
    })
}
```
There is no colon after `state.if_verbose`, because we need to return its value. If you do something after the step, you need to store the result in a variable and return it from the main computational step afterwards.

This will print out
```output
10/100 J=31.051164
20/100 J=108.493699
30/100 J=234.690039
40/100 J=410.056327
50/100 J=634.799262
60/100 J=909.042928
70/100 J=1232.870172
80/100 J=1606.340254
90/100 J=2029.497673
100/100 J=2502.377071
```
*/

use colored::{Colorize, ColoredString};
use core::fmt::Debug;
use serde::{Serialize, Deserialize};
use cpu_time::ProcessTime;
use std::marker::PhantomData;
use std::time::Duration;
use std::error::Error;
use std::cell::RefCell;
use std::rc::Rc;
use crate::types::*;
use crate::logger::*;

/// Create the displayed presentation for log items.
pub trait LogRepr : Debug {
    fn logrepr(&self) -> ColoredString { format!("« {self:?} »").as_str().into() }
}

impl LogRepr for str {
    fn logrepr(&self) -> ColoredString { self.into() }
}

impl LogRepr for String {
    fn logrepr(&self) -> ColoredString { self.as_str().into() }
}

impl<T> LogRepr for T where T : Num {
    fn logrepr(&self) -> ColoredString { format!("J={self}").as_str().into() }
}

impl<V> LogRepr for Option<V> where V : LogRepr {
    fn logrepr(&self) -> ColoredString {
        match self {
            None    => { "===missing value===".red() }
            Some(v) => { v.logrepr() }
        }
    }
}

/// Helper struct for returning results annotated with an additional string to
/// [`if_verbose`][AlgIteratorState::if_verbose]. The [`LogRepr`] implementation will
/// display that string when so decided by the specific [`AlgIterator`] in use.
#[derive(Debug,Clone)]
pub struct Annotated<F>(pub F, pub String);

impl<V> LogRepr for Annotated<V> where V : LogRepr {
    fn logrepr(&self) -> ColoredString {
        format!("{}\t| {}", self.0.logrepr(), self.1).as_str().into()
    }
}


/// Basic log item.
#[derive(Serialize, Deserialize, Debug, Eq, PartialEq, Clone)]
pub struct LogItem<V> {
    pub iter : usize,
    // This causes [`csv`] to crash.
    //#[serde(flatten)]
    pub data : V
}

impl<V> LogItem<V> {
    /// Creates a new log item
    fn new(iter : usize, data : V) -> Self {
        LogItem{ iter, data }
    }
}

/// State of an [`AlgIterator`].
///
/// This is the parameter obtained by the closure passed to [`AlgIterator::iterate`] or
/// [`AlgIteratorFactory::iterate`].
pub trait AlgIteratorState : Sized {
    /// Call `call_objective` if this is a verbose iteration.
    ///
    /// Verbosity depends on the [`AlgIterator`] that produced this state.
    ///
    /// The closure `calc_objective` should return an arbitrary value of type `V`, to be inserted
    /// into the log, or whatever is deemed by the [`AlgIterator`]. For usage instructions see the
    /// [module documentation][self].
    fn if_verbose<V, E : Error>(self, calc_objective : impl FnOnce() -> V) -> Step<V, Self, E>;

    /// Returns the current iteration count.
    fn iteration(&self) -> usize;

    /// Indicates whether the iterator is quiet
    fn is_quiet(&self) -> bool;
}

/// Result of a step of an [`AlgIterator`]
#[derive(Debug, Serialize)]
pub enum Step<V, S, Fail : Error = std::convert::Infallible> {
    /// Iteration should be terminated
    Terminated,
    /// Iteration should be terminated due to failure
    Failure(Fail),
    /// No result this iteration (due to verbosity settings)
    Quiet,
    /// Result of this iteration (due to verbosity settings)
    Result(V, S),
}

impl<V, S, E : Error> Step<V, S, E> {
    /// Maps the value contained within the `Step`, if any, by the closure `f`.
    pub fn map<U>(self, mut f : impl FnMut(V) -> U) -> Step<U, S, E> {
        match self {
            Step::Result(v, s) =>  Step::Result(f(v), s),
            Step::Failure(e) => Step::Failure(e),
            Step::Quiet =>      Step::Quiet,
            Step::Terminated => Step::Terminated,
        }
    }
}

impl<V, S, E : Error> Default for Step<V, S, E> {
    fn default() -> Self {
        Step::Quiet
    }
}

/// An iterator for algorithms, produced by [`AlgIteratorFactory::prepare`].
///
/// Typically not accessed directly, but transparently produced by an [`AlgIteratorFactory`].
/// Every [`AlgIteratorFactory`] has to implement a corresponding `AlgIterator`.
pub trait AlgIterator : Sized {
    /// The state type
    type State : AlgIteratorState;
    /// The output type for [`Self::poststep`] and [`Self::step`].
    type Output;
    /// The input type for [`Self::poststep`].
    type Input;

    /// Advance the iterator, performing `step_fn` with the state
    fn step<F, E>(&mut self, step_fn : &mut F) -> Step<Self::Output, Self::State, E>
    where F : FnMut(Self::State) -> Step<Self::Input, Self::State, E>,
          E : Error {
        self.prestep().map_or(Step::Terminated,
                              |state| self.poststep(step_fn(state)))
    }

    /// Initial stage of advancing the iterator, before the actual step
    fn prestep(&mut self) -> Option<Self::State>;

    /// Handle step result
    fn poststep<E>(&mut self, result : Step<Self::Input, Self::State, E>)
    -> Step<Self::Output, Self::State, E>
    where E : Error;

    /// Return current iteration count.
    fn iteration(&self) -> usize {
        self.state().iteration()
    }

    /// Return current state.
    fn state(&self) -> Self::State;

    /// Iterate the `AlgIterator` until termination, erforming `step_fn` on each step.
    ///
    /// Returns either `()` or an error if the step closure terminated in [`Step::Failure´].
    #[inline]
    fn iterate<F, E>(&mut self, mut step_fn : F) -> Result<(), E>
    where F : FnMut(Self::State) -> Step<Self::Input, Self::State, E>,
          E : Error {
        loop {
            match self.step(&mut step_fn) {
                Step::Terminated => return Ok(()),
                Step::Failure(e) => return Err(e),
                _ => {},
            }
        }
    }
}

/// A factory for producing an [`AlgIterator`].
///
/// For usage instructions see the [module documentation][self].
pub trait AlgIteratorFactory<V> : Sized {
    type Iter : AlgIterator<State = Self::State, Input = V, Output = Self::Output>;

    /// The state type of the corresponding [`AlgIterator`].
    /// A reference to this is passed to the closures passed to methods such as [`Self::iterate`].
    type State : AlgIteratorState;
    /// The output type of the corresponding [`AlgIterator`].
    /// This is the output of the closures passed to methods such as [`Self::iterate`] after
    /// mappings performed by each [`AlgIterator`] implementation.
    type Output;

    /// Prepare an [`AlgIterator`], consuming the factory.
    fn prepare(self) -> Self::Iter;

    /// Iterate the the closure `step`.
    ///
    /// The closure should accept a `state` parameter (satisfying the trait [`AlgIteratorState`]).
    /// It should return the output of
    /// `state.`[`if_verbose`][AlgIteratorState::if_verbose], [`Step::Terminated`] to indicate
    /// completion for other reason, or [`Step::Failure`] for termination for failure.
    ///
    /// This method is equivalent to [`Self::prepare`] followed by [`AlgIterator::iterate`].
    #[inline]
    fn iterate_fallible<F, E>(self, step : F) -> Result<(), E>
    where F : FnMut(Self::State) -> Step<V, Self::State, E>,
          E : Error {
        self.prepare().iterate(step)
    }

    /// Iterate the closure `step`.
    ///
    /// The closure should accept a `state` parameter (satisfying the trait [`AlgIteratorState`]),
    /// It should return the output of
    /// `state.`[`if_verbose`][AlgIteratorState::if_verbose].
    ///
    /// For usage instructions see the [module documentation][self].
    ///
    /// This method is equivalent to [`Self::prepare`] followed by [`AlgIterator::iterate`]
    /// with the error type `E=`[`std::convert::Infallible`].
    #[inline]
    fn iterate<F>(self, step : F)
    where F : FnMut(Self::State) -> Step<V, Self::State> {
        self.iterate_fallible(step).unwrap_or_default()
    }

    /// Iterate the closure `step` with data produced by `datasource`.
    ///
    /// The closure should accept a `state` parameter (satisfying the trait [`AlgIteratorState`]),
    /// and a data parameter taken from `datasource`. It should return the output of
    /// `state.`[`if_verbose`][AlgIteratorState::if_verbose], [`Step::Terminated`] to indicate
    /// completion for other reason, or [`Step::Failure`] for termination for failure.
    ///
    /// If the `datasource` runs out of data, the iterator is considered having terminated
    /// successsfully.
    ///
    /// For usage instructions see the [module documentation][self].
    #[inline]
    fn iterate_data_fallible<F, D, I, E>(self, mut datasource : I, mut step : F)
    -> Result<(), E>
    where F : FnMut(Self::State, D) -> Step<V, Self::State, E>,
          I : Iterator<Item = D>,
          E : Error {
        self.prepare().iterate(move |state| {
            datasource.next().map_or(Step::Terminated, |d| step(state, d))
        })
    }

    /// Iterate the closure `step` with data produced by `datasource`.
    ///
    /// The closure should accept a `state` parameter (satisfying the trait [`AlgIteratorState`]),
    /// and a data parameter taken from `datasource`. It should return the output of
    /// `state.`[`if_verbose`][AlgIteratorState::if_verbose].
    ///
    /// If the `datasource` runs out of data, the iterator is considered having terminated
    /// successsfully.
    ///
    /// For usage instructions see the [module documentation][self].
    #[inline]
    fn iterate_data<F, D, I>(self, datasource : I, step : F)
    where F : FnMut(Self::State, D) -> Step<V, Self::State>,
          I : Iterator<Item = D> {
        self.iterate_data_fallible(datasource, step).unwrap_or_default()
    }

    // fn make_iterate<'own>(self)
    // -> Box<dyn (FnMut(dyn FnMut(&Self::State) -> Option<V>) -> ()) + 'own> {
    //     Box::new(move |step| self.iterate(step))
    // }

    // fn make_iterate_data<'own, D, I>(self, datasource : I)
    // -> Box<dyn (FnMut(dyn FnMut(&Self::State, D) -> Option<V>) -> ()) + 'own>
    // where I : Iterator<Item = D> + 'own {
    //     Box::new(move |step| self.iterate_data(step, datasource))
    // }

    /// Add logging to the iterator produced by the factory.
    ///
    /// Returns a new factory whose corresponding [`AlgIterator`] only inserts that data into the
    /// log without passing it onwards.
    ///
    /// Use as:
    /// ```rust
    /// # use alg_tools::iterate::*;
    /// # use alg_tools::logger::*;
    /// let iter = AlgIteratorOptions::default();
    /// let mut log = Logger::new();
    /// iter.into_log(&mut log).iterate(|state|{
    ///     // perform iterations
    ///     state.if_verbose(||{
    ///         // calculate and return function value or other displayed data v
    ///         return 0
    ///     })
    /// })
    /// ```
    fn into_log<'log>(self, logger : &'log mut Logger<Self::Output>)
    -> LoggingIteratorFactory<'log, Self::Output, Self>
    where Self : Sized {
        LoggingIteratorFactory {
            base_options : self,
            logger,
        }
    }

    /// Map the output of the iterator produced by the factory.
    ///
    /// Returns a new factory.
    fn mapped<U, G>(self, map : G)
    -> MappingIteratorFactory<G, Self>
    where Self : Sized,
          G : Fn(usize, Self::Output) -> U {
        MappingIteratorFactory {
            base_options : self,
            map
        }
    }

    /// Adds iteration number to the output.
    ///
    /// Returns a new factory.
    /// Typically followed by [`Self::into_log`].
    fn with_iteration_number(self)
    -> MappingIteratorFactory<fn(usize, Self::Output) -> LogItem<Self::Output>, Self>
    where Self : Sized {
        self.mapped(LogItem::new)
    }

    /// Add timing to the iterator produced by the factory.
    fn timed(self) -> TimingIteratorFactory<Self>
    where Self : Sized {
        TimingIteratorFactory(self)
    }

    /// Add value stopping threshold to the iterator produce by the factory
    fn stop_target(self, target : Self::Output) -> ValueIteratorFactory<Self::Output, Self>
    where Self : Sized,
          Self::Output : Num {
        ValueIteratorFactory { base_options : self, target : target }
    }

    /// Add stall stopping to the iterator produce by the factory
    fn stop_stall(self, stall : Self::Output) -> StallIteratorFactory<Self::Output, Self>
    where Self : Sized,
          Self::Output : Num {
        StallIteratorFactory { base_options : self, stall : stall }
    }

    /// Is the iterator quiet, i.e., on-verbose?
    fn is_quiet(&self) -> bool { false }

    /// Returns an an [`std::iter::Iterator`] that can be used in a `for`-loop.
    fn iter(self) -> AlgIteratorIterator<Self::Iter> {
        AlgIteratorIterator {
            algi : Rc::new(RefCell::new(self.prepare())),
        }
    }

    /// Returns an an [`std::iter::Iterator`] that can be used in a `for`-loop,
    /// also inputting an initial iteration status calculated by `f` if needed.
    fn iter_init(self, f : impl FnOnce() -> <Self::Iter as AlgIterator>::Input)
    -> AlgIteratorIterator<Self::Iter> {
        let mut i = self.prepare();
        let st = i.state();
        let step : Step<<Self::Iter as AlgIterator>::Input, Self::State> = st.if_verbose(f);
        i.poststep(step);
        AlgIteratorIterator {
            algi : Rc::new(RefCell::new(i)),
        }
    }
}

/// Options for [`BasicAlgIteratorFactory`].
///
///  Use as:
/// ```
/// # use alg_tools::iterate::*;
/// let iter = AlgIteratorOptions{ max_iter : 10000, .. Default::default() };
/// ```
#[derive(Clone, Copy, Debug, Serialize, Deserialize, Eq, PartialEq)]
pub struct AlgIteratorOptions {
    /// Maximum number of iterations
    pub max_iter : usize,
    /// Number of iterations between verbose iterations that display state.
    pub verbose_iter : Verbose,
    /// Whether verbose iterations are displayed, or just passed onwards to a containing
    /// `AlgIterator`.
    pub quiet : bool,
}

#[derive(Clone, Copy, Debug, Serialize, Deserialize, Eq, PartialEq)]
pub enum Verbose {
    /// Be verbose every $n$ iterations.
    Every(usize),
    /// Be verbose every $n$ iterations and initial $m$ iterations.
    EveryAndInitial{ every : usize, initial : usize },
    /// Be verbose if iteration number $n$ divides by $b^{\text{floor}(\log_b(n))}$, where
    /// $b$ is indicated logarithmic base. So, with $b=10$,
    /// * every iteration for first 10 iterations,
    /// * every 10 iterations from there on until 100 iterations,
    /// * every 100 iteartinos frmo there on until 1000 iterations, etc.
    Logarithmic(usize),
    /// Same as `Logarithmic`, but $\log_b(n)$ is replaced by $min\{c, \log_b(n)\}$ where $c$
    /// is the given `cap`. For example, with `base=10` and `cap=2`, the first ten iterations
    /// will be output, then every tenth iteration, and after 100 iterations, every 100th iteration,
    /// without further logarithmic progression.
    LogarithmicCap{ base : usize, cap : u32 },
}

impl Verbose {
    /// Indicates whether given iteration number is verbose
    pub fn is_verbose(&self, iter : usize) -> bool {
        match self {
            &Verbose::Every(every) => {
                every != 0 && iter % every == 0
            },
            &Verbose::EveryAndInitial{ every, initial } => {
                iter <= initial || (every != 0 && iter % every == 0)
            },
            &Verbose::Logarithmic(base) => {
                let every = base.pow((iter as float).log(base as float).floor() as u32);
                iter % every == 0
            }
            &Verbose::LogarithmicCap{base, cap} => {
                let every = base.pow(((iter as float).log(base as float).floor() as u32).min(cap));
                iter % every == 0
            }
        }
    }
}

impl Default for AlgIteratorOptions {
    fn default() -> AlgIteratorOptions {
        AlgIteratorOptions{
            max_iter : 1000,
            verbose_iter : Verbose::EveryAndInitial { every : 100, initial : 10 },
            quiet : false
        }
    }
}

/// State of a `BasicAlgIterator`
#[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)]
pub struct BasicState {
    /// Current iteration
    iter : usize,
    /// Whether the iteration is verbose, i.e., results should be displayed.
    /// Requires `calc` to be `true`.
    verbose : bool,
    /// Whether results should be calculated.
    calc : bool,
    /// Indicates whether the iteration is quiet
    quiet : bool,
}

/// [`AlgIteratorFactory`] for [`BasicAlgIterator`]
#[derive(Clone,Debug)]
pub struct BasicAlgIteratorFactory<V> {
    options : AlgIteratorOptions,
    _phantoms : PhantomData<V>,
}

/// The simplest [`AlgIterator`], created by [`BasicAlgIteratorFactory`]
#[derive(Clone,Debug)]
pub struct BasicAlgIterator<V> {
    options : AlgIteratorOptions,
    iter : usize,
    _phantoms : PhantomData<V>,
}

impl AlgIteratorOptions {
    /// [`AlgIteratorOptions`] is directly a factory for [`BasicAlgIterator`],
    /// however, due to type inference issues, it may become convenient to instantiate
    /// it to a specific return type for the inner step function. This method does that.
    pub fn instantiate<V>(&self) -> BasicAlgIteratorFactory<V> {
        BasicAlgIteratorFactory {
            options : self.clone(),
            _phantoms : PhantomData
        }
    }
}

impl<V> AlgIteratorFactory<V> for AlgIteratorOptions
where V : LogRepr {
    type State = BasicState;
    type Iter = BasicAlgIterator<V>;
    type Output = V;

    fn prepare(self) -> Self::Iter {
        BasicAlgIterator{
            options : self,
            iter : 0,
            _phantoms : PhantomData,
        }
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.quiet
    }
}

impl<V> AlgIteratorFactory<V> for BasicAlgIteratorFactory<V>
where V : LogRepr {
    type State = BasicState;
    type Iter = BasicAlgIterator<V>;
    type Output = V;

    fn prepare(self) -> Self::Iter {
        BasicAlgIterator {
            options : self.options,
            iter : 0,
            _phantoms : PhantomData
        }
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.options.quiet
    }
}

impl<V> AlgIterator for BasicAlgIterator<V>
where V : LogRepr {
    type State = BasicState;
    type Output = V;
    type Input = V;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        if self.iter >= self.options.max_iter {
            None
        } else {
            self.iter += 1;
            Some(self.state())
        }
    }

    fn poststep<E : Error>(&mut self, res : Step<V, Self::State, E>) -> Step<V, Self::State, E> {
        if let Step::Result(ref val, ref state) = res {
            if state.verbose && !self.options.quiet {
                println!("{}{}/{} {}{}", "".dimmed(),
                        state.iter,
                        self.options.max_iter,
                        val.logrepr(),
                        "".clear());
            }
        }
        res
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.iter
    }

    #[inline]
    fn state(&self) -> BasicState {
        let iter = self.iter;
        let verbose = self.options.verbose_iter.is_verbose(iter);
        BasicState {
            iter : iter,
            verbose : verbose,
            calc : verbose,
            quiet : self.options.quiet
        }
    }
}

impl AlgIteratorState for BasicState {
    #[inline]
    fn if_verbose<V, E : Error>(self, calc_objective : impl FnOnce() -> V) -> Step<V, Self, E> {
        if self.calc {
            Step::Result(calc_objective(), self)
        } else {
            Step::Quiet
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.iter
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.quiet
    }
}

//
// Stall detecting iteration function.
//

/// An [`AlgIteratorFactory`] for an [`AlgIterator`] that detects “stall”.
///
/// We define stall as $(v_{k+n}-v_k)/v_k ≤ θ$, where $n$ the distance between
/// [`Step::Result`] iterations, and $θ$ is the provided `stall` parameter.
#[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)]
pub struct StallIteratorFactory<U : Num, BaseFactory> {
    /// An [`AlgIteratorFactory`] on which to build on
    pub base_options : BaseFactory,
    /// Stalling threshold $θ$.
    pub stall : U,
}

/// Iterator produced by [`StallIteratorFactory`].
pub struct StallIterator<U : Num, BaseIterator> {
    base_iterator : BaseIterator,
    stall : U,
    previous_value : Option<U>,
}

impl<V, U, BaseFactory> AlgIteratorFactory<V>
for StallIteratorFactory<U, BaseFactory>
where BaseFactory : AlgIteratorFactory<V, Output=U>,
      U : SignedNum + PartialOrd {
    type Iter = StallIterator<U, BaseFactory::Iter>;
    type State = BaseFactory::State;
    type Output = BaseFactory::Output;

    fn prepare(self) -> Self::Iter {
        StallIterator {
            base_iterator : self.base_options.prepare(),
            stall : self.stall,
            previous_value : None,
        }
    }

    fn is_quiet(&self) -> bool {
        self.base_options.is_quiet()
    }
}

impl<U, BaseIterator> AlgIterator
for StallIterator<U, BaseIterator>
where BaseIterator : AlgIterator<Output=U>,
      U : SignedNum + PartialOrd {
    type State = BaseIterator::State;
    type Output = U;
    type Input = BaseIterator::Input;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        self.base_iterator.prestep()
    }

    #[inline]
    fn poststep<E>(&mut self, res : Step<Self::Input, Self::State, E>) -> Step<U, Self::State, E>
    where E : Error {
        match self.base_iterator.poststep(res) {
            Step::Result(nv, state) => {
                let previous_v = self.previous_value;
                self.previous_value = Some(nv);
                match previous_v {
                    Some(pv) if (nv - pv).abs() <= self.stall * pv.abs() => Step::Terminated,
                    _ => Step::Result(nv, state),
                }
            },
            val => val,
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.base_iterator.iteration()
    }

    #[inline]
    fn state(&self) -> Self::State {
        self.base_iterator.state()
    }
}

/// An [`AlgIteratorFactory`] for an [`AlgIterator`] that detect whether step function
/// return value is less than `target`, and terminates if it is.
#[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)]
pub struct ValueIteratorFactory<U : Num, BaseFactory> {
    /// An [`AlgIteratorFactory`] on which to build on
    pub base_options : BaseFactory,
    /// Target value
    pub target : U,
}

/// Iterator produced by [`ValueIteratorFactory`].
pub struct ValueIterator<U : Num, BaseIterator> {
    base_iterator : BaseIterator,
    target : U,
}

impl<V, U, BaseFactory> AlgIteratorFactory<V>
for ValueIteratorFactory<U, BaseFactory>
where BaseFactory : AlgIteratorFactory<V, Output=U>,
      U : SignedNum + PartialOrd {
    type Iter = ValueIterator<U, BaseFactory::Iter>;
    type State = BaseFactory::State;
    type Output = BaseFactory::Output;

    fn prepare(self) -> Self::Iter {
        ValueIterator {
            base_iterator : self.base_options.prepare(),
            target : self.target
        }
    }

    fn is_quiet(&self) -> bool {
        self.base_options.is_quiet()
    }
}

impl<U, BaseIterator> AlgIterator
for ValueIterator<U, BaseIterator>
where BaseIterator : AlgIterator<Output=U>,
      U : SignedNum + PartialOrd {
    type State = BaseIterator::State;
    type Output = U;
    type Input = BaseIterator::Input;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        self.base_iterator.prestep()
    }

    #[inline]
    fn poststep<E>(&mut self, res : Step<Self::Input, Self::State, E>) -> Step<U, Self::State, E> where E : Error{
        match self.base_iterator.poststep(res) {
            Step::Result(v, state) => {
                 if v <= self.target {
                    Step::Terminated
                 } else {
                    Step::Result(v, state)
                 }
            },
            val => val,
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.base_iterator.iteration()
    }

    #[inline]
    fn state(&self) -> Self::State {
        self.base_iterator.state()
    }
}

//
// Logging iterator
//

/// [`AlgIteratorFactory`] for a logging [`AlgIterator`].
///
/// Typically produced with [`AlgIteratorFactory::into_log`].
/// The `Output` of the corresponding [`LoggingIterator`] is `()`:
#[derive(Debug)]
pub struct LoggingIteratorFactory<'log, U, BaseFactory> {
    /// Base [`AlgIteratorFactory`] on which to build
    base_options : BaseFactory,
    /// The `Logger` to use.
    logger : &'log mut Logger<U>,
}

/// Iterator produced by `LoggingIteratorFactory`.
pub struct LoggingIterator<'log, U, BaseIterator> {
    base_iterator : BaseIterator,
    logger : &'log mut Logger<U>,
}


impl<'log, V, BaseFactory> AlgIteratorFactory<V>
for LoggingIteratorFactory<'log, BaseFactory::Output, BaseFactory>
where BaseFactory : AlgIteratorFactory<V>,
      BaseFactory::Output : 'log {
    type State = BaseFactory::State;
    type Iter = LoggingIterator<'log, BaseFactory::Output, BaseFactory::Iter>;
    type Output = ();

    fn prepare(self) -> Self::Iter {
        LoggingIterator {
            base_iterator : self.base_options.prepare(),
            logger : self.logger,
        }
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.base_options.is_quiet()
    }
}

impl<'log, BaseIterator> AlgIterator
for LoggingIterator<'log, BaseIterator::Output, BaseIterator>
where BaseIterator : AlgIterator,
      BaseIterator::Output : 'log {
    type State = BaseIterator::State;
    type Output = ();
    type Input = BaseIterator::Input;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        self.base_iterator.prestep()
    }

    #[inline]
    fn poststep<E>(&mut self, res : Step<Self::Input, Self::State, E>) -> Step<(), Self::State, E> where E : Error {
        match self.base_iterator.poststep(res) {
            Step::Result(v, _) => {
                self.logger.log(v);
                Step::Quiet
            },
            Step::Quiet => Step::Quiet,
            Step::Terminated => Step::Terminated,
            Step::Failure(e) => Step::Failure(e),
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.base_iterator.iteration()
    }

    #[inline]
    fn state(&self) -> Self::State {
        self.base_iterator.state()
    }
}

/// This [`AlgIteratorFactory`] allows output mapping.
///
/// Typically produced with [`AlgIteratorFactory::mapped`].
#[derive(Debug)]
pub struct MappingIteratorFactory<G, BaseFactory> {
    /// Base [`AlgIteratorFactory`] on which to build
    base_options : BaseFactory,
    /// A closure `G : Fn(usize, BaseFactory::Output) -> U` that gets the current iteration
    /// and the output of the base factory as input, and produces a new output.
    map : G,
}

/// [`AlgIterator`] produced by [`MappingIteratorFactory`].
pub struct MappingIterator<G, BaseIterator> {
    base_iterator : BaseIterator,
    map : G,
}


impl<V, U, G, BaseFactory> AlgIteratorFactory<V>
for MappingIteratorFactory<G, BaseFactory>
where BaseFactory : AlgIteratorFactory<V>,
      G : Fn(usize, BaseFactory::Output) -> U {
    type State = BaseFactory::State;
    type Iter = MappingIterator<G, BaseFactory::Iter>;
    type Output = U;

    fn prepare(self) -> Self::Iter {
        MappingIterator {
            base_iterator : self.base_options.prepare(),
            map : self.map
        }
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.base_options.is_quiet()
    }
}

impl<U, G, BaseIterator> AlgIterator
for MappingIterator<G, BaseIterator>
where BaseIterator : AlgIterator,
      G : Fn(usize, BaseIterator::Output) -> U {
    type State = BaseIterator::State;
    type Output = U;
    type Input = BaseIterator::Input;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        self.base_iterator.prestep()
    }

    #[inline]
    fn poststep<E>(&mut self, res : Step<Self::Input, Self::State, E>) -> Step<Self::Output, Self::State, E> where E : Error {
        match self.base_iterator.poststep(res) {
            Step::Result(v, state) => Step::Result((self.map)(self.iteration(), v), state),
            Step::Quiet => Step::Quiet,
            Step::Terminated => Step::Terminated,
            Step::Failure(e) => Step::Failure(e),
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.base_iterator.iteration()
    }

    #[inline]
    fn state(&self) -> Self::State {
        self.base_iterator.state()
    }
}

//
// Timing iterator
//

/// An [`AlgIteratorFactory`] for an [`AlgIterator`] that adds spent CPU time to verbose events.
#[derive(Debug)]
pub struct TimingIteratorFactory<BaseFactory>(pub BaseFactory);

/// Iterator produced by [`TimingIteratorFactory`]
#[derive(Debug)]
pub struct TimingIterator<BaseIterator> {
    base_iterator : BaseIterator,
    start_time : ProcessTime,
}

/// Data `U` with production time attached
#[derive(Copy, Clone, Debug, Serialize)]
pub struct Timed<U> {
    /// CPU time taken
    pub cpu_time : Duration,
    /// Iteration number
    pub iter : usize,
    /// User data
    //#[serde(flatten)]
    pub data : U
}

impl<T> LogRepr for Timed<T> where T : LogRepr {
    fn logrepr(&self) -> ColoredString {
        format!("[{:.3}s] {}", self.cpu_time.as_secs_f64(), self.data.logrepr()).as_str().into()
    }
}


impl<V, BaseFactory> AlgIteratorFactory<V>
for TimingIteratorFactory<BaseFactory>
where BaseFactory : AlgIteratorFactory<V> {
    type State = BaseFactory::State;
    type Iter = TimingIterator<BaseFactory::Iter>;
    type Output = Timed<BaseFactory::Output>;

    fn prepare(self) -> Self::Iter {
        TimingIterator {
            base_iterator : self.0.prepare(),
            start_time : ProcessTime::now()
        }
    }

    #[inline]
    fn is_quiet(&self) -> bool {
        self.0.is_quiet()
    }
}

impl<BaseIterator> AlgIterator
for TimingIterator<BaseIterator>
where BaseIterator : AlgIterator {
    type State = BaseIterator::State;
    type Output = Timed<BaseIterator::Output>;
    type Input = BaseIterator::Input;

    #[inline]
    fn prestep(&mut self) -> Option<Self::State> {
        self.base_iterator.prestep()
    }

    #[inline]
    fn poststep<E>(&mut self, res : Step<Self::Input, Self::State, E>) -> Step<Self::Output, Self::State, E> where E : Error {
        match self.base_iterator.poststep(res) {
            Step::Result(data, state) => {
                Step::Result(Timed{
                    cpu_time : self.start_time.elapsed(),
                    iter : self.iteration(),
                    data
                }, state)
            },
            Step::Quiet => Step::Quiet,
            Step::Terminated => Step::Terminated,
            Step::Failure(e) => Step::Failure(e),
        }
    }

    #[inline]
    fn iteration(&self) -> usize {
        self.base_iterator.iteration()
    }

    #[inline]
    fn state(&self) -> Self::State {
        self.base_iterator.state()
    }
}

//
// New for-loop interface
//

pub struct AlgIteratorIterator<I : AlgIterator> {
    algi : Rc<RefCell<I>>,
}

pub struct AlgIteratorIteration<I : AlgIterator> {
    state : I::State,
    algi : Rc<RefCell<I>>,
}

impl<I : AlgIterator> std::iter::Iterator for AlgIteratorIterator<I> {
    type Item = AlgIteratorIteration<I>;

    fn next(&mut self) -> Option<Self::Item> {
        let algi = self.algi.clone();
        RefCell::borrow_mut(&self.algi).prestep().map(|state| AlgIteratorIteration {
            state,
            algi,
        })
    }
}

/// Types of errors that may occur
#[derive(Debug,PartialEq,Eq)]
pub enum IterationError {
    /// [`AlgIteratorIteration::if_verbose_check`] is not called in iteration order.
    ReportingOrderingError
}

impl<I : AlgIterator> AlgIteratorIteration<I> {
    /// Call `call_objective` if this is a verbose iteration.
    ///
    /// Verbosity depends on the [`AlgIterator`] that produced this state.
    ///
    /// The closure `calc_objective` should return an arbitrary value of type `V`, to be inserted
    /// into the log, or whatever is deemed by the [`AlgIterator`]. For usage instructions see the
    /// [module documentation][self].
    ///
    /// This function may panic if result reporting is not ordered correctly (an unlikely mistake
    /// if using this facility correctly). For a version that propagates errors, see
    /// [`Self::if_verbose_check`].
    pub fn if_verbose(self, calc_objective : impl FnOnce() -> I::Input) {
        self.if_verbose_check(calc_objective).unwrap()
    }

    /// Version of [`Self::if_verbose`] that propagates errors instead of panicking.
    pub fn if_verbose_check(self, calc_objective : impl FnOnce() -> I::Input)
    -> Result<(), IterationError> {
        let mut algi = match RefCell::try_borrow_mut(&self.algi) {
            Err(_) => return Err(IterationError::ReportingOrderingError),
            Ok(algi) => algi
        };
        if self.state.iteration() != algi.iteration() {
            Err(IterationError::ReportingOrderingError)
        } else {
            let res : Step<I::Input, I::State, std::convert::Infallible>
                = self.state.if_verbose(calc_objective);
            algi.poststep(res);
            Ok(())
        }
    }

    /// Returns the current iteration count.
    pub fn iteration(&self) -> usize {
        self.state.iteration()
    }

    /// Indicates whether the iterator is quiet
    pub fn is_quiet(&self) -> bool {
        self.state.is_quiet()
    }
}

//
// Tests
//

#[cfg(test)]
mod tests {
    use super::*;
    use crate::logger::Logger;
    #[test]
    fn iteration() {
        let options = AlgIteratorOptions{
            max_iter : 10,
            verbose_iter : Verbose::Every(3),
            .. Default::default()
        };

        {
            let mut start = 1 as int;
            options.iterate(|state| {
                start = start * 2;
                state.if_verbose(|| start)
            });
            assert_eq!(start, (2 as int).pow(10));
        }

        {
            let mut start = 1 as int;
            let mut log = Logger::new();
            let factory = options.instantiate()
                                 .with_iteration_number()
                                 .into_log(&mut log);
            factory.iterate(|state| {
                start = start * 2;
                state.if_verbose(|| start)
            });
            assert_eq!(start, (2 as int).pow(10));
            assert_eq!(log.data()
                          .iter()
                          .map(|LogItem{ data : v, iter : _ }| v.clone())
                          .collect::<Vec<int>>(),
                      (1..10).map(|i| (2 as int).pow(i))
                             .skip(2)
                             .step_by(3)
                             .collect::<Vec<int>>())
        }
    }

    #[test]
    fn iteration_for_loop() {
        let options = AlgIteratorOptions{
            max_iter : 10,
            verbose_iter : Verbose::Every(3),
            .. Default::default()
        };

        {
            let mut start = 1 as int;
            for state in options.iter() {
                start = start * 2;
                state.if_verbose(|| start)
            }
            assert_eq!(start, (2 as int).pow(10));
        }

        {
            let mut start = 1 as int;
            let mut log = Logger::new();
            let factory = options.instantiate()
                                 .with_iteration_number()
                                 .into_log(&mut log);
            for state in factory.iter() {
                start = start * 2;
                state.if_verbose(|| start)
            }
            assert_eq!(start, (2 as int).pow(10));
            assert_eq!(log.data()
                          .iter()
                          .map(|LogItem{ data : v, iter : _ }| v.clone())
                          .collect::<Vec<int>>(),
                      (1..10).map(|i| (2 as int).pow(i))
                             .skip(2)
                             .step_by(3)
                             .collect::<Vec<int>>())
        }
    }

}