From 4132b5115c8146a1fb67de6be762aa3d3a08e258 Mon Sep 17 00:00:00 2001
From: Finn Bear <finnbearlabs@gmail.com>
Date: Sat, 15 Jan 2022 16:41:33 -0800
Subject: Fix termination behavior and add comprehensive test cases.

---
 src/histbuf.rs | 83 ++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 60 insertions(+), 23 deletions(-)

(limited to 'src/histbuf.rs')

diff --git a/src/histbuf.rs b/src/histbuf.rs
index 5b2f54e4..eb808b48 100644
--- a/src/histbuf.rs
+++ b/src/histbuf.rs
@@ -202,16 +202,15 @@ impl<T, const N: usize> HistoryBuffer<T, N> {
             OldestOrdered {
                 buf: self,
                 cur: self.write_at,
+                wrapped: false,
             }
-        } else if self.write_at == 0 {
-            // special case of empty buffer. first call to next
-            // will wrap cur to 0, equaling write_at, resulting in None.
+        } else {
+            // special case: act like we wrapped already to handle empty buffer.
             OldestOrdered {
                 buf: self,
-                cur: usize::MAX,
+                cur: 0,
+                wrapped: true,
             }
-        } else {
-            OldestOrdered { buf: self, cur: 0 }
         }
     }
 }
@@ -285,26 +284,25 @@ impl<T, const N: usize> Default for HistoryBuffer<T, N> {
 pub struct OldestOrdered<'a, T, const N: usize> {
     buf: &'a HistoryBuffer<T, N>,
     cur: usize,
+    wrapped: bool,
 }
 
 impl<'a, T, const N: usize> Iterator for OldestOrdered<'a, T, N> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<&'a T> {
-        let mut next = self.cur.wrapping_add(1);
-
-        // roll-over
-        if next == self.buf.len() {
-            next = 0;
+        if self.cur == self.buf.len() && self.buf.filled {
+            // roll-over
+            self.cur = 0;
+            self.wrapped = true;
         }
 
-        // end of iteration
-        if next == self.buf.write_at {
+        if self.cur == self.buf.write_at && self.wrapped {
             return None;
         }
 
         let item = &self.buf[self.cur];
-        self.cur = next;
+        self.cur += 1;
         Some(item)
     }
 }
@@ -312,6 +310,7 @@ impl<'a, T, const N: usize> Iterator for OldestOrdered<'a, T, N> {
 #[cfg(test)]
 mod tests {
     use crate::HistoryBuffer;
+    use core::fmt::Debug;
 
     #[test]
     fn new() {
@@ -381,23 +380,61 @@ mod tests {
     fn ordered() {
         // test on an empty buffer
         let buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
-        assert_eq!(buffer.oldest_ordered().next(), None);
-        assert_eq!(buffer.oldest_ordered().next(), None);
+        let mut iter = buffer.oldest_ordered();
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.next(), None);
+
+        let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
+        buffer.write(1);
+        let mut iter = buffer.oldest_ordered();
+        assert_eq!(iter.next(), Some(&1));
+        assert_eq!(iter.next(), None);
 
         // test on a filled buffer
         let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
         buffer.extend([0, 0, 0, 1, 2, 3, 4, 5, 6]);
-        let expected = [1, 2, 3, 4, 5, 6];
-        for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
-            assert_eq!(x, y);
-        }
+        assert_eq!(buffer.len(), 6);
+
+        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3, 4, 5, 6]);
 
         // test on a un-filled buffer
         let mut buffer: HistoryBuffer<u8, 6> = HistoryBuffer::new();
         buffer.extend([1, 2, 3]);
-        let expected = [1, 2, 3];
-        for (x, y) in buffer.oldest_ordered().zip(expected.iter()) {
-            assert_eq!(x, y);
+        assert_eq!(buffer.len(), 3);
+        assert_eq_iter(buffer.oldest_ordered(), &[1, 2, 3]);
+
+        // comprehensive test
+        for n in 0..50 {
+            const N: usize = 7;
+            let mut buffer: HistoryBuffer<u8, N> = HistoryBuffer::new();
+            buffer.extend(0..n);
+            assert_eq_iter(
+                buffer.oldest_ordered().copied(),
+                n.saturating_sub(N as u8)..n,
+            );
+        }
+    }
+
+    /// Compares two iterators item by item, making sure they stop at the same time.
+    fn assert_eq_iter<I: Eq + Debug>(
+        a: impl IntoIterator<Item = I>,
+        b: impl IntoIterator<Item = I>,
+    ) {
+        let mut a = a.into_iter();
+        let mut b = b.into_iter();
+
+        let mut i = 0;
+        loop {
+            let a_item = a.next();
+            let b_item = b.next();
+
+            assert_eq!(a_item, b_item, "{}", i);
+
+            i += 1;
+
+            if b_item.is_none() {
+                break;
+            }
         }
     }
 }
-- 
cgit v1.2.3