use std::cmp::{Ordering};
use std::mem::replace;

type ConstraintList = Vec<usize>;

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Square {
    Unknown,
    Empty,
    Filled,
}

// The ConstraintList is a list of the lengths of contigious blocks of Filled Squares. (With any non-zero number of Empty between)
// Any number, including zero, of Empty are allowed before or after the first/last blocks
// Return true if the given iterator is consistent with the given constraint,
// i.e. does not contradict the given lengths by having a block that is too long or a block interrupted by an Empty.
fn validate_line(consts: &ConstraintList, line: impl Iterator<Item=Square>) -> bool {
    let block_lengths = RepIterator::new(line)
        .filter(|&(v, _)| v == Square::Filled)
        .map(|(_, c)| c); // Converts the current state into an iterator of the same format (i.e. lengths of filled sqs) as the constraint

    let v: Vec<_> = block_lengths.collect();
    let mut block_lengths = v.into_iter();

    let mut constraints = consts.iter().cloned();
    loop {
        let (blo, co) = (block_lengths.next(), constraints.next());
        return match (blo, co) {
            (Some(bl), Some(co)) => match bl.cmp(&co) {
                Ordering::Greater => false,
                Ordering::Equal => continue,
                Ordering::Less => block_lengths.next().is_none(),
            },
            (Some(_), None) => false,
            (None, _) => true,
        };
    }
}




// Convert an Iterator<T> into an Iterator<(T, usize)> that yields each element, and the number of times that element is repeated by the original Iterator
pub struct RepIterator<T, I>
where
    T: Eq,
    I: Iterator<Item = T>,
{
    iter: I,
    last_item: Option<T>,
    count: usize,
}

impl<T, I> RepIterator<T, I>
where
    T: Eq,
    I: Iterator<Item = T>,
{
    pub fn new(iter: I) -> RepIterator<T, I> {
        RepIterator {
            iter,
            last_item: None,
            count: 0,
        }
    }
}

impl<T, I> Iterator for RepIterator<T, I>
where
    T: Eq,
    I: Iterator<Item = T> + Sized,
{
    type Item = (T, usize);
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.iter.next() {
                None => {
                    let old = self.last_item.take();
                    let old_count = replace(&mut self.count, 0);
                    return old.map(|v| (v, old_count));
                    // Might be in the middle of a string of Some values, so return that, then return None if we get another None
                    // Doesn't matter if the count of None is wrong
                }
                Some(ref item) if Some(item) == self.last_item.as_ref() => {
                    self.count += 1;
                }
                Some(item) => {
                    let old = replace(&mut self.last_item, Some(item));
                    let c = replace(&mut self.count, 1);
                    if let Some(i) = old {
                        return Some((i, c));
                    }
                }
            }
        }
    }
}

fn main() {
    let real_vals = vec![Square::Filled, Square::Empty, Square::Empty, Square::Empty];
    let consts = vec![4];
    let truf = validate_line(&consts, real_vals.into_iter());
    assert!(!truf);


}