scanmut/
lib.rs

1//! Insert or remove multiple elements from a [Vec] in `O(n)` time.
2//!
3//! This crate provides two types for versatile and efficient [Vec] mutation; [Inserter] and
4//! [Remover]. These two types can be seen as more generic implementations of [Vec::insert] and
5//! [Vec::drain], allowing you to for example efficiently insert a slice, conditionally drain
6//! elements, or access elements of a [Vec] while draining from it.
7//!
8//! [Inserter] and [Remover] requires an ordering of the insert and removal indices; monotonically
9//! non-increasing for [Inserter] and monotonically increasing for [Remover].
10//!
11//! For convenience, there are also extension traits adding common higher level operations using the
12//! [Inserter] and [Remover]. See [ScanMut], [InsertSliceClone], and [InsertSliceCopy].
13//!
14//! # Examples
15//!
16//! Inserting a slice into a vec using [ScanMut::insert_all]:
17//!
18//! ```
19//! use scanmut::prelude::*;
20//!
21//! let mut v = vec!['a', 'b', 'c'];
22//! v.insert_all(1, ['d', 'e'].iter().cloned());
23//! assert_eq!(v, vec!['a', 'd', 'e', 'b', 'c']);
24//! ```
25//! 
26//! Removing multiple elements in one scan using [ScanMut::multi_remove]:
27//!
28//! ```
29//! use scanmut::prelude::*;
30//!
31//! let mut v = vec!['a', 'b', 'c'];
32//! v.multi_remove([0, 2].iter().cloned(), drop);
33//! assert_eq!(v, vec!['b']);
34//! ```
35
36#![deny(missing_debug_implementations, missing_docs)]
37#![no_std]
38
39#[cfg(test)]
40extern crate std;
41extern crate alloc;
42
43mod inserter;
44mod remover;
45
46#[cfg(test)]
47pub mod proputils;
48
49use alloc::vec::Vec;
50pub use inserter::Inserter;
51pub use remover::Remover;
52
53/// Module of commonly-used traits
54pub mod prelude {
55    pub use super::{InsertSliceClone, InsertSliceCopy, ScanMut};
56}
57
58/// Multiple insert/remove functions
59pub trait ScanMut<T> {
60    /// Insert multiple elements at specific indices in `O(n)` time.
61    ///
62    /// Indices must be in monotonically non-increasing order (i.e. the next index must be smaller
63    /// than or equal to the previous index).
64    ///
65    /// # Example
66    ///
67    /// ```
68    /// use scanmut::ScanMut;
69    ///
70    /// let mut v = vec![1, 2, 3, 4, 5];
71    /// v.multi_insert([(3, 8), (3, 7), (0, 6)].iter().cloned());
72    ///
73    /// assert_eq!(v, vec![6, 1, 2, 3, 7, 8, 4, 5]);
74    /// ```
75    ///
76    /// # Panics
77    ///
78    /// Panics if
79    /// - The indices are not monotonically non-increasing.
80    /// - An index is out of bounds.
81    ///
82    fn multi_insert<I>(&mut self, iter: I)
83    where
84        I: IntoIterator<Item = (usize, T)>,
85        I::IntoIter: ExactSizeIterator;
86
87    /// Remove multiple elements by index and calls a sink function with the removed element.
88    ///
89    /// Indices must be in monotonically increasing order (i.e. the next index must be more than the
90    /// previous index).
91    ///
92    /// # Example
93    ///
94    /// ```
95    /// use scanmut::ScanMut;
96    ///
97    /// let mut v = vec![1, 2, 3, 4, 5];
98    /// v.multi_remove([0, 3].iter().cloned(), drop);
99    ///
100    /// assert_eq!(v, vec![2, 3, 5]);
101    /// ```
102    ///
103    /// # Panics
104    ///
105    /// Panics if
106    /// - The indices are not monotonically increasing.
107    /// - An index is out of bounds.
108    fn multi_remove<I, F>(&mut self, iter: I, sink: F)
109    where
110        I: IntoIterator<Item = usize>,
111        F: FnMut(T);
112
113    // Ideally, the above function  would return an iterator of removed elements instead, but that
114    // currently does not seem possible without generic associated types. 🤷
115
116    /// Inserts items from an iterator at the given index.
117    ///
118    /// # Panics
119    ///
120    /// Panics if
121    /// - The range `index..(index + items.len())` is out of bounds for this `Vec`.
122    /// - The iterator is shorter or longer than the reported length.
123    fn insert_all<I>(&mut self, index: usize, items: I)
124    where
125        I: IntoIterator<Item = T>,
126        I::IntoIter: ExactSizeIterator + DoubleEndedIterator;
127
128    /// Inserts items in reverse from an iterator at the given index.
129    ///
130    /// # Panics
131    ///
132    /// Panics if
133    /// - The range `index..(index + items.len())` is out of bounds for this `Vec`.
134    /// - The iterator is shorter or longer than the reported length.
135    fn insert_all_rev<I>(&mut self, index: usize, items: I)
136    where
137        I: IntoIterator<Item = T>,
138        I::IntoIter: ExactSizeIterator;
139}
140
141impl<T> ScanMut<T> for Vec<T> {
142    fn multi_insert<I>(&mut self, iter: I)
143    where
144        I: IntoIterator<Item = (usize, T)>,
145        I::IntoIter: ExactSizeIterator,
146    {
147        let iter = iter.into_iter();
148        let mut inserter = Inserter::new(self, iter.len());
149        iter.for_each(|(ix, item)| {
150            inserter.move_to(ix);
151            inserter.insert(item);
152        });
153
154        assert!(
155            inserter.remaining_inserts() == 0,
156            "Iterator shorter than reported length"
157        );
158    }
159
160    fn multi_remove<I, F>(&mut self, iter: I, mut sink: F)
161    where
162        I: IntoIterator<Item = usize>,
163        F: FnMut(T),
164    {
165        let mut remover = Remover::new(self);
166        iter.into_iter().for_each(|ix| {
167            remover.move_to(ix);
168            sink(remover.remove());
169        });
170    }
171
172    fn insert_all<I>(&mut self, index: usize, items: I)
173    where
174        I: IntoIterator<Item = T>,
175        I::IntoIter: ExactSizeIterator + DoubleEndedIterator,
176    {
177        let iter = items.into_iter();
178        let mut inserter = Inserter::new(self, iter.len());
179        inserter.move_to(index);
180        inserter.insert_all(iter);
181
182        assert!(
183            inserter.remaining_inserts() == 0,
184            "Iterator shorter than reported length"
185        );
186    }
187
188    fn insert_all_rev<I>(&mut self, index: usize, items: I)
189    where
190        I: IntoIterator<Item = T>,
191        I::IntoIter: ExactSizeIterator,
192    {
193        let iter = items.into_iter();
194        let mut inserter = Inserter::new(self, iter.len());
195        inserter.move_to(index);
196        inserter.insert_all_rev(iter);
197
198        assert!(
199            inserter.remaining_inserts() == 0,
200            "Iterator shorter than reported length"
201        );
202    }
203}
204
205/// ScanMut extension trait for `Vec`s with cloneable items.
206pub trait InsertSliceClone<T: Clone>: ScanMut<T> {
207    /// Inserts items from a slice at the given index by cloning elements.
208    ///
209    /// # Panics
210    ///
211    /// Panics if
212    /// - The range `index..(index + slice.len())` is out of bounds for this `Vec`.
213    fn insert_slice_clone(&mut self, index: usize, slice: &[T]);
214}
215
216impl<T: Clone> InsertSliceClone<T> for Vec<T> {
217    fn insert_slice_clone(&mut self, index: usize, slice: &[T]) {
218        let mut inserter = Inserter::new(self, slice.len());
219        inserter.move_to(index);
220        inserter.insert_slice_clone(slice);
221    }
222}
223
224/// ScanMut extension trait for `Vec`s with copyable items.
225pub trait InsertSliceCopy<T: Copy>: InsertSliceClone<T> {
226    /// Inserts items from a slice at the given index by copying elements.
227    ///
228    /// # Panics
229    ///
230    /// Panics if
231    /// - The range `index..(index + slice.len())` is out of bounds for this `Vec`.
232    fn insert_slice_copy(&mut self, index: usize, slice: &[T]);
233}
234
235impl<T: Copy> InsertSliceCopy<T> for Vec<T> {
236    fn insert_slice_copy(&mut self, index: usize, slice: &[T]) {
237        let mut inserter = Inserter::new(self, slice.len());
238        inserter.move_to(index);
239        inserter.insert_slice_copy(slice);
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246    use alloc::vec;
247    use core::iter::once;
248
249    #[test]
250    fn multimutate_single_insert() {
251        let mut items = Vec::new();
252        items.multi_insert(once((0, 1)));
253        assert_eq!(items, vec![1]);
254    }
255
256    #[test]
257    fn multimutate_single_insert_pre() {
258        let mut items = vec![0];
259        items.multi_insert(once((0, 1)));
260        assert_eq!(items, vec![1, 0]);
261    }
262
263    #[test]
264    fn multimutate_single_insert_mid() {
265        let mut items = vec![0, 2];
266        items.multi_insert(once((1, 1)));
267        assert_eq!(items, vec![0, 1, 2]);
268    }
269
270    #[test]
271    fn multimutate_single_insert_post() {
272        let mut items = vec![0];
273        items.multi_insert(once((1, 1)));
274        assert_eq!(items, vec![0, 1]);
275    }
276
277    #[test]
278    #[should_panic]
279    fn multimutate_single_insert_out_of_bounds() {
280        let mut items = vec![0];
281        items.multi_insert(once((2, 1)));
282    }
283
284    #[test]
285    fn multimutate_multiple_insert() {
286        let mut items = vec![1];
287        items.multi_insert([(1, 2), (0, 0)].iter().cloned());
288        assert_eq!(items, vec![0, 1, 2]);
289    }
290
291    #[test]
292    fn multimutate_single_insert_zero_sized() {
293        let mut items = vec![()];
294        items.multi_insert(once((0, ())));
295        assert_eq!(items, vec![(), ()]);
296    }
297
298    #[test]
299    #[should_panic]
300    fn multimutate_single_insert_zero_sized_out_of_bounds() {
301        let mut items = vec![()];
302        items.multi_insert(once((2, ())));
303        assert_eq!(items, vec![(), ()]);
304    }
305
306    #[test]
307    #[should_panic]
308    fn multimutate_remove() {
309        let mut items = vec![1, 2, 3];
310        let mut index = 0;
311
312        items.multi_remove(vec![1, 2], |x| {
313            assert_eq!(
314                x,
315                match index {
316                    0 => 1,
317                    1 => 2,
318                    _ => panic!(),
319                }
320            );
321
322            index += 1;
323        });
324
325        assert_eq!(items, [1]);
326    }
327
328    #[test]
329    fn insert_all() {
330        let mut items = vec![1, 2, 3];
331        items.insert_all(1, [4, 5, 6].iter().cloned());
332        assert_eq!(items, [1, 4, 5, 6, 2, 3]);
333    }
334
335    #[test]
336    fn insert_all_end() {
337        let mut items = vec![1, 2, 3];
338        items.insert_all(3, [4, 5, 6].iter().cloned());
339        assert_eq!(items, [1, 2, 3, 4, 5, 6]);
340    }
341
342    #[test]
343    fn insert_all_rev() {
344        let mut items = vec![1, 2, 3];
345        items.insert_all_rev(1, [4, 5, 6].iter().cloned());
346        assert_eq!(items, [1, 6, 5, 4, 2, 3]);
347    }
348
349    #[test]
350    fn insert_all_rev_end() {
351        let mut items = vec![1, 2, 3];
352        items.insert_all_rev(3, [4, 5, 6].iter().cloned());
353        assert_eq!(items, [1, 2, 3, 6, 5, 4]);
354    }
355
356    #[test]
357    fn insert_slice_clone() {
358        let mut items = vec![1, 2, 3];
359        items.insert_slice_clone(1, &[4, 5, 6]);
360        assert_eq!(items, [1, 4, 5, 6, 2, 3]);
361    }
362
363    #[test]
364    fn insert_slice_copy() {
365        let mut items = vec![1, 2, 3];
366        items.insert_slice_copy(1, &[4, 5, 6]);
367        assert_eq!(items, [1, 4, 5, 6, 2, 3]);
368    }
369}
scanmut/lib.rs

scanmut/
lib.rs
