1 // This Source Code Form is subject to the terms of the Mozilla Public
2 // License, v. 2.0. If a copy of the MPL was not distributed with this
3 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5 //! A persistent vector.
6 //!
7 //! This is a sequence of elements in insertion order - if you need a
8 //! list of things, any kind of list of things, this is what you're
9 //! looking for.
10 //!
11 //! It's implemented as an [RRB vector][rrbpaper] with [smart
12 //! head/tail chunking][chunkedseq]. In performance terms, this means
13 //! that practically every operation is O(log n), except push/pop on
14 //! both sides, which will be O(1) amortised, and O(log n) in the
15 //! worst case. In practice, the push/pop operations will be
16 //! blindingly fast, nearly on par with the native
17 //! [`VecDeque`][VecDeque], and other operations will have decent, if
18 //! not high, performance, but they all have more or less the same
19 //! O(log n) complexity, so you don't need to keep their performance
20 //! characteristics in mind - everything, even splitting and merging,
21 //! is safe to use and never too slow.
22 //!
23 //! ## Performance Notes
24 //!
25 //! Because of the head/tail chunking technique, until you push a
26 //! number of items above double the tree's branching factor (that's
27 //! `self.len()` = 2 × *k* (where *k* = 64) = 128) on either side, the
28 //! data structure is still just a handful of arrays, not yet an RRB
29 //! tree, so you'll see performance and memory characteristics fairly
30 //! close to [`Vec`][Vec] or [`VecDeque`][VecDeque].
31 //!
32 //! This means that the structure always preallocates four chunks of
33 //! size *k* (*k* being the tree's branching factor), equivalent to a
34 //! [`Vec`][Vec] with an initial capacity of 256. Beyond that, it will
35 //! allocate tree nodes of capacity *k* as needed.
36 //!
37 //! In addition, vectors start out as single chunks, and only expand into the
38 //! full data structure once you go past the chunk size. This makes them
39 //! perform identically to [`Vec`][Vec] at small sizes.
40 //!
41 //! [rrbpaper]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf
42 //! [chunkedseq]: http://deepsea.inria.fr/pasl/chunkedseq.pdf
43 //! [Vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
44 //! [VecDeque]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
45
46 use std::borrow::Borrow;
47 use std::cmp::Ordering;
48 use std::fmt::{Debug, Error, Formatter};
49 use std::hash::{Hash, Hasher};
50 use std::iter::Sum;
51 use std::iter::{FromIterator, FusedIterator};
52 use std::mem::{replace, swap};
53 use std::ops::{Add, Index, IndexMut, RangeBounds};
54
55 use sized_chunks::InlineArray;
56
57 use crate::nodes::chunk::{Chunk, CHUNK_SIZE};
58 use crate::nodes::rrb::{Node, PopResult, PushResult, SplitResult};
59 use crate::sort;
60 use crate::util::{clone_ref, swap_indices, to_range, Pool, PoolDefault, PoolRef, Ref, Side};
61
62 use self::VectorInner::{Full, Inline, Single};
63
64 mod focus;
65
66 pub use self::focus::{Focus, FocusMut};
67
68 mod pool;
69 pub use self::pool::RRBPool;
70
71 #[cfg(all(threadsafe, any(test, feature = "rayon")))]
72 pub mod rayon;
73
74 /// Construct a vector from a sequence of elements.
75 ///
76 /// # Examples
77 ///
78 /// ```
79 /// # #[macro_use] extern crate im_rc as im;
80 /// # use im::vector::Vector;
81 /// # fn main() {
82 /// assert_eq!(
83 /// vector![1, 2, 3],
84 /// Vector::from(vec![1, 2, 3])
85 /// );
86 /// # }
87 /// ```
88 #[macro_export]
89 macro_rules! vector {
90 () => { $crate::vector::Vector::new() };
91
92 ( $($x:expr),* ) => {{
93 let mut l = $crate::vector::Vector::new();
94 $(
95 l.push_back($x);
96 )*
97 l
98 }};
99
100 ( $($x:expr ,)* ) => {{
101 let mut l = $crate::vector::Vector::new();
102 $(
103 l.push_back($x);
104 )*
105 l
106 }};
107 }
108
109 /// A persistent vector.
110 ///
111 /// This is a sequence of elements in insertion order - if you need a list of
112 /// things, any kind of list of things, this is what you're looking for.
113 ///
114 /// It's implemented as an [RRB vector][rrbpaper] with [smart head/tail
115 /// chunking][chunkedseq]. In performance terms, this means that practically
116 /// every operation is O(log n), except push/pop on both sides, which will be
117 /// O(1) amortised, and O(log n) in the worst case. In practice, the push/pop
118 /// operations will be blindingly fast, nearly on par with the native
119 /// [`VecDeque`][VecDeque], and other operations will have decent, if not high,
120 /// performance, but they all have more or less the same O(log n) complexity, so
121 /// you don't need to keep their performance characteristics in mind -
122 /// everything, even splitting and merging, is safe to use and never too slow.
123 ///
124 /// ## Performance Notes
125 ///
126 /// Because of the head/tail chunking technique, until you push a number of
127 /// items above double the tree's branching factor (that's `self.len()` = 2 ×
128 /// *k* (where *k* = 64) = 128) on either side, the data structure is still just
129 /// a handful of arrays, not yet an RRB tree, so you'll see performance and
130 /// memory characteristics similar to [`Vec`][Vec] or [`VecDeque`][VecDeque].
131 ///
132 /// This means that the structure always preallocates four chunks of size *k*
133 /// (*k* being the tree's branching factor), equivalent to a [`Vec`][Vec] with
134 /// an initial capacity of 256. Beyond that, it will allocate tree nodes of
135 /// capacity *k* as needed.
136 ///
137 /// In addition, vectors start out as single chunks, and only expand into the
138 /// full data structure once you go past the chunk size. This makes them
139 /// perform identically to [`Vec`][Vec] at small sizes.
140 ///
141 /// [rrbpaper]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf
142 /// [chunkedseq]: http://deepsea.inria.fr/pasl/chunkedseq.pdf
143 /// [Vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
144 /// [VecDeque]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
145 pub struct Vector<A> {
146 vector: VectorInner<A>,
147 }
148
149 enum VectorInner<A> {
150 Inline(RRBPool<A>, InlineArray<A, RRB<A>>),
151 Single(RRBPool<A>, PoolRef<Chunk<A>>),
152 Full(RRBPool<A>, RRB<A>),
153 }
154
155 #[doc(hidden)]
156 pub struct RRB<A> {
157 length: usize,
158 middle_level: usize,
159 outer_f: PoolRef<Chunk<A>>,
160 inner_f: PoolRef<Chunk<A>>,
161 middle: Ref<Node<A>>,
162 inner_b: PoolRef<Chunk<A>>,
163 outer_b: PoolRef<Chunk<A>>,
164 }
165
166 impl<A> Clone for RRB<A> {
clone(&self) -> Self167 fn clone(&self) -> Self {
168 RRB {
169 length: self.length,
170 middle_level: self.middle_level,
171 outer_f: self.outer_f.clone(),
172 inner_f: self.inner_f.clone(),
173 middle: self.middle.clone(),
174 inner_b: self.inner_b.clone(),
175 outer_b: self.outer_b.clone(),
176 }
177 }
178 }
179
180 impl<A: Clone> Vector<A> {
181 /// Get a reference to the memory pool this `Vector` is using.
182 ///
183 /// Note that if you didn't specifically construct it with a pool, you'll
184 /// get back a reference to a pool of size 0.
185 #[cfg_attr(not(feature = "pool"), doc = "hidden")]
pool(&self) -> &RRBPool<A>186 pub fn pool(&self) -> &RRBPool<A> {
187 match self.vector {
188 Inline(ref pool, _) => pool,
189 Single(ref pool, _) => pool,
190 Full(ref pool, _) => pool,
191 }
192 }
193
194 /// True if a vector is a full inline or single chunk, ie. must be promoted
195 /// to grow further.
needs_promotion(&self) -> bool196 fn needs_promotion(&self) -> bool {
197 match &self.vector {
198 Inline(_, chunk) if chunk.is_full() => true,
199 Single(_, chunk) if chunk.is_full() => true,
200 _ => false,
201 }
202 }
203
204 /// Promote an inline to a single.
promote_inline(&mut self)205 fn promote_inline(&mut self) {
206 if let Inline(pool, chunk) = &mut self.vector {
207 self.vector = Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into()));
208 }
209 }
210
211 /// Promote a single to a full, with the single chunk becoming inner_f, or
212 /// promote an inline to a single.
promote_front(&mut self)213 fn promote_front(&mut self) {
214 self.vector = match &mut self.vector {
215 Inline(pool, chunk) => {
216 Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into()))
217 }
218 Single(pool, chunk) => {
219 let chunk = chunk.clone();
220 Full(
221 pool.clone(),
222 RRB {
223 length: chunk.len(),
224 middle_level: 0,
225 outer_f: PoolRef::default(&pool.value_pool),
226 inner_f: chunk,
227 middle: Ref::new(Node::new()),
228 inner_b: PoolRef::default(&pool.value_pool),
229 outer_b: PoolRef::default(&pool.value_pool),
230 },
231 )
232 }
233 Full(_, _) => return,
234 }
235 }
236
237 /// Promote a single to a full, with the single chunk becoming inner_b, or
238 /// promote an inline to a single.
promote_back(&mut self)239 fn promote_back(&mut self) {
240 self.vector = match &mut self.vector {
241 Inline(pool, chunk) => {
242 Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into()))
243 }
244 Single(pool, chunk) => {
245 let chunk = chunk.clone();
246 Full(
247 pool.clone(),
248 RRB {
249 length: chunk.len(),
250 middle_level: 0,
251 outer_f: PoolRef::default(&pool.value_pool),
252 inner_f: PoolRef::default(&pool.value_pool),
253 middle: Ref::new(Node::new()),
254 inner_b: chunk,
255 outer_b: PoolRef::default(&pool.value_pool),
256 },
257 )
258 }
259 Full(_, _) => return,
260 }
261 }
262
263 /// Construct an empty vector.
264 #[must_use]
new() -> Self265 pub fn new() -> Self {
266 Self {
267 vector: Inline(RRBPool::default(), InlineArray::new()),
268 }
269 }
270
271 /// Construct an empty vector using a specific memory pool.
272 #[cfg(feature = "pool")]
273 #[must_use]
with_pool(pool: &RRBPool<A>) -> Self274 pub fn with_pool(pool: &RRBPool<A>) -> Self {
275 Self {
276 vector: Inline(pool.clone(), InlineArray::new()),
277 }
278 }
279
280 /// Get the length of a vector.
281 ///
282 /// Time: O(1)
283 ///
284 /// # Examples
285 ///
286 /// ```
287 /// # #[macro_use] extern crate im_rc as im;
288 /// assert_eq!(5, vector![1, 2, 3, 4, 5].len());
289 /// ```
290 #[inline]
291 #[must_use]
len(&self) -> usize292 pub fn len(&self) -> usize {
293 match &self.vector {
294 Inline(_, chunk) => chunk.len(),
295 Single(_, chunk) => chunk.len(),
296 Full(_, tree) => tree.length,
297 }
298 }
299
300 /// Test whether a vector is empty.
301 ///
302 /// Time: O(1)
303 ///
304 /// # Examples
305 ///
306 /// ```
307 /// # #[macro_use] extern crate im_rc as im;
308 /// # use im::Vector;
309 /// let vec = vector!["Joe", "Mike", "Robert"];
310 /// assert_eq!(false, vec.is_empty());
311 /// assert_eq!(true, Vector::<i32>::new().is_empty());
312 /// ```
313 #[inline]
314 #[must_use]
is_empty(&self) -> bool315 pub fn is_empty(&self) -> bool {
316 self.len() == 0
317 }
318
319 /// Test whether a vector is currently inlined.
320 ///
321 /// Vectors small enough that their contents could be stored entirely inside
322 /// the space of `std::mem::size_of::<Vector<A>>()` bytes are stored inline on
323 /// the stack instead of allocating any chunks. This method returns `true` if
324 /// this vector is currently inlined, or `false` if it currently has chunks allocated
325 /// on the heap.
326 ///
327 /// This may be useful in conjunction with [`ptr_eq()`][ptr_eq], which checks if
328 /// two vectors' heap allocations are the same, and thus will never return `true`
329 /// for inlined vectors.
330 ///
331 /// Time: O(1)
332 ///
333 /// [ptr_eq]: #method.ptr_eq
334 #[inline]
335 #[must_use]
is_inline(&self) -> bool336 pub fn is_inline(&self) -> bool {
337 if let Inline(_, _) = &self.vector {
338 true
339 } else {
340 false
341 }
342 }
343
344 /// Test whether two vectors refer to the same content in memory.
345 ///
346 /// This uses the following rules to determine equality:
347 /// * If the two sides are references to the same vector, return true.
348 /// * If the two sides are single chunk vectors pointing to the same chunk, return true.
349 /// * If the two sides are full trees pointing to the same chunks, return true.
350 ///
351 /// This would return true if you're comparing a vector to itself, or
352 /// if you're comparing a vector to a fresh clone of itself. The exception to this is
353 /// if you've cloned an inline array (ie. an array with so few elements they can fit
354 /// inside the space a `Vector` allocates for its pointers, so there are no heap allocations
355 /// to compare).
356 ///
357 /// Time: O(1), or O(n) for inline vectors
358 #[must_use]
ptr_eq(&self, other: &Self) -> bool359 pub fn ptr_eq(&self, other: &Self) -> bool {
360 fn cmp_chunk<A>(left: &PoolRef<Chunk<A>>, right: &PoolRef<Chunk<A>>) -> bool {
361 (left.is_empty() && right.is_empty()) || PoolRef::ptr_eq(left, right)
362 }
363
364 if std::ptr::eq(self, other) {
365 return true;
366 }
367
368 match (&self.vector, &other.vector) {
369 (Single(_, left), Single(_, right)) => cmp_chunk(left, right),
370 (Full(_, left), Full(_, right)) => {
371 cmp_chunk(&left.outer_f, &right.outer_f)
372 && cmp_chunk(&left.inner_f, &right.inner_f)
373 && cmp_chunk(&left.inner_b, &right.inner_b)
374 && cmp_chunk(&left.outer_b, &right.outer_b)
375 && ((left.middle.is_empty() && right.middle.is_empty())
376 || Ref::ptr_eq(&left.middle, &right.middle))
377 }
378 _ => false,
379 }
380 }
381
382 /// Get an iterator over a vector.
383 ///
384 /// Time: O(1)
385 #[inline]
386 #[must_use]
iter(&self) -> Iter<'_, A>387 pub fn iter(&self) -> Iter<'_, A> {
388 Iter::new(self)
389 }
390
391 /// Get a mutable iterator over a vector.
392 ///
393 /// Time: O(1)
394 #[inline]
395 #[must_use]
iter_mut(&mut self) -> IterMut<'_, A>396 pub fn iter_mut(&mut self) -> IterMut<'_, A> {
397 IterMut::new(self)
398 }
399
400 /// Get an iterator over the leaf nodes of a vector.
401 ///
402 /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the
403 /// RRB tree. These are useful for efficient parallelisation of work on
404 /// the vector, but should not be used for basic iteration.
405 ///
406 /// Time: O(1)
407 ///
408 /// [Chunk]: ../chunk/struct.Chunk.html
409 #[inline]
410 #[must_use]
leaves(&self) -> Chunks<'_, A>411 pub fn leaves(&self) -> Chunks<'_, A> {
412 Chunks::new(self)
413 }
414
415 /// Get a mutable iterator over the leaf nodes of a vector.
416 //
417 /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the
418 /// RRB tree. These are useful for efficient parallelisation of work on
419 /// the vector, but should not be used for basic iteration.
420 ///
421 /// Time: O(1)
422 ///
423 /// [Chunk]: ../chunk/struct.Chunk.html
424 #[inline]
425 #[must_use]
leaves_mut(&mut self) -> ChunksMut<'_, A>426 pub fn leaves_mut(&mut self) -> ChunksMut<'_, A> {
427 ChunksMut::new(self)
428 }
429
430 /// Construct a [`Focus`][Focus] for a vector.
431 ///
432 /// Time: O(1)
433 ///
434 /// [Focus]: enum.Focus.html
435 #[inline]
436 #[must_use]
focus(&self) -> Focus<'_, A>437 pub fn focus(&self) -> Focus<'_, A> {
438 Focus::new(self)
439 }
440
441 /// Construct a [`FocusMut`][FocusMut] for a vector.
442 ///
443 /// Time: O(1)
444 ///
445 /// [FocusMut]: enum.FocusMut.html
446 #[inline]
447 #[must_use]
focus_mut(&mut self) -> FocusMut<'_, A>448 pub fn focus_mut(&mut self) -> FocusMut<'_, A> {
449 FocusMut::new(self)
450 }
451
452 /// Get a reference to the value at index `index` in a vector.
453 ///
454 /// Returns `None` if the index is out of bounds.
455 ///
456 /// Time: O(log n)
457 ///
458 /// # Examples
459 ///
460 /// ```
461 /// # #[macro_use] extern crate im_rc as im;
462 /// # use im::Vector;
463 /// let vec = vector!["Joe", "Mike", "Robert"];
464 /// assert_eq!(Some(&"Robert"), vec.get(2));
465 /// assert_eq!(None, vec.get(5));
466 /// ```
467 #[must_use]
get(&self, index: usize) -> Option<&A>468 pub fn get(&self, index: usize) -> Option<&A> {
469 if index >= self.len() {
470 return None;
471 }
472
473 match &self.vector {
474 Inline(_, chunk) => chunk.get(index),
475 Single(_, chunk) => chunk.get(index),
476 Full(_, tree) => {
477 let mut local_index = index;
478
479 if local_index < tree.outer_f.len() {
480 return Some(&tree.outer_f[local_index]);
481 }
482 local_index -= tree.outer_f.len();
483
484 if local_index < tree.inner_f.len() {
485 return Some(&tree.inner_f[local_index]);
486 }
487 local_index -= tree.inner_f.len();
488
489 if local_index < tree.middle.len() {
490 return Some(tree.middle.index(tree.middle_level, local_index));
491 }
492 local_index -= tree.middle.len();
493
494 if local_index < tree.inner_b.len() {
495 return Some(&tree.inner_b[local_index]);
496 }
497 local_index -= tree.inner_b.len();
498
499 Some(&tree.outer_b[local_index])
500 }
501 }
502 }
503
504 /// Get a mutable reference to the value at index `index` in a
505 /// vector.
506 ///
507 /// Returns `None` if the index is out of bounds.
508 ///
509 /// Time: O(log n)
510 ///
511 /// # Examples
512 ///
513 /// ```
514 /// # #[macro_use] extern crate im_rc as im;
515 /// # use im::Vector;
516 /// let mut vec = vector!["Joe", "Mike", "Robert"];
517 /// {
518 /// let robert = vec.get_mut(2).unwrap();
519 /// assert_eq!(&mut "Robert", robert);
520 /// *robert = "Bjarne";
521 /// }
522 /// assert_eq!(vector!["Joe", "Mike", "Bjarne"], vec);
523 /// ```
524 #[must_use]
get_mut(&mut self, index: usize) -> Option<&mut A>525 pub fn get_mut(&mut self, index: usize) -> Option<&mut A> {
526 if index >= self.len() {
527 return None;
528 }
529
530 match &mut self.vector {
531 Inline(_, chunk) => chunk.get_mut(index),
532 Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).get_mut(index),
533 Full(pool, tree) => {
534 let mut local_index = index;
535
536 if local_index < tree.outer_f.len() {
537 let outer_f = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f);
538 return Some(&mut outer_f[local_index]);
539 }
540 local_index -= tree.outer_f.len();
541
542 if local_index < tree.inner_f.len() {
543 let inner_f = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f);
544 return Some(&mut inner_f[local_index]);
545 }
546 local_index -= tree.inner_f.len();
547
548 if local_index < tree.middle.len() {
549 let middle = Ref::make_mut(&mut tree.middle);
550 return Some(middle.index_mut(pool, tree.middle_level, local_index));
551 }
552 local_index -= tree.middle.len();
553
554 if local_index < tree.inner_b.len() {
555 let inner_b = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b);
556 return Some(&mut inner_b[local_index]);
557 }
558 local_index -= tree.inner_b.len();
559
560 let outer_b = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b);
561 Some(&mut outer_b[local_index])
562 }
563 }
564 }
565
566 /// Get the first element of a vector.
567 ///
568 /// If the vector is empty, `None` is returned.
569 ///
570 /// Time: O(log n)
571 #[inline]
572 #[must_use]
front(&self) -> Option<&A>573 pub fn front(&self) -> Option<&A> {
574 self.get(0)
575 }
576
577 /// Get a mutable reference to the first element of a vector.
578 ///
579 /// If the vector is empty, `None` is returned.
580 ///
581 /// Time: O(log n)
582 #[inline]
583 #[must_use]
front_mut(&mut self) -> Option<&mut A>584 pub fn front_mut(&mut self) -> Option<&mut A> {
585 self.get_mut(0)
586 }
587
588 /// Get the first element of a vector.
589 ///
590 /// If the vector is empty, `None` is returned.
591 ///
592 /// This is an alias for the [`front`][front] method.
593 ///
594 /// Time: O(log n)
595 ///
596 /// [front]: #method.front
597 #[inline]
598 #[must_use]
head(&self) -> Option<&A>599 pub fn head(&self) -> Option<&A> {
600 self.get(0)
601 }
602
603 /// Get the last element of a vector.
604 ///
605 /// If the vector is empty, `None` is returned.
606 ///
607 /// Time: O(log n)
608 #[must_use]
back(&self) -> Option<&A>609 pub fn back(&self) -> Option<&A> {
610 if self.is_empty() {
611 None
612 } else {
613 self.get(self.len() - 1)
614 }
615 }
616
617 /// Get a mutable reference to the last element of a vector.
618 ///
619 /// If the vector is empty, `None` is returned.
620 ///
621 /// Time: O(log n)
622 #[must_use]
back_mut(&mut self) -> Option<&mut A>623 pub fn back_mut(&mut self) -> Option<&mut A> {
624 if self.is_empty() {
625 None
626 } else {
627 let len = self.len();
628 self.get_mut(len - 1)
629 }
630 }
631
632 /// Get the last element of a vector.
633 ///
634 /// If the vector is empty, `None` is returned.
635 ///
636 /// This is an alias for the [`back`][back] method.
637 ///
638 /// Time: O(log n)
639 ///
640 /// [back]: #method.back
641 #[inline]
642 #[must_use]
last(&self) -> Option<&A>643 pub fn last(&self) -> Option<&A> {
644 self.back()
645 }
646
647 /// Get the index of a given element in the vector.
648 ///
649 /// Searches the vector for the first occurrence of a given value,
650 /// and returns the index of the value if it's there. Otherwise,
651 /// it returns `None`.
652 ///
653 /// Time: O(n)
654 ///
655 /// # Examples
656 ///
657 /// ```
658 /// # #[macro_use] extern crate im_rc as im;
659 /// # use im::Vector;
660 /// let mut vec = vector![1, 2, 3, 4, 5];
661 /// assert_eq!(Some(2), vec.index_of(&3));
662 /// assert_eq!(None, vec.index_of(&31337));
663 /// ```
664 #[must_use]
index_of(&self, value: &A) -> Option<usize> where A: PartialEq,665 pub fn index_of(&self, value: &A) -> Option<usize>
666 where
667 A: PartialEq,
668 {
669 for (index, item) in self.iter().enumerate() {
670 if value == item {
671 return Some(index);
672 }
673 }
674 None
675 }
676
677 /// Test if a given element is in the vector.
678 ///
679 /// Searches the vector for the first occurrence of a given value,
680 /// and returns `true if it's there. If it's nowhere to be found
681 /// in the vector, it returns `false`.
682 ///
683 /// Time: O(n)
684 ///
685 /// # Examples
686 ///
687 /// ```
688 /// # #[macro_use] extern crate im_rc as im;
689 /// # use im::Vector;
690 /// let mut vec = vector![1, 2, 3, 4, 5];
691 /// assert_eq!(true, vec.contains(&3));
692 /// assert_eq!(false, vec.contains(&31337));
693 /// ```
694 #[inline]
695 #[must_use]
contains(&self, value: &A) -> bool where A: PartialEq,696 pub fn contains(&self, value: &A) -> bool
697 where
698 A: PartialEq,
699 {
700 self.index_of(value).is_some()
701 }
702
703 /// Discard all elements from the vector.
704 ///
705 /// This leaves you with an empty vector, and all elements that
706 /// were previously inside it are dropped.
707 ///
708 /// Time: O(n)
clear(&mut self)709 pub fn clear(&mut self) {
710 if !self.is_empty() {
711 self.vector = Inline(self.pool().clone(), InlineArray::new());
712 }
713 }
714
715 /// Binary search a sorted vector for a given element using a comparator
716 /// function.
717 ///
718 /// Assumes the vector has already been sorted using the same comparator
719 /// function, eg. by using [`sort_by`][sort_by].
720 ///
721 /// If the value is found, it returns `Ok(index)` where `index` is the index
722 /// of the element. If the value isn't found, it returns `Err(index)` where
723 /// `index` is the index at which the element would need to be inserted to
724 /// maintain sorted order.
725 ///
726 /// Time: O(log n)
727 ///
728 /// [sort_by]: #method.sort_by
binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> where F: FnMut(&A) -> Ordering,729 pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize>
730 where
731 F: FnMut(&A) -> Ordering,
732 {
733 let mut size = self.len();
734 if size == 0 {
735 return Err(0);
736 }
737 let mut base = 0;
738 while size > 1 {
739 let half = size / 2;
740 let mid = base + half;
741 base = match f(&self[mid]) {
742 Ordering::Greater => base,
743 _ => mid,
744 };
745 size -= half;
746 }
747 match f(&self[base]) {
748 Ordering::Equal => Ok(base),
749 Ordering::Greater => Err(base),
750 Ordering::Less => Err(base + 1),
751 }
752 }
753
754 /// Binary search a sorted vector for a given element.
755 ///
756 /// If the value is found, it returns `Ok(index)` where `index` is the index
757 /// of the element. If the value isn't found, it returns `Err(index)` where
758 /// `index` is the index at which the element would need to be inserted to
759 /// maintain sorted order.
760 ///
761 /// Time: O(log n)
binary_search(&self, value: &A) -> Result<usize, usize> where A: Ord,762 pub fn binary_search(&self, value: &A) -> Result<usize, usize>
763 where
764 A: Ord,
765 {
766 self.binary_search_by(|e| e.cmp(value))
767 }
768
769 /// Binary search a sorted vector for a given element with a key extract
770 /// function.
771 ///
772 /// Assumes the vector has already been sorted using the same key extract
773 /// function, eg. by using [`sort_by_key`][sort_by_key].
774 ///
775 /// If the value is found, it returns `Ok(index)` where `index` is the index
776 /// of the element. If the value isn't found, it returns `Err(index)` where
777 /// `index` is the index at which the element would need to be inserted to
778 /// maintain sorted order.
779 ///
780 /// Time: O(log n)
781 ///
782 /// [sort_by_key]: #method.sort_by_key
binary_search_by_key<B, F>(&self, b: &B, mut f: F) -> Result<usize, usize> where F: FnMut(&A) -> B, B: Ord,783 pub fn binary_search_by_key<B, F>(&self, b: &B, mut f: F) -> Result<usize, usize>
784 where
785 F: FnMut(&A) -> B,
786 B: Ord,
787 {
788 self.binary_search_by(|k| f(k).cmp(b))
789 }
790 }
791
792 impl<A: Clone> Vector<A> {
793 /// Construct a vector with a single value.
794 ///
795 /// # Examples
796 ///
797 /// ```
798 /// # #[macro_use] extern crate im_rc as im;
799 /// # use im::vector::Vector;
800 /// let vec = Vector::unit(1337);
801 /// assert_eq!(1, vec.len());
802 /// assert_eq!(
803 /// vec.get(0),
804 /// Some(&1337)
805 /// );
806 /// ```
807 #[inline]
808 #[must_use]
unit(a: A) -> Self809 pub fn unit(a: A) -> Self {
810 let pool = RRBPool::default();
811 if InlineArray::<A, RRB<A>>::CAPACITY > 0 {
812 let mut array = InlineArray::new();
813 array.push(a);
814 Self {
815 vector: Inline(pool, array),
816 }
817 } else {
818 let chunk = PoolRef::new(&pool.value_pool, Chunk::unit(a));
819 Self {
820 vector: Single(pool, chunk),
821 }
822 }
823 }
824
825 /// Create a new vector with the value at index `index` updated.
826 ///
827 /// Panics if the index is out of bounds.
828 ///
829 /// Time: O(log n)
830 ///
831 /// # Examples
832 ///
833 /// ```
834 /// # #[macro_use] extern crate im_rc as im;
835 /// # use im::Vector;
836 /// let mut vec = vector![1, 2, 3];
837 /// assert_eq!(vector![1, 5, 3], vec.update(1, 5));
838 /// ```
839 #[must_use]
update(&self, index: usize, value: A) -> Self840 pub fn update(&self, index: usize, value: A) -> Self {
841 let mut out = self.clone();
842 out[index] = value;
843 out
844 }
845
846 /// Update the value at index `index` in a vector.
847 ///
848 /// Returns the previous value at the index.
849 ///
850 /// Panics if the index is out of bounds.
851 ///
852 /// Time: O(log n)
853 #[inline]
set(&mut self, index: usize, value: A) -> A854 pub fn set(&mut self, index: usize, value: A) -> A {
855 replace(&mut self[index], value)
856 }
857
858 /// Swap the elements at indices `i` and `j`.
859 ///
860 /// Time: O(log n)
swap(&mut self, i: usize, j: usize)861 pub fn swap(&mut self, i: usize, j: usize) {
862 swap_indices(self, i, j)
863 }
864
865 /// Push a value to the front of a vector.
866 ///
867 /// Time: O(1)*
868 ///
869 /// # Examples
870 ///
871 /// ```
872 /// # #[macro_use] extern crate im_rc as im;
873 /// # use im::Vector;
874 /// let mut vec = vector![5, 6, 7];
875 /// vec.push_front(4);
876 /// assert_eq!(vector![4, 5, 6, 7], vec);
877 /// ```
push_front(&mut self, value: A)878 pub fn push_front(&mut self, value: A) {
879 if self.needs_promotion() {
880 self.promote_back();
881 }
882 match &mut self.vector {
883 Inline(_, chunk) => {
884 chunk.insert(0, value);
885 }
886 Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).push_front(value),
887 Full(pool, tree) => tree.push_front(pool, value),
888 }
889 }
890
891 /// Push a value to the back of a vector.
892 ///
893 /// Time: O(1)*
894 ///
895 /// # Examples
896 ///
897 /// ```
898 /// # #[macro_use] extern crate im_rc as im;
899 /// # use im::Vector;
900 /// let mut vec = vector![1, 2, 3];
901 /// vec.push_back(4);
902 /// assert_eq!(vector![1, 2, 3, 4], vec);
903 /// ```
push_back(&mut self, value: A)904 pub fn push_back(&mut self, value: A) {
905 if self.needs_promotion() {
906 self.promote_front();
907 }
908 match &mut self.vector {
909 Inline(_, chunk) => {
910 chunk.push(value);
911 }
912 Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).push_back(value),
913 Full(pool, tree) => tree.push_back(pool, value),
914 }
915 }
916
917 /// Remove the first element from a vector and return it.
918 ///
919 /// Time: O(1)*
920 ///
921 /// # Examples
922 ///
923 /// ```
924 /// # #[macro_use] extern crate im_rc as im;
925 /// # use im::Vector;
926 /// let mut vec = vector![1, 2, 3];
927 /// assert_eq!(Some(1), vec.pop_front());
928 /// assert_eq!(vector![2, 3], vec);
929 /// ```
pop_front(&mut self) -> Option<A>930 pub fn pop_front(&mut self) -> Option<A> {
931 if self.is_empty() {
932 None
933 } else {
934 match &mut self.vector {
935 Inline(_, chunk) => chunk.remove(0),
936 Single(pool, chunk) => Some(PoolRef::make_mut(&pool.value_pool, chunk).pop_front()),
937 Full(pool, tree) => tree.pop_front(pool),
938 }
939 }
940 }
941
942 /// Remove the last element from a vector and return it.
943 ///
944 /// Time: O(1)*
945 ///
946 /// # Examples
947 ///
948 /// ```
949 /// # #[macro_use] extern crate im_rc as im;
950 /// # use im::Vector;
951 /// let mut vec = vector![1, 2, 3];
952 /// assert_eq!(Some(3), vec.pop_back());
953 /// assert_eq!(vector![1, 2], vec);
954 /// ```
pop_back(&mut self) -> Option<A>955 pub fn pop_back(&mut self) -> Option<A> {
956 if self.is_empty() {
957 None
958 } else {
959 match &mut self.vector {
960 Inline(_, chunk) => chunk.pop(),
961 Single(pool, chunk) => Some(PoolRef::make_mut(&pool.value_pool, chunk).pop_back()),
962 Full(pool, tree) => tree.pop_back(pool),
963 }
964 }
965 }
966
967 /// Append the vector `other` to the end of the current vector.
968 ///
969 /// Time: O(log n)
970 ///
971 /// # Examples
972 ///
973 /// ```
974 /// # #[macro_use] extern crate im_rc as im;
975 /// # use im::vector::Vector;
976 /// let mut vec = vector![1, 2, 3];
977 /// vec.append(vector![7, 8, 9]);
978 /// assert_eq!(vector![1, 2, 3, 7, 8, 9], vec);
979 /// ```
append(&mut self, mut other: Self)980 pub fn append(&mut self, mut other: Self) {
981 if other.is_empty() {
982 return;
983 }
984
985 if self.is_empty() {
986 replace(self, other);
987 return;
988 }
989
990 self.promote_inline();
991 other.promote_inline();
992
993 let total_length = self
994 .len()
995 .checked_add(other.len())
996 .expect("Vector length overflow");
997
998 match &mut self.vector {
999 Inline(_, _) => unreachable!("inline vecs should have been promoted"),
1000 Single(pool, left) => {
1001 match &mut other.vector {
1002 Inline(_, _) => unreachable!("inline vecs should have been promoted"),
1003 // If both are single chunks and left has room for right: directly
1004 // memcpy right into left
1005 Single(_, ref mut right) if total_length <= CHUNK_SIZE => {
1006 PoolRef::make_mut(&pool.value_pool, left)
1007 .append(PoolRef::make_mut(&pool.value_pool, right));
1008 return;
1009 }
1010 // If only left is a single chunk and has room for right: push
1011 // right's elements into left
1012 _ if total_length <= CHUNK_SIZE => {
1013 while let Some(value) = other.pop_front() {
1014 PoolRef::make_mut(&pool.value_pool, left).push_back(value);
1015 }
1016 return;
1017 }
1018 _ => {}
1019 }
1020 }
1021 Full(pool, left) => {
1022 if let Full(_, mut right) = other.vector {
1023 // If left and right are trees with empty middles, left has no back
1024 // buffers, and right has no front buffers: copy right's back
1025 // buffers over to left
1026 if left.middle.is_empty()
1027 && right.middle.is_empty()
1028 && left.outer_b.is_empty()
1029 && left.inner_b.is_empty()
1030 && right.outer_f.is_empty()
1031 && right.inner_f.is_empty()
1032 {
1033 left.inner_b = right.inner_b;
1034 left.outer_b = right.outer_b;
1035 left.length = total_length;
1036 return;
1037 }
1038 // If left and right are trees with empty middles and left's buffers
1039 // can fit right's buffers: push right's elements onto left
1040 if left.middle.is_empty()
1041 && right.middle.is_empty()
1042 && total_length <= CHUNK_SIZE * 4
1043 {
1044 while let Some(value) = right.pop_front(pool) {
1045 left.push_back(pool, value);
1046 }
1047 return;
1048 }
1049 // Both are full and big: do the full RRB join
1050 let inner_b1 = left.inner_b.clone();
1051 left.push_middle(pool, Side::Right, inner_b1);
1052 let outer_b1 = left.outer_b.clone();
1053 left.push_middle(pool, Side::Right, outer_b1);
1054 let inner_f2 = right.inner_f.clone();
1055 right.push_middle(pool, Side::Left, inner_f2);
1056 let outer_f2 = right.outer_f.clone();
1057 right.push_middle(pool, Side::Left, outer_f2);
1058
1059 let mut middle1 = clone_ref(replace(&mut left.middle, Ref::from(Node::new())));
1060 let mut middle2 = clone_ref(right.middle);
1061 let normalised_middle = match left.middle_level.cmp(&right.middle_level) {
1062 Ordering::Greater => {
1063 middle2 = middle2.elevate(pool, left.middle_level - right.middle_level);
1064 left.middle_level
1065 }
1066 Ordering::Less => {
1067 middle1 = middle1.elevate(pool, right.middle_level - left.middle_level);
1068 right.middle_level
1069 }
1070 Ordering::Equal => left.middle_level,
1071 };
1072 left.middle = Ref::new(Node::merge(pool, middle1, middle2, normalised_middle));
1073 left.middle_level = normalised_middle + 1;
1074
1075 left.inner_b = right.inner_b;
1076 left.outer_b = right.outer_b;
1077 left.length = total_length;
1078 left.prune();
1079 return;
1080 }
1081 }
1082 }
1083 // No optimisations available, and either left, right or both are
1084 // single: promote both to full and retry
1085 self.promote_front();
1086 other.promote_back();
1087 self.append(other)
1088 }
1089
1090 /// Retain only the elements specified by the predicate.
1091 ///
1092 /// Remove all elements for which the provided function `f`
1093 /// returns false from the vector.
1094 ///
1095 /// Time: O(n)
retain<F>(&mut self, mut f: F) where F: FnMut(&A) -> bool,1096 pub fn retain<F>(&mut self, mut f: F)
1097 where
1098 F: FnMut(&A) -> bool,
1099 {
1100 let len = self.len();
1101 let mut del = 0;
1102 {
1103 let mut focus = self.focus_mut();
1104 for i in 0..len {
1105 if !f(focus.index(i)) {
1106 del += 1;
1107 } else if del > 0 {
1108 focus.swap(i - del, i);
1109 }
1110 }
1111 }
1112 if del > 0 {
1113 self.split_off(len - del);
1114 }
1115 }
1116
1117 /// Split a vector at a given index.
1118 ///
1119 /// Split a vector at a given index, consuming the vector and
1120 /// returning a pair of the left hand side and the right hand side
1121 /// of the split.
1122 ///
1123 /// Time: O(log n)
1124 ///
1125 /// # Examples
1126 ///
1127 /// ```
1128 /// # #[macro_use] extern crate im_rc as im;
1129 /// # use im::vector::Vector;
1130 /// let mut vec = vector![1, 2, 3, 7, 8, 9];
1131 /// let (left, right) = vec.split_at(3);
1132 /// assert_eq!(vector![1, 2, 3], left);
1133 /// assert_eq!(vector![7, 8, 9], right);
1134 /// ```
split_at(mut self, index: usize) -> (Self, Self)1135 pub fn split_at(mut self, index: usize) -> (Self, Self) {
1136 let right = self.split_off(index);
1137 (self, right)
1138 }
1139
1140 /// Split a vector at a given index.
1141 ///
1142 /// Split a vector at a given index, leaving the left hand side in
1143 /// the current vector and returning a new vector containing the
1144 /// right hand side.
1145 ///
1146 /// Time: O(log n)
1147 ///
1148 /// # Examples
1149 ///
1150 /// ```
1151 /// # #[macro_use] extern crate im_rc as im;
1152 /// # use im::vector::Vector;
1153 /// let mut left = vector![1, 2, 3, 7, 8, 9];
1154 /// let right = left.split_off(3);
1155 /// assert_eq!(vector![1, 2, 3], left);
1156 /// assert_eq!(vector![7, 8, 9], right);
1157 /// ```
split_off(&mut self, index: usize) -> Self1158 pub fn split_off(&mut self, index: usize) -> Self {
1159 assert!(index <= self.len());
1160
1161 match &mut self.vector {
1162 Inline(pool, chunk) => Self {
1163 vector: Inline(pool.clone(), chunk.split_off(index)),
1164 },
1165 Single(pool, chunk) => Self {
1166 vector: Single(
1167 pool.clone(),
1168 PoolRef::new(
1169 &pool.value_pool,
1170 PoolRef::make_mut(&pool.value_pool, chunk).split_off(index),
1171 ),
1172 ),
1173 },
1174 Full(pool, tree) => {
1175 let mut local_index = index;
1176
1177 if local_index < tree.outer_f.len() {
1178 let of2 = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f)
1179 .split_off(local_index);
1180 let right = RRB {
1181 length: tree.length - index,
1182 middle_level: tree.middle_level,
1183 outer_f: PoolRef::new(&pool.value_pool, of2),
1184 inner_f: replace_pool_def(&pool.value_pool, &mut tree.inner_f),
1185 middle: std::mem::take(&mut tree.middle),
1186 inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b),
1187 outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b),
1188 };
1189 tree.length = index;
1190 tree.middle_level = 0;
1191 return Self {
1192 vector: Full(pool.clone(), right),
1193 };
1194 }
1195
1196 local_index -= tree.outer_f.len();
1197
1198 if local_index < tree.inner_f.len() {
1199 let if2 = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f)
1200 .split_off(local_index);
1201 let right = RRB {
1202 length: tree.length - index,
1203 middle_level: tree.middle_level,
1204 outer_f: PoolRef::new(&pool.value_pool, if2),
1205 inner_f: PoolRef::<Chunk<A>>::default(&pool.value_pool),
1206 middle: std::mem::take(&mut tree.middle),
1207 inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b),
1208 outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b),
1209 };
1210 tree.length = index;
1211 tree.middle_level = 0;
1212 swap(&mut tree.outer_b, &mut tree.inner_f);
1213 return Self {
1214 vector: Full(pool.clone(), right),
1215 };
1216 }
1217
1218 local_index -= tree.inner_f.len();
1219
1220 if local_index < tree.middle.len() {
1221 let mut right_middle = tree.middle.clone();
1222 let (c1, c2) = {
1223 let m1 = Ref::make_mut(&mut tree.middle);
1224 let m2 = Ref::make_mut(&mut right_middle);
1225 match m1.split(pool, tree.middle_level, Side::Right, local_index) {
1226 SplitResult::Dropped(_) => (),
1227 SplitResult::OutOfBounds => unreachable!(),
1228 };
1229 match m2.split(pool, tree.middle_level, Side::Left, local_index) {
1230 SplitResult::Dropped(_) => (),
1231 SplitResult::OutOfBounds => unreachable!(),
1232 };
1233 let c1 = match m1.pop_chunk(pool, tree.middle_level, Side::Right) {
1234 PopResult::Empty => PoolRef::default(&pool.value_pool),
1235 PopResult::Done(chunk) => chunk,
1236 PopResult::Drained(chunk) => {
1237 m1.clear_node();
1238 chunk
1239 }
1240 };
1241 let c2 = match m2.pop_chunk(pool, tree.middle_level, Side::Left) {
1242 PopResult::Empty => PoolRef::default(&pool.value_pool),
1243 PopResult::Done(chunk) => chunk,
1244 PopResult::Drained(chunk) => {
1245 m2.clear_node();
1246 chunk
1247 }
1248 };
1249 (c1, c2)
1250 };
1251 let mut right = RRB {
1252 length: tree.length - index,
1253 middle_level: tree.middle_level,
1254 outer_f: c2,
1255 inner_f: PoolRef::<Chunk<A>>::default(&pool.value_pool),
1256 middle: right_middle,
1257 inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b),
1258 outer_b: replace(&mut tree.outer_b, c1),
1259 };
1260 tree.length = index;
1261 tree.prune();
1262 right.prune();
1263 return Self {
1264 vector: Full(pool.clone(), right),
1265 };
1266 }
1267
1268 local_index -= tree.middle.len();
1269
1270 if local_index < tree.inner_b.len() {
1271 let ib2 = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b)
1272 .split_off(local_index);
1273 let right = RRB {
1274 length: tree.length - index,
1275 outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b),
1276 outer_f: PoolRef::new(&pool.value_pool, ib2),
1277 ..RRB::new(pool)
1278 };
1279 tree.length = index;
1280 swap(&mut tree.outer_b, &mut tree.inner_b);
1281 return Self {
1282 vector: Full(pool.clone(), right),
1283 };
1284 }
1285
1286 local_index -= tree.inner_b.len();
1287
1288 let ob2 =
1289 PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b).split_off(local_index);
1290 tree.length = index;
1291 Self {
1292 vector: Single(pool.clone(), PoolRef::new(&pool.value_pool, ob2)),
1293 }
1294 }
1295 }
1296 }
1297
1298 /// Construct a vector with `count` elements removed from the
1299 /// start of the current vector.
1300 ///
1301 /// Time: O(log n)
1302 #[must_use]
skip(&self, count: usize) -> Self1303 pub fn skip(&self, count: usize) -> Self {
1304 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1305 self.clone().split_off(count)
1306 }
1307
1308 /// Construct a vector of the first `count` elements from the
1309 /// current vector.
1310 ///
1311 /// Time: O(log n)
1312 #[must_use]
take(&self, count: usize) -> Self1313 pub fn take(&self, count: usize) -> Self {
1314 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1315 let mut left = self.clone();
1316 left.split_off(count);
1317 left
1318 }
1319
1320 /// Truncate a vector to the given size.
1321 ///
1322 /// Discards all elements in the vector beyond the given length.
1323 ///
1324 /// Panics if the new length is greater than the current length.
1325 ///
1326 /// Time: O(log n)
truncate(&mut self, len: usize)1327 pub fn truncate(&mut self, len: usize) {
1328 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1329 self.split_off(len);
1330 }
1331
1332 /// Extract a slice from a vector.
1333 ///
1334 /// Remove the elements from `start_index` until `end_index` in
1335 /// the current vector and return the removed slice as a new
1336 /// vector.
1337 ///
1338 /// Time: O(log n)
slice<R>(&mut self, range: R) -> Self where R: RangeBounds<usize>,1339 pub fn slice<R>(&mut self, range: R) -> Self
1340 where
1341 R: RangeBounds<usize>,
1342 {
1343 let r = to_range(&range, self.len());
1344 if r.start >= r.end || r.start >= self.len() {
1345 return Vector::new();
1346 }
1347 let mut middle = self.split_off(r.start);
1348 let right = middle.split_off(r.end - r.start);
1349 self.append(right);
1350 middle
1351 }
1352
1353 /// Insert an element into a vector.
1354 ///
1355 /// Insert an element at position `index`, shifting all elements
1356 /// after it to the right.
1357 ///
1358 /// ## Performance Note
1359 ///
1360 /// While `push_front` and `push_back` are heavily optimised
1361 /// operations, `insert` in the middle of a vector requires a
1362 /// split, a push, and an append. Thus, if you want to insert
1363 /// many elements at the same location, instead of `insert`ing
1364 /// them one by one, you should rather create a new vector
1365 /// containing the elements to insert, split the vector at the
1366 /// insertion point, and append the left hand, the new vector and
1367 /// the right hand in order.
1368 ///
1369 /// Time: O(log n)
insert(&mut self, index: usize, value: A)1370 pub fn insert(&mut self, index: usize, value: A) {
1371 if index == 0 {
1372 return self.push_front(value);
1373 }
1374 if index == self.len() {
1375 return self.push_back(value);
1376 }
1377 assert!(index < self.len());
1378 if if let Inline(_, chunk) = &self.vector {
1379 chunk.is_full()
1380 } else {
1381 false
1382 } {
1383 self.promote_inline();
1384 }
1385 match &mut self.vector {
1386 Inline(_, chunk) => {
1387 chunk.insert(index, value);
1388 }
1389 Single(pool, chunk) if chunk.len() < CHUNK_SIZE => {
1390 PoolRef::make_mut(&pool.value_pool, chunk).insert(index, value)
1391 }
1392 // TODO a lot of optimisations still possible here
1393 _ => {
1394 let right = self.split_off(index);
1395 self.push_back(value);
1396 self.append(right);
1397 }
1398 }
1399 }
1400
1401 /// Remove an element from a vector.
1402 ///
1403 /// Remove the element from position 'index', shifting all
1404 /// elements after it to the left, and return the removec element.
1405 ///
1406 /// ## Performance Note
1407 ///
1408 /// While `pop_front` and `pop_back` are heavily optimised
1409 /// operations, `remove` in the middle of a vector requires a
1410 /// split, a pop, and an append. Thus, if you want to remove many
1411 /// elements from the same location, instead of `remove`ing them
1412 /// one by one, it is much better to use [`slice`][slice].
1413 ///
1414 /// Time: O(log n)
1415 ///
1416 /// [slice]: #method.slice
remove(&mut self, index: usize) -> A1417 pub fn remove(&mut self, index: usize) -> A {
1418 assert!(index < self.len());
1419 match &mut self.vector {
1420 Inline(_, chunk) => chunk.remove(index).unwrap(),
1421 Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).remove(index),
1422 _ => {
1423 if index == 0 {
1424 return self.pop_front().unwrap();
1425 }
1426 if index == self.len() - 1 {
1427 return self.pop_back().unwrap();
1428 }
1429 // TODO a lot of optimisations still possible here
1430 let mut right = self.split_off(index);
1431 let value = right.pop_front().unwrap();
1432 self.append(right);
1433 value
1434 }
1435 }
1436 }
1437
1438 /// Insert an element into a sorted vector.
1439 ///
1440 /// Insert an element into a vector in sorted order, assuming the vector is
1441 /// already in sorted order.
1442 ///
1443 /// Time: O(log n)
1444 ///
1445 /// # Examples
1446 ///
1447 /// ```
1448 /// # #[macro_use] extern crate im_rc as im;
1449 /// # use im::vector::Vector;
1450 /// let mut vec = vector![1, 2, 3, 7, 8, 9];
1451 /// vec.insert_ord(5);
1452 /// assert_eq!(vector![1, 2, 3, 5, 7, 8, 9], vec);
1453 /// ```
insert_ord(&mut self, item: A) where A: Ord,1454 pub fn insert_ord(&mut self, item: A)
1455 where
1456 A: Ord,
1457 {
1458 match self.binary_search(&item) {
1459 Ok(index) => self.insert(index, item),
1460 Err(index) => self.insert(index, item),
1461 }
1462 }
1463
1464 /// Sort a vector.
1465 ///
1466 /// Time: O(n log n)
1467 ///
1468 /// # Examples
1469 ///
1470 /// ```
1471 /// # #[macro_use] extern crate im_rc as im;
1472 /// # use im::vector::Vector;
1473 /// let mut vec = vector![3, 2, 5, 4, 1];
1474 /// vec.sort();
1475 /// assert_eq!(vector![1, 2, 3, 4, 5], vec);
1476 /// ```
sort(&mut self) where A: Ord,1477 pub fn sort(&mut self)
1478 where
1479 A: Ord,
1480 {
1481 self.sort_by(Ord::cmp)
1482 }
1483
1484 /// Sort a vector using a comparator function.
1485 ///
1486 /// Time: O(n log n)
1487 ///
1488 /// # Examples
1489 ///
1490 /// ```
1491 /// # #[macro_use] extern crate im_rc as im;
1492 /// # use im::vector::Vector;
1493 /// let mut vec = vector![3, 2, 5, 4, 1];
1494 /// vec.sort_by(|left, right| left.cmp(right));
1495 /// assert_eq!(vector![1, 2, 3, 4, 5], vec);
1496 /// ```
sort_by<F>(&mut self, cmp: F) where F: Fn(&A, &A) -> Ordering,1497 pub fn sort_by<F>(&mut self, cmp: F)
1498 where
1499 F: Fn(&A, &A) -> Ordering,
1500 {
1501 let len = self.len();
1502 if len > 1 {
1503 sort::quicksort(self.focus_mut(), &cmp);
1504 }
1505 }
1506
1507 /// Verify the internal consistency of a vector.
1508 ///
1509 /// This method walks the RRB tree making up the current `Vector`
1510 /// (if it has one) and verifies that all the invariants hold.
1511 /// If something is wrong, it will panic.
1512 ///
1513 /// This method requires the `debug` feature flag.
1514 #[cfg(any(test, feature = "debug"))]
assert_invariants(&self)1515 pub fn assert_invariants(&self) {
1516 if let Full(_, ref tree) = self.vector {
1517 tree.assert_invariants();
1518 }
1519 }
1520 }
1521
1522 // Implementation details
1523
1524 impl<A: Clone> RRB<A> {
new(pool: &RRBPool<A>) -> Self1525 fn new(pool: &RRBPool<A>) -> Self {
1526 RRB {
1527 length: 0,
1528 middle_level: 0,
1529 outer_f: PoolRef::default(&pool.value_pool),
1530 inner_f: PoolRef::default(&pool.value_pool),
1531 middle: Ref::new(Node::new()),
1532 inner_b: PoolRef::default(&pool.value_pool),
1533 outer_b: PoolRef::default(&pool.value_pool),
1534 }
1535 }
1536
1537 #[cfg(any(test, feature = "debug"))]
assert_invariants(&self)1538 fn assert_invariants(&self) {
1539 let ml = self.middle.assert_invariants(self.middle_level);
1540 assert_eq!(
1541 self.length,
1542 self.outer_f.len() + self.inner_f.len() + ml + self.inner_b.len() + self.outer_b.len()
1543 );
1544 }
1545
prune(&mut self)1546 fn prune(&mut self) {
1547 if self.middle.is_empty() {
1548 self.middle = Ref::new(Node::new());
1549 self.middle_level = 0;
1550 } else {
1551 while self.middle_level > 0 && self.middle.is_single() {
1552 // FIXME could be optimised, cloning the node is expensive
1553 self.middle = Ref::new(self.middle.first_child().clone());
1554 self.middle_level -= 1;
1555 }
1556 }
1557 }
1558
pop_front(&mut self, pool: &RRBPool<A>) -> Option<A>1559 fn pop_front(&mut self, pool: &RRBPool<A>) -> Option<A> {
1560 if self.length == 0 {
1561 return None;
1562 }
1563 if self.outer_f.is_empty() {
1564 if self.inner_f.is_empty() {
1565 if self.middle.is_empty() {
1566 if self.inner_b.is_empty() {
1567 swap(&mut self.outer_f, &mut self.outer_b);
1568 } else {
1569 swap(&mut self.outer_f, &mut self.inner_b);
1570 }
1571 } else {
1572 self.outer_f = self.pop_middle(pool, Side::Left).unwrap();
1573 }
1574 } else {
1575 swap(&mut self.outer_f, &mut self.inner_f);
1576 }
1577 }
1578 self.length -= 1;
1579 let outer_f = PoolRef::make_mut(&pool.value_pool, &mut self.outer_f);
1580 Some(outer_f.pop_front())
1581 }
1582
pop_back(&mut self, pool: &RRBPool<A>) -> Option<A>1583 fn pop_back(&mut self, pool: &RRBPool<A>) -> Option<A> {
1584 if self.length == 0 {
1585 return None;
1586 }
1587 if self.outer_b.is_empty() {
1588 if self.inner_b.is_empty() {
1589 if self.middle.is_empty() {
1590 if self.inner_f.is_empty() {
1591 swap(&mut self.outer_b, &mut self.outer_f);
1592 } else {
1593 swap(&mut self.outer_b, &mut self.inner_f);
1594 }
1595 } else {
1596 self.outer_b = self.pop_middle(pool, Side::Right).unwrap();
1597 }
1598 } else {
1599 swap(&mut self.outer_b, &mut self.inner_b);
1600 }
1601 }
1602 self.length -= 1;
1603 let outer_b = PoolRef::make_mut(&pool.value_pool, &mut self.outer_b);
1604 Some(outer_b.pop_back())
1605 }
1606
push_front(&mut self, pool: &RRBPool<A>, value: A)1607 fn push_front(&mut self, pool: &RRBPool<A>, value: A) {
1608 if self.outer_f.is_full() {
1609 swap(&mut self.outer_f, &mut self.inner_f);
1610 if !self.outer_f.is_empty() {
1611 let mut chunk = PoolRef::new(&pool.value_pool, Chunk::new());
1612 swap(&mut chunk, &mut self.outer_f);
1613 self.push_middle(pool, Side::Left, chunk);
1614 }
1615 }
1616 self.length = self.length.checked_add(1).expect("Vector length overflow");
1617 let outer_f = PoolRef::make_mut(&pool.value_pool, &mut self.outer_f);
1618 outer_f.push_front(value)
1619 }
1620
push_back(&mut self, pool: &RRBPool<A>, value: A)1621 fn push_back(&mut self, pool: &RRBPool<A>, value: A) {
1622 if self.outer_b.is_full() {
1623 swap(&mut self.outer_b, &mut self.inner_b);
1624 if !self.outer_b.is_empty() {
1625 let mut chunk = PoolRef::new(&pool.value_pool, Chunk::new());
1626 swap(&mut chunk, &mut self.outer_b);
1627 self.push_middle(pool, Side::Right, chunk);
1628 }
1629 }
1630 self.length = self.length.checked_add(1).expect("Vector length overflow");
1631 let outer_b = PoolRef::make_mut(&pool.value_pool, &mut self.outer_b);
1632 outer_b.push_back(value)
1633 }
1634
push_middle(&mut self, pool: &RRBPool<A>, side: Side, chunk: PoolRef<Chunk<A>>)1635 fn push_middle(&mut self, pool: &RRBPool<A>, side: Side, chunk: PoolRef<Chunk<A>>) {
1636 if chunk.is_empty() {
1637 return;
1638 }
1639 let new_middle = {
1640 let middle = Ref::make_mut(&mut self.middle);
1641 match middle.push_chunk(pool, self.middle_level, side, chunk) {
1642 PushResult::Done => return,
1643 PushResult::Full(chunk, _num_drained) => Ref::from({
1644 match side {
1645 Side::Left => Node::from_chunk(pool, self.middle_level, chunk)
1646 .join_branches(pool, middle.clone(), self.middle_level),
1647 Side::Right => middle.clone().join_branches(
1648 pool,
1649 Node::from_chunk(pool, self.middle_level, chunk),
1650 self.middle_level,
1651 ),
1652 }
1653 }),
1654 }
1655 };
1656 self.middle_level += 1;
1657 self.middle = new_middle;
1658 }
1659
pop_middle(&mut self, pool: &RRBPool<A>, side: Side) -> Option<PoolRef<Chunk<A>>>1660 fn pop_middle(&mut self, pool: &RRBPool<A>, side: Side) -> Option<PoolRef<Chunk<A>>> {
1661 let chunk = {
1662 let middle = Ref::make_mut(&mut self.middle);
1663 match middle.pop_chunk(pool, self.middle_level, side) {
1664 PopResult::Empty => return None,
1665 PopResult::Done(chunk) => chunk,
1666 PopResult::Drained(chunk) => {
1667 middle.clear_node();
1668 self.middle_level = 0;
1669 chunk
1670 }
1671 }
1672 };
1673 Some(chunk)
1674 }
1675 }
1676
1677 #[inline]
replace_pool_def<A: PoolDefault>(pool: &Pool<A>, dest: &mut PoolRef<A>) -> PoolRef<A>1678 fn replace_pool_def<A: PoolDefault>(pool: &Pool<A>, dest: &mut PoolRef<A>) -> PoolRef<A> {
1679 replace(dest, PoolRef::default(pool))
1680 }
1681
1682 // Core traits
1683
1684 impl<A: Clone> Default for Vector<A> {
default() -> Self1685 fn default() -> Self {
1686 Self::new()
1687 }
1688 }
1689
1690 impl<A: Clone> Clone for Vector<A> {
1691 /// Clone a vector.
1692 ///
1693 /// Time: O(1), or O(n) with a very small, bounded *n* for an inline vector.
clone(&self) -> Self1694 fn clone(&self) -> Self {
1695 Self {
1696 vector: match &self.vector {
1697 Inline(pool, chunk) => Inline(pool.clone(), chunk.clone()),
1698 Single(pool, chunk) => Single(pool.clone(), chunk.clone()),
1699 Full(pool, tree) => Full(pool.clone(), tree.clone()),
1700 },
1701 }
1702 }
1703 }
1704
1705 impl<A: Clone + Debug> Debug for Vector<A> {
fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>1706 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
1707 f.debug_list().entries(self.iter()).finish()
1708 // match self {
1709 // Full(rrb) => {
1710 // writeln!(f, "Head: {:?} {:?}", rrb.outer_f, rrb.inner_f)?;
1711 // rrb.middle.print(f, 0, rrb.middle_level)?;
1712 // writeln!(f, "Tail: {:?} {:?}", rrb.inner_b, rrb.outer_b)
1713 // }
1714 // Single(_) => write!(f, "nowt"),
1715 // }
1716 }
1717 }
1718
1719 #[cfg(not(has_specialisation))]
1720 impl<A: Clone + PartialEq> PartialEq for Vector<A> {
eq(&self, other: &Self) -> bool1721 fn eq(&self, other: &Self) -> bool {
1722 self.len() == other.len() && self.iter().eq(other.iter())
1723 }
1724 }
1725
1726 #[cfg(has_specialisation)]
1727 impl<A: Clone + PartialEq> PartialEq for Vector<A> {
eq(&self, other: &Self) -> bool1728 default fn eq(&self, other: &Self) -> bool {
1729 self.len() == other.len() && self.iter().eq(other.iter())
1730 }
1731 }
1732
1733 #[cfg(has_specialisation)]
1734 impl<A: Clone + Eq> PartialEq for Vector<A> {
eq(&self, other: &Self) -> bool1735 fn eq(&self, other: &Self) -> bool {
1736 fn cmp_chunk<A>(left: &PoolRef<Chunk<A>>, right: &PoolRef<Chunk<A>>) -> bool {
1737 (left.is_empty() && right.is_empty()) || PoolRef::ptr_eq(left, right)
1738 }
1739
1740 if std::ptr::eq(self, other) {
1741 return true;
1742 }
1743
1744 match (&self.vector, &other.vector) {
1745 (Single(_, left), Single(_, right)) => {
1746 if cmp_chunk(left, right) {
1747 return true;
1748 }
1749 self.iter().eq(other.iter())
1750 }
1751 (Full(_, left), Full(_, right)) => {
1752 if left.length != right.length {
1753 return false;
1754 }
1755
1756 if cmp_chunk(&left.outer_f, &right.outer_f)
1757 && cmp_chunk(&left.inner_f, &right.inner_f)
1758 && cmp_chunk(&left.inner_b, &right.inner_b)
1759 && cmp_chunk(&left.outer_b, &right.outer_b)
1760 && ((left.middle.is_empty() && right.middle.is_empty())
1761 || Ref::ptr_eq(&left.middle, &right.middle))
1762 {
1763 return true;
1764 }
1765 self.iter().eq(other.iter())
1766 }
1767 _ => self.len() == other.len() && self.iter().eq(other.iter()),
1768 }
1769 }
1770 }
1771
1772 impl<A: Clone + Eq> Eq for Vector<A> {}
1773
1774 impl<A: Clone + PartialOrd> PartialOrd for Vector<A> {
partial_cmp(&self, other: &Self) -> Option<Ordering>1775 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1776 self.iter().partial_cmp(other.iter())
1777 }
1778 }
1779
1780 impl<A: Clone + Ord> Ord for Vector<A> {
cmp(&self, other: &Self) -> Ordering1781 fn cmp(&self, other: &Self) -> Ordering {
1782 self.iter().cmp(other.iter())
1783 }
1784 }
1785
1786 impl<A: Clone + Hash> Hash for Vector<A> {
hash<H: Hasher>(&self, state: &mut H)1787 fn hash<H: Hasher>(&self, state: &mut H) {
1788 for i in self {
1789 i.hash(state)
1790 }
1791 }
1792 }
1793
1794 impl<A: Clone> Sum for Vector<A> {
sum<I>(it: I) -> Self where I: Iterator<Item = Self>,1795 fn sum<I>(it: I) -> Self
1796 where
1797 I: Iterator<Item = Self>,
1798 {
1799 it.fold(Self::new(), |a, b| a + b)
1800 }
1801 }
1802
1803 impl<A: Clone> Add for Vector<A> {
1804 type Output = Vector<A>;
1805
1806 /// Concatenate two vectors.
1807 ///
1808 /// Time: O(log n)
add(mut self, other: Self) -> Self::Output1809 fn add(mut self, other: Self) -> Self::Output {
1810 self.append(other);
1811 self
1812 }
1813 }
1814
1815 impl<'a, A: Clone> Add for &'a Vector<A> {
1816 type Output = Vector<A>;
1817
1818 /// Concatenate two vectors.
1819 ///
1820 /// Time: O(log n)
add(self, other: Self) -> Self::Output1821 fn add(self, other: Self) -> Self::Output {
1822 let mut out = self.clone();
1823 out.append(other.clone());
1824 out
1825 }
1826 }
1827
1828 impl<A: Clone> Extend<A> for Vector<A> {
1829 /// Add values to the end of a vector by consuming an iterator.
1830 ///
1831 /// Time: O(n)
extend<I>(&mut self, iter: I) where I: IntoIterator<Item = A>,1832 fn extend<I>(&mut self, iter: I)
1833 where
1834 I: IntoIterator<Item = A>,
1835 {
1836 for item in iter {
1837 self.push_back(item)
1838 }
1839 }
1840 }
1841
1842 impl<A: Clone> Index<usize> for Vector<A> {
1843 type Output = A;
1844 /// Get a reference to the value at index `index` in the vector.
1845 ///
1846 /// Time: O(log n)
index(&self, index: usize) -> &Self::Output1847 fn index(&self, index: usize) -> &Self::Output {
1848 match self.get(index) {
1849 Some(value) => value,
1850 None => panic!(
1851 "Vector::index: index out of bounds: {} < {}",
1852 index,
1853 self.len()
1854 ),
1855 }
1856 }
1857 }
1858
1859 impl<A: Clone> IndexMut<usize> for Vector<A> {
1860 /// Get a mutable reference to the value at index `index` in the
1861 /// vector.
1862 ///
1863 /// Time: O(log n)
index_mut(&mut self, index: usize) -> &mut Self::Output1864 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
1865 match self.get_mut(index) {
1866 Some(value) => value,
1867 None => panic!("Vector::index_mut: index out of bounds"),
1868 }
1869 }
1870 }
1871
1872 // Conversions
1873
1874 impl<'a, A: Clone> IntoIterator for &'a Vector<A> {
1875 type Item = &'a A;
1876 type IntoIter = Iter<'a, A>;
into_iter(self) -> Self::IntoIter1877 fn into_iter(self) -> Self::IntoIter {
1878 self.iter()
1879 }
1880 }
1881
1882 impl<A: Clone> IntoIterator for Vector<A> {
1883 type Item = A;
1884 type IntoIter = ConsumingIter<A>;
into_iter(self) -> Self::IntoIter1885 fn into_iter(self) -> Self::IntoIter {
1886 ConsumingIter::new(self)
1887 }
1888 }
1889
1890 impl<A: Clone> FromIterator<A> for Vector<A> {
1891 /// Create a vector from an iterator.
1892 ///
1893 /// Time: O(n)
from_iter<I>(iter: I) -> Self where I: IntoIterator<Item = A>,1894 fn from_iter<I>(iter: I) -> Self
1895 where
1896 I: IntoIterator<Item = A>,
1897 {
1898 let mut seq = Self::new();
1899 for item in iter {
1900 seq.push_back(item)
1901 }
1902 seq
1903 }
1904 }
1905
1906 impl<'s, 'a, A, OA> From<&'s Vector<&'a A>> for Vector<OA>
1907 where
1908 A: ToOwned<Owned = OA>,
1909 OA: Borrow<A> + Clone,
1910 {
from(vec: &Vector<&A>) -> Self1911 fn from(vec: &Vector<&A>) -> Self {
1912 vec.iter().map(|a| (*a).to_owned()).collect()
1913 }
1914 }
1915
1916 impl<'a, A: Clone> From<&'a [A]> for Vector<A> {
from(slice: &[A]) -> Self1917 fn from(slice: &[A]) -> Self {
1918 slice.iter().cloned().collect()
1919 }
1920 }
1921
1922 impl<A: Clone> From<Vec<A>> for Vector<A> {
1923 /// Create a vector from a [`std::vec::Vec`][vec].
1924 ///
1925 /// Time: O(n)
1926 ///
1927 /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
from(vec: Vec<A>) -> Self1928 fn from(vec: Vec<A>) -> Self {
1929 vec.into_iter().collect()
1930 }
1931 }
1932
1933 impl<'a, A: Clone> From<&'a Vec<A>> for Vector<A> {
1934 /// Create a vector from a [`std::vec::Vec`][vec].
1935 ///
1936 /// Time: O(n)
1937 ///
1938 /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
from(vec: &Vec<A>) -> Self1939 fn from(vec: &Vec<A>) -> Self {
1940 vec.iter().cloned().collect()
1941 }
1942 }
1943
1944 // Iterators
1945
1946 /// An iterator over vectors with values of type `A`.
1947 ///
1948 /// To obtain one, use [`Vector::iter()`][iter].
1949 ///
1950 /// [iter]: enum.Vector.html#method.iter
1951 pub struct Iter<'a, A> {
1952 focus: Focus<'a, A>,
1953 front_index: usize,
1954 back_index: usize,
1955 }
1956
1957 impl<'a, A: Clone> Iter<'a, A> {
new(seq: &'a Vector<A>) -> Self1958 fn new(seq: &'a Vector<A>) -> Self {
1959 Iter {
1960 focus: seq.focus(),
1961 front_index: 0,
1962 back_index: seq.len(),
1963 }
1964 }
1965
from_focus(focus: Focus<'a, A>) -> Self1966 fn from_focus(focus: Focus<'a, A>) -> Self {
1967 Iter {
1968 front_index: 0,
1969 back_index: focus.len(),
1970 focus,
1971 }
1972 }
1973 }
1974
1975 impl<'a, A: Clone> Iterator for Iter<'a, A> {
1976 type Item = &'a A;
1977
1978 /// Advance the iterator and return the next value.
1979 ///
1980 /// Time: O(1)*
next(&mut self) -> Option<Self::Item>1981 fn next(&mut self) -> Option<Self::Item> {
1982 if self.front_index >= self.back_index {
1983 return None;
1984 }
1985 #[allow(unsafe_code)]
1986 let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
1987 let value = focus.get(self.front_index);
1988 self.front_index += 1;
1989 value
1990 }
1991
size_hint(&self) -> (usize, Option<usize>)1992 fn size_hint(&self) -> (usize, Option<usize>) {
1993 let remaining = self.back_index - self.front_index;
1994 (remaining, Some(remaining))
1995 }
1996 }
1997
1998 impl<'a, A: Clone> DoubleEndedIterator for Iter<'a, A> {
1999 /// Advance the iterator and return the next value.
2000 ///
2001 /// Time: O(1)*
next_back(&mut self) -> Option<Self::Item>2002 fn next_back(&mut self) -> Option<Self::Item> {
2003 if self.front_index >= self.back_index {
2004 return None;
2005 }
2006 self.back_index -= 1;
2007 #[allow(unsafe_code)]
2008 let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2009 focus.get(self.back_index)
2010 }
2011 }
2012
2013 impl<'a, A: Clone> ExactSizeIterator for Iter<'a, A> {}
2014
2015 impl<'a, A: Clone> FusedIterator for Iter<'a, A> {}
2016
2017 /// A mutable iterator over vectors with values of type `A`.
2018 ///
2019 /// To obtain one, use [`Vector::iter_mut()`][iter_mut].
2020 ///
2021 /// [iter_mut]: enum.Vector.html#method.iter_mut
2022 pub struct IterMut<'a, A> {
2023 focus: FocusMut<'a, A>,
2024 front_index: usize,
2025 back_index: usize,
2026 }
2027
2028 impl<'a, A> IterMut<'a, A>
2029 where
2030 A: Clone,
2031 {
new(seq: &'a mut Vector<A>) -> Self2032 fn new(seq: &'a mut Vector<A>) -> Self {
2033 let focus = seq.focus_mut();
2034 let len = focus.len();
2035 IterMut {
2036 focus,
2037 front_index: 0,
2038 back_index: len,
2039 }
2040 }
2041
from_focus(focus: FocusMut<'a, A>) -> Self2042 fn from_focus(focus: FocusMut<'a, A>) -> Self {
2043 IterMut {
2044 front_index: 0,
2045 back_index: focus.len(),
2046 focus,
2047 }
2048 }
2049 }
2050
2051 impl<'a, A> Iterator for IterMut<'a, A>
2052 where
2053 A: 'a + Clone,
2054 {
2055 type Item = &'a mut A;
2056
2057 /// Advance the iterator and return the next value.
2058 ///
2059 /// Time: O(1)*
next(&mut self) -> Option<Self::Item>2060 fn next(&mut self) -> Option<Self::Item> {
2061 if self.front_index >= self.back_index {
2062 return None;
2063 }
2064 #[allow(unsafe_code)]
2065 let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2066 let value = focus.get_mut(self.front_index);
2067 self.front_index += 1;
2068 value
2069 }
2070
size_hint(&self) -> (usize, Option<usize>)2071 fn size_hint(&self) -> (usize, Option<usize>) {
2072 let remaining = self.back_index - self.front_index;
2073 (remaining, Some(remaining))
2074 }
2075 }
2076
2077 impl<'a, A> DoubleEndedIterator for IterMut<'a, A>
2078 where
2079 A: 'a + Clone,
2080 {
2081 /// Remove and return an element from the back of the iterator.
2082 ///
2083 /// Time: O(1)*
next_back(&mut self) -> Option<Self::Item>2084 fn next_back(&mut self) -> Option<Self::Item> {
2085 if self.front_index >= self.back_index {
2086 return None;
2087 }
2088 self.back_index -= 1;
2089 #[allow(unsafe_code)]
2090 let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2091 focus.get_mut(self.back_index)
2092 }
2093 }
2094
2095 impl<'a, A: Clone> ExactSizeIterator for IterMut<'a, A> {}
2096
2097 impl<'a, A: Clone> FusedIterator for IterMut<'a, A> {}
2098
2099 /// A consuming iterator over vectors with values of type `A`.
2100 pub struct ConsumingIter<A> {
2101 vector: Vector<A>,
2102 }
2103
2104 impl<A: Clone> ConsumingIter<A> {
new(vector: Vector<A>) -> Self2105 fn new(vector: Vector<A>) -> Self {
2106 Self { vector }
2107 }
2108 }
2109
2110 impl<A: Clone> Iterator for ConsumingIter<A> {
2111 type Item = A;
2112
2113 /// Advance the iterator and return the next value.
2114 ///
2115 /// Time: O(1)*
next(&mut self) -> Option<Self::Item>2116 fn next(&mut self) -> Option<Self::Item> {
2117 self.vector.pop_front()
2118 }
2119
size_hint(&self) -> (usize, Option<usize>)2120 fn size_hint(&self) -> (usize, Option<usize>) {
2121 let len = self.vector.len();
2122 (len, Some(len))
2123 }
2124 }
2125
2126 impl<A: Clone> DoubleEndedIterator for ConsumingIter<A> {
2127 /// Remove and return an element from the back of the iterator.
2128 ///
2129 /// Time: O(1)*
next_back(&mut self) -> Option<Self::Item>2130 fn next_back(&mut self) -> Option<Self::Item> {
2131 self.vector.pop_back()
2132 }
2133 }
2134
2135 impl<A: Clone> ExactSizeIterator for ConsumingIter<A> {}
2136
2137 impl<A: Clone> FusedIterator for ConsumingIter<A> {}
2138
2139 /// An iterator over the leaf nodes of a vector.
2140 ///
2141 /// To obtain one, use [`Vector::chunks()`][chunks].
2142 ///
2143 /// [chunks]: enum.Vector.html#method.chunks
2144 pub struct Chunks<'a, A> {
2145 focus: Focus<'a, A>,
2146 front_index: usize,
2147 back_index: usize,
2148 }
2149
2150 impl<'a, A: Clone> Chunks<'a, A> {
new(seq: &'a Vector<A>) -> Self2151 fn new(seq: &'a Vector<A>) -> Self {
2152 Chunks {
2153 focus: seq.focus(),
2154 front_index: 0,
2155 back_index: seq.len(),
2156 }
2157 }
2158 }
2159
2160 impl<'a, A: Clone> Iterator for Chunks<'a, A> {
2161 type Item = &'a [A];
2162
2163 /// Advance the iterator and return the next value.
2164 ///
2165 /// Time: O(1)*
next(&mut self) -> Option<Self::Item>2166 fn next(&mut self) -> Option<Self::Item> {
2167 if self.front_index >= self.back_index {
2168 return None;
2169 }
2170 #[allow(unsafe_code)]
2171 let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2172 let (range, value) = focus.chunk_at(self.front_index);
2173 self.front_index = range.end;
2174 Some(value)
2175 }
2176 }
2177
2178 impl<'a, A: Clone> DoubleEndedIterator for Chunks<'a, A> {
2179 /// Remove and return an element from the back of the iterator.
2180 ///
2181 /// Time: O(1)*
next_back(&mut self) -> Option<Self::Item>2182 fn next_back(&mut self) -> Option<Self::Item> {
2183 if self.front_index >= self.back_index {
2184 return None;
2185 }
2186 self.back_index -= 1;
2187 #[allow(unsafe_code)]
2188 let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2189 let (range, value) = focus.chunk_at(self.back_index);
2190 self.back_index = range.start;
2191 Some(value)
2192 }
2193 }
2194
2195 impl<'a, A: Clone> FusedIterator for Chunks<'a, A> {}
2196
2197 /// A mutable iterator over the leaf nodes of a vector.
2198 ///
2199 /// To obtain one, use [`Vector::chunks_mut()`][chunks_mut].
2200 ///
2201 /// [chunks_mut]: enum.Vector.html#method.chunks_mut
2202 pub struct ChunksMut<'a, A> {
2203 focus: FocusMut<'a, A>,
2204 front_index: usize,
2205 back_index: usize,
2206 }
2207
2208 impl<'a, A: Clone> ChunksMut<'a, A> {
new(seq: &'a mut Vector<A>) -> Self2209 fn new(seq: &'a mut Vector<A>) -> Self {
2210 let len = seq.len();
2211 ChunksMut {
2212 focus: seq.focus_mut(),
2213 front_index: 0,
2214 back_index: len,
2215 }
2216 }
2217 }
2218
2219 impl<'a, A: Clone> Iterator for ChunksMut<'a, A> {
2220 type Item = &'a mut [A];
2221
2222 /// Advance the iterator and return the next value.
2223 ///
2224 /// Time: O(1)*
next(&mut self) -> Option<Self::Item>2225 fn next(&mut self) -> Option<Self::Item> {
2226 if self.front_index >= self.back_index {
2227 return None;
2228 }
2229 #[allow(unsafe_code)]
2230 let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2231 let (range, value) = focus.chunk_at(self.front_index);
2232 self.front_index = range.end;
2233 Some(value)
2234 }
2235 }
2236
2237 impl<'a, A: Clone> DoubleEndedIterator for ChunksMut<'a, A> {
2238 /// Remove and return an element from the back of the iterator.
2239 ///
2240 /// Time: O(1)*
next_back(&mut self) -> Option<Self::Item>2241 fn next_back(&mut self) -> Option<Self::Item> {
2242 if self.front_index >= self.back_index {
2243 return None;
2244 }
2245 self.back_index -= 1;
2246 #[allow(unsafe_code)]
2247 let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) };
2248 let (range, value) = focus.chunk_at(self.back_index);
2249 self.back_index = range.start;
2250 Some(value)
2251 }
2252 }
2253
2254 impl<'a, A: Clone> FusedIterator for ChunksMut<'a, A> {}
2255
2256 // Proptest
2257 #[cfg(any(test, feature = "proptest"))]
2258 #[doc(hidden)]
2259 pub mod proptest {
2260 #[deprecated(
2261 since = "14.3.0",
2262 note = "proptest strategies have moved to im::proptest"
2263 )]
2264 pub use crate::proptest::vector;
2265 }
2266
2267 // Tests
2268
2269 #[cfg(test)]
2270 mod test {
2271 use super::*;
2272 use crate::proptest::vector;
2273 use ::proptest::collection::vec;
2274 use ::proptest::num::{i32, usize};
2275 use ::proptest::proptest;
2276
2277 #[test]
macro_allows_trailing_comma()2278 fn macro_allows_trailing_comma() {
2279 let vec1 = vector![1, 2, 3];
2280 let vec2 = vector![1, 2, 3,];
2281 assert_eq!(vec1, vec2);
2282 }
2283
2284 #[test]
indexing()2285 fn indexing() {
2286 let mut vec = vector![0, 1, 2, 3, 4, 5];
2287 vec.push_front(0);
2288 assert_eq!(0, *vec.get(0).unwrap());
2289 assert_eq!(0, vec[0]);
2290 }
2291
2292 #[test]
large_vector_focus()2293 fn large_vector_focus() {
2294 let input = Vector::from_iter(0..100_000);
2295 let vec = input.clone();
2296 let mut sum: i64 = 0;
2297 let mut focus = vec.focus();
2298 for i in 0..input.len() {
2299 sum += *focus.index(i);
2300 }
2301 let expected: i64 = (0..100_000).sum();
2302 assert_eq!(expected, sum);
2303 }
2304
2305 #[test]
large_vector_focus_mut()2306 fn large_vector_focus_mut() {
2307 let input = Vector::from_iter(0..100_000);
2308 let mut vec = input.clone();
2309 {
2310 let mut focus = vec.focus_mut();
2311 for i in 0..input.len() {
2312 let p = focus.index_mut(i);
2313 *p += 1;
2314 }
2315 }
2316 let expected: Vector<i32> = input.into_iter().map(|i| i + 1).collect();
2317 assert_eq!(expected, vec);
2318 }
2319
2320 #[test]
issue_55_fwd()2321 fn issue_55_fwd() {
2322 let mut l = Vector::new();
2323 for i in 0..4098 {
2324 l.append(Vector::unit(i));
2325 }
2326 l.append(Vector::unit(4098));
2327 assert_eq!(Some(&4097), l.get(4097));
2328 assert_eq!(Some(&4096), l.get(4096));
2329 }
2330
2331 #[test]
issue_55_back()2332 fn issue_55_back() {
2333 let mut l = Vector::unit(0);
2334 for i in 0..4099 {
2335 let mut tmp = Vector::unit(i + 1);
2336 tmp.append(l);
2337 l = tmp;
2338 }
2339 assert_eq!(Some(&4098), l.get(1));
2340 assert_eq!(Some(&4097), l.get(2));
2341 let len = l.len();
2342 l.slice(2..len);
2343 }
2344
2345 #[test]
issue_55_append()2346 fn issue_55_append() {
2347 let mut vec1 = Vector::from_iter(0..92);
2348 let vec2 = Vector::from_iter(0..165);
2349 vec1.append(vec2);
2350 }
2351
2352 #[test]
issue_70()2353 fn issue_70() {
2354 let mut x = Vector::new();
2355 for _ in 0..262 {
2356 x.push_back(0);
2357 }
2358 for _ in 0..97 {
2359 x.pop_front();
2360 }
2361 for &offset in &[160, 163, 160] {
2362 x.remove(offset);
2363 }
2364 for _ in 0..64 {
2365 x.push_back(0);
2366 }
2367 // At this point middle contains three chunks of size 64, 64 and 1
2368 // respectively. Previously the next `push_back()` would append another
2369 // zero-sized chunk to middle even though there is enough space left.
2370 match x.vector {
2371 VectorInner::Full(_, ref tree) => {
2372 assert_eq!(129, tree.middle.len());
2373 assert_eq!(3, tree.middle.number_of_children());
2374 }
2375 _ => unreachable!(),
2376 }
2377 x.push_back(0);
2378 match x.vector {
2379 VectorInner::Full(_, ref tree) => {
2380 assert_eq!(131, tree.middle.len());
2381 assert_eq!(3, tree.middle.number_of_children())
2382 }
2383 _ => unreachable!(),
2384 }
2385 for _ in 0..64 {
2386 x.push_back(0);
2387 }
2388 for _ in x.iter() {}
2389 }
2390
2391 #[test]
issue_67()2392 fn issue_67() {
2393 let mut l = Vector::unit(4100);
2394 for i in (0..4099).rev() {
2395 let mut tmp = Vector::unit(i);
2396 tmp.append(l);
2397 l = tmp;
2398 }
2399 assert_eq!(4100, l.len());
2400 let len = l.len();
2401 let tail = l.slice(1..len);
2402 assert_eq!(1, l.len());
2403 assert_eq!(4099, tail.len());
2404 assert_eq!(Some(&0), l.get(0));
2405 assert_eq!(Some(&1), tail.get(0));
2406 }
2407
2408 #[test]
issue_74_simple_size()2409 fn issue_74_simple_size() {
2410 use crate::nodes::rrb::NODE_SIZE;
2411 let mut x = Vector::new();
2412 for _ in 0..(CHUNK_SIZE
2413 * (
2414 1 // inner_f
2415 + (2 * NODE_SIZE) // middle: two full Entry::Nodes (4096 elements each)
2416 + 1 // inner_b
2417 + 1
2418 // outer_b
2419 ))
2420 {
2421 x.push_back(0u32);
2422 }
2423 let middle_first_node_start = CHUNK_SIZE;
2424 let middle_second_node_start = middle_first_node_start + NODE_SIZE * CHUNK_SIZE;
2425 // This reduces the size of the second node to 4095.
2426 x.remove(middle_second_node_start);
2427 // As outer_b is full, this will cause inner_b (length 64) to be pushed
2428 // to middle. The first element will be merged into the second node, the
2429 // remaining 63 elements will end up in a new node.
2430 x.push_back(0u32);
2431 match x.vector {
2432 VectorInner::Full(_, tree) => {
2433 assert_eq!(3, tree.middle.number_of_children());
2434 assert_eq!(
2435 2 * NODE_SIZE * CHUNK_SIZE + CHUNK_SIZE - 1,
2436 tree.middle.len()
2437 );
2438 }
2439 _ => unreachable!(),
2440 }
2441 }
2442
2443 #[test]
issue_77()2444 fn issue_77() {
2445 let mut x = Vector::new();
2446 for _ in 0..44 {
2447 x.push_back(0);
2448 }
2449 for _ in 0..20 {
2450 x.insert(0, 0);
2451 }
2452 x.insert(1, 0);
2453 for _ in 0..441 {
2454 x.push_back(0);
2455 }
2456 for _ in 0..58 {
2457 x.insert(0, 0);
2458 }
2459 x.insert(514, 0);
2460 for _ in 0..73 {
2461 x.push_back(0);
2462 }
2463 for _ in 0..10 {
2464 x.insert(0, 0);
2465 }
2466 x.insert(514, 0);
2467 }
2468
2469 #[test]
issue_105()2470 fn issue_105() {
2471 let mut v = Vector::new();
2472
2473 for i in 0..270_000 {
2474 v.push_front(i);
2475 }
2476
2477 while !v.is_empty() {
2478 v = v.take(v.len() - 1);
2479 }
2480 }
2481
2482 #[test]
issue_107_split_off_causes_overflow()2483 fn issue_107_split_off_causes_overflow() {
2484 let mut vec = Vector::from_iter(0..4289);
2485 let mut control = Vec::from_iter(0..4289);
2486 let chunk = 64;
2487
2488 while vec.len() >= chunk {
2489 vec = vec.split_off(chunk);
2490 control = control.split_off(chunk);
2491 assert_eq!(vec.len(), control.len());
2492 assert_eq!(control, vec.iter().cloned().collect::<Vec<_>>());
2493 }
2494 }
2495
2496 #[test]
collect_crash()2497 fn collect_crash() {
2498 let _vector: Vector<i32> = (0..5953).collect();
2499 // let _vector: Vector<i32> = (0..16384).collect();
2500 }
2501
2502 #[test]
issue_116()2503 fn issue_116() {
2504 let vec = Vector::from_iter(0..300);
2505 let rev_vec: Vector<u32> = vec.clone().into_iter().rev().collect();
2506 assert_eq!(vec.len(), rev_vec.len());
2507 }
2508
2509 #[test]
issue_131()2510 fn issue_131() {
2511 let smol = std::iter::repeat(42).take(64).collect::<Vector<_>>();
2512 let mut smol2 = smol.clone();
2513 assert!(smol.ptr_eq(&smol2));
2514 smol2.set(63, 420);
2515 assert!(!smol.ptr_eq(&smol2));
2516
2517 let huge = std::iter::repeat(42).take(65).collect::<Vector<_>>();
2518 let mut huge2 = huge.clone();
2519 assert!(huge.ptr_eq(&huge2));
2520 huge2.set(63, 420);
2521 assert!(!huge.ptr_eq(&huge2));
2522 }
2523
2524 #[test]
ptr_eq()2525 fn ptr_eq() {
2526 for len in 32..256 {
2527 let input = std::iter::repeat(42).take(len).collect::<Vector<_>>();
2528 let mut inp2 = input.clone();
2529 assert!(input.ptr_eq(&inp2));
2530 inp2.set(len - 1, 98);
2531 assert_ne!(inp2.get(len - 1), input.get(len - 1));
2532 assert!(!input.ptr_eq(&inp2), len);
2533 }
2534 }
2535
2536 proptest! {
2537 #[test]
2538 fn iter(ref vec in vec(i32::ANY, 0..1000)) {
2539 let seq: Vector<i32> = Vector::from_iter(vec.iter().cloned());
2540 for (index, item) in seq.iter().enumerate() {
2541 assert_eq!(&vec[index], item);
2542 }
2543 assert_eq!(vec.len(), seq.len());
2544 }
2545
2546 #[test]
2547 fn push_front_mut(ref input in vec(i32::ANY, 0..1000)) {
2548 let mut vector = Vector::new();
2549 for (count, value) in input.iter().cloned().enumerate() {
2550 assert_eq!(count, vector.len());
2551 vector.push_front(value);
2552 assert_eq!(count + 1, vector.len());
2553 }
2554 let input2 = Vec::from_iter(input.iter().rev().cloned());
2555 assert_eq!(input2, Vec::from_iter(vector.iter().cloned()));
2556 }
2557
2558 #[test]
2559 fn push_back_mut(ref input in vec(i32::ANY, 0..1000)) {
2560 let mut vector = Vector::new();
2561 for (count, value) in input.iter().cloned().enumerate() {
2562 assert_eq!(count, vector.len());
2563 vector.push_back(value);
2564 assert_eq!(count + 1, vector.len());
2565 }
2566 assert_eq!(input, &Vec::from_iter(vector.iter().cloned()));
2567 }
2568
2569 #[test]
2570 fn pop_back_mut(ref input in vec(i32::ANY, 0..1000)) {
2571 let mut vector = Vector::from_iter(input.iter().cloned());
2572 assert_eq!(input.len(), vector.len());
2573 for (index, value) in input.iter().cloned().enumerate().rev() {
2574 match vector.pop_back() {
2575 None => panic!("vector emptied unexpectedly"),
2576 Some(item) => {
2577 assert_eq!(index, vector.len());
2578 assert_eq!(value, item);
2579 }
2580 }
2581 }
2582 assert_eq!(0, vector.len());
2583 }
2584
2585 #[test]
2586 fn pop_front_mut(ref input in vec(i32::ANY, 0..1000)) {
2587 let mut vector = Vector::from_iter(input.iter().cloned());
2588 assert_eq!(input.len(), vector.len());
2589 for (index, value) in input.iter().cloned().rev().enumerate().rev() {
2590 match vector.pop_front() {
2591 None => panic!("vector emptied unexpectedly"),
2592 Some(item) => {
2593 assert_eq!(index, vector.len());
2594 assert_eq!(value, item);
2595 }
2596 }
2597 }
2598 assert_eq!(0, vector.len());
2599 }
2600
2601 // #[test]
2602 // fn push_and_pop(ref input in vec(i32::ANY, 0..1000)) {
2603 // let mut vector = Vector::new();
2604 // for (count, value) in input.iter().cloned().enumerate() {
2605 // assert_eq!(count, vector.len());
2606 // vector.push_back(value);
2607 // assert_eq!(count + 1, vector.len());
2608 // }
2609 // for (index, value) in input.iter().cloned().rev().enumerate().rev() {
2610 // match vector.pop_front() {
2611 // None => panic!("vector emptied unexpectedly"),
2612 // Some(item) => {
2613 // assert_eq!(index, vector.len());
2614 // assert_eq!(value, item);
2615 // }
2616 // }
2617 // }
2618 // assert_eq!(true, vector.is_empty());
2619 // }
2620
2621 #[test]
2622 fn split(ref vec in vec(i32::ANY, 1..2000), split_pos in usize::ANY) {
2623 let split_index = split_pos % (vec.len() + 1);
2624 let mut left = Vector::from_iter(vec.iter().cloned());
2625 let right = left.split_off(split_index);
2626 assert_eq!(left.len(), split_index);
2627 assert_eq!(right.len(), vec.len() - split_index);
2628 for (index, item) in left.iter().enumerate() {
2629 assert_eq!(& vec[index], item);
2630 }
2631 for (index, item) in right.iter().enumerate() {
2632 assert_eq!(&vec[split_index + index], item);
2633 }
2634 }
2635
2636 #[test]
2637 fn append(ref vec1 in vec(i32::ANY, 0..1000), ref vec2 in vec(i32::ANY, 0..1000)) {
2638 let mut seq1 = Vector::from_iter(vec1.iter().cloned());
2639 let seq2 = Vector::from_iter(vec2.iter().cloned());
2640 assert_eq!(seq1.len(), vec1.len());
2641 assert_eq!(seq2.len(), vec2.len());
2642 seq1.append(seq2);
2643 let mut vec = vec1.clone();
2644 vec.extend(vec2);
2645 assert_eq!(seq1.len(), vec.len());
2646 for (index, item) in seq1.into_iter().enumerate() {
2647 assert_eq!(vec[index], item);
2648 }
2649 }
2650
2651 #[test]
2652 fn iter_mut(ref input in vector(i32::ANY, 0..10000)) {
2653 let mut vec = input.clone();
2654 {
2655 for p in vec.iter_mut() {
2656 *p = p.overflowing_add(1).0;
2657 }
2658 }
2659 let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect();
2660 assert_eq!(expected, vec);
2661 }
2662
2663 #[test]
2664 fn focus(ref input in vector(i32::ANY, 0..10000)) {
2665 let mut vec = input.clone();
2666 {
2667 let mut focus = vec.focus_mut();
2668 for i in 0..input.len() {
2669 let p = focus.index_mut(i);
2670 *p = p.overflowing_add(1).0;
2671 }
2672 }
2673 let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect();
2674 assert_eq!(expected, vec);
2675 }
2676
2677 #[test]
2678 fn focus_mut_split(ref input in vector(i32::ANY, 0..10000)) {
2679 let mut vec = input.clone();
2680
2681 fn split_down(focus: FocusMut<'_, i32>) {
2682 let len = focus.len();
2683 if len < 8 {
2684 for p in focus {
2685 *p = p.overflowing_add(1).0;
2686 }
2687 } else {
2688 let (left, right) = focus.split_at(len / 2);
2689 split_down(left);
2690 split_down(right);
2691 }
2692 }
2693
2694 split_down(vec.focus_mut());
2695
2696 let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect();
2697 assert_eq!(expected, vec);
2698 }
2699
2700 #[test]
2701 fn chunks(ref input in vector(i32::ANY, 0..10000)) {
2702 let output: Vector<_> = input.leaves().flatten().cloned().collect();
2703 assert_eq!(input, &output);
2704 let rev_in: Vector<_> = input.iter().rev().cloned().collect();
2705 let rev_out: Vector<_> = input.leaves().rev().map(|c| c.iter().rev()).flatten().cloned().collect();
2706 assert_eq!(rev_in, rev_out);
2707 }
2708
2709 #[test]
2710 fn chunks_mut(ref mut input_src in vector(i32::ANY, 0..10000)) {
2711 let mut input = input_src.clone();
2712 #[allow(clippy::map_clone)]
2713 let output: Vector<_> = input.leaves_mut().flatten().map(|v| *v).collect();
2714 assert_eq!(input, output);
2715 let rev_in: Vector<_> = input.iter().rev().cloned().collect();
2716 let rev_out: Vector<_> = input.leaves_mut().rev().map(|c| c.iter().rev()).flatten().cloned().collect();
2717 assert_eq!(rev_in, rev_out);
2718 }
2719
2720 // The following two tests are very slow and there are unit tests above
2721 // which test for regression of issue #55. It would still be good to
2722 // run them occasionally.
2723
2724 // #[test]
2725 // fn issue55_back(count in 0..10000, slice_at in usize::ANY) {
2726 // let count = count as usize;
2727 // let slice_at = slice_at % count;
2728 // let mut l = Vector::unit(0);
2729 // for _ in 0..count {
2730 // let mut tmp = Vector::unit(0);
2731 // tmp.append(l);
2732 // l = tmp;
2733 // }
2734 // let len = l.len();
2735 // l.slice(slice_at..len);
2736 // }
2737
2738 // #[test]
2739 // fn issue55_fwd(count in 0..10000, slice_at in usize::ANY) {
2740 // let count = count as usize;
2741 // let slice_at = slice_at % count;
2742 // let mut l = Vector::new();
2743 // for i in 0..count {
2744 // l.append(Vector::unit(i));
2745 // }
2746 // assert_eq!(Some(&slice_at), l.get(slice_at));
2747 // }
2748 }
2749 }
2750