bivec/
lib.rs

1#![deny(clippy::use_self, unsafe_op_in_unsafe_fn)]
2
3use core::ops::{Index, IndexMut};
4use std::{
5    fmt,
6    slice::{Iter, IterMut},
7};
8
9use serde::{Deserialize, Deserializer, Serialize, Serializer};
10
11/// A BiVec is like a Vec, except we allow indices to be negative. It has a min_degree
12/// property which tells us where the starting index is.
13///
14/// Note that properties like length and capacity are defined to be the maximum index allowed. For
15/// example, if `v.min_degree = -2` and `v.len() = 3`, it means we can access `v[-2], v[-1], v[0],
16/// v[1], v[2]` but not `v[3]`.
17#[derive(Clone, PartialEq, Eq)]
18pub struct BiVec<T> {
19    data: Vec<T>,
20    min_degree: i32,
21}
22
23impl<T: fmt::Debug> fmt::Debug for BiVec<T> {
24    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
25        write!(formatter, "BiVec({}) ", self.min_degree)?;
26        self.data.fmt(formatter)
27    }
28}
29
30impl<T> std::default::Default for BiVec<T> {
31    fn default() -> Self {
32        Self::new(0)
33    }
34}
35
36impl<T: Clone> BiVec<T> {
37    /// If `min_degree < self.min_degree`, set `self.min_degree` to `min_degree` and pad the
38    /// remaining spaces with `default`.
39    /// # Example
40    /// ```
41    /// # use bivec::BiVec;
42    /// let mut v = BiVec::from_vec(-2, vec![3, 4, 6, 2]);
43    /// v.extend_negative(-4, 0);
44    /// assert_eq!(v[1], 2);
45    /// assert_eq!(v[-4], 0);
46    /// assert_eq!(v.min_degree(), -4);
47    /// ```
48    pub fn extend_negative(&mut self, min_degree: i32, default: T) {
49        let shift = self.min_degree - min_degree;
50        if shift <= 0 {
51            return;
52        }
53        self.data
54            .splice(..0, std::iter::repeat_n(default, shift as usize));
55        self.min_degree = min_degree;
56    }
57}
58
59impl<T> BiVec<T> {
60    pub fn new(min_degree: i32) -> Self {
61        Self {
62            data: Vec::new(),
63            min_degree,
64        }
65    }
66
67    pub fn from_vec(min_degree: i32, data: Vec<T>) -> Self {
68        Self { data, min_degree }
69    }
70
71    pub fn into_vec(self) -> Vec<T> {
72        self.data
73    }
74
75    pub fn with_capacity(min_degree: i32, capacity: i32) -> Self {
76        debug_assert!(capacity >= min_degree);
77        Self {
78            data: Vec::with_capacity((capacity - min_degree) as usize),
79            min_degree,
80        }
81    }
82
83    pub const fn min_degree(&self) -> i32 {
84        self.min_degree
85    }
86
87    /// This returns the largest degree in the bivector. This is equal to `self.len() - 1`.
88    ///
89    /// # Example
90    /// ```
91    /// # use bivec::BiVec;
92    /// let v = BiVec::from_vec(-2, vec![3, 4, 6, 8, 2]);
93    /// assert_eq!(v.max_degree(), 2);
94    /// ```
95    pub fn max_degree(&self) -> i32 {
96        self.len() - 1
97    }
98
99    /// This returns the "length" of the bivector, defined to be the smallest i such that
100    /// `v[i]`
101    /// is not defined.
102    ///
103    /// # Example
104    /// ```
105    /// # use bivec::BiVec;
106    /// let v = BiVec::from_vec(-2, vec![3, 4, 6, 8, 2]);
107    /// assert_eq!(v.len(), 3);
108    /// ```
109    pub fn len(&self) -> i32 {
110        self.data.len() as i32 + self.min_degree
111    }
112
113    pub fn is_empty(&self) -> bool {
114        self.data.is_empty()
115    }
116
117    pub fn push(&mut self, x: T) {
118        self.data.push(x);
119    }
120
121    pub fn get(&self, idx: i32) -> Option<&T> {
122        self.data.get((idx - self.min_degree) as usize)
123    }
124
125    /// Get the `idx`th element if it exists; the last element otherwise
126    pub fn get_max(&self, idx: i32) -> &T {
127        self.get(idx).unwrap_or_else(|| self.data.last().unwrap())
128    }
129
130    pub fn last(&self) -> Option<&T> {
131        self.data.last()
132    }
133
134    pub fn iter(&self) -> Iter<'_, T> {
135        self.data.iter()
136    }
137
138    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
139        self.data.iter_mut()
140    }
141
142    pub fn iter_enum(&self) -> impl DoubleEndedIterator<Item = (i32, &T)> {
143        let min_degree = self.min_degree;
144        self.data
145            .iter()
146            .enumerate()
147            .map(move |(i, t)| (i as i32 + min_degree, t))
148    }
149
150    pub fn iter_mut_enum(&mut self) -> impl DoubleEndedIterator<Item = (i32, &mut T)> {
151        let min_degree = self.min_degree;
152        self.data
153            .iter_mut()
154            .enumerate()
155            .map(move |(i, t)| (i as i32 + min_degree, t))
156    }
157
158    pub fn into_iter_enum(self) -> impl DoubleEndedIterator<Item = (i32, T)> {
159        let min_degree = self.min_degree;
160        self.data
161            .into_iter()
162            .enumerate()
163            .map(move |(i, t)| (i as i32 + min_degree, t))
164    }
165
166    /// Extends the bivec such that `max_degree()` is at least `max`. If `max_degree()` is
167    /// already at least `max`, the function does nothing. Otherwise, it fills the new entries
168    /// with the return value of `F(i)`, where i is the index of the new entry.
169    pub fn extend_with<F>(&mut self, max: i32, mut f: F)
170    where
171        F: FnMut(i32) -> T,
172    {
173        if max > self.max_degree() {
174            self.data.reserve((max - self.max_degree()) as usize);
175            for i in self.len()..=max {
176                self.data.push(f(i));
177            }
178        }
179    }
180
181    pub fn reserve(&mut self, num: usize) {
182        self.data.reserve(num);
183    }
184
185    /// Mutably borrows i and j. Panic if i != j.
186    ///
187    /// # Example
188    /// ```
189    /// # use bivec::BiVec;
190    /// let mut v = BiVec::from_vec(1, vec![3, 5, 2]);
191    /// let (x, y) = v.split_borrow_mut(1, 3);
192    /// assert_eq!(*x, 3);
193    /// assert_eq!(*y, 2);
194    ///
195    /// let (x, y) = v.split_borrow_mut(3, 2);
196    /// assert_eq!(*x, 2);
197    /// assert_eq!(*y, 5);
198    /// ```
199    pub fn split_borrow_mut(&mut self, i: i32, j: i32) -> (&mut T, &mut T) {
200        assert!(i != j);
201        let min = self.min_degree;
202        if i > j {
203            let (f, s) = self.data.split_at_mut((i - min) as usize);
204            (&mut s[0], &mut f[(j - min) as usize])
205        } else {
206            let (f, s) = self.data.split_at_mut((j - min) as usize);
207            (&mut f[(i - min) as usize], &mut s[0])
208        }
209    }
210
211    pub fn range(&self) -> std::ops::Range<i32> {
212        self.min_degree..self.len()
213    }
214}
215
216impl<T> IntoIterator for BiVec<T> {
217    type IntoIter = std::vec::IntoIter<T>;
218    type Item = T;
219
220    fn into_iter(self) -> Self::IntoIter {
221        self.data.into_iter()
222    }
223}
224
225impl<'a, T> IntoIterator for &'a BiVec<T> {
226    type IntoIter = std::slice::Iter<'a, T>;
227    type Item = &'a T;
228
229    fn into_iter(self) -> Self::IntoIter {
230        self.iter()
231    }
232}
233
234impl<'a, T> IntoIterator for &'a mut BiVec<T> {
235    type IntoIter = std::slice::IterMut<'a, T>;
236    type Item = &'a mut T;
237
238    fn into_iter(self) -> Self::IntoIter {
239        self.iter_mut()
240    }
241}
242
243impl<A> std::iter::Extend<A> for BiVec<A> {
244    fn extend<T>(&mut self, iter: T)
245    where
246        T: IntoIterator<Item = A>,
247    {
248        self.data.extend(iter)
249    }
250}
251
252impl<T: Serialize> Serialize for BiVec<T> {
253    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
254    where
255        S: Serializer,
256    {
257        self.data.serialize(serializer) // Do better than this
258    }
259}
260
261impl<'de, T: Deserialize<'de>> Deserialize<'de> for BiVec<T> {
262    fn deserialize<D>(_deserializer: D) -> Result<Self, D::Error>
263    where
264        D: Deserializer<'de>,
265    {
266        unimplemented!()
267    }
268}
269
270impl<T> Index<i32> for BiVec<T> {
271    type Output = T;
272
273    fn index(&self, i: i32) -> &T {
274        assert!(
275            i >= self.min_degree(),
276            "Index out of bounds: the minimum degree is {} but the index is {i}",
277            self.min_degree()
278        );
279        assert!(
280            i < self.len(),
281            "Index out of bounds: the length is {} but the index is {i}",
282            self.len()
283        );
284        &(self.data[(i - self.min_degree) as usize])
285    }
286}
287
288impl<T> IndexMut<i32> for BiVec<T> {
289    fn index_mut(&mut self, i: i32) -> &mut T {
290        assert!(
291            i >= self.min_degree(),
292            "Index out of bounds: the minimum degree is {} but the index is {i}",
293            self.min_degree()
294        );
295        assert!(
296            i < self.len(),
297            "Index out of bounds: the length is {} but the index is {i}",
298            self.len()
299        );
300        &mut (self.data[(i - self.min_degree) as usize])
301    }
302}
bivec/lib.rs

bivec/
lib.rs
