Mercurial > repos > alg_tools / file revision

/*!
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;
iter.iterate(|state|{
    // 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 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 {
    /// 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 FnMut() -> V) -> Step<V, E>;

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

/// Result of a step of an [`AlgIterator`]
#[derive(Debug, Serialize)]
pub enum Step<V, 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),
}

impl<V, E : Error> Step<V, 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, E> {
        match self {
            Step::Result(v) =>  Step::Result(f(v)),
            Step::Failure(e) => Step::Failure(e),
            Step::Quiet =>      Step::Quiet,
            Step::Terminated => Step::Terminated,
        }
    }
}

/// 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::step`].
    type Output;
    /// The error type for [`Self::step`] and [`Self::iterate`].
    type Err : Error;

    /// Advance the iterator.
    fn step(&mut self) -> Step<Self::Output, Self::Err>;

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

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

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

    /// Converts the `AlgIterator` into a plain [`Iterator`].
    ///
    /// [`Step::Quiet`] results are discarded, and [`Step::Failure`] results **panic**.
    fn downcast(self) -> AlgIteratorI<Self> {
        AlgIteratorI(self)
    }
}

/// Conversion of an `AlgIterator` into a plain [`Iterator`].
///
/// The conversion discards [`Step::Quiet`] and **panics** on [`Step::Failure`].
pub struct AlgIteratorI<A>(A);

impl<A> Iterator for AlgIteratorI<A>
where A : AlgIterator {
    type Item = A::Output;

    fn next(&mut self) -> Option<A::Output> {
        loop {
            match self.0.step() {
                Step::Result(v) => return Some(v),
                Step::Failure(e) => panic!("{e:?}"),
                Step::Terminated => return None,
                Step::Quiet => continue,
            }
        }
    }
}

/// A factory for producing an [`AlgIterator`].
///
/// For usage instructions see the [module documentation][self].
pub trait AlgIteratorFactory<V> : Sized {
    type Iter<F, E> : AlgIterator<State = Self::State, Output = Self::Output, Err = E>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    /// 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.
    ///
    /// The function `step_fn` should accept a `state` ([`AlgIteratorState`] parameter, and return
    /// a [`Step`].
    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error;

    /// 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, E>,
          E : Error {
        self.prepare(step).iterate()
    }

    /// 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].
    ///
    /// 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.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, E>,
          I : Iterator<Item = D>,
          E : Error {
        self.prepare(move |state| {
            datasource.next().map_or(Step::Terminated, |d| step(state, d))
        }).iterate()
    }

    /// 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>,
          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 }
}

/// 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),
}

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 = 10usize.pow((iter as float).log(base as float).floor() as u32);
                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,
}

/// [`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<F, V, E : Error> {
    options : AlgIteratorOptions,
    iter : usize,
    step_fn : F,
    _phantoms : PhantomData<(V, E)>,
}

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<F, E> = BasicAlgIterator<F, V, E>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type Output = V;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        BasicAlgIterator{
            options : self,
            iter : 0,
            step_fn,
            _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<F, E> = BasicAlgIterator<F, V, E>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type Output = V;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        BasicAlgIterator {
            options : self.options,
            iter : 0,
            step_fn,
            _phantoms : PhantomData
        }
    }

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

impl<F, V, E> AlgIterator for BasicAlgIterator<F, V, E>
where V : LogRepr,
      E : Error,
      F : FnMut(&BasicState) -> Step<V, E> {
    type State = BasicState;
    type Output = V;
    type Err = E;

    #[inline]
    fn step(&mut self) -> Step<V, E> {
        if self.iter >= self.options.max_iter {
            Step::Terminated
        } else {
            self.iter += 1;
            let state = self.state();
            let res = (self.step_fn)(&state);
            if let Step::Result(ref val) = 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,
        }
    }
}

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

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

//
// 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<F, E> = StallIterator<U, BaseFactory::Iter<F, E>>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type State = BaseFactory::State;
    type Output = BaseFactory::Output;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        StallIterator {
            base_iterator : self.base_options.prepare(step_fn),
            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 = BaseIterator::Output;
    type Err = BaseIterator::Err;

    #[inline]
    fn step(&mut self) -> Step<U, Self::Err> {
        match self.base_iterator.step() {
            Step::Result(nv) => {
                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),
                }
            },
            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<F, E> = ValueIterator<U, BaseFactory::Iter<F, E>>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type State = BaseFactory::State;
    type Output = BaseFactory::Output;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        ValueIterator {
            base_iterator : self.base_options.prepare(step_fn),
            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 = BaseIterator::Output;
    type Err = BaseIterator::Err;

    #[inline]
    fn step(&mut self) -> Step<U, Self::Err> {
        match self.base_iterator.step() {
            Step::Result(v) => {
                 if v <= self.target {
                    Step::Terminated
                 } else {
                    Step::Result(v)
                 }
            },
            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<F, E> = LoggingIterator<'log, BaseFactory::Output, BaseFactory::Iter<F, E>>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type Output = ();

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        LoggingIterator {
            base_iterator : self.base_options.prepare(step_fn),
            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 Err = BaseIterator::Err;

    #[inline]
    fn step(&mut self) -> Step<Self::Output, Self::Err> {
        match self.base_iterator.step() {
            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<F, E> = MappingIterator<G, BaseFactory::Iter<F, E>>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type Output = U;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        MappingIterator {
            base_iterator : self.base_options.prepare(step_fn),
            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 Err = BaseIterator::Err;

    #[inline]
    fn step(&mut self) -> Step<Self::Output, Self::Err> {
        match self.base_iterator.step() {
            Step::Result(v) => Step::Result((self.map)(self.iteration(), v)),
            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> {
    pub cpu_time : Duration,
    //#[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<F, E> = TimingIterator<BaseFactory::Iter<F, E>>
        where F : FnMut(&Self::State) -> Step<V, E>,
              E : Error;
    type Output = Timed<BaseFactory::Output>;

    fn prepare<F, E>(self, step_fn : F) -> Self::Iter<F, E>
    where F : FnMut(&Self::State) -> Step<V, E>,
          E : Error {
        TimingIterator {
            base_iterator : self.0.prepare(step_fn),
            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 Err = BaseIterator::Err;

    #[inline]
    fn step(&mut self) -> Step<Self::Output, Self::Err> {
        match self.base_iterator.step() {
            Step::Result(data) => {
                Step::Result(Timed{
                    cpu_time : self.start_time.elapsed(),
                    data
                })
            },
            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()
    }
}

//
// 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>>())
        }
    }
}