use std::{
collections::Bound,
ops::RangeBounds,
slice::SliceIndex,
};
#[derive(Debug)]
pub struct MemoIter<I, T> where
I: Iterator<Item=T>,
{
exhausted: bool,
iterator: I,
sequence: Vec<T>,
}
impl<I, T> MemoIter<I, T> where
I: Iterator<Item=T>,
{
pub fn new(iterator: I) -> Self {
Self {
exhausted: false,
iterator,
sequence: Vec::new(),
}
}
pub fn with_capacity(capacity: usize, iterator: I) -> Self {
Self {
exhausted: false,
iterator,
sequence: Vec::with_capacity(capacity),
}
}
pub fn with_vec(iterator: I, sequence: Vec<T>) -> Self {
Self {
exhausted: false,
iterator,
sequence,
}
}
#[inline]
pub fn evaluated(&self) -> usize {
self.sequence.len()
}
fn expand_to_contain(&mut self, idx: usize) {
if !self.exhausted {
let len: usize = self.sequence.len();
if idx >= len {
self.sequence.reserve(idx - len + 1);
for _i in len..=idx {
#[cfg(test)] println!("+ {}", _i);
match self.iterator.next() {
Some(next) => self.sequence.push(next),
None => {
self.exhausted = true;
self.sequence.shrink_to_fit();
return;
}
}
}
}
}
}
pub fn get(&mut self, idx: usize) -> Option<&T> {
#[cfg(test)] println!("get({}):", idx);
self.expand_to_contain(idx);
self.sequence.get(idx)
}
pub fn get_slice<R>(&mut self, range: R) -> &[T] where
R: RangeBounds<usize> + SliceIndex<[T], Output=[T]>,
{
let first: usize = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(&i) => i,
Bound::Excluded(&i) => i + 1,
};
match range.end_bound() {
Bound::Unbounded => {
let end: usize = self.sequence.len();
&self.sequence[first.min(end)..end]
}
Bound::Included(&i) => {
self.expand_to_contain(i);
let last: usize = self.sequence.len().saturating_sub(1).min(i);
if first <= last {
&self.sequence[first..=last]
} else {
&[]
}
}
Bound::Excluded(&i) => {
self.expand_to_contain(i.saturating_sub(1));
let end: usize = self.sequence.len().min(i);
&self.sequence[first.min(end)..end]
}
}
}
#[inline]
pub fn is_exhausted(&self) -> bool {
self.exhausted
}
pub fn recall(&mut self, idx: usize) -> Option<&T> {
#[cfg(test)] println!("recall({})", idx);
self.sequence.get(idx)
}
pub fn consume(self) -> (Vec<T>, I) {
let Self { sequence, iterator, .. } = self;
(sequence, iterator)
}
}
impl<I, T> ExactSizeIterator for MemoIter<I, T> where
I: ExactSizeIterator + Iterator<Item=T>,
T: Copy,
{
#[inline]
fn len(&self) -> usize {
self.sequence.len() + self.iterator.len()
}
}
impl<F, I, T> From<F> for MemoIter<I, T> where
F: IntoIterator<Item=T, IntoIter=I>,
I: Iterator<Item=T>,
{
fn from(into: F) -> Self {
Self::new(into.into_iter())
}
}
impl<I, T> Iterator for MemoIter<I, T> where
I: Iterator<Item=T>,
T: Copy,
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if !self.exhausted {
match self.iterator.next() {
Some(next) => {
self.sequence.push(next);
Some(next)
}
None => {
self.exhausted = true;
self.sequence.shrink_to_fit();
None
}
}
} else { None }
}
}
#[cfg(test)]
mod tests {
use std::iter::successors;
use super::*;
#[test]
fn test_factorial() {
let mut factorial: MemoIter<_, u32> = successors(
Some((0, 1)),
|&(idx0, acc)| {
let idx1: u32 = idx0 + 1;
Some((idx1, idx1 * acc))
},
).map(|p| p.1).into();
assert_eq!(factorial.sequence, [], "MemoIter does not start empty.");
assert_eq!(factorial.recall(3), None);
assert_eq!(factorial.get(0), Some(&1));
assert_eq!(factorial.get(1), Some(&1));
assert_eq!(factorial.get(4), Some(&24));
assert_eq!(factorial.get(6), Some(&720));
assert_eq!(factorial.get(4), Some(&24));
assert_eq!(factorial.get(2), Some(&2));
assert_eq!(factorial.get(0), Some(&1));
assert_eq!(factorial.recall(3), Some(&6));
println!("{:?}", &factorial);
assert_eq!(factorial.get_slice(..), [1, 1, 2, 6, 24, 120, 720]);
assert_eq!(factorial.get_slice(0..4), [1, 1, 2, 6]);
assert_eq!(factorial.get_slice(..=7), [1, 1, 2, 6, 24, 120, 720, 5040]);
assert_eq!(factorial.get_slice(5..8), [120, 720, 5040]);
let (seq, _) = factorial.consume();
assert_eq!(
seq, [1, 1, 2, 6, 24, 120, 720, 5040],
"MemoIter does not correctly store its past values.",
);
}
#[test]
fn test_fibonacci() {
let mut fibonacci: MemoIter<_, u32> = successors(
Some((0, 1)),
|&(a, b)| Some((b, b + a)),
).map(|p| p.0).into();
assert_eq!(fibonacci.get(0), Some(&0));
assert_eq!(fibonacci.get(1), Some(&1));
assert_eq!(fibonacci.get(4), Some(&3));
assert_eq!(fibonacci.get(9), Some(&34));
println!("{:?}", &fibonacci);
let (seq, _) = fibonacci.consume();
assert_eq!(seq, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
}
#[test]
fn test_len() {
let mut five = MemoIter::new(0..5);
assert!(!five.is_exhausted());
assert_eq!(five.evaluated(), 0);
assert_eq!(five.len(), 5);
assert_eq!(five.get(3), Some(&3));
assert!(!five.is_exhausted());
assert_eq!(five.evaluated(), 4);
assert_eq!(five.len(), 5);
assert_eq!(five.get(7), None);
assert!(five.is_exhausted());
assert_eq!(five.evaluated(), 5);
assert_eq!(five.len(), 5);
}
#[test]
fn test_prevec() {
let mut five = MemoIter::with_vec(1..5, vec![0]);
assert!(!five.is_exhausted());
assert_eq!(five.len(), 5);
assert_eq!(five.evaluated(), 1);
assert_eq!(five.recall(0), Some(&0));
assert_eq!(five.recall(1), None);
assert_eq!(five.get_slice(..), [0]);
assert_eq!(five.get(10), None);
assert!(five.is_exhausted());
assert_eq!(five.len(), 5);
assert_eq!(five.evaluated(), 5);
assert_eq!(five.recall(0), Some(&0));
assert_eq!(five.recall(1), Some(&1));
assert_eq!(five.get_slice(..), [0, 1, 2, 3, 4]);
}
#[test]
fn test_slice() {
let mut five = MemoIter::new(0..5);
assert!(!five.is_exhausted());
assert_eq!(five.evaluated(), 0);
assert_eq!(five.get_slice(..), []);
assert_eq!(five.get_slice(..0), []);
assert_eq!(five.get_slice(..=0), [0]);
assert_eq!(five.get_slice(0..1), [0]);
assert_eq!(five.get_slice(0..), [0]);
assert_eq!(five.get_slice(..), [0]);
assert!(!five.is_exhausted());
assert_eq!(five.evaluated(), 1);
assert_eq!(five.get_slice(10..20), []);
assert_eq!(five.get_slice(4..=20), [4]);
assert_eq!(five.get_slice(10..=20), []);
assert_eq!(five.get_slice(..20), [0, 1, 2, 3, 4]);
assert_eq!(five.get_slice(..=9), [0, 1, 2, 3, 4]);
assert_eq!(five.get_slice(10..), []);
assert_eq!(five.get_slice(..), [0, 1, 2, 3, 4]);
assert_eq!(five.get_slice(..=usize::MAX), [0, 1, 2, 3, 4]);
assert_eq!(five.get_slice(50..40), []);
assert!(five.is_exhausted());
assert_eq!(five.evaluated(), 5);
assert_eq!(five.len(), 5);
}
}