1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//! A circular buffer.
//!
//! See the documentation on the [CircularBuffer] type.

use std::ops::IndexMut;

/// A circular buffer.
///
/// A circular buffer is an ordered buffer with a fixed capacity and the property that if it is full
/// and a new element is pushed to the front, the oldest element is deleted.
///
/// The buffer is created using the [new](CircularBuffer::new) method, elements are pushed to the
/// front using [push](CircularBuffer::push), and retrieved using
/// [std::ops::Index::index] trait method.
///
/// ```
/// # use texcraft_stdext::collections::circularbuffer::CircularBuffer;
/// # use std::ops::Index;
/// let mut buf = CircularBuffer::new(3);
/// buf.push(0);
/// buf.push(1);
/// assert_eq![buf.index(0), &1];
/// assert_eq![buf.index(1), &0];
/// buf.push(2);
/// buf.push(3);
/// assert_eq![buf.index(0), &3];
/// assert_eq![buf.index(1), &2];
/// assert_eq![buf.index(2), &1];
/// ```
pub struct CircularBuffer<T> {
    data: Vec<T>,
    head: usize,
}

impl<T> CircularBuffer<T> {
    /// Create a new circular buffer with the provided capacity.
    pub fn new(capacity: usize) -> CircularBuffer<T> {
        CircularBuffer {
            data: Vec::with_capacity(capacity),
            head: 0,
        }
    }

    /// Push a new element to the front of the buffer.
    pub fn push(&mut self, elem: T) {
        if self.data.len() < self.data.capacity() {
            self.data.push(elem);
            self.head = self.data.len() - 1;
            return;
        }
        self.head = (self.head + 1) % self.capacity();
        *self.data.index_mut(self.head) = elem;
    }

    /// Return the buffer's capacity.
    pub fn capacity(&self) -> usize {
        self.data.capacity()
    }

    fn internal_index(&self, i: usize) -> usize {
        (self.head + self.capacity() - i) % self.capacity()
    }
}

impl<T> std::ops::Index<usize> for CircularBuffer<T> {
    type Output = T;

    /// Get the element at the provided index.
    ///
    /// The first element in the buffer has index 0, the next element index 1, etc.
    ///
    /// This method may panic if the index is valid.
    fn index(&self, i: usize) -> &T {
        &self.data[self.internal_index(i)]
    }
}

impl<T: Clone> CircularBuffer<T> {
    /// Clone the element at the provided index to the front of the buffer.
    ///
    /// The buffer contains the following optimization: if the buffer is full and the
    /// referenced element is the tail element, this method is a no-op.
    /// If the method's clone function has side effects, these will not be seen, as in
    /// the following example.
    ///
    /// ```
    /// # use texcraft_stdext::collections::circularbuffer::CircularBuffer;
    /// # use std::rc::Rc;
    /// # use std::cell::RefCell;
    /// /// A struct whose clone function has a side effect; i.e., is not pure.
    /// /// The side effect is that a shared counter owned by all clones is incremented.
    /// /// The shared counter thus records the number of times a clone has occured.
    /// struct ImpureClone {
    ///     counter: Rc<RefCell<i64>>,
    /// }
    ///
    /// impl Clone for ImpureClone {
    ///     fn clone(&self) -> Self {
    ///         let old_count = *self.counter.borrow();
    ///         *self.counter.borrow_mut() = old_count + 1;
    ///         ImpureClone {
    ///             counter: self.counter.clone()
    ///         }
    ///     }
    /// }
    ///
    /// let mut buf = CircularBuffer::new(2);
    /// let counter = Rc::new(RefCell::new(0));
    /// buf.push(ImpureClone{counter: counter.clone()});
    /// assert_eq![*counter.borrow(), 0];
    ///
    /// buf.clone_to_front(0);
    /// assert_eq![*counter.borrow(), 1];
    ///
    /// // Clone from the tail - no clone occurs!
    /// buf.clone_to_front(1);
    /// assert_eq![*counter.borrow(), 1];
    /// ```
    pub fn clone_to_front(&mut self, i: usize) -> &mut T {
        let i = self.internal_index(i);
        if self.data.len() < self.data.capacity() {
            self.push(self.data[i].clone());
            return self.data.last_mut().unwrap();
        }
        let tail_i = (self.head + 1) % self.capacity();
        match i.cmp(&tail_i) {
            std::cmp::Ordering::Equal => {
                // If we're cloning the current tail, we just make it the head by incrementing
                // the head ptr. No need to clone in this case!
            }
            std::cmp::Ordering::Less => {
                let (front, back) = self.data.split_at_mut(tail_i);
                back[0].clone_from(&front[i]);
            }
            std::cmp::Ordering::Greater => {
                let (front, back) = self.data.split_at_mut(i);
                front[tail_i].clone_from(&back[0]);
            }
        }
        self.head = tail_i;
        self.data.index_mut(self.head)
    }
}