vecdeque_stableix/
lib.rs

1// Copyright 2019-2020 Ian Jackson
2// SPDX-License-Identifier: GPL-3.0-or-later
3// There is NO WARRANTY.
4
5//! deque (double-ended queue) with stable element indices
6//! ------------------------------------------------------
7//!
8//! ```
9//! # use vecdeque_stableix::Deque;
10//! let mut deque = Deque::new();
11//! let pushed_a : i64 = deque.push_back('a');
12//! let pushed_b = deque.push_back('b');
13//! assert_eq!(deque.get(pushed_a), Some(&'a'));
14//! assert_eq!(deque.pop_front(), Some('a'));
15//! assert_eq!(deque[pushed_b], 'b'); // would panic if it had been removed
16//! ```
17//!
18//! Index type
19//! ----------
20//!
21//! You can use a suitable signed integer type, eg. `i64`, as the
22//! element index.  It is important that it doesn't overflow ---
23//! see below.
24//!
25//! You may have to specify the index type explicitly:
26//! ```
27//! # use vecdeque_stableix::Deque;
28//! let mut deque : Deque<_,i64> = Deque::new();
29//! deque.push_front(42);
30//! assert_eq!(deque.front(), Some(&42));
31//! ```
32//!
33//! Index stabiliy
34//! --------------
35//! This `Deque` is implemented by adding a front counter to
36//! `std::vec_deque::VecDeque`.  The abstraction is rather thin.
37//! Methods are provided to access the individual parts.  If you
38//! use them, you may invalidate your existing indices, so that
39//! they no longer point to the same elements.
40//!
41//! If this happens, your program will still be memory-safe,
42//! but it may function incorrectly.
43//!
44//! Methods with a risk of panicking are so noted in the documentation.
45//!
46//! Panics, and index overflow
47//! --------------------------
48//! This library will panic if the index type overflows.
49//! This can occur if you push more than 2^n values
50//! through the queue, where n is the size of your integer type.
51//!
52//! If you prefer to wrap, reusing element indices rather than
53//! panicing, you can `impl Offset` for a newtype containing
54//! an unsigned type, and perform wrapping arithmetic.
55//!
56//! It would be possible to provide non-panicing library entrypoints,
57//! which return errors instead.  Patches for that welcome.
58//!
59//! Changelog
60//! ---------
61//!
62//! ### 1.1.1
63//!
64//!  * Update the README from the crate-level docs.
65//!
66//! ### 1.1.0
67//!
68//!  * Provide [`IterMut`] (from [`iter_mut`](Deque::iter_mut)).
69//!  * Provide draining [`IntoIter`] (via `impl IntoIterator`).
70//!  * Implement `Eq` and `PartialEq` for `Deque`.
71//!  * Implement `FromIterator` and `Extend` for `Deque`.
72//!
73//! ### 1.0.0
74//!
75//!  * Initial public release.
76
77use std::collections::{vec_deque, VecDeque};
78use std::convert::{TryInto,TryFrom};
79use std::iter::{ExactSizeIterator, FusedIterator, FromIterator};
80use std::ops::{Neg,Index,IndexMut};
81use std::fmt::Debug;
82use num_traits::{Zero,One,CheckedAdd,CheckedSub};
83
84/// Double-ended queue with stable indices
85#[derive(Clone,Debug,Hash,Eq,PartialEq)]
86pub struct Deque<T,I:Offset> {
87  advanced : I, // how many more pop_front than push_front
88  v : VecDeque<T>,
89}
90
91/// Types that can be used as an index for a Deque.
92///
93/// The (fallible) operations required are a very limited subset of
94/// arithmetic, combined with conversion between `Offset` and `usize`.
95///
96/// The provided generic implementation covers `isize`, `i64`, etc.
97pub trait Offset : Clone + Debug + Neg + PartialEq + Eq {
98  /// Should return `None` on overflow.
99  /// Currently, this will cause the library to panic,
100  /// but that may not always be the case.
101  fn try_increment(&mut self) -> Option<()>;
102  /// Should return `None` on overflow.
103  /// Currently, this will cause the library to panic,
104  /// but that may not always be the case.
105  fn try_decrement(&mut self) -> Option<()>;
106  fn zero() -> Self;
107
108  /// Should return `Some(input - self)`, or `None` on overflow.
109  ///
110  /// Overflows can easily happen with a very old index, if the index
111  /// type is bigger than `usize`; this is handled gracefully by the
112  /// library.
113  /// So `index_input` **must not panic** on overflow.
114  fn index_input(&self, input: Self) -> Option<usize>;
115
116  /// Should return `Some(output + self)`.
117  ///
118  /// Should return `None` on overflow;
119  /// Currently, this will cause the library to panic,
120  /// but that may not always be the case.
121  fn index_output(&self, inner: usize) -> Option<Self>;
122}
123
124impl<T> Offset for T where T
125  : Clone + Debug + Neg + PartialEq + Eq
126  + Zero
127  + One
128  + CheckedAdd
129  + CheckedSub
130  + TryInto<usize>
131  + TryFrom<usize>
132{
133  fn try_increment(&mut self) -> Option<()> {
134    *self = self.checked_add(&One::one())?;
135    Some(())
136  }
137  fn try_decrement(&mut self) -> Option<()>  {
138    *self = self.checked_sub(&One::one())?;
139    Some(())
140  }
141  fn index_input(&self, input: Self) -> Option<usize> {
142    input.checked_sub(&self)?.try_into().ok()
143  }
144  fn index_output(&self, output: usize) -> Option<Self> {
145    self.checked_add(&output.try_into().ok()?)
146  }
147  fn zero() -> Self { Zero::zero() }
148}
149
150impl<T, I:Offset> Index<I> for Deque<T,I> {
151  type Output = T;
152  fn index(&self, i : I) -> &T { self.get(i).unwrap() }
153}
154impl<T, I:Offset> IndexMut<I> for Deque<T,I> {
155  fn index_mut(&mut self, i : I) -> &mut T { self.get_mut(i).unwrap() }
156}
157
158impl<T, I:Offset> Default for Deque<T,I> {
159  fn default() -> Self { Self::new() }
160}
161
162impl<T, I:Offset> FromIterator<T> for Deque<T,I> {
163  fn from_iter<X>(iter: X) -> Self where X: IntoIterator<Item=T> {
164    Deque {
165      advanced: I::zero(),
166      v: <VecDeque<T> as FromIterator<T>>::from_iter(iter)
167    }
168  }
169}
170
171impl<T, I:Offset> Extend<T> for Deque<T,I> {
172  fn extend<X>(&mut self, iter: X) where X: IntoIterator<Item=T> {
173    self.v.extend(iter);
174  }
175}
176
177macro_rules! define_iter {
178  { $Iter:ident $get:ident $iter:ident $($mmut:ident)? } => {
179    impl<'v, T, I:Offset> Iterator for $Iter<'v,T,I> {
180      type Item = (I,&'v $($mmut)? T);
181      fn next(&mut self) -> Option<Self::Item> {
182        let t = self.vd.next()?;
183        let i = self.front.clone();
184        self.front.try_increment().unwrap();
185        Some((i,t))
186      }
187    }
188    impl<'v, T, I:Offset> DoubleEndedIterator for $Iter<'v,T,I> {
189      fn next_back(&mut self) -> Option<Self::Item> {
190        let t = self.vd.next_back()?;
191        let i = self.front.clone().index_output(self.vd.len()).unwrap();
192        Some((i,t))
193      }
194    }
195
196    impl<'v, T, I:Offset> IntoIterator for &'v $($mmut)? Deque<T,I> {
197      type Item = (I, &'v $($mmut)?T);
198      type IntoIter = $Iter<'v,T,I>;
199      fn into_iter(self) -> $Iter<'v,T,I> {
200        self.$iter()
201      }
202    }
203
204    impl<'v, T, I:Offset> ExactSizeIterator for $Iter<'v,T,I> where I: Clone {
205      fn len(&self) -> usize {
206        self.vd.len()
207      }
208    }
209    impl<'v, T, I:Offset> FusedIterator for $Iter<'v,T,I> { }
210  }
211}
212
213/// Iterator over elements of a `Deque`
214#[derive(Clone,Debug)]
215pub struct Iter<'v, T, I:Offset> {
216  front : I,
217  vd : vec_deque::Iter<'v, T>,
218}
219define_iter!{ Iter get iter }
220
221/// Iterator over elements of a `Deque`, that returns mutable references
222#[derive(Debug)]
223pub struct IterMut<'v, T, I:Offset> {
224  front : I,
225  vd : vec_deque::IterMut<'v, T>,
226}
227define_iter!{ IterMut get_mut iter_mut mut }
228
229/// Owning iterator over the elements of a `Deque`
230///
231/// Created by the [`into_iter`](Deque::into_iter) method on `Deque`,
232/// provided by the `IntoIterator` trait.
233#[derive(Clone,Debug)]
234pub struct IntoIter<T,I:Offset> {
235  dq: Deque<T,I>
236}
237
238impl<T, I:Offset> IntoIterator for Deque<T,I> {
239  type Item = (I, T);
240  type IntoIter = IntoIter<T,I>;
241  fn into_iter(self) -> IntoIter<T,I> { IntoIter { dq: self } }
242}
243
244impl<T, I:Offset> Iterator for IntoIter<T,I> {
245  type Item = (I,T);
246  fn next(&mut self) -> Option<Self::Item> {
247    Some((self.dq.front_index(), self.dq.pop_front()?))
248  }
249}
250impl<T, I:Offset> DoubleEndedIterator for IntoIter<T,I> {
251  fn next_back(&mut self) -> Option<Self::Item> {
252    let t = self.dq.pop_back()?;
253    Some((self.dq.end_index(), t))
254  }
255}
256impl<T, I:Offset> ExactSizeIterator for IntoIter<T,I> {
257  fn len(&self) -> usize {
258    self.dq.len()
259  }
260}
261impl<T, I:Offset> FusedIterator for IntoIter<T,I> { }
262
263impl<T, I:Offset> Deque<T,I> {
264  pub fn new() -> Self { Deque {
265    advanced : Offset::zero(),
266    v : VecDeque::new(),
267  } }
268  /// Like `VecDeque::with_capacity`
269  pub fn with_capacity(cap : usize) -> Self {
270    Deque {
271      advanced : Offset::zero(),
272      v : VecDeque::with_capacity(cap),
273    }
274  }
275
276  pub fn len(&self) -> usize { self.v.len() }
277  pub fn is_empty(&self) -> bool { self.v.is_empty() }
278
279  pub fn front    (&    self) -> Option<&    T> { self.v.front    () }
280  pub fn back     (&    self) -> Option<&    T> { self.v.back     () }
281  pub fn front_mut(&mut self) -> Option<&mut T> { self.v.front_mut() }
282  pub fn back_mut (&mut self) -> Option<&mut T> { self.v.back_mut () }
283
284  /// Returns the element with index `i`, if it is still in the deque.
285  pub fn get(&self, i : I) -> Option<&T> {
286    self.v.get( self.advanced.index_input(i)? )
287  }
288  pub fn get_mut(&mut self, i : I) -> Option<&mut T> {
289    self.v.get_mut( self.advanced.index_input(i)? )
290  }
291
292  /// **Panics** on index overflow.
293  pub fn push_front(&mut self, e : T) -> I {
294    let p = 0;
295    self.v.push_front(e);
296    self.advanced.try_decrement().unwrap();
297    self.advanced.index_output(p).unwrap()
298  }
299  /// **Panics** on index overflow.
300  pub fn push_back(&mut self, e : T) -> I {
301    let p = self.v.len();
302    self.v.push_back(e);
303    self.advanced.index_output(p).unwrap()
304  }
305
306  /// **Panics** on index overflow.
307  pub fn pop_front(&mut self) -> Option<T> {
308    let r = self.v.pop_front()?;
309    self.advanced.try_increment().unwrap();
310    Some(r)
311  }
312  /// **Panics** on index overflow.
313  // Actually, it can't panic, but that's not part of the API.
314  pub fn pop_back(&mut self) -> Option<T> {
315    let r = self.v.pop_back()?;
316    Some(r)
317  }
318
319  /// Removes the element with index `i`, by replacing it with the
320  /// eleement from the front.  Invalidates the index of the front
321  /// element element (now `i` refers to that) but leaves other
322  /// indices valid.  **Panics** on index overflow.
323  pub fn swap_remove_front(&mut self, i: I) -> Option<T> {
324    let r = self.v.swap_remove_front( self.advanced.index_input(i)? )?;
325    self.advanced.try_increment().unwrap();
326    Some(r)
327  }
328  /// Removes the element with index `i`, by replacing it with the
329  /// eleement from the back.  Invalidates the index of the back
330  /// element (now `i` refers to that), but leaves other indices
331  /// valid.  **Panics** on index overflow.
332  pub fn swap_remove_back(&mut self, i: I) -> Option<T> {
333    let r = self.v.swap_remove_back( self.advanced.index_input(i)? )?;
334    Some(r)
335  }
336
337  /// The index of the first item the deque.  If the queue is
338  /// empty, this is the same as `end_index`.
339  pub fn front_index(&self) -> I {
340    self.advanced.index_output(0).unwrap()
341  }
342  /// The index just after the end of the qeue.  I.e., the index that
343  /// would be assigned to a new element added with `push_back`.
344  /// **Panics** on index overflow.
345  pub fn end_index(&self) -> I {
346    self.advanced.index_output(self.len()).unwrap()
347  }
348
349  /// Returns a (front-to-back) iterator.
350  pub fn iter(&self) -> Iter<'_,T,I> {
351    Iter {
352      front : self.front_index(),
353      vd : self.v.iter(),
354    }
355  }
356  /// Returns a (front-to-back) iterator which returns mutable references.
357  pub fn iter_mut(&mut self) -> IterMut<'_,T,I> {
358    IterMut {
359      front : self.front_index(),
360      vd : self.v.iter_mut(),
361    }
362  }
363
364  /// `I` is how many more times `pop_front` has been called than
365  /// `push_back`.
366  pub fn counter(&self) -> &I { &self.advanced }
367  /// Modifying this invalidates all indices.
368  pub fn counter_mut(&mut self) -> &mut I { &mut self.advanced }
369
370  /// Allos access to the `VecDeque` inside this `Deque`
371  pub fn inner(&self) -> &VecDeque<T> { &self.v }
372  /// Mutable access to the `VecDeque` inside this `Dequeu`.
373  /// Adding/removing elements at the front of of the `VecDeque`
374  /// invalidates all indices.
375  pub fn inner_mut(&mut self) -> &mut VecDeque<T> { &mut self.v }
376  pub fn into_parts(self) -> (I, VecDeque<T>) {
377    (self.advanced, self.v)
378  }
379  pub fn from_parts(advanced: I, v: VecDeque<T>) -> Self {
380    Self { advanced, v }
381  }
382  pub fn as_parts(&self) -> (&I, &VecDeque<T>) {
383    (&self.advanced, &self.v)
384  }
385  /// Modifying the parts inconsistently will invalidate indices.
386  pub fn as_mut_parts(&mut self) -> (&mut I, &mut VecDeque<T>) {
387    (&mut self.advanced, &mut self.v)
388  }
389}
390
391#[cfg(test)]
392impl<I:Offset> Deque<char,I> {
393  fn chk(&self) -> String {
394    let s : String = self.inner().iter().collect();
395    format!("{:?} {} {}", self.front_index(), self.len(), &s)
396  }
397}
398
399#[test]
400fn with_i8() {
401  let mut siv : Deque<char,i8> = Default::default();
402
403  assert_eq!(None, siv.pop_front());
404  assert_eq!(None, siv.pop_back());
405
406  for (i, c) in ('a'..='g').enumerate() {
407    let j = siv.push_back(c);
408    assert_eq!(i, j as usize);
409  }
410  assert_eq!('d', siv[ 3]);
411  assert_eq!(-1, siv.push_front('Z'));
412  assert_eq!( 7, siv.push_back('H'));
413  assert_eq!("-1 9 ZabcdefgH", siv.chk());
414  assert_eq!('Z', siv[-1]);
415  assert_eq!('d', siv[ 3]);
416
417  assert_eq!(None, siv.swap_remove_front(-2));
418  assert_eq!(None, siv.swap_remove_back(10));
419
420  assert_eq!(Some('Z'), siv.pop_front());
421  assert_eq!(Some('H'), siv.pop_back());
422  assert_eq!("0 7 abcdefg", siv.chk());
423
424  assert_eq!(Some('c'), siv.swap_remove_front(2));
425  assert_eq!("1 6 badefg", siv.chk());
426
427  assert_eq!(Some('d'), siv.swap_remove_back(3));
428  assert_eq!("1 5 bagef", siv.chk());
429
430  *siv.get_mut(4).unwrap() = 'E';
431  assert_eq!("1 5 bagEf", siv.chk());
432
433  assert_eq!(6, siv.end_index());
434
435  let (a,v) = siv.into_parts();
436  let mut siv = Deque::from_parts(a,v);
437  assert_eq!("1 5 bagEf", siv.chk());
438
439  siv.inner_mut()[0] = 'B';
440  assert_eq!("1 5 BagEf", siv.chk());
441
442  let mut l = vec![];
443  for ent in &siv { l.push(ent); }
444  assert_eq!("[(1, 'B'), (2, 'a'), (3, 'g'), (4, 'E'), (5, 'f')]",
445             format!("{:?}", &l));
446
447  for (i, ent) in &mut siv {
448    *ent = char::from_u32((*ent as u32) + (i as u32)).unwrap();
449  }
450
451  let mut l = vec![];
452  for ent in siv.into_iter().rev() { l.push(ent); }
453  assert_eq!("[(5, 'k'), (4, 'I'), (3, 'j'), (2, 'c'), (1, 'C')]",
454             format!("{:?}", &l));
455
456  let mut siv: VecDeque<char> = ['p','q','r'].iter().cloned().collect();
457  assert_eq!(siv.len(), 3);
458  assert_eq!(siv.get(1), Some(&'q'));
459
460  siv.extend(['x','y'].iter().cloned());
461  assert_eq!(siv.get(4), Some(&'y'));
462}
463
464#[test]
465fn with_isize() {
466  // Mostly this is to check it compiles with isize and something
467  // with Drop etc.
468  let mut siv = <Deque<String,isize>>::new();
469  siv.push_back("s".to_owned());
470}
471
472#[test]
473fn with_big() {
474  #[cfg(target_pointer_width="16")]
475  let a = 123 * 1_000_000_i32;
476
477  #[cfg(target_pointer_width="32")]
478  let a = 123 * 1_000_000_000_000_000_i64;
479
480  #[cfg(target_pointer_width="64")]
481  let a = 123 * 1_000_000_000_000_000_000_000_000_000_000_i128;
482
483  // point of this test is to check that we do cope properly
484  // with `advance` values that don't fit in usize
485  assert_eq!(None, usize::try_from(a).ok());
486
487  let v : VecDeque<char> = Default::default();
488  let mut siv = Deque::from_parts(a,v);
489  siv.push_back('a');
490  siv.push_back('b');
491  assert_eq!('a', *siv.front().unwrap());
492  assert_eq!('b', *siv.back ().unwrap());
493  *siv.front_mut().unwrap() = 'A';
494  *siv.back_mut() .unwrap() = 'B';
495  assert_eq!(format!("{} 2 AB", &a), siv.chk());
496  assert_eq!(None, siv.get(0));
497}
vecdeque_stableix/lib.rs

vecdeque_stableix/
lib.rs
