texcraft_stdext/collections/
circularbuffer.rs

1//! A circular buffer.
2//!
3//! See the documentation on the [CircularBuffer] type.
4
5use std::ops::IndexMut;
6
7/// A circular buffer.
8///
9/// A circular buffer is an ordered buffer with a fixed capacity and the property that if it is full
10/// and a new element is pushed to the front, the oldest element is deleted.
11///
12/// The buffer is created using the [new](CircularBuffer::new) method, elements are pushed to the
13/// front using [push](CircularBuffer::push), and retrieved using
14/// [std::ops::Index::index] trait method.
15///
16/// ```
17/// # use texcraft_stdext::collections::circularbuffer::CircularBuffer;
18/// # use std::ops::Index;
19/// let mut buf = CircularBuffer::new(3);
20/// buf.push(0);
21/// buf.push(1);
22/// assert_eq![buf.index(0), &1];
23/// assert_eq![buf.index(1), &0];
24/// buf.push(2);
25/// buf.push(3);
26/// assert_eq![buf.index(0), &3];
27/// assert_eq![buf.index(1), &2];
28/// assert_eq![buf.index(2), &1];
29/// ```
30pub struct CircularBuffer<T> {
31    data: Vec<T>,
32    head: usize,
33}
34
35impl<T> CircularBuffer<T> {
36    /// Create a new circular buffer with the provided capacity.
37    pub fn new(capacity: usize) -> CircularBuffer<T> {
38        CircularBuffer {
39            data: Vec::with_capacity(capacity),
40            head: 0,
41        }
42    }
43
44    /// Push a new element to the front of the buffer.
45    pub fn push(&mut self, elem: T) {
46        if self.data.len() < self.data.capacity() {
47            self.data.push(elem);
48            self.head = self.data.len() - 1;
49            return;
50        }
51        self.head = (self.head + 1) % self.capacity();
52        *self.data.index_mut(self.head) = elem;
53    }
54
55    /// Return the buffer's capacity.
56    pub fn capacity(&self) -> usize {
57        self.data.capacity()
58    }
59
60    fn internal_index(&self, i: usize) -> usize {
61        (self.head + self.capacity() - i) % self.capacity()
62    }
63}
64
65impl<T> std::ops::Index<usize> for CircularBuffer<T> {
66    type Output = T;
67
68    /// Get the element at the provided index.
69    ///
70    /// The first element in the buffer has index 0, the next element index 1, etc.
71    ///
72    /// This method may panic if the index is valid.
73    fn index(&self, i: usize) -> &T {
74        &self.data[self.internal_index(i)]
75    }
76}
77
78impl<T: Clone> CircularBuffer<T> {
79    /// Clone the element at the provided index to the front of the buffer.
80    ///
81    /// The buffer contains the following optimization: if the buffer is full and the
82    /// referenced element is the tail element, this method is a no-op.
83    /// If the method's clone function has side effects, these will not be seen, as in
84    /// the following example.
85    ///
86    /// ```
87    /// # use texcraft_stdext::collections::circularbuffer::CircularBuffer;
88    /// # use std::rc::Rc;
89    /// # use std::cell::RefCell;
90    /// /// A struct whose clone function has a side effect; i.e., is not pure.
91    /// /// The side effect is that a shared counter owned by all clones is incremented.
92    /// /// The shared counter thus records the number of times a clone has occured.
93    /// struct ImpureClone {
94    ///     counter: Rc<RefCell<i64>>,
95    /// }
96    ///
97    /// impl Clone for ImpureClone {
98    ///     fn clone(&self) -> Self {
99    ///         let old_count = *self.counter.borrow();
100    ///         *self.counter.borrow_mut() = old_count + 1;
101    ///         ImpureClone {
102    ///             counter: self.counter.clone()
103    ///         }
104    ///     }
105    /// }
106    ///
107    /// let mut buf = CircularBuffer::new(2);
108    /// let counter = Rc::new(RefCell::new(0));
109    /// buf.push(ImpureClone{counter: counter.clone()});
110    /// assert_eq![*counter.borrow(), 0];
111    ///
112    /// buf.clone_to_front(0);
113    /// assert_eq![*counter.borrow(), 1];
114    ///
115    /// // Clone from the tail - no clone occurs!
116    /// buf.clone_to_front(1);
117    /// assert_eq![*counter.borrow(), 1];
118    /// ```
119    pub fn clone_to_front(&mut self, i: usize) -> &mut T {
120        let i = self.internal_index(i);
121        if self.data.len() < self.data.capacity() {
122            self.push(self.data[i].clone());
123            return self.data.last_mut().unwrap();
124        }
125        let tail_i = (self.head + 1) % self.capacity();
126        match i.cmp(&tail_i) {
127            std::cmp::Ordering::Equal => {
128                // If we're cloning the current tail, we just make it the head by incrementing
129                // the head ptr. No need to clone in this case!
130            }
131            std::cmp::Ordering::Less => {
132                let (front, back) = self.data.split_at_mut(tail_i);
133                back[0].clone_from(&front[i]);
134            }
135            std::cmp::Ordering::Greater => {
136                let (front, back) = self.data.split_at_mut(i);
137                front[tail_i].clone_from(&back[0]);
138            }
139        }
140        self.head = tail_i;
141        self.data.index_mut(self.head)
142    }
143}
texcraft_stdext/collections/circularbuffer.rs

texcraft_stdext/collections/
circularbuffer.rs
