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
use std::cmp::min;
use std::fmt::Debug;
#[derive(Debug)]
pub struct RingVec<T: Debug> {
inner: Vec<Option<T>>,
capacity: usize,
start: usize,
len: usize,
}
impl<T: Debug> RingVec<T> {
pub fn new(capacity: usize) -> RingVec<T> {
if capacity > 0 {
RingVec { inner: Vec::new(), capacity, start: 0, len: 0 }
} else {
panic!("RingVec requires a nonzero capacity");
}
}
pub fn new_preallocated(capacity: usize) -> RingVec<T> {
let inner = Vec::with_capacity(capacity);
RingVec { inner, capacity, start: 0, len: 0 }
}
pub fn is_full(&self) -> bool { self.len == self.capacity }
pub fn len(&self) -> usize { self.inner.len() - self.start }
pub fn capacity(&self) -> usize { self.capacity }
pub fn peek(&self) -> Option<&T> {
if self.len > 0 { self.inner[self.start].as_ref() }
else { None }
}
pub fn pop(&mut self) -> Option<T> {
if self.len > 0 {
let start = self.start;
self.start = (self.start + 1) % self.capacity;
self.len -= 1;
let ret = self.inner[start].take();
ret
} else { None }
}
pub fn push(&mut self, item: T) -> Result<(), T> {
if self.len < self.capacity {
let end = self.start + self.len;
if end >= self.inner.capacity() {
self.inner.push(Some(item));
} else {
self.inner[end % self.capacity] = Some(item);
}
self.len += 1;
Ok(())
} else {
Err(item)
}
}
pub fn empty(&mut self) {
self.inner.clear();
self.start = 0;
self.len = 0;
}
pub fn shrink_to_fit(&mut self) {
if self.len == self.capacity { return; }
let mut new = Vec::with_capacity(self.len());
let end = self.start + self.len;
for i in self.start..min(end, self.capacity) {
new.push(self.inner[i].take());
}
if end > self.capacity {
for i in 0..(end - self.capacity) {
new.push(self.inner[i].take());
}
}
self.inner = new;
}
}
#[cfg(test)]
mod tests {
use crate::RingVec;
#[test]
fn works() {
let mut q: RingVec<usize> = RingVec::new(1);
assert_eq!(q.peek(), None);
assert_eq!(q.pop(), None);
assert_eq!(q.push(1), Ok(()));
assert_eq!(q.peek(), Some(&1));
assert_eq!(q.pop(), Some(1));
assert_eq!(q.peek(), None);
assert_eq!(q.pop(), None);
assert_eq!(q.push(2), Ok(()));
assert_eq!(q.peek(), Some(&2));
assert_eq!(q.push(3), Err(3));
assert_eq!(q.pop(), Some(2));
assert_eq!(q.push(4), Ok(()));
assert_eq!(q.peek(), Some(&4));
assert_eq!(q.pop(), Some(4));
assert_eq!(q.peek(), None);
assert_eq!(q.pop(), None);
assert_eq!(q.peek(), None);
}
}