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;
# 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 crate::logger::*;
use crate::types::*;
use colored::{ColoredString, Colorize};
use core::fmt::Debug;
use cpu_time::ProcessTime;
use serde::{Deserialize, Serialize};
use std::cell::RefCell;
use std::error::Error;
use std::marker::PhantomData;
use std::rc::Rc;
use std::time::Duration;

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