isize_vec/
lib.rs

1//! Vector of items with associated [isize] for ordering.
2#![deny(
3    missing_docs,
4    trivial_casts,
5    trivial_numeric_casts,
6    unsafe_code,
7    unused_import_braces,
8    unused_qualifications
9)]
10use std::{
11    mem,
12    ops::{Index, IndexMut, RangeBounds},
13    slice::{Iter, IterMut, SliceIndex},
14    vec::{Drain, IntoIter},
15};
16
17/// Container for multiple elements sorted by a certain `isize` order.
18///
19/// Every element `T` is tagged with an associated `isize`. The `isize` value decides the relative
20/// ordering of the elements. All manipulations keep the items `T` ordered according to the `isize`
21/// values from lowest to highest.
22///
23/// ```
24/// use isize_vec::IsizeVec;
25///
26/// let mut vector = IsizeVec::new();
27///
28/// vector.insert(10, 'a');
29/// vector.insert(5, 'b');
30///
31/// println!("{:?}", vector);
32///
33/// for value in vector {
34///     println!("{}", value);
35/// }
36/// ```
37#[derive(Clone, Debug)]
38pub struct IsizeVec<T> {
39    items: Vec<T>,
40    order: Vec<isize>,
41}
42
43impl<T> Default for IsizeVec<T> {
44    fn default() -> Self {
45        Self {
46            items: Vec::new(),
47            order: Vec::new(),
48        }
49    }
50}
51
52impl<T> IsizeVec<T> {
53    /// Create a new vector.
54    pub fn new() -> Self {
55        Self {
56            items: Vec::new(),
57            order: Vec::new(),
58        }
59    }
60
61    /// Get an iterator to the values.
62    #[inline]
63    pub fn iter(&self) -> Iter<T> {
64        self.items.iter()
65    }
66
67    /// Get an iterator to the values (mutable).
68    #[inline]
69    pub fn iter_mut(&mut self) -> IterMut<T> {
70        self.items.iter_mut()
71    }
72
73    /// Push a value to the end of the vector, with `relative: isize::MAX`.
74    pub fn push(&mut self, item: T) -> usize {
75        self.items.push(item);
76        self.order.push(isize::MAX);
77        self.items.len() - 1
78    }
79
80    /// Remove the last element from this vector.
81    pub fn pop(&mut self) -> Option<(T, isize)> {
82        if !self.items.is_empty() {
83            Some((self.items.pop().unwrap(), self.order.pop().unwrap()))
84        } else {
85            None
86        }
87    }
88
89    /// Create a drain iterator.
90    pub fn drain<R>(&mut self, range: R) -> Drain<T>
91    where
92        R: Clone + RangeBounds<usize>,
93    {
94        self.order.drain(range.clone());
95        self.items.drain(range)
96    }
97
98    /// Returns the length of the container
99    pub fn len(&self) -> usize {
100        self.items.len()
101    }
102
103    /// Returns whether the container is empty.
104    pub fn is_empty(&self) -> bool {
105        self.items.is_empty()
106    }
107
108    /// Get the item at a given index.
109    pub fn get(&self, index: usize) -> Option<&T> {
110        self.items.get(index)
111    }
112
113    /// Get the item at a given index.
114    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
115        self.items.get_mut(index)
116    }
117
118    /// Return the backing vector and clear this container.
119    pub fn extract(&mut self) -> Vec<T> {
120        self.order.clear();
121        mem::replace(&mut self.items, Vec::new())
122    }
123
124    /// Find the index at which positive elements start.
125    pub fn first_positive(&self) -> usize {
126        self.first_right_of(-1)
127    }
128
129    /// Insert a value into this vector.
130    ///
131    /// The value `relative` indicates where the value will be put in the list relative to other
132    /// values. If two values have the same `relative` value, then the value will be prepended if it
133    /// is signed, and appended if unsigned.
134    ///
135    /// Returns the index of insertion.
136    pub fn insert(&mut self, relative: isize, item: T) -> usize {
137        match self.order.binary_search(&relative) {
138            Ok(exact) => {
139                if relative >= 0 {
140                    match self.order[exact..]
141                        .iter()
142                        .enumerate()
143                        .find(|(_, &x)| x != relative)
144                    {
145                        Some((idx, _)) => {
146                            self.items.insert(exact + idx, item);
147                            self.order.insert(exact + idx, relative);
148                            exact + idx
149                        }
150                        None => {
151                            self.items.push(item);
152                            self.order.push(relative);
153                            self.items.len() - 1
154                        }
155                    }
156                } else {
157                    match self.order[..exact]
158                        .iter()
159                        .rev()
160                        .enumerate()
161                        .find(|(_, &x)| x != relative)
162                    {
163                        Some((idx, _)) => {
164                            self.items.insert(exact - idx, item);
165                            self.order.insert(exact - idx, relative);
166                            exact - idx
167                        }
168                        None => {
169                            self.items.insert(0, item);
170                            self.order.insert(0, relative);
171                            0
172                        }
173                    }
174                }
175            }
176            Err(order) => {
177                self.items.insert(order, item);
178                self.order.insert(order, relative);
179                order
180            }
181        }
182    }
183
184    /// Remove the given index from the vector.
185    pub fn remove(&mut self, index: usize) -> (T, isize) {
186        (self.items.remove(index), self.order.remove(index))
187    }
188
189    /// Find the first index to the right of the relative list.
190    pub fn first_right_of(&self, relative: isize) -> usize {
191        match self.order.binary_search(&relative) {
192            Ok(exact) => self.order[exact..]
193                .iter()
194                .enumerate()
195                .find(|(_, &x)| x != relative)
196                .map(|(index, _)| exact + index)
197                .unwrap_or_else(|| self.order.len()),
198            Err(order) => order,
199        }
200    }
201
202    /// Swap two elements in the list. Associated order is swapped.
203    pub fn swap(&mut self, a: usize, b: usize) {
204        self.items.swap(a, b);
205    }
206
207    /// Same as [Vec::retain].
208    pub fn retain<F>(&mut self, mut f: F)
209    where
210        F: FnMut(&T) -> bool,
211    {
212        let mut removed = 0;
213        let mut idx = 0;
214        let order = &mut self.order;
215        self.items.retain(|x| {
216            idx += 1;
217            if (f)(x) {
218                true
219            } else {
220                order.remove(idx - 1 - removed);
221                removed += 1;
222                false
223            }
224        });
225    }
226}
227
228impl<T, I> Index<I> for IsizeVec<T>
229where
230    I: SliceIndex<[T]>,
231{
232    type Output = <I as SliceIndex<[T]>>::Output;
233    fn index(&self, index: I) -> &<Vec<T> as Index<I>>::Output {
234        &self.items[index]
235    }
236}
237
238impl<T, I> IndexMut<I> for IsizeVec<T>
239where
240    I: SliceIndex<[T]>,
241{
242    fn index_mut(&mut self, index: I) -> &mut <Vec<T> as Index<I>>::Output {
243        &mut self.items[index]
244    }
245}
246
247impl<T> IntoIterator for IsizeVec<T> {
248    type Item = T;
249    type IntoIter = IntoIter<T>;
250    fn into_iter(self) -> IntoIter<T> {
251        self.items.into_iter()
252    }
253}
254
255impl<'a, T> IntoIterator for &'a IsizeVec<T> {
256    type Item = &'a T;
257    type IntoIter = Iter<'a, T>;
258    fn into_iter(self) -> Iter<'a, T> {
259        self.items.iter()
260    }
261}
262
263impl<'a, T> IntoIterator for &'a mut IsizeVec<T> {
264    type Item = &'a mut T;
265    type IntoIter = IterMut<'a, T>;
266    fn into_iter(self) -> IterMut<'a, T> {
267        self.items.iter_mut()
268    }
269}
270
271#[cfg(test)]
272mod tests {
273    use super::IsizeVec;
274
275    #[quickcheck_macros::quickcheck]
276    fn inserting_appends_or_prepends(relative: isize, values: usize) {
277        let mut vector = IsizeVec::new();
278
279        for value in 0..values {
280            vector.insert(relative, value);
281        }
282
283        if relative >= 0 {
284            let mut value = 0;
285            for item in vector.iter() {
286                assert_eq!(value, *item);
287                value += 1;
288            }
289            assert_eq!(value, values);
290        } else {
291            let mut value = values;
292            for item in vector.iter() {
293                value -= 1;
294                assert_eq!(value, *item);
295            }
296            assert_eq!(value, 0);
297        }
298    }
299
300    #[quickcheck_macros::quickcheck]
301    fn insertion_behaves_as_ordering(orders: Vec<(u8, isize)>) {
302        let mut vector = IsizeVec::new();
303
304        for (item, order) in &orders {
305            vector.insert(*order, item);
306        }
307
308        let mut unsigned = orders
309            .iter()
310            .cloned()
311            .filter(|(_, o)| o >= &0)
312            .collect::<Vec<_>>();
313
314        let mut signed = orders
315            .iter()
316            .cloned()
317            .filter(|(_, o)| o < &0)
318            .collect::<Vec<_>>();
319
320        unsigned.sort_by(|a, b| a.1.cmp(&b.1));
321        signed.reverse();
322        signed.sort_by(|a, b| a.1.cmp(&b.1));
323
324        for (idx, (item, _)) in signed.iter().chain(unsigned.iter()).enumerate() {
325            assert_eq!(vector[idx], item);
326        }
327    }
328
329    #[quickcheck_macros::quickcheck]
330    fn first_right_of_size(orders: Vec<isize>) {
331        let mut vector = IsizeVec::new();
332
333        for order in &orders {
334            vector.insert(*order, ());
335        }
336
337        assert_eq!(vector.first_right_of(isize::MAX), vector.len());
338    }
339
340    #[test]
341    fn basic() {
342        let mut vector = IsizeVec::new();
343
344        let value = 0;
345        vector.insert(0, 0);
346        vector.insert(1, 1);
347
348        let mut number = 0;
349        for item in vector.iter() {
350            assert_eq!(number, *item);
351            number += 1;
352        }
353        assert_eq!(number, 2);
354
355        vector.retain(|&x| x != value);
356
357        let mut number = 1;
358        for item in vector.iter() {
359            assert_eq!(number, *item);
360            number += 1;
361        }
362        assert_eq!(number, 2);
363    }
364
365    #[test]
366    fn haystack() {
367        let mut vector = IsizeVec::new();
368
369        let value = 0;
370        for _ in 0..10 {
371            vector.insert(0, value);
372        }
373        for _ in 0..10 {
374            vector.insert(2, value);
375        }
376
377        vector.insert(1, 1);
378
379        vector.retain(|&x| x != value);
380
381        let mut count = 0;
382        for item in vector.iter() {
383            assert_eq!(*item, 1);
384            count += 1;
385        }
386        assert_eq!(count, 1);
387    }
388
389    #[test]
390    fn find_first_positive() {
391        let mut vector = IsizeVec::new();
392        vector.insert(-1, 'a');
393        vector.insert(0, 'b');
394        vector.insert(1, 'c');
395
396        assert!(matches!(vector.first_positive(), 1));
397
398        let mut vector = IsizeVec::new();
399        vector.insert(-2, 'a');
400        vector.insert(-1, 'b');
401
402        assert!(matches!(vector.first_positive(), 2));
403
404        let mut vector = IsizeVec::new();
405        vector.insert(-2, 'a');
406        vector.insert(0, 'b');
407
408        assert!(matches!(vector.first_positive(), 1));
409
410        let mut vector = IsizeVec::new();
411        vector.insert(0, 'a');
412        vector.insert(1, 'b');
413
414        assert!(matches!(vector.first_positive(), 0));
415
416        let mut vector = IsizeVec::new();
417        vector.insert(0, 'a');
418        vector.insert(0, 'b');
419        vector.insert(0, 'c');
420
421        assert!(matches!(vector.first_positive(), 0));
422    }
423
424    #[test]
425    fn find_first_right_of() {
426        let mut vector = IsizeVec::new();
427        vector.insert(0, 'a');
428        vector.insert(1, 'a');
429
430        assert!(matches!(vector.first_right_of(1), 2));
431
432        let mut vector = IsizeVec::new();
433        vector.insert(0, 'a');
434        vector.insert(1, 'a');
435        vector.insert(2, 'a');
436
437        assert!(matches!(vector.first_right_of(1), 2));
438
439        let mut vector = IsizeVec::new();
440        vector.insert(0, 'a');
441        vector.insert(2, 'a');
442
443        assert!(matches!(vector.first_right_of(1), 1));
444
445        let mut vector = IsizeVec::new();
446        vector.insert(-101, 'a');
447        vector.insert(-100, 'b');
448
449        assert!(matches!(vector.first_right_of(0), 2));
450        assert!(matches!(vector.first_right_of(-100), 2));
451        assert!(matches!(vector.first_right_of(-101), 1));
452        assert!(matches!(vector.first_right_of(-1000), 0));
453
454        let mut vector = IsizeVec::new();
455        vector.insert(0, 'a');
456        vector.insert(0, 'b');
457
458        assert!(matches!(vector.first_right_of(0), 2));
459    }
460}
isize_vec/lib.rs

isize_vec/
lib.rs
