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}