//! Provides a simple iterator adaptor that buffers data from the
//! underlying iterator when needed. It will only read ahead when peek requests
//! are made, but it will only request each element from the source once. That
//! is, no matter how many positions of lookahead you allocate, they won't be
//! filled unless you need them, once you have seen them they will be buffered
//! until iterated to.
//!
//! This is a fundamental, low level component of lexical analyzers and of
//! parsers in general as well as many other systems.

/// LookAhead uses a statically allocated ring buffer to store it's data in, an
/// internal array of Options to make moving the data in and out easier.
///
/// C: How many positions are in the buffer, this should be 1+lookahead length,
/// that is C=2 means you get a current value and one lookahead token.
/// T: The type of the underlying items
/// U: The type of the underlying iterator, must implement Iterator with Type=T
pub struct LookAhead<const C: usize, T, U>
where
    U: Iterator<Item=T> + Sized
{
    iter: U,
    data: [Option<T>;C],
    cur: usize,
    fill: usize,
}

impl<const C: usize, T, U> LookAhead<C,T,U>
where
    U: Iterator<Item=T> + Sized
{
    /// Create a new LookAhead Iterator wrapping the provided iterator.
    ///
    /// This does nothing to the base iterator, it does not begin reading yet.
    pub fn new(iter: U) -> Self {
        Self {
            iter,
            data: [const {None};C],
            cur: 0,
            fill: 0,
        }
    }

    /// Look ahead into the buffered look-ahead. If you exceed the size of the
    /// internal buffer (C) then this will panic. This will fill the buffer to
    /// the point requested if it is not already full. This will not advance
    /// the iterator, so multiple calls to peek for the same position without
    /// calling next() will provide the same value and will not affect the state
    /// of the interior iterator.
    pub fn peek(&mut self, offset: usize) -> Option<&T> {
        assert!(offset<C);
        self.fill_to( offset );
        self.data[(self.cur+offset)%C].as_ref()
    }

    /// Fills the internal buffer to the requested level by calling next() on
    /// the underlying iterator. This will call the underlying iterator for
    /// each position to fill, even if the next() function has returned None.
    /// It will simply fill the lookahead buffer with None values.
    fn fill_to(&mut self, qty: usize) {
        for i in self.fill..=qty {
            if let Some(x) = self.iter.next() {
                self.data[(self.cur+i)%C].replace( x );
                self.fill += 1;
            }
        }
    }
}

impl<const C: usize, T, U> std::iter::Iterator for LookAhead<C,T,U> 
where
    U: Iterator<Item=T> + Sized
{
    type Item=T;

    /// Follows the standard rules for an iterator. This will only call the
    /// underlying iterator's next function if our lookahead buffer is empty.
    /// Otherwise this is a pass-through. It does nothing special in the case
    /// of a None response from the underlying iterator.
    fn next(&mut self) -> Option<T> {
        if self.fill == 0 {
            self.iter.next()
        } else {
            let old = self.cur;
            self.cur = (self.cur+1)%C;
            self.fill -= 1;
            self.data[old].take()
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic() {
        let data = [1, 2, 3, 4, 5, 6, 7, 8];
        let mut i = LookAhead::<3,_,_>::new(data.iter());
        assert_eq!(i.next(), Some(&1));
        assert_eq!(i.peek(1), Some(&&3));
        assert_eq!(i.peek(0), Some(&&2));
        assert_eq!(i.next(), Some(&2));
        assert_eq!(i.peek(0), Some(&&3));
        assert_eq!(i.next(), Some(&3));
        assert_eq!(i.next(), Some(&4));
        assert_eq!(i.next(), Some(&5));
        assert_eq!(i.peek(0), Some(&&6));
        assert_eq!(i.peek(1), Some(&&7));
        assert_eq!(i.peek(2), Some(&&8));
        assert_eq!(i.next(), Some(&6));
        assert_eq!(i.peek(2), None);
        assert_eq!(i.next(), Some(&7));
        assert_eq!(i.peek(2), None);
        assert_eq!(i.next(), Some(&8));
        assert_eq!(i.next(), None);
    }
}