Skip to main content

ferrochart_core/data/
deq_column.rs

1//! `DeqColumn<T>`: a contiguous column that grows at both ends.
2//!
3//! Series columns grow at the back (`Append`, real-time ticks) and at the front
4//! (`Prepend` when the user scrolls left and the host loads history). A `Vec`
5//! makes front insertion O(n) per call; `VecDeque` is not contiguous, so it
6//! cannot be handed out as one slice or uploaded with one copy. `DeqColumn` keeps
7//! free space on both sides of a single contiguous buffer.
8//!
9
10use core::ops::{Deref, DerefMut};
11
12use crate::error::{Error, Result};
13
14/// Smallest buffer allocated when a column first grows.
15const MIN_CAPACITY: usize = 16;
16
17/// A contiguous column with free space at both ends.
18///
19/// Elements are stored in one contiguous buffer as `[front free | data | back free]`.
20/// Adding at either end is amortized O(1), and the data is always available as a
21/// single slice (through [`Deref`] to `[T]`), so it can be copied or uploaded in
22/// one go.
23///
24/// When the end that needs room is full:
25/// - if at least half of the buffer would still be free, the data is re-centred
26///   in place (no allocation);
27/// - otherwise a new buffer of at least twice the size is allocated and the data
28///   is placed in its centre.
29///
30/// Either way both ends get room again, so mixed front and back growth stays
31/// amortized O(1). Allocation failures are returned as [`Error::OutOfMemory`];
32/// nothing panics.
33///
34/// The whole buffer is kept initialized (free slots hold `T::default()`), which is
35/// why `T: Copy + Default`. Column element types (`i64`, `f64`, `f32`, `u32`) all
36/// satisfy this.
37///
38/// # Examples
39///
40/// ```
41/// use ferrochart_core::data::DeqColumn;
42///
43/// let mut col = DeqColumn::from_vec(vec![3.0, 4.0]);
44/// col.push_back(5.0)?;            // append a bar
45/// col.extend_front(&[1.0, 2.0])?; // prepend history
46/// if let Some(last) = col.last_mut() {
47///     *last = 5.5;                // real-time update of the last bar
48/// }
49/// assert_eq!(&col[..], &[1.0, 2.0, 3.0, 4.0, 5.5]);
50/// # Ok::<(), ferrochart_core::Error>(())
51/// ```
52#[derive(Clone, Debug)]
53pub struct DeqColumn<T> {
54    /// Fully initialized buffer; its length is the column's capacity.
55    buf: Vec<T>,
56    /// Index of the first element in `buf`.
57    head: usize,
58    /// Number of elements.
59    len: usize,
60}
61
62#[derive(Clone, Copy)]
63enum Side {
64    Front,
65    Back,
66}
67
68impl<T> DeqColumn<T> {
69    /// Creates an empty column without allocating.
70    ///
71    /// # Examples
72    ///
73    /// ```
74    /// use ferrochart_core::data::DeqColumn;
75    ///
76    /// let col = DeqColumn::<f64>::new();
77    /// assert!(col.is_empty());
78    /// assert_eq!(col.capacity(), 0);
79    /// ```
80    pub const fn new() -> Self {
81        Self {
82            buf: Vec::new(),
83            head: 0,
84            len: 0,
85        }
86    }
87
88    /// Takes ownership of `v` without copying. The column has no free space at
89    /// either end until it grows.
90    ///
91    /// This is the path for `set_data`: the input column is moved in as is.
92    ///
93    /// # Examples
94    ///
95    /// ```
96    /// use ferrochart_core::data::DeqColumn;
97    ///
98    /// let col = DeqColumn::from_vec(vec![1_i64, 2, 3]);
99    /// assert_eq!(&col[..], &[1, 2, 3]);
100    /// assert_eq!(col.capacity(), 3);
101    /// ```
102    pub fn from_vec(v: Vec<T>) -> Self {
103        let len = v.len();
104        Self {
105            buf: v,
106            head: 0,
107            len,
108        }
109    }
110
111    /// Total number of slots (used and free) in the buffer.
112    ///
113    /// The heap allocation may be slightly larger: a `Vec` passed to
114    /// [`from_vec`](Self::from_vec) keeps its spare capacity until
115    /// [`shrink_to_fit`](Self::shrink_to_fit).
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use ferrochart_core::data::DeqColumn;
121    ///
122    /// let mut col = DeqColumn::<u32>::new();
123    /// col.push_back(1)?;
124    /// assert!(col.capacity() >= 1);
125    /// assert_eq!(col.capacity(), col.front_capacity() + col.len() + col.back_capacity());
126    /// # Ok::<(), ferrochart_core::Error>(())
127    /// ```
128    pub fn capacity(&self) -> usize {
129        self.buf.len()
130    }
131
132    /// Number of free slots before the first element.
133    ///
134    /// # Examples
135    ///
136    /// ```
137    /// use ferrochart_core::data::DeqColumn;
138    ///
139    /// let mut col = DeqColumn::<f32>::new();
140    /// col.reserve_front(10)?;
141    /// assert!(col.front_capacity() >= 10);
142    /// # Ok::<(), ferrochart_core::Error>(())
143    /// ```
144    pub fn front_capacity(&self) -> usize {
145        self.head
146    }
147
148    /// Number of free slots after the last element.
149    ///
150    /// # Examples
151    ///
152    /// ```
153    /// use ferrochart_core::data::DeqColumn;
154    ///
155    /// let mut col = DeqColumn::<f32>::new();
156    /// col.reserve_back(10)?;
157    /// assert!(col.back_capacity() >= 10);
158    /// # Ok::<(), ferrochart_core::Error>(())
159    /// ```
160    pub fn back_capacity(&self) -> usize {
161        self.buf.len() - self.head - self.len
162    }
163
164    /// The elements as one contiguous slice. Same as dereferencing.
165    ///
166    /// # Examples
167    ///
168    /// ```
169    /// use ferrochart_core::data::DeqColumn;
170    ///
171    /// let col = DeqColumn::from_vec(vec![1, 2]);
172    /// assert_eq!(col.as_slice(), &[1, 2]);
173    /// ```
174    pub fn as_slice(&self) -> &[T] {
175        &self.buf[self.head..self.head + self.len]
176    }
177
178    /// The elements as one contiguous mutable slice. Same as mutable dereferencing.
179    ///
180    /// # Examples
181    ///
182    /// ```
183    /// use ferrochart_core::data::DeqColumn;
184    ///
185    /// let mut col = DeqColumn::from_vec(vec![1, 2]);
186    /// col.as_mut_slice()[0] = 9;
187    /// assert_eq!(&col[..], &[9, 2]);
188    /// ```
189    pub fn as_mut_slice(&mut self) -> &mut [T] {
190        &mut self.buf[self.head..self.head + self.len]
191    }
192
193    /// Removes all elements. The buffer is kept, and the (empty) data position is
194    /// moved to its centre so both ends have room. Does not allocate.
195    ///
196    /// # Examples
197    ///
198    /// ```
199    /// use ferrochart_core::data::DeqColumn;
200    ///
201    /// let mut col = DeqColumn::from_vec(vec![1, 2, 3, 4]);
202    /// col.clear();
203    /// assert!(col.is_empty());
204    /// assert_eq!(col.capacity(), 4);
205    /// assert_eq!(col.front_capacity(), 2);
206    /// ```
207    pub fn clear(&mut self) {
208        self.head = self.buf.len() / 2;
209        self.len = 0;
210    }
211
212    /// Removes up to `front` elements at the front and then up to `back` at
213    /// the back, keeping the capacity (undoes an `extend_*`).
214    pub(crate) fn truncate_ends(&mut self, front: usize, back: usize) {
215        let front = front.min(self.len);
216        self.head += front;
217        self.len -= front;
218        self.len -= back.min(self.len);
219    }
220}
221
222impl<T: Copy + Default> DeqColumn<T> {
223    /// Appends one element at the back. Amortized O(1).
224    ///
225    /// # Errors
226    ///
227    /// [`Error::OutOfMemory`] if the buffer has to grow and the allocation fails.
228    /// The column is unchanged in that case.
229    ///
230    /// # Examples
231    ///
232    /// ```
233    /// use ferrochart_core::data::DeqColumn;
234    ///
235    /// let mut col = DeqColumn::new();
236    /// col.push_back(1.0)?;
237    /// col.push_back(2.0)?;
238    /// assert_eq!(&col[..], &[1.0, 2.0]);
239    /// # Ok::<(), ferrochart_core::Error>(())
240    /// ```
241    pub fn push_back(&mut self, value: T) -> Result<()> {
242        self.reserve_back(1)?;
243        self.buf[self.head + self.len] = value;
244        self.len += 1;
245        Ok(())
246    }
247
248    /// Inserts one element at the front. Amortized O(1).
249    ///
250    /// # Errors
251    ///
252    /// [`Error::OutOfMemory`] if the buffer has to grow and the allocation fails.
253    /// The column is unchanged in that case.
254    ///
255    /// # Examples
256    ///
257    /// ```
258    /// use ferrochart_core::data::DeqColumn;
259    ///
260    /// let mut col = DeqColumn::from_vec(vec![2.0]);
261    /// col.push_front(1.0)?;
262    /// assert_eq!(&col[..], &[1.0, 2.0]);
263    /// # Ok::<(), ferrochart_core::Error>(())
264    /// ```
265    pub fn push_front(&mut self, value: T) -> Result<()> {
266        self.reserve_front(1)?;
267        self.head -= 1;
268        self.buf[self.head] = value;
269        self.len += 1;
270        Ok(())
271    }
272
273    /// Appends all elements of `src` at the back, in order. Amortized O(`src.len()`).
274    ///
275    /// # Errors
276    ///
277    /// [`Error::OutOfMemory`] if the buffer has to grow and the allocation fails.
278    /// The column is unchanged in that case.
279    ///
280    /// # Examples
281    ///
282    /// ```
283    /// use ferrochart_core::data::DeqColumn;
284    ///
285    /// let mut col = DeqColumn::from_vec(vec![1]);
286    /// col.extend_back(&[2, 3])?;
287    /// assert_eq!(&col[..], &[1, 2, 3]);
288    /// # Ok::<(), ferrochart_core::Error>(())
289    /// ```
290    pub fn extend_back(&mut self, src: &[T]) -> Result<()> {
291        self.reserve_back(src.len())?;
292        let start = self.head + self.len;
293        self.buf[start..start + src.len()].copy_from_slice(src);
294        self.len += src.len();
295        Ok(())
296    }
297
298    /// Inserts all elements of `src` at the front, keeping their order: afterwards
299    /// the column starts with `src`. Amortized O(`src.len()`); existing elements
300    /// are not moved unless the front is full.
301    ///
302    /// # Errors
303    ///
304    /// [`Error::OutOfMemory`] if the buffer has to grow and the allocation fails.
305    /// The column is unchanged in that case.
306    ///
307    /// # Examples
308    ///
309    /// ```
310    /// use ferrochart_core::data::DeqColumn;
311    ///
312    /// let mut col = DeqColumn::from_vec(vec![3]);
313    /// col.extend_front(&[1, 2])?;
314    /// assert_eq!(&col[..], &[1, 2, 3]);
315    /// # Ok::<(), ferrochart_core::Error>(())
316    /// ```
317    pub fn extend_front(&mut self, src: &[T]) -> Result<()> {
318        self.reserve_front(src.len())?;
319        self.head -= src.len();
320        self.buf[self.head..self.head + src.len()].copy_from_slice(src);
321        self.len += src.len();
322        Ok(())
323    }
324
325    /// Appends `n` copies of `value` at the back. Amortized O(`n`).
326    ///
327    /// # Errors
328    ///
329    /// [`Error::OutOfMemory`] if the allocation fails. The column is unchanged.
330    ///
331    /// # Examples
332    ///
333    /// ```
334    /// use ferrochart_core::data::DeqColumn;
335    ///
336    /// let mut col = DeqColumn::from_vec(vec![1]);
337    /// col.grow_back(2, 0)?;
338    /// assert_eq!(&col[..], &[1, 0, 0]);
339    /// # Ok::<(), ferrochart_core::Error>(())
340    /// ```
341    pub fn grow_back(&mut self, n: usize, value: T) -> Result<()> {
342        self.reserve_back(n)?;
343        let start = self.head + self.len;
344        self.buf[start..start + n].fill(value);
345        self.len += n;
346        Ok(())
347    }
348
349    /// Inserts `n` copies of `value` at the front. Amortized O(`n`).
350    ///
351    /// # Errors
352    ///
353    /// [`Error::OutOfMemory`] if the allocation fails. The column is unchanged.
354    ///
355    /// # Examples
356    ///
357    /// ```
358    /// use ferrochart_core::data::DeqColumn;
359    ///
360    /// let mut col = DeqColumn::from_vec(vec![1]);
361    /// col.grow_front(2, 0)?;
362    /// assert_eq!(&col[..], &[0, 0, 1]);
363    /// # Ok::<(), ferrochart_core::Error>(())
364    /// ```
365    pub fn grow_front(&mut self, n: usize, value: T) -> Result<()> {
366        self.reserve_front(n)?;
367        self.head -= n;
368        self.buf[self.head..self.head + n].fill(value);
369        self.len += n;
370        Ok(())
371    }
372
373    /// Makes sure at least `additional` free slots exist after the last element.
374    ///
375    /// # Errors
376    ///
377    /// [`Error::OutOfMemory`] if the allocation fails or the size overflows.
378    /// The column is unchanged in that case.
379    ///
380    /// # Examples
381    ///
382    /// ```
383    /// use ferrochart_core::data::DeqColumn;
384    ///
385    /// let mut col = DeqColumn::<i64>::new();
386    /// col.reserve_back(100)?;
387    /// let cap = col.capacity();
388    /// for i in 0..100 {
389    ///     col.push_back(i)?;
390    /// }
391    /// assert_eq!(col.capacity(), cap); // no further growth
392    /// # Ok::<(), ferrochart_core::Error>(())
393    /// ```
394    pub fn reserve_back(&mut self, additional: usize) -> Result<()> {
395        if self.back_capacity() >= additional {
396            return Ok(());
397        }
398        self.make_room(additional, Side::Back)
399    }
400
401    /// Makes sure at least `additional` free slots exist before the first element.
402    ///
403    /// # Errors
404    ///
405    /// [`Error::OutOfMemory`] if the allocation fails or the size overflows.
406    /// The column is unchanged in that case.
407    ///
408    /// # Examples
409    ///
410    /// ```
411    /// use ferrochart_core::data::DeqColumn;
412    ///
413    /// let mut col = DeqColumn::from_vec(vec![0_i64]);
414    /// col.reserve_front(100)?;
415    /// let cap = col.capacity();
416    /// for i in 1..=100 {
417    ///     col.push_front(-i)?;
418    /// }
419    /// assert_eq!(col.capacity(), cap); // no further growth
420    /// # Ok::<(), ferrochart_core::Error>(())
421    /// ```
422    pub fn reserve_front(&mut self, additional: usize) -> Result<()> {
423        if self.front_capacity() >= additional {
424            return Ok(());
425        }
426        self.make_room(additional, Side::Front)
427    }
428
429    /// Releases all free space: afterwards `capacity() == len()` and the heap
430    /// allocation is shrunk as far as the allocator allows. Called after
431    /// `set_data` so the steady state carries no growth slack.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// use ferrochart_core::data::DeqColumn;
437    ///
438    /// let mut col = DeqColumn::new();
439    /// col.extend_back(&[1, 2, 3])?;
440    /// col.shrink_to_fit();
441    /// assert_eq!(col.capacity(), 3);
442    /// assert_eq!(&col[..], &[1, 2, 3]);
443    /// # Ok::<(), ferrochart_core::Error>(())
444    /// ```
445    pub fn shrink_to_fit(&mut self) {
446        if self.head != 0 {
447            self.buf.copy_within(self.head..self.head + self.len, 0);
448            self.head = 0;
449        }
450        self.buf.truncate(self.len);
451        self.buf.shrink_to_fit();
452    }
453
454    /// Ensures `additional` free slots on `side`, either by re-centring in place or
455    /// by moving to a larger buffer. On error nothing is modified.
456    fn make_room(&mut self, additional: usize, side: Side) -> Result<()> {
457        let needed = self.len.checked_add(additional).ok_or(Error::OutOfMemory)?;
458        let cap = self.buf.len();
459
460        // Re-centring in place costs O(len). Doing it only while at least half of
461        // the buffer stays free guarantees it yields >= len / 2 free slots on the
462        // requested side, so the cost is amortized O(1) per element.
463        let recentre = needed.checked_mul(2).is_some_and(|twice| cap >= twice);
464        if recentre {
465            let head = centred_head(cap, needed, additional, side);
466            self.buf.copy_within(self.head..self.head + self.len, head);
467            self.head = head;
468            return Ok(());
469        }
470
471        let new_cap = cap
472            .saturating_mul(2)
473            .max(needed.checked_mul(2).ok_or(Error::OutOfMemory)?)
474            .max(MIN_CAPACITY);
475        let mut buf = Vec::new();
476        buf.try_reserve_exact(new_cap)
477            .map_err(|_| Error::OutOfMemory)?;
478        // Within the reserved capacity: does not reallocate.
479        buf.resize(new_cap, T::default());
480        let head = centred_head(new_cap, needed, additional, side);
481        buf[head..head + self.len].copy_from_slice(self.as_slice());
482        self.buf = buf;
483        self.head = head;
484        Ok(())
485    }
486}
487
488/// Where the data starts after re-centring in a buffer of `cap` slots that must
489/// hold `needed = len + additional` elements, with the `additional` slots on
490/// `side`. The remaining free space is split evenly between both ends.
491fn centred_head(cap: usize, needed: usize, additional: usize, side: Side) -> usize {
492    let left = (cap - needed) / 2;
493    match side {
494        Side::Front => left + additional,
495        Side::Back => left,
496    }
497}
498
499impl<T> Default for DeqColumn<T> {
500    fn default() -> Self {
501        Self::new()
502    }
503}
504
505impl<T> Deref for DeqColumn<T> {
506    type Target = [T];
507
508    fn deref(&self) -> &[T] {
509        self.as_slice()
510    }
511}
512
513impl<T> DerefMut for DeqColumn<T> {
514    fn deref_mut(&mut self) -> &mut [T] {
515        self.as_mut_slice()
516    }
517}
518
519/// Compares the elements only; free space and capacity are ignored.
520impl<T: PartialEq> PartialEq for DeqColumn<T> {
521    fn eq(&self, other: &Self) -> bool {
522        self.as_slice() == other.as_slice()
523    }
524}
525
526impl<T: Eq> Eq for DeqColumn<T> {}
527
528#[cfg(test)]
529mod tests {
530    use super::*;
531    use proptest::prelude::*;
532    use std::collections::VecDeque;
533
534    fn check<T: Copy + PartialEq + core::fmt::Debug>(col: &DeqColumn<T>, model: &VecDeque<T>) {
535        assert!(col.head + col.len <= col.buf.len());
536        let expected: Vec<T> = model.iter().copied().collect();
537        assert_eq!(col.as_slice(), &expected[..]);
538    }
539
540    #[test]
541    fn empty_column_does_not_allocate() {
542        let col = DeqColumn::<f64>::new();
543        assert_eq!(col.buf.capacity(), 0);
544        assert_eq!(col.len(), 0);
545        assert_eq!(col.first(), None);
546    }
547
548    #[test]
549    fn from_vec_is_zero_copy() {
550        let v = vec![1.0_f64, 2.0, 3.0];
551        let ptr = v.as_ptr();
552        let col = DeqColumn::from_vec(v);
553        assert_eq!(col.as_ptr(), ptr);
554    }
555
556    #[test]
557    fn growth_centres_data() {
558        let mut col = DeqColumn::from_vec(vec![0_u32; 100]);
559        col.push_back(1).unwrap();
560        // New buffer, data in the middle: both ends got room.
561        assert!(col.capacity() >= 200);
562        assert!(col.front_capacity() >= 40);
563        assert!(col.back_capacity() >= 40);
564    }
565
566    #[test]
567    fn appends_are_amortized() {
568        // Pure back growth: the number of reallocations is logarithmic.
569        let mut col = DeqColumn::<i64>::new();
570        let mut reallocs = 0;
571        let mut last_cap = col.capacity();
572        for i in 0..1_000_000 {
573            col.push_back(i).unwrap();
574            if col.capacity() != last_cap {
575                reallocs += 1;
576                last_cap = col.capacity();
577            }
578        }
579        assert!(reallocs <= 40, "{reallocs} reallocations");
580        // Capacity stays within a constant factor of the length.
581        assert!(col.capacity() <= 4 * col.len());
582    }
583
584    #[test]
585    fn prepends_are_amortized() {
586        // Elements moved by re-centring/reallocation stay O(n) in total.
587        let mut col = DeqColumn::<i64>::new();
588        let mut moved = 0usize;
589        let mut last_head = col.head;
590        for i in 0..1_000_000 {
591            let before = col.len();
592            col.push_front(-i).unwrap();
593            if col.head + 1 != last_head {
594                moved += before;
595            }
596            last_head = col.head;
597        }
598        assert!(moved <= 4 * col.len(), "moved {moved}");
599    }
600
601    #[test]
602    fn recentres_in_place_when_mostly_free() {
603        let mut col = DeqColumn::<u32>::new();
604        col.reserve_back(1000).unwrap();
605        let cap = col.capacity();
606        col.extend_back(&[7; 10]).unwrap();
607        // Front is small after centring for a back reservation; asking for more
608        // front room than exists must re-centre, not reallocate.
609        let want = col.front_capacity() + 1;
610        col.reserve_front(want).unwrap();
611        assert_eq!(col.capacity(), cap);
612        assert!(col.front_capacity() >= want);
613        assert_eq!(&col[..], &[7; 10]);
614    }
615
616    #[test]
617    fn out_of_memory_is_an_error_and_leaves_column_unchanged() {
618        let mut col = DeqColumn::from_vec(vec![1_u64, 2, 3]);
619        for additional in [usize::MAX, usize::MAX / 2, usize::MAX / 16] {
620            assert_eq!(col.reserve_back(additional), Err(Error::OutOfMemory));
621            assert_eq!(col.reserve_front(additional), Err(Error::OutOfMemory));
622        }
623        assert_eq!(&col[..], &[1, 2, 3]);
624        assert_eq!(col.capacity(), 3);
625    }
626
627    #[test]
628    fn clear_keeps_buffer() {
629        let mut col = DeqColumn::from_vec(vec![1_u8; 64]);
630        col.clear();
631        assert!(col.is_empty());
632        assert_eq!(col.capacity(), 64);
633        col.extend_front(&[1; 32]).unwrap();
634        col.extend_back(&[2; 32]).unwrap();
635        assert_eq!(col.capacity(), 64);
636    }
637
638    #[test]
639    fn shrink_to_fit_moves_data_to_start() {
640        let mut col = DeqColumn::<i32>::new();
641        col.extend_back(&[1, 2, 3]).unwrap();
642        col.extend_front(&[-1, 0]).unwrap();
643        col.shrink_to_fit();
644        assert_eq!(col.capacity(), 5);
645        assert_eq!(col.front_capacity(), 0);
646        assert_eq!(&col[..], &[-1, 0, 1, 2, 3]);
647        assert!(col.buf.capacity() >= 5);
648    }
649
650    #[derive(Clone, Debug)]
651    enum Op {
652        PushBack(i32),
653        PushFront(i32),
654        ExtendBack(Vec<i32>),
655        ExtendFront(Vec<i32>),
656        ReserveBack(usize),
657        ReserveFront(usize),
658        SetLast(i32),
659        Clear,
660        Shrink,
661    }
662
663    fn op() -> impl Strategy<Value = Op> {
664        prop_oneof![
665            4 => any::<i32>().prop_map(Op::PushBack),
666            4 => any::<i32>().prop_map(Op::PushFront),
667            2 => prop::collection::vec(any::<i32>(), 0..50).prop_map(Op::ExtendBack),
668            2 => prop::collection::vec(any::<i32>(), 0..50).prop_map(Op::ExtendFront),
669            1 => (0usize..200).prop_map(Op::ReserveBack),
670            1 => (0usize..200).prop_map(Op::ReserveFront),
671            2 => any::<i32>().prop_map(Op::SetLast),
672            1 => Just(Op::Clear),
673            1 => Just(Op::Shrink),
674        ]
675    }
676
677    proptest! {
678        /// Model test against `VecDeque`: any sequence of operations yields the
679        /// same elements in the same order.
680        #[test]
681        fn behaves_like_vecdeque(init in prop::collection::vec(any::<i32>(), 0..20),
682                                 ops in prop::collection::vec(op(), 0..200)) {
683            let mut col = DeqColumn::from_vec(init.clone());
684            let mut model: VecDeque<i32> = init.into_iter().collect();
685            for op in ops {
686                match op {
687                    Op::PushBack(v) => { col.push_back(v).unwrap(); model.push_back(v); }
688                    Op::PushFront(v) => { col.push_front(v).unwrap(); model.push_front(v); }
689                    Op::ExtendBack(s) => { col.extend_back(&s).unwrap(); model.extend(s); }
690                    Op::ExtendFront(s) => {
691                        col.extend_front(&s).unwrap();
692                        for v in s.into_iter().rev() { model.push_front(v); }
693                    }
694                    Op::ReserveBack(n) => {
695                        col.reserve_back(n).unwrap();
696                        prop_assert!(col.back_capacity() >= n);
697                    }
698                    Op::ReserveFront(n) => {
699                        col.reserve_front(n).unwrap();
700                        prop_assert!(col.front_capacity() >= n);
701                    }
702                    Op::SetLast(v) => {
703                        if let Some(last) = col.last_mut() { *last = v; }
704                        if let Some(last) = model.back_mut() { *last = v; }
705                    }
706                    Op::Clear => { col.clear(); model.clear(); }
707                    Op::Shrink => {
708                        col.shrink_to_fit();
709                        prop_assert_eq!(col.capacity(), col.len());
710                    }
711                }
712                check(&col, &model);
713            }
714        }
715    }
716}