stable_queue/
lib.rs

Help
1use std::{
2    collections::VecDeque,
3    ops::{Index, IndexMut},
4};
5
6#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
7pub struct StableIndex(usize);
8impl StableIndex {
9    pub fn next_idx(self) -> StableIndex {
10        StableIndex(self.0 + 1)
11    }
12}
13
14/// As long as the element is not popped, the index returned by [push_back](Self::push_back)
15/// will continue to point to the pushed element.
16pub struct StableQueue<T> {
17    inner: VecDeque<T>,
18    head: StableIndex,
19    fixed_capacity: Option<usize>,
20}
21
22impl<T> StableQueue<T> {
23    pub fn new_unbounded() -> Self {
24        Self {
25            inner: VecDeque::new(),
26            head: StableIndex(0),
27            fixed_capacity: None,
28        }
29    }
30
31    /// If initialized with a fixed capacity, the queue cannot grow beyond that capacity
32    /// and the address in memory of elements inserted into the queue will not change.
33    pub fn with_fixed_capacity(cap: usize) -> Self {
34        Self {
35            inner: VecDeque::with_capacity(cap),
36            head: StableIndex(0),
37            fixed_capacity: Some(cap),
38        }
39    }
40
41    pub fn front(&self) -> Option<&T> {
42        self.inner.front()
43    }
44
45    pub fn front_mut(&mut self) -> Option<&mut T> {
46        self.inner.front_mut()
47    }
48
49    pub fn back(&self) -> Option<&T> {
50        self.inner.back()
51    }
52
53    pub fn back_mut(&mut self) -> Option<&mut T> {
54        self.inner.back_mut()
55    }
56
57    pub fn push_back(&mut self, value: T) -> Result<StableIndex, T> {
58        if Some(self.len()) == self.fixed_capacity {
59            return Err(value);
60        }
61        let i = self.back_idx().map_or(self.head, StableIndex::next_idx);
62        self.inner.push_back(value);
63        Ok(i)
64    }
65
66    pub fn pop_front(&mut self) -> Option<T> {
67        let popped = self.inner.pop_front()?;
68        self.head = self.head.next_idx();
69        Some(popped)
70    }
71
72    pub fn len(&self) -> usize {
73        self.inner.len()
74    }
75
76    pub fn is_empty(&self) -> bool {
77        self.inner.is_empty()
78    }
79
80    pub fn get(&self, StableIndex(physical_idx): StableIndex) -> Option<&T> {
81        let StableIndex(head) = self.head;
82        if physical_idx < head {
83            return None;
84        }
85        let ind = physical_idx - head;
86        self.inner.get(ind)
87    }
88
89    pub fn get_mut(&mut self, StableIndex(physical_idx): StableIndex) -> Option<&mut T> {
90        let StableIndex(head) = self.head;
91        if physical_idx < head {
92            return None;
93        }
94        let ind = physical_idx - head;
95        self.inner.get_mut(ind)
96    }
97
98    pub fn front_idx(&self) -> Option<StableIndex> {
99        if self.is_empty() {
100            None
101        } else {
102            Some(self.head)
103        }
104    }
105
106    pub fn back_idx(&self) -> Option<StableIndex> {
107        if self.is_empty() {
108            return None;
109        }
110        let StableIndex(head) = self.head;
111        Some(StableIndex(head + (self.len() - 1)))
112    }
113
114    pub fn fixed_capacity(&self) -> Option<usize> {
115        self.fixed_capacity
116    }
117}
118
119impl<T> Index<StableIndex> for StableQueue<T> {
120    type Output = T;
121
122    fn index(&self, idx: StableIndex) -> &Self::Output {
123        self.get(idx).unwrap()
124    }
125}
126
127impl<T> IndexMut<StableIndex> for StableQueue<T> {
128    fn index_mut(&mut self, idx: StableIndex) -> &mut Self::Output {
129        self.get_mut(idx).unwrap()
130    }
131}
stable_queue/lib.rs

stable_queue/
lib.rs
