misc_iterators 0.3.3

#![deny(missing_docs)]
#![doc = include_str!("../README.md")]

/// Breath first search iterator.
pub mod breadth_first_search;
/// Depth first search iterator.
pub mod depth_first_search;
/// Itertor for integer tuples that add to less than a number.
pub mod integer_decomposition;
/// DDA iterator.
pub mod raster_line;

/// Start value, termination, update step.
pub struct Interval(pub isize, pub isize, pub isize);

impl Iterator for Interval
{
    type Item = isize;

    fn next(&mut self) -> Option<Self::Item>
    {
        let current = self.0.clone();
        // If end_condition(current).
        if current == self.1
        {
            return None;
        }

        // current = update(current).
        self.0 += self.2;

        Some(current)
    }
}

/// Oriented interval representation.
pub struct SmartInterval
{
    interval: Interval,
}

impl SmartInterval
{
    /// `start` can be greater than `end`, the iterator will
    /// span the space in the order specified from start to end.
    pub fn new(start: isize, end: isize) -> Self
    {
        let step = (end - start).signum();
        let mut range = [start, end];
        range.sort();

        Self {
            interval: Interval(range[0], range[1], step),
        }
    }
}

impl Iterator for SmartInterval
{
    type Item = isize;

    fn next(&mut self) -> Option<Self::Item> { self.interval.next() }
}

/// Iterator that can properly iterate a multidiemnsional array of given sizes.
/// For example a 3D array with dimensions (100, 30, 900).
/// Last dimension is updated least frequently, first is updated most
/// frequently.
#[derive(Clone)]
pub struct IterDimensions<const N: usize>
{
    extents: [usize; N],
    index: [usize; N],
}
impl<const N: usize> IterDimensions<N>
{
    /// Specify the dimensions of the hyper cube.
    pub fn new(extents: [usize; N]) -> Self
    {
        Self {
            extents,
            index: [0; N],
        }
    }
}
impl<const N: usize> Iterator for IterDimensions<N>
{
    type Item = [usize; N];

    fn next(&mut self) -> Option<Self::Item>
    {
        let ret = self.index;
        self.index[0] += 1;

        for i in 0..N - 1
        {
            // If we have exceeded the dimension then the next dimension needs to go up.
            let carry = self.index[i] / self.extents[i];
            // Use modulus to bring index back to the start when the extent is exceeded.
            self.index[i] = self.index[i] % self.extents[i];

            // Increment the current dimension if needed.
            self.index[i + 1] += carry;
        }

        if ret[N - 1] > self.extents[N - 1] - 1
        {
            return None;
        }

        Some(ret)
    }
}

/// Iterator that can index a rectangular subblock of a multidimensional domain.
/// For example, if one wants to iterate over the range:
/// (1 -> 100) x (100 -> -10) x (90 -> 20)
/// Prefer `IterDimensions` when possible.
/// WARNING: This checks for exact matches against the bounds. If they are not
///  correct, it will iterate forever.
pub struct MultiIndex<const N: usize>
{
    starts: [isize; N],
    ends: [isize; N],
    updates: [i32; N],
    index: [isize; N],
}
impl<const N: usize> MultiIndex<N>
{
    /// Specify the bounds of an integer grid in N dimensions.
    pub fn new(starts: [isize; N], ends: [isize; N], updates: [i32; N]) -> Self
    {
        let index = starts;
        Self {
            starts,
            ends,
            updates,
            index,
        }
    }
}

impl<const N: usize> Iterator for MultiIndex<N>
{
    type Item = [isize; N];

    fn next(&mut self) -> Option<Self::Item>
    {
        let ret = self.index;

        self.index[0] += self.updates[0] as isize;
        for i in 0..N - 1
        {
            if self.index[i] == self.ends[i]
            {
                self.index[i + 1] += self.updates[i + 1] as isize;
                self.index[i] = self.starts[i];
            }
        }

        if ret[N - 1] == self.ends[N - 1]
        {
            return None;
        }

        Some(ret)
    }
}

/// Apply a permutation to a list.
/// The permutation list is assumed to be ordered as (source, target) so
/// for example:
///
/// [a, b, c], [1, 0, 2] -> [b, a, c]
/// [a, b, c, d], [3, 1, 2, 0] -> [d, b, c, a]
///
/// Beware that online resources usually use the opposite ordering (target,
/// source) for permutations.
// TODO(low): This can be done in place in O(1) space and O(n) steps.
pub fn permute<T>(list: &mut Vec<T>, permutation: Vec<usize>)
where
    T: Clone + Copy,
{
    let mut result = list.clone();

    for i in 0..permutation.len()
    {
        result[i] = list[permutation[i]];
    }

    *list = result
}