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/.
5 //! A persistent vector.
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
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.
23 //! ## Performance Notes
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].
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.
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.
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
46 use std
::borrow
::Borrow
;
47 use std
::cmp
::Ordering
;
48 use std
::fmt
::{Debug, Error, Formatter}
;
49 use std
::hash
::{Hash, Hasher}
;
51 use std
::iter
::{FromIterator, FusedIterator}
;
52 use std
::mem
::{replace, swap}
;
53 use std
::ops
::{Add, Index, IndexMut, RangeBounds}
;
55 use sized_chunks
::InlineArray
;
57 use crate::nodes
::chunk
::{Chunk, CHUNK_SIZE}
;
58 use crate::nodes
::rrb
::{Node, PopResult, PushResult, SplitResult}
;
60 use crate::util
::{clone_ref, swap_indices, to_range, Pool, PoolDefault, PoolRef, Ref, Side}
;
62 use self::VectorInner
::{Full, Inline, Single}
;
66 pub use self::focus
::{Focus, FocusMut}
;
69 pub use self::pool
::RRBPool
;
71 #[cfg(all(threadsafe, any(test, feature = "rayon")))]
74 /// Construct a vector from a sequence of elements.
79 /// # #[macro_use] extern crate im_rc as im;
80 /// # use im::vector::Vector;
84 /// Vector::from(vec![1, 2, 3])
90 () => { $crate::vector::Vector::new() }
;
92 ( $
($x
:expr
),* ) => {{
93 let mut l
= $
crate::vector
::Vector
::new();
100 ( $
($x
:expr
,)* ) => {{
101 let mut l
= $
crate::vector
::Vector
::new();
109 /// A persistent vector.
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.
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.
124 /// ## Performance Notes
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].
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.
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.
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
>,
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
>),
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
>>,
166 impl<A
> Clone
for Rrb
<A
> {
167 fn clone(&self) -> Self {
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(),
180 impl<A
: Clone
> Vector
<A
> {
181 /// Get a reference to the memory pool this `Vector` is using.
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))]
186 pub fn pool(&self) -> &RRBPool
<A
> {
188 Inline(ref pool
, _
) => pool
,
189 Single(ref pool
, _
) => pool
,
190 Full(ref pool
, _
) => pool
,
194 /// True if a vector is a full inline or single chunk, ie. must be promoted
196 fn needs_promotion(&self) -> bool
{
198 Inline(_
, chunk
) if chunk
.is_full() => true,
199 Single(_
, chunk
) if chunk
.is_full() => true,
204 /// Promote an inline to a single.
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()));
211 /// Promote a single to a full, with the single chunk becoming inner_f, or
212 /// promote an inline to a single.
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()))
218 Single(pool
, chunk
) => {
219 let chunk
= chunk
.clone();
225 outer_f
: PoolRef
::default(&pool
.value_pool
),
227 middle
: Ref
::new(Node
::new()),
228 inner_b
: PoolRef
::default(&pool
.value_pool
),
229 outer_b
: PoolRef
::default(&pool
.value_pool
),
233 Full(_
, _
) => return,
237 /// Promote a single to a full, with the single chunk becoming inner_b, or
238 /// promote an inline to a single.
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()))
244 Single(pool
, chunk
) => {
245 let chunk
= chunk
.clone();
251 outer_f
: PoolRef
::default(&pool
.value_pool
),
252 inner_f
: PoolRef
::default(&pool
.value_pool
),
253 middle
: Ref
::new(Node
::new()),
255 outer_b
: PoolRef
::default(&pool
.value_pool
),
259 Full(_
, _
) => return,
263 /// Construct an empty vector.
265 pub fn new() -> Self {
267 vector
: Inline(RRBPool
::default(), InlineArray
::new()),
271 /// Construct an empty vector using a specific memory pool.
272 #[cfg(feature = "pool")]
274 pub fn with_pool(pool
: &RRBPool
<A
>) -> Self {
276 vector
: Inline(pool
.clone(), InlineArray
::new()),
280 /// Get the length of a vector.
287 /// # #[macro_use] extern crate im_rc as im;
288 /// assert_eq!(5, vector![1, 2, 3, 4, 5].len());
292 pub fn len(&self) -> usize {
294 Inline(_
, chunk
) => chunk
.len(),
295 Single(_
, chunk
) => chunk
.len(),
296 Full(_
, tree
) => tree
.length
,
300 /// Test whether a vector is empty.
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());
315 pub fn is_empty(&self) -> bool
{
319 /// Test whether a vector is currently inlined.
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
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.
333 /// [ptr_eq]: #method.ptr_eq
336 pub fn is_inline(&self) -> bool
{
337 matches
!(&self.vector
, Inline(_
, _
))
340 /// Test whether two vectors refer to the same content in memory.
342 /// This uses the following rules to determine equality:
343 /// * If the two sides are references to the same vector, return true.
344 /// * If the two sides are single chunk vectors pointing to the same chunk, return true.
345 /// * If the two sides are full trees pointing to the same chunks, return true.
347 /// This would return true if you're comparing a vector to itself, or
348 /// if you're comparing a vector to a fresh clone of itself. The exception to this is
349 /// if you've cloned an inline array (ie. an array with so few elements they can fit
350 /// inside the space a `Vector` allocates for its pointers, so there are no heap allocations
355 pub fn ptr_eq(&self, other
: &Self) -> bool
{
356 fn cmp_chunk
<A
>(left
: &PoolRef
<Chunk
<A
>>, right
: &PoolRef
<Chunk
<A
>>) -> bool
{
357 (left
.is_empty() && right
.is_empty()) || PoolRef
::ptr_eq(left
, right
)
360 if std
::ptr
::eq(self, other
) {
364 match (&self.vector
, &other
.vector
) {
365 (Single(_
, left
), Single(_
, right
)) => cmp_chunk(left
, right
),
366 (Full(_
, left
), Full(_
, right
)) => {
367 cmp_chunk(&left
.outer_f
, &right
.outer_f
)
368 && cmp_chunk(&left
.inner_f
, &right
.inner_f
)
369 && cmp_chunk(&left
.inner_b
, &right
.inner_b
)
370 && cmp_chunk(&left
.outer_b
, &right
.outer_b
)
371 && ((left
.middle
.is_empty() && right
.middle
.is_empty())
372 || Ref
::ptr_eq(&left
.middle
, &right
.middle
))
378 /// Get an iterator over a vector.
383 pub fn iter(&self) -> Iter
<'_
, A
> {
387 /// Get a mutable iterator over a vector.
392 pub fn iter_mut(&mut self) -> IterMut
<'_
, A
> {
396 /// Get an iterator over the leaf nodes of a vector.
398 /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the
399 /// RRB tree. These are useful for efficient parallelisation of work on
400 /// the vector, but should not be used for basic iteration.
404 /// [Chunk]: ../chunk/struct.Chunk.html
407 pub fn leaves(&self) -> Chunks
<'_
, A
> {
411 /// Get a mutable iterator over the leaf nodes of a vector.
413 /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the
414 /// RRB tree. These are useful for efficient parallelisation of work on
415 /// the vector, but should not be used for basic iteration.
419 /// [Chunk]: ../chunk/struct.Chunk.html
422 pub fn leaves_mut(&mut self) -> ChunksMut
<'_
, A
> {
426 /// Construct a [`Focus`][Focus] for a vector.
430 /// [Focus]: enum.Focus.html
433 pub fn focus(&self) -> Focus
<'_
, A
> {
437 /// Construct a [`FocusMut`][FocusMut] for a vector.
441 /// [FocusMut]: enum.FocusMut.html
444 pub fn focus_mut(&mut self) -> FocusMut
<'_
, A
> {
448 /// Get a reference to the value at index `index` in a vector.
450 /// Returns `None` if the index is out of bounds.
457 /// # #[macro_use] extern crate im_rc as im;
458 /// # use im::Vector;
459 /// let vec = vector!["Joe", "Mike", "Robert"];
460 /// assert_eq!(Some(&"Robert"), vec.get(2));
461 /// assert_eq!(None, vec.get(5));
464 pub fn get(&self, index
: usize) -> Option
<&A
> {
465 if index
>= self.len() {
470 Inline(_
, chunk
) => chunk
.get(index
),
471 Single(_
, chunk
) => chunk
.get(index
),
473 let mut local_index
= index
;
475 if local_index
< tree
.outer_f
.len() {
476 return Some(&tree
.outer_f
[local_index
]);
478 local_index
-= tree
.outer_f
.len();
480 if local_index
< tree
.inner_f
.len() {
481 return Some(&tree
.inner_f
[local_index
]);
483 local_index
-= tree
.inner_f
.len();
485 if local_index
< tree
.middle
.len() {
486 return Some(tree
.middle
.index(tree
.middle_level
, local_index
));
488 local_index
-= tree
.middle
.len();
490 if local_index
< tree
.inner_b
.len() {
491 return Some(&tree
.inner_b
[local_index
]);
493 local_index
-= tree
.inner_b
.len();
495 Some(&tree
.outer_b
[local_index
])
500 /// Get a mutable reference to the value at index `index` in a
503 /// Returns `None` if the index is out of bounds.
510 /// # #[macro_use] extern crate im_rc as im;
511 /// # use im::Vector;
512 /// let mut vec = vector!["Joe", "Mike", "Robert"];
514 /// let robert = vec.get_mut(2).unwrap();
515 /// assert_eq!(&mut "Robert", robert);
516 /// *robert = "Bjarne";
518 /// assert_eq!(vector!["Joe", "Mike", "Bjarne"], vec);
521 pub fn get_mut(&mut self, index
: usize) -> Option
<&mut A
> {
522 if index
>= self.len() {
526 match &mut self.vector
{
527 Inline(_
, chunk
) => chunk
.get_mut(index
),
528 Single(pool
, chunk
) => PoolRef
::make_mut(&pool
.value_pool
, chunk
).get_mut(index
),
529 Full(pool
, tree
) => {
530 let mut local_index
= index
;
532 if local_index
< tree
.outer_f
.len() {
533 let outer_f
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.outer_f
);
534 return Some(&mut outer_f
[local_index
]);
536 local_index
-= tree
.outer_f
.len();
538 if local_index
< tree
.inner_f
.len() {
539 let inner_f
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.inner_f
);
540 return Some(&mut inner_f
[local_index
]);
542 local_index
-= tree
.inner_f
.len();
544 if local_index
< tree
.middle
.len() {
545 let middle
= Ref
::make_mut(&mut tree
.middle
);
546 return Some(middle
.index_mut(pool
, tree
.middle_level
, local_index
));
548 local_index
-= tree
.middle
.len();
550 if local_index
< tree
.inner_b
.len() {
551 let inner_b
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.inner_b
);
552 return Some(&mut inner_b
[local_index
]);
554 local_index
-= tree
.inner_b
.len();
556 let outer_b
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.outer_b
);
557 Some(&mut outer_b
[local_index
])
562 /// Get the first element of a vector.
564 /// If the vector is empty, `None` is returned.
569 pub fn front(&self) -> Option
<&A
> {
573 /// Get a mutable reference to the first element of a vector.
575 /// If the vector is empty, `None` is returned.
580 pub fn front_mut(&mut self) -> Option
<&mut A
> {
584 /// Get the first element of a vector.
586 /// If the vector is empty, `None` is returned.
588 /// This is an alias for the [`front`][front] method.
592 /// [front]: #method.front
595 pub fn head(&self) -> Option
<&A
> {
599 /// Get the last element of a vector.
601 /// If the vector is empty, `None` is returned.
605 pub fn back(&self) -> Option
<&A
> {
609 self.get(self.len() - 1)
613 /// Get a mutable reference to the last element of a vector.
615 /// If the vector is empty, `None` is returned.
619 pub fn back_mut(&mut self) -> Option
<&mut A
> {
623 let len
= self.len();
624 self.get_mut(len
- 1)
628 /// Get the last element of a vector.
630 /// If the vector is empty, `None` is returned.
632 /// This is an alias for the [`back`][back] method.
636 /// [back]: #method.back
639 pub fn last(&self) -> Option
<&A
> {
643 /// Get the index of a given element in the vector.
645 /// Searches the vector for the first occurrence of a given value,
646 /// and returns the index of the value if it's there. Otherwise,
647 /// it returns `None`.
654 /// # #[macro_use] extern crate im_rc as im;
655 /// # use im::Vector;
656 /// let mut vec = vector![1, 2, 3, 4, 5];
657 /// assert_eq!(Some(2), vec.index_of(&3));
658 /// assert_eq!(None, vec.index_of(&31337));
661 pub fn index_of(&self, value
: &A
) -> Option
<usize>
665 for (index
, item
) in self.iter().enumerate() {
673 /// Test if a given element is in the vector.
675 /// Searches the vector for the first occurrence of a given value,
676 /// and returns `true` if it's there. If it's nowhere to be found
677 /// in the vector, it returns `false`.
684 /// # #[macro_use] extern crate im_rc as im;
685 /// # use im::Vector;
686 /// let mut vec = vector![1, 2, 3, 4, 5];
687 /// assert_eq!(true, vec.contains(&3));
688 /// assert_eq!(false, vec.contains(&31337));
692 pub fn contains(&self, value
: &A
) -> bool
696 self.index_of(value
).is_some()
699 /// Discard all elements from the vector.
701 /// This leaves you with an empty vector, and all elements that
702 /// were previously inside it are dropped.
705 pub fn clear(&mut self) {
706 if !self.is_empty() {
707 self.vector
= Inline(self.pool().clone(), InlineArray
::new());
711 /// Binary search a sorted vector for a given element using a comparator
714 /// Assumes the vector has already been sorted using the same comparator
715 /// function, eg. by using [`sort_by`][sort_by].
717 /// If the value is found, it returns `Ok(index)` where `index` is the index
718 /// of the element. If the value isn't found, it returns `Err(index)` where
719 /// `index` is the index at which the element would need to be inserted to
720 /// maintain sorted order.
724 /// [sort_by]: #method.sort_by
725 pub fn binary_search_by
<F
>(&self, mut f
: F
) -> Result
<usize, usize>
727 F
: FnMut(&A
) -> Ordering
,
729 let mut size
= self.len();
736 let mid
= base
+ half
;
737 base
= match f(&self[mid
]) {
738 Ordering
::Greater
=> base
,
743 match f(&self[base
]) {
744 Ordering
::Equal
=> Ok(base
),
745 Ordering
::Greater
=> Err(base
),
746 Ordering
::Less
=> Err(base
+ 1),
750 /// Binary search a sorted vector for a given element.
752 /// If the value is found, it returns `Ok(index)` where `index` is the index
753 /// of the element. If the value isn't found, it returns `Err(index)` where
754 /// `index` is the index at which the element would need to be inserted to
755 /// maintain sorted order.
758 pub fn binary_search(&self, value
: &A
) -> Result
<usize, usize>
762 self.binary_search_by(|e
| e
.cmp(value
))
765 /// Binary search a sorted vector for a given element with a key extract
768 /// Assumes the vector has already been sorted using the same key extract
769 /// function, eg. by using [`sort_by_key`][sort_by_key].
771 /// If the value is found, it returns `Ok(index)` where `index` is the index
772 /// of the element. If the value isn't found, it returns `Err(index)` where
773 /// `index` is the index at which the element would need to be inserted to
774 /// maintain sorted order.
778 /// [sort_by_key]: #method.sort_by_key
779 pub fn binary_search_by_key
<B
, F
>(&self, b
: &B
, mut f
: F
) -> Result
<usize, usize>
784 self.binary_search_by(|k
| f(k
).cmp(b
))
788 impl<A
: Clone
> Vector
<A
> {
789 /// Construct a vector with a single value.
794 /// # #[macro_use] extern crate im_rc as im;
795 /// # use im::vector::Vector;
796 /// let vec = Vector::unit(1337);
797 /// assert_eq!(1, vec.len());
805 pub fn unit(a
: A
) -> Self {
806 let pool
= RRBPool
::default();
807 if InlineArray
::<A
, Rrb
<A
>>::CAPACITY
> 0 {
808 let mut array
= InlineArray
::new();
811 vector
: Inline(pool
, array
),
814 let chunk
= PoolRef
::new(&pool
.value_pool
, Chunk
::unit(a
));
816 vector
: Single(pool
, chunk
),
821 /// Create a new vector with the value at index `index` updated.
823 /// Panics if the index is out of bounds.
830 /// # #[macro_use] extern crate im_rc as im;
831 /// # use im::Vector;
832 /// let mut vec = vector![1, 2, 3];
833 /// assert_eq!(vector![1, 5, 3], vec.update(1, 5));
836 pub fn update(&self, index
: usize, value
: A
) -> Self {
837 let mut out
= self.clone();
842 /// Update the value at index `index` in a vector.
844 /// Returns the previous value at the index.
846 /// Panics if the index is out of bounds.
850 pub fn set(&mut self, index
: usize, value
: A
) -> A
{
851 replace(&mut self[index
], value
)
854 /// Swap the elements at indices `i` and `j`.
857 pub fn swap(&mut self, i
: usize, j
: usize) {
858 swap_indices(self, i
, j
)
861 /// Push a value to the front of a vector.
868 /// # #[macro_use] extern crate im_rc as im;
869 /// # use im::Vector;
870 /// let mut vec = vector![5, 6, 7];
871 /// vec.push_front(4);
872 /// assert_eq!(vector![4, 5, 6, 7], vec);
874 pub fn push_front(&mut self, value
: A
) {
875 if self.needs_promotion() {
878 match &mut self.vector
{
879 Inline(_
, chunk
) => {
880 chunk
.insert(0, value
);
882 Single(pool
, chunk
) => PoolRef
::make_mut(&pool
.value_pool
, chunk
).push_front(value
),
883 Full(pool
, tree
) => tree
.push_front(pool
, value
),
887 /// Push a value to the back of a vector.
894 /// # #[macro_use] extern crate im_rc as im;
895 /// # use im::Vector;
896 /// let mut vec = vector![1, 2, 3];
897 /// vec.push_back(4);
898 /// assert_eq!(vector![1, 2, 3, 4], vec);
900 pub fn push_back(&mut self, value
: A
) {
901 if self.needs_promotion() {
902 self.promote_front();
904 match &mut self.vector
{
905 Inline(_
, chunk
) => {
908 Single(pool
, chunk
) => PoolRef
::make_mut(&pool
.value_pool
, chunk
).push_back(value
),
909 Full(pool
, tree
) => tree
.push_back(pool
, value
),
913 /// Remove the first element from a vector and return it.
920 /// # #[macro_use] extern crate im_rc as im;
921 /// # use im::Vector;
922 /// let mut vec = vector![1, 2, 3];
923 /// assert_eq!(Some(1), vec.pop_front());
924 /// assert_eq!(vector![2, 3], vec);
926 pub fn pop_front(&mut self) -> Option
<A
> {
930 match &mut self.vector
{
931 Inline(_
, chunk
) => chunk
.remove(0),
932 Single(pool
, chunk
) => Some(PoolRef
::make_mut(&pool
.value_pool
, chunk
).pop_front()),
933 Full(pool
, tree
) => tree
.pop_front(pool
),
938 /// Remove the last element from a vector and return it.
945 /// # #[macro_use] extern crate im_rc as im;
946 /// # use im::Vector;
947 /// let mut vec = vector![1, 2, 3];
948 /// assert_eq!(Some(3), vec.pop_back());
949 /// assert_eq!(vector![1, 2], vec);
951 pub fn pop_back(&mut self) -> Option
<A
> {
955 match &mut self.vector
{
956 Inline(_
, chunk
) => chunk
.pop(),
957 Single(pool
, chunk
) => Some(PoolRef
::make_mut(&pool
.value_pool
, chunk
).pop_back()),
958 Full(pool
, tree
) => tree
.pop_back(pool
),
963 /// Append the vector `other` to the end of the current vector.
970 /// # #[macro_use] extern crate im_rc as im;
971 /// # use im::vector::Vector;
972 /// let mut vec = vector![1, 2, 3];
973 /// vec.append(vector![7, 8, 9]);
974 /// assert_eq!(vector![1, 2, 3, 7, 8, 9], vec);
976 pub fn append(&mut self, mut other
: Self) {
977 if other
.is_empty() {
986 self.promote_inline();
987 other
.promote_inline();
989 let total_length
= self
991 .checked_add(other
.len())
992 .expect("Vector length overflow");
994 match &mut self.vector
{
995 Inline(_
, _
) => unreachable
!("inline vecs should have been promoted"),
996 Single(pool
, left
) => {
997 match &mut other
.vector
{
998 Inline(_
, _
) => unreachable
!("inline vecs should have been promoted"),
999 // If both are single chunks and left has room for right: directly
1000 // memcpy right into left
1001 Single(_
, ref mut right
) if total_length
<= CHUNK_SIZE
=> {
1002 PoolRef
::make_mut(&pool
.value_pool
, left
)
1003 .append(PoolRef
::make_mut(&pool
.value_pool
, right
));
1006 // If only left is a single chunk and has room for right: push
1007 // right's elements into left
1008 _
if total_length
<= CHUNK_SIZE
=> {
1009 while let Some(value
) = other
.pop_front() {
1010 PoolRef
::make_mut(&pool
.value_pool
, left
).push_back(value
);
1017 Full(pool
, left
) => {
1018 if let Full(_
, mut right
) = other
.vector
{
1019 // If left and right are trees with empty middles, left has no back
1020 // buffers, and right has no front buffers: copy right's back
1021 // buffers over to left
1022 if left
.middle
.is_empty()
1023 && right
.middle
.is_empty()
1024 && left
.outer_b
.is_empty()
1025 && left
.inner_b
.is_empty()
1026 && right
.outer_f
.is_empty()
1027 && right
.inner_f
.is_empty()
1029 left
.inner_b
= right
.inner_b
;
1030 left
.outer_b
= right
.outer_b
;
1031 left
.length
= total_length
;
1034 // If left and right are trees with empty middles and left's buffers
1035 // can fit right's buffers: push right's elements onto left
1036 if left
.middle
.is_empty()
1037 && right
.middle
.is_empty()
1038 && total_length
<= CHUNK_SIZE
* 4
1040 while let Some(value
) = right
.pop_front(pool
) {
1041 left
.push_back(pool
, value
);
1045 // Both are full and big: do the full RRB join
1046 let inner_b1
= left
.inner_b
.clone();
1047 left
.push_middle(pool
, Side
::Right
, inner_b1
);
1048 let outer_b1
= left
.outer_b
.clone();
1049 left
.push_middle(pool
, Side
::Right
, outer_b1
);
1050 let inner_f2
= right
.inner_f
.clone();
1051 right
.push_middle(pool
, Side
::Left
, inner_f2
);
1052 let outer_f2
= right
.outer_f
.clone();
1053 right
.push_middle(pool
, Side
::Left
, outer_f2
);
1055 let mut middle1
= clone_ref(replace(&mut left
.middle
, Ref
::from(Node
::new())));
1056 let mut middle2
= clone_ref(right
.middle
);
1057 let normalised_middle
= match left
.middle_level
.cmp(&right
.middle_level
) {
1058 Ordering
::Greater
=> {
1059 middle2
= middle2
.elevate(pool
, left
.middle_level
- right
.middle_level
);
1063 middle1
= middle1
.elevate(pool
, right
.middle_level
- left
.middle_level
);
1066 Ordering
::Equal
=> left
.middle_level
,
1068 left
.middle
= Ref
::new(Node
::merge(pool
, middle1
, middle2
, normalised_middle
));
1069 left
.middle_level
= normalised_middle
+ 1;
1071 left
.inner_b
= right
.inner_b
;
1072 left
.outer_b
= right
.outer_b
;
1073 left
.length
= total_length
;
1079 // No optimisations available, and either left, right or both are
1080 // single: promote both to full and retry
1081 self.promote_front();
1082 other
.promote_back();
1086 /// Retain only the elements specified by the predicate.
1088 /// Remove all elements for which the provided function `f`
1089 /// returns false from the vector.
1092 pub fn retain
<F
>(&mut self, mut f
: F
)
1094 F
: FnMut(&A
) -> bool
,
1096 let len
= self.len();
1099 let mut focus
= self.focus_mut();
1101 if !f(focus
.index(i
)) {
1104 focus
.swap(i
- del
, i
);
1109 self.split_off(len
- del
);
1113 /// Split a vector at a given index.
1115 /// Split a vector at a given index, consuming the vector and
1116 /// returning a pair of the left hand side and the right hand side
1124 /// # #[macro_use] extern crate im_rc as im;
1125 /// # use im::vector::Vector;
1126 /// let mut vec = vector![1, 2, 3, 7, 8, 9];
1127 /// let (left, right) = vec.split_at(3);
1128 /// assert_eq!(vector![1, 2, 3], left);
1129 /// assert_eq!(vector![7, 8, 9], right);
1131 pub fn split_at(mut self, index
: usize) -> (Self, Self) {
1132 let right
= self.split_off(index
);
1136 /// Split a vector at a given index.
1138 /// Split a vector at a given index, leaving the left hand side in
1139 /// the current vector and returning a new vector containing the
1140 /// right hand side.
1147 /// # #[macro_use] extern crate im_rc as im;
1148 /// # use im::vector::Vector;
1149 /// let mut left = vector![1, 2, 3, 7, 8, 9];
1150 /// let right = left.split_off(3);
1151 /// assert_eq!(vector![1, 2, 3], left);
1152 /// assert_eq!(vector![7, 8, 9], right);
1154 pub fn split_off(&mut self, index
: usize) -> Self {
1155 assert
!(index
<= self.len());
1157 match &mut self.vector
{
1158 Inline(pool
, chunk
) => Self {
1159 vector
: Inline(pool
.clone(), chunk
.split_off(index
)),
1161 Single(pool
, chunk
) => Self {
1166 PoolRef
::make_mut(&pool
.value_pool
, chunk
).split_off(index
),
1170 Full(pool
, tree
) => {
1171 let mut local_index
= index
;
1173 if local_index
< tree
.outer_f
.len() {
1174 let of2
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.outer_f
)
1175 .split_off(local_index
);
1177 length
: tree
.length
- index
,
1178 middle_level
: tree
.middle_level
,
1179 outer_f
: PoolRef
::new(&pool
.value_pool
, of2
),
1180 inner_f
: replace_pool_def(&pool
.value_pool
, &mut tree
.inner_f
),
1181 middle
: std
::mem
::take(&mut tree
.middle
),
1182 inner_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.inner_b
),
1183 outer_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.outer_b
),
1185 tree
.length
= index
;
1186 tree
.middle_level
= 0;
1188 vector
: Full(pool
.clone(), right
),
1192 local_index
-= tree
.outer_f
.len();
1194 if local_index
< tree
.inner_f
.len() {
1195 let if2
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.inner_f
)
1196 .split_off(local_index
);
1198 length
: tree
.length
- index
,
1199 middle_level
: tree
.middle_level
,
1200 outer_f
: PoolRef
::new(&pool
.value_pool
, if2
),
1201 inner_f
: PoolRef
::<Chunk
<A
>>::default(&pool
.value_pool
),
1202 middle
: std
::mem
::take(&mut tree
.middle
),
1203 inner_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.inner_b
),
1204 outer_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.outer_b
),
1206 tree
.length
= index
;
1207 tree
.middle_level
= 0;
1208 swap(&mut tree
.outer_b
, &mut tree
.inner_f
);
1210 vector
: Full(pool
.clone(), right
),
1214 local_index
-= tree
.inner_f
.len();
1216 if local_index
< tree
.middle
.len() {
1217 let mut right_middle
= tree
.middle
.clone();
1219 let m1
= Ref
::make_mut(&mut tree
.middle
);
1220 let m2
= Ref
::make_mut(&mut right_middle
);
1221 match m1
.split(pool
, tree
.middle_level
, Side
::Right
, local_index
) {
1222 SplitResult
::Dropped(_
) => (),
1223 SplitResult
::OutOfBounds
=> unreachable
!(),
1225 match m2
.split(pool
, tree
.middle_level
, Side
::Left
, local_index
) {
1226 SplitResult
::Dropped(_
) => (),
1227 SplitResult
::OutOfBounds
=> unreachable
!(),
1229 let c1
= match m1
.pop_chunk(pool
, tree
.middle_level
, Side
::Right
) {
1230 PopResult
::Empty
=> PoolRef
::default(&pool
.value_pool
),
1231 PopResult
::Done(chunk
) => chunk
,
1232 PopResult
::Drained(chunk
) => {
1237 let c2
= match m2
.pop_chunk(pool
, tree
.middle_level
, Side
::Left
) {
1238 PopResult
::Empty
=> PoolRef
::default(&pool
.value_pool
),
1239 PopResult
::Done(chunk
) => chunk
,
1240 PopResult
::Drained(chunk
) => {
1247 let mut right
= Rrb
{
1248 length
: tree
.length
- index
,
1249 middle_level
: tree
.middle_level
,
1251 inner_f
: PoolRef
::<Chunk
<A
>>::default(&pool
.value_pool
),
1252 middle
: right_middle
,
1253 inner_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.inner_b
),
1254 outer_b
: replace(&mut tree
.outer_b
, c1
),
1256 tree
.length
= index
;
1260 vector
: Full(pool
.clone(), right
),
1264 local_index
-= tree
.middle
.len();
1266 if local_index
< tree
.inner_b
.len() {
1267 let ib2
= PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.inner_b
)
1268 .split_off(local_index
);
1270 length
: tree
.length
- index
,
1271 outer_b
: replace_pool_def(&pool
.value_pool
, &mut tree
.outer_b
),
1272 outer_f
: PoolRef
::new(&pool
.value_pool
, ib2
),
1275 tree
.length
= index
;
1276 swap(&mut tree
.outer_b
, &mut tree
.inner_b
);
1278 vector
: Full(pool
.clone(), right
),
1282 local_index
-= tree
.inner_b
.len();
1285 PoolRef
::make_mut(&pool
.value_pool
, &mut tree
.outer_b
).split_off(local_index
);
1286 tree
.length
= index
;
1288 vector
: Single(pool
.clone(), PoolRef
::new(&pool
.value_pool
, ob2
)),
1294 /// Construct a vector with `count` elements removed from the
1295 /// start of the current vector.
1299 pub fn skip(&self, count
: usize) -> Self {
1300 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1301 self.clone().split_off(count
)
1304 /// Construct a vector of the first `count` elements from the
1309 pub fn take(&self, count
: usize) -> Self {
1310 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1311 let mut left
= self.clone();
1312 left
.split_off(count
);
1316 /// Truncate a vector to the given size.
1318 /// Discards all elements in the vector beyond the given length.
1320 /// Panics if the new length is greater than the current length.
1323 pub fn truncate(&mut self, len
: usize) {
1324 // FIXME can be made more efficient by dropping the unwanted side without constructing it
1325 self.split_off(len
);
1328 /// Extract a slice from a vector.
1330 /// Remove the elements from `start_index` until `end_index` in
1331 /// the current vector and return the removed slice as a new
1335 pub fn slice
<R
>(&mut self, range
: R
) -> Self
1337 R
: RangeBounds
<usize>,
1339 let r
= to_range(&range
, self.len());
1340 if r
.start
>= r
.end
|| r
.start
>= self.len() {
1341 return Vector
::new();
1343 let mut middle
= self.split_off(r
.start
);
1344 let right
= middle
.split_off(r
.end
- r
.start
);
1349 /// Insert an element into a vector.
1351 /// Insert an element at position `index`, shifting all elements
1352 /// after it to the right.
1354 /// ## Performance Note
1356 /// While `push_front` and `push_back` are heavily optimised
1357 /// operations, `insert` in the middle of a vector requires a
1358 /// split, a push, and an append. Thus, if you want to insert
1359 /// many elements at the same location, instead of `insert`ing
1360 /// them one by one, you should rather create a new vector
1361 /// containing the elements to insert, split the vector at the
1362 /// insertion point, and append the left hand, the new vector and
1363 /// the right hand in order.
1366 pub fn insert(&mut self, index
: usize, value
: A
) {
1368 return self.push_front(value
);
1370 if index
== self.len() {
1371 return self.push_back(value
);
1373 assert
!(index
< self.len());
1374 if if let Inline(_
, chunk
) = &self.vector
{
1379 self.promote_inline();
1381 match &mut self.vector
{
1382 Inline(_
, chunk
) => {
1383 chunk
.insert(index
, value
);
1385 Single(pool
, chunk
) if chunk
.len() < CHUNK_SIZE
=> {
1386 PoolRef
::make_mut(&pool
.value_pool
, chunk
).insert(index
, value
)
1388 // TODO a lot of optimisations still possible here
1390 let right
= self.split_off(index
);
1391 self.push_back(value
);
1397 /// Remove an element from a vector.
1399 /// Remove the element from position 'index', shifting all
1400 /// elements after it to the left, and return the removed element.
1402 /// ## Performance Note
1404 /// While `pop_front` and `pop_back` are heavily optimised
1405 /// operations, `remove` in the middle of a vector requires a
1406 /// split, a pop, and an append. Thus, if you want to remove many
1407 /// elements from the same location, instead of `remove`ing them
1408 /// one by one, it is much better to use [`slice`][slice].
1412 /// [slice]: #method.slice
1413 pub fn remove(&mut self, index
: usize) -> A
{
1414 assert
!(index
< self.len());
1415 match &mut self.vector
{
1416 Inline(_
, chunk
) => chunk
.remove(index
).unwrap(),
1417 Single(pool
, chunk
) => PoolRef
::make_mut(&pool
.value_pool
, chunk
).remove(index
),
1420 return self.pop_front().unwrap();
1422 if index
== self.len() - 1 {
1423 return self.pop_back().unwrap();
1425 // TODO a lot of optimisations still possible here
1426 let mut right
= self.split_off(index
);
1427 let value
= right
.pop_front().unwrap();
1434 /// Insert an element into a sorted vector.
1436 /// Insert an element into a vector in sorted order, assuming the vector is
1437 /// already in sorted order.
1444 /// # #[macro_use] extern crate im_rc as im;
1445 /// # use im::vector::Vector;
1446 /// let mut vec = vector![1, 2, 3, 7, 8, 9];
1447 /// vec.insert_ord(5);
1448 /// assert_eq!(vector![1, 2, 3, 5, 7, 8, 9], vec);
1450 pub fn insert_ord(&mut self, item
: A
)
1454 match self.binary_search(&item
) {
1455 Ok(index
) => self.insert(index
, item
),
1456 Err(index
) => self.insert(index
, item
),
1462 /// Time: O(n log n)
1467 /// # #[macro_use] extern crate im_rc as im;
1468 /// # use im::vector::Vector;
1469 /// let mut vec = vector![3, 2, 5, 4, 1];
1471 /// assert_eq!(vector![1, 2, 3, 4, 5], vec);
1473 pub fn sort(&mut self)
1477 self.sort_by(Ord
::cmp
)
1480 /// Sort a vector using a comparator function.
1482 /// Time: O(n log n)
1487 /// # #[macro_use] extern crate im_rc as im;
1488 /// # use im::vector::Vector;
1489 /// let mut vec = vector![3, 2, 5, 4, 1];
1490 /// vec.sort_by(|left, right| left.cmp(right));
1491 /// assert_eq!(vector![1, 2, 3, 4, 5], vec);
1493 pub fn sort_by
<F
>(&mut self, cmp
: F
)
1495 F
: Fn(&A
, &A
) -> Ordering
,
1497 let len
= self.len();
1499 sort
::quicksort(self.focus_mut(), &cmp
);
1503 /// Verify the internal consistency of a vector.
1505 /// This method walks the RRB tree making up the current `Vector`
1506 /// (if it has one) and verifies that all the invariants hold.
1507 /// If something is wrong, it will panic.
1509 /// This method requires the `debug` feature flag.
1510 #[cfg(any(test, feature = "debug"))]
1511 pub fn assert_invariants(&self) {
1512 if let Full(_
, ref tree
) = self.vector
{
1513 tree
.assert_invariants();
1518 // Implementation details
1520 impl<A
: Clone
> Rrb
<A
> {
1521 fn new(pool
: &RRBPool
<A
>) -> Self {
1525 outer_f
: PoolRef
::default(&pool
.value_pool
),
1526 inner_f
: PoolRef
::default(&pool
.value_pool
),
1527 middle
: Ref
::new(Node
::new()),
1528 inner_b
: PoolRef
::default(&pool
.value_pool
),
1529 outer_b
: PoolRef
::default(&pool
.value_pool
),
1533 #[cfg(any(test, feature = "debug"))]
1534 fn assert_invariants(&self) {
1535 let ml
= self.middle
.assert_invariants(self.middle_level
);
1538 self.outer_f
.len() + self.inner_f
.len() + ml
+ self.inner_b
.len() + self.outer_b
.len()
1542 fn prune(&mut self) {
1543 if self.middle
.is_empty() {
1544 self.middle
= Ref
::new(Node
::new());
1545 self.middle_level
= 0;
1547 while self.middle_level
> 0 && self.middle
.is_single() {
1548 // FIXME could be optimised, cloning the node is expensive
1549 self.middle
= Ref
::new(self.middle
.first_child().clone());
1550 self.middle_level
-= 1;
1555 fn pop_front(&mut self, pool
: &RRBPool
<A
>) -> Option
<A
> {
1556 if self.length
== 0 {
1559 if self.outer_f
.is_empty() {
1560 if self.inner_f
.is_empty() {
1561 if self.middle
.is_empty() {
1562 if self.inner_b
.is_empty() {
1563 swap(&mut self.outer_f
, &mut self.outer_b
);
1565 swap(&mut self.outer_f
, &mut self.inner_b
);
1568 self.outer_f
= self.pop_middle(pool
, Side
::Left
).unwrap();
1571 swap(&mut self.outer_f
, &mut self.inner_f
);
1575 let outer_f
= PoolRef
::make_mut(&pool
.value_pool
, &mut self.outer_f
);
1576 Some(outer_f
.pop_front())
1579 fn pop_back(&mut self, pool
: &RRBPool
<A
>) -> Option
<A
> {
1580 if self.length
== 0 {
1583 if self.outer_b
.is_empty() {
1584 if self.inner_b
.is_empty() {
1585 if self.middle
.is_empty() {
1586 if self.inner_f
.is_empty() {
1587 swap(&mut self.outer_b
, &mut self.outer_f
);
1589 swap(&mut self.outer_b
, &mut self.inner_f
);
1592 self.outer_b
= self.pop_middle(pool
, Side
::Right
).unwrap();
1595 swap(&mut self.outer_b
, &mut self.inner_b
);
1599 let outer_b
= PoolRef
::make_mut(&pool
.value_pool
, &mut self.outer_b
);
1600 Some(outer_b
.pop_back())
1603 fn push_front(&mut self, pool
: &RRBPool
<A
>, value
: A
) {
1604 if self.outer_f
.is_full() {
1605 swap(&mut self.outer_f
, &mut self.inner_f
);
1606 if !self.outer_f
.is_empty() {
1607 let mut chunk
= PoolRef
::new(&pool
.value_pool
, Chunk
::new());
1608 swap(&mut chunk
, &mut self.outer_f
);
1609 self.push_middle(pool
, Side
::Left
, chunk
);
1612 self.length
= self.length
.checked_add(1).expect("Vector length overflow");
1613 let outer_f
= PoolRef
::make_mut(&pool
.value_pool
, &mut self.outer_f
);
1614 outer_f
.push_front(value
)
1617 fn push_back(&mut self, pool
: &RRBPool
<A
>, value
: A
) {
1618 if self.outer_b
.is_full() {
1619 swap(&mut self.outer_b
, &mut self.inner_b
);
1620 if !self.outer_b
.is_empty() {
1621 let mut chunk
= PoolRef
::new(&pool
.value_pool
, Chunk
::new());
1622 swap(&mut chunk
, &mut self.outer_b
);
1623 self.push_middle(pool
, Side
::Right
, chunk
);
1626 self.length
= self.length
.checked_add(1).expect("Vector length overflow");
1627 let outer_b
= PoolRef
::make_mut(&pool
.value_pool
, &mut self.outer_b
);
1628 outer_b
.push_back(value
)
1631 fn push_middle(&mut self, pool
: &RRBPool
<A
>, side
: Side
, chunk
: PoolRef
<Chunk
<A
>>) {
1632 if chunk
.is_empty() {
1636 let middle
= Ref
::make_mut(&mut self.middle
);
1637 match middle
.push_chunk(pool
, self.middle_level
, side
, chunk
) {
1638 PushResult
::Done
=> return,
1639 PushResult
::Full(chunk
, _num_drained
) => Ref
::from({
1641 Side
::Left
=> Node
::from_chunk(pool
, self.middle_level
, chunk
)
1642 .join_branches(pool
, middle
.clone(), self.middle_level
),
1643 Side
::Right
=> middle
.clone().join_branches(
1645 Node
::from_chunk(pool
, self.middle_level
, chunk
),
1652 self.middle_level
+= 1;
1653 self.middle
= new_middle
;
1656 fn pop_middle(&mut self, pool
: &RRBPool
<A
>, side
: Side
) -> Option
<PoolRef
<Chunk
<A
>>> {
1658 let middle
= Ref
::make_mut(&mut self.middle
);
1659 match middle
.pop_chunk(pool
, self.middle_level
, side
) {
1660 PopResult
::Empty
=> return None
,
1661 PopResult
::Done(chunk
) => chunk
,
1662 PopResult
::Drained(chunk
) => {
1663 middle
.clear_node();
1664 self.middle_level
= 0;
1674 fn replace_pool_def
<A
: PoolDefault
>(pool
: &Pool
<A
>, dest
: &mut PoolRef
<A
>) -> PoolRef
<A
> {
1675 replace(dest
, PoolRef
::default(pool
))
1680 impl<A
: Clone
> Default
for Vector
<A
> {
1681 fn default() -> Self {
1686 impl<A
: Clone
> Clone
for Vector
<A
> {
1689 /// Time: O(1), or O(n) with a very small, bounded *n* for an inline vector.
1690 fn clone(&self) -> Self {
1692 vector
: match &self.vector
{
1693 Inline(pool
, chunk
) => Inline(pool
.clone(), chunk
.clone()),
1694 Single(pool
, chunk
) => Single(pool
.clone(), chunk
.clone()),
1695 Full(pool
, tree
) => Full(pool
.clone(), tree
.clone()),
1701 impl<A
: Clone
+ Debug
> Debug
for Vector
<A
> {
1702 fn fmt(&self, f
: &mut Formatter
<'_
>) -> Result
<(), Error
> {
1703 f
.debug_list().entries(self.iter()).finish()
1706 // writeln!(f, "Head: {:?} {:?}", rrb.outer_f, rrb.inner_f)?;
1707 // rrb.middle.print(f, 0, rrb.middle_level)?;
1708 // writeln!(f, "Tail: {:?} {:?}", rrb.inner_b, rrb.outer_b)
1710 // Single(_) => write!(f, "nowt"),
1715 #[cfg(not(has_specialisation))]
1716 impl<A
: Clone
+ PartialEq
> PartialEq
for Vector
<A
> {
1717 fn eq(&self, other
: &Self) -> bool
{
1718 self.len() == other
.len() && self.iter().eq(other
.iter())
1722 #[cfg(has_specialisation)]
1723 impl<A
: Clone
+ PartialEq
> PartialEq
for Vector
<A
> {
1724 default fn eq(&self, other
: &Self) -> bool
{
1725 self.len() == other
.len() && self.iter().eq(other
.iter())
1729 #[cfg(has_specialisation)]
1730 impl<A
: Clone
+ Eq
> PartialEq
for Vector
<A
> {
1731 fn eq(&self, other
: &Self) -> bool
{
1732 fn cmp_chunk
<A
>(left
: &PoolRef
<Chunk
<A
>>, right
: &PoolRef
<Chunk
<A
>>) -> bool
{
1733 (left
.is_empty() && right
.is_empty()) || PoolRef
::ptr_eq(left
, right
)
1736 if std
::ptr
::eq(self, other
) {
1740 match (&self.vector
, &other
.vector
) {
1741 (Single(_
, left
), Single(_
, right
)) => {
1742 if cmp_chunk(left
, right
) {
1745 self.iter().eq(other
.iter())
1747 (Full(_
, left
), Full(_
, right
)) => {
1748 if left
.length
!= right
.length
{
1752 if cmp_chunk(&left
.outer_f
, &right
.outer_f
)
1753 && cmp_chunk(&left
.inner_f
, &right
.inner_f
)
1754 && cmp_chunk(&left
.inner_b
, &right
.inner_b
)
1755 && cmp_chunk(&left
.outer_b
, &right
.outer_b
)
1756 && ((left
.middle
.is_empty() && right
.middle
.is_empty())
1757 || Ref
::ptr_eq(&left
.middle
, &right
.middle
))
1761 self.iter().eq(other
.iter())
1763 _
=> self.len() == other
.len() && self.iter().eq(other
.iter()),
1768 impl<A
: Clone
+ Eq
> Eq
for Vector
<A
> {}
1770 impl<A
: Clone
+ PartialOrd
> PartialOrd
for Vector
<A
> {
1771 fn partial_cmp(&self, other
: &Self) -> Option
<Ordering
> {
1772 self.iter().partial_cmp(other
.iter())
1776 impl<A
: Clone
+ Ord
> Ord
for Vector
<A
> {
1777 fn cmp(&self, other
: &Self) -> Ordering
{
1778 self.iter().cmp(other
.iter())
1782 impl<A
: Clone
+ Hash
> Hash
for Vector
<A
> {
1783 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
1790 impl<A
: Clone
> Sum
for Vector
<A
> {
1791 fn sum
<I
>(it
: I
) -> Self
1793 I
: Iterator
<Item
= Self>,
1795 it
.fold(Self::new(), |a
, b
| a
+ b
)
1799 impl<A
: Clone
> Add
for Vector
<A
> {
1800 type Output
= Vector
<A
>;
1802 /// Concatenate two vectors.
1805 fn add(mut self, other
: Self) -> Self::Output
{
1811 impl<'a
, A
: Clone
> Add
for &'a Vector
<A
> {
1812 type Output
= Vector
<A
>;
1814 /// Concatenate two vectors.
1817 fn add(self, other
: Self) -> Self::Output
{
1818 let mut out
= self.clone();
1819 out
.append(other
.clone());
1824 impl<A
: Clone
> Extend
<A
> for Vector
<A
> {
1825 /// Add values to the end of a vector by consuming an iterator.
1828 fn extend
<I
>(&mut self, iter
: I
)
1830 I
: IntoIterator
<Item
= A
>,
1833 self.push_back(item
)
1838 impl<A
: Clone
> Index
<usize> for Vector
<A
> {
1840 /// Get a reference to the value at index `index` in the vector.
1843 fn index(&self, index
: usize) -> &Self::Output
{
1844 match self.get(index
) {
1845 Some(value
) => value
,
1847 "Vector::index: index out of bounds: {} < {}",
1855 impl<A
: Clone
> IndexMut
<usize> for Vector
<A
> {
1856 /// Get a mutable reference to the value at index `index` in the
1860 fn index_mut(&mut self, index
: usize) -> &mut Self::Output
{
1861 match self.get_mut(index
) {
1862 Some(value
) => value
,
1863 None
=> panic
!("Vector::index_mut: index out of bounds"),
1870 impl<'a
, A
: Clone
> IntoIterator
for &'a Vector
<A
> {
1872 type IntoIter
= Iter
<'a
, A
>;
1873 fn into_iter(self) -> Self::IntoIter
{
1878 impl<A
: Clone
> IntoIterator
for Vector
<A
> {
1880 type IntoIter
= ConsumingIter
<A
>;
1881 fn into_iter(self) -> Self::IntoIter
{
1882 ConsumingIter
::new(self)
1886 impl<A
: Clone
> FromIterator
<A
> for Vector
<A
> {
1887 /// Create a vector from an iterator.
1890 fn from_iter
<I
>(iter
: I
) -> Self
1892 I
: IntoIterator
<Item
= A
>,
1894 let mut seq
= Self::new();
1902 impl<'s
, 'a
, A
, OA
> From
<&'s Vector
<&'a A
>> for Vector
<OA
>
1904 A
: ToOwned
<Owned
= OA
>,
1905 OA
: Borrow
<A
> + Clone
,
1907 fn from(vec
: &Vector
<&A
>) -> Self {
1908 vec
.iter().map(|a
| (*a
).to_owned()).collect()
1912 impl<'a
, A
: Clone
> From
<&'a
[A
]> for Vector
<A
> {
1913 fn from(slice
: &[A
]) -> Self {
1914 slice
.iter().cloned().collect()
1918 impl<A
: Clone
> From
<Vec
<A
>> for Vector
<A
> {
1919 /// Create a vector from a [`std::vec::Vec`][vec].
1923 /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
1924 fn from(vec
: Vec
<A
>) -> Self {
1925 vec
.into_iter().collect()
1929 impl<'a
, A
: Clone
> From
<&'a Vec
<A
>> for Vector
<A
> {
1930 /// Create a vector from a [`std::vec::Vec`][vec].
1934 /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html
1935 fn from(vec
: &Vec
<A
>) -> Self {
1936 vec
.iter().cloned().collect()
1942 /// An iterator over vectors with values of type `A`.
1944 /// To obtain one, use [`Vector::iter()`][iter].
1946 /// [iter]: enum.Vector.html#method.iter
1947 pub struct Iter
<'a
, A
> {
1948 focus
: Focus
<'a
, A
>,
1953 impl<'a
, A
: Clone
> Iter
<'a
, A
> {
1954 fn new(seq
: &'a Vector
<A
>) -> Self {
1958 back_index
: seq
.len(),
1962 fn from_focus(focus
: Focus
<'a
, A
>) -> Self {
1965 back_index
: focus
.len(),
1971 impl<'a
, A
: Clone
> Iterator
for Iter
<'a
, A
> {
1974 /// Advance the iterator and return the next value.
1977 fn next(&mut self) -> Option
<Self::Item
> {
1978 if self.front_index
>= self.back_index
{
1981 #[allow(unsafe_code)]
1982 let focus
: &'a
mut Focus
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
1983 let value
= focus
.get(self.front_index
);
1984 self.front_index
+= 1;
1988 fn size_hint(&self) -> (usize, Option
<usize>) {
1989 let remaining
= self.back_index
- self.front_index
;
1990 (remaining
, Some(remaining
))
1994 impl<'a
, A
: Clone
> DoubleEndedIterator
for Iter
<'a
, A
> {
1995 /// Advance the iterator and return the next value.
1998 fn next_back(&mut self) -> Option
<Self::Item
> {
1999 if self.front_index
>= self.back_index
{
2002 self.back_index
-= 1;
2003 #[allow(unsafe_code)]
2004 let focus
: &'a
mut Focus
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2005 focus
.get(self.back_index
)
2009 impl<'a
, A
: Clone
> ExactSizeIterator
for Iter
<'a
, A
> {}
2011 impl<'a
, A
: Clone
> FusedIterator
for Iter
<'a
, A
> {}
2013 /// A mutable iterator over vectors with values of type `A`.
2015 /// To obtain one, use [`Vector::iter_mut()`][iter_mut].
2017 /// [iter_mut]: enum.Vector.html#method.iter_mut
2018 pub struct IterMut
<'a
, A
> {
2019 focus
: FocusMut
<'a
, A
>,
2024 impl<'a
, A
> IterMut
<'a
, A
>
2028 fn new(seq
: &'a
mut Vector
<A
>) -> Self {
2029 let focus
= seq
.focus_mut();
2030 let len
= focus
.len();
2038 fn from_focus(focus
: FocusMut
<'a
, A
>) -> Self {
2041 back_index
: focus
.len(),
2047 impl<'a
, A
> Iterator
for IterMut
<'a
, A
>
2051 type Item
= &'a
mut A
;
2053 /// Advance the iterator and return the next value.
2056 fn next(&mut self) -> Option
<Self::Item
> {
2057 if self.front_index
>= self.back_index
{
2060 #[allow(unsafe_code)]
2061 let focus
: &'a
mut FocusMut
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2062 let value
= focus
.get_mut(self.front_index
);
2063 self.front_index
+= 1;
2067 fn size_hint(&self) -> (usize, Option
<usize>) {
2068 let remaining
= self.back_index
- self.front_index
;
2069 (remaining
, Some(remaining
))
2073 impl<'a
, A
> DoubleEndedIterator
for IterMut
<'a
, A
>
2077 /// Remove and return an element from the back of the iterator.
2080 fn next_back(&mut self) -> Option
<Self::Item
> {
2081 if self.front_index
>= self.back_index
{
2084 self.back_index
-= 1;
2085 #[allow(unsafe_code)]
2086 let focus
: &'a
mut FocusMut
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2087 focus
.get_mut(self.back_index
)
2091 impl<'a
, A
: Clone
> ExactSizeIterator
for IterMut
<'a
, A
> {}
2093 impl<'a
, A
: Clone
> FusedIterator
for IterMut
<'a
, A
> {}
2095 /// A consuming iterator over vectors with values of type `A`.
2096 pub struct ConsumingIter
<A
> {
2100 impl<A
: Clone
> ConsumingIter
<A
> {
2101 fn new(vector
: Vector
<A
>) -> Self {
2106 impl<A
: Clone
> Iterator
for ConsumingIter
<A
> {
2109 /// Advance the iterator and return the next value.
2112 fn next(&mut self) -> Option
<Self::Item
> {
2113 self.vector
.pop_front()
2116 fn size_hint(&self) -> (usize, Option
<usize>) {
2117 let len
= self.vector
.len();
2122 impl<A
: Clone
> DoubleEndedIterator
for ConsumingIter
<A
> {
2123 /// Remove and return an element from the back of the iterator.
2126 fn next_back(&mut self) -> Option
<Self::Item
> {
2127 self.vector
.pop_back()
2131 impl<A
: Clone
> ExactSizeIterator
for ConsumingIter
<A
> {}
2133 impl<A
: Clone
> FusedIterator
for ConsumingIter
<A
> {}
2135 /// An iterator over the leaf nodes of a vector.
2137 /// To obtain one, use [`Vector::chunks()`][chunks].
2139 /// [chunks]: enum.Vector.html#method.chunks
2140 pub struct Chunks
<'a
, A
> {
2141 focus
: Focus
<'a
, A
>,
2146 impl<'a
, A
: Clone
> Chunks
<'a
, A
> {
2147 fn new(seq
: &'a Vector
<A
>) -> Self {
2151 back_index
: seq
.len(),
2156 impl<'a
, A
: Clone
> Iterator
for Chunks
<'a
, A
> {
2157 type Item
= &'a
[A
];
2159 /// Advance the iterator and return the next value.
2162 fn next(&mut self) -> Option
<Self::Item
> {
2163 if self.front_index
>= self.back_index
{
2166 #[allow(unsafe_code)]
2167 let focus
: &'a
mut Focus
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2168 let (range
, value
) = focus
.chunk_at(self.front_index
);
2169 self.front_index
= range
.end
;
2174 impl<'a
, A
: Clone
> DoubleEndedIterator
for Chunks
<'a
, A
> {
2175 /// Remove and return an element from the back of the iterator.
2178 fn next_back(&mut self) -> Option
<Self::Item
> {
2179 if self.front_index
>= self.back_index
{
2182 self.back_index
-= 1;
2183 #[allow(unsafe_code)]
2184 let focus
: &'a
mut Focus
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2185 let (range
, value
) = focus
.chunk_at(self.back_index
);
2186 self.back_index
= range
.start
;
2191 impl<'a
, A
: Clone
> FusedIterator
for Chunks
<'a
, A
> {}
2193 /// A mutable iterator over the leaf nodes of a vector.
2195 /// To obtain one, use [`Vector::chunks_mut()`][chunks_mut].
2197 /// [chunks_mut]: enum.Vector.html#method.chunks_mut
2198 pub struct ChunksMut
<'a
, A
> {
2199 focus
: FocusMut
<'a
, A
>,
2204 impl<'a
, A
: Clone
> ChunksMut
<'a
, A
> {
2205 fn new(seq
: &'a
mut Vector
<A
>) -> Self {
2206 let len
= seq
.len();
2208 focus
: seq
.focus_mut(),
2215 impl<'a
, A
: Clone
> Iterator
for ChunksMut
<'a
, A
> {
2216 type Item
= &'a
mut [A
];
2218 /// Advance the iterator and return the next value.
2221 fn next(&mut self) -> Option
<Self::Item
> {
2222 if self.front_index
>= self.back_index
{
2225 #[allow(unsafe_code)]
2226 let focus
: &'a
mut FocusMut
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2227 let (range
, value
) = focus
.chunk_at(self.front_index
);
2228 self.front_index
= range
.end
;
2233 impl<'a
, A
: Clone
> DoubleEndedIterator
for ChunksMut
<'a
, A
> {
2234 /// Remove and return an element from the back of the iterator.
2237 fn next_back(&mut self) -> Option
<Self::Item
> {
2238 if self.front_index
>= self.back_index
{
2241 self.back_index
-= 1;
2242 #[allow(unsafe_code)]
2243 let focus
: &'a
mut FocusMut
<'a
, A
> = unsafe { &mut *(&mut self.focus as *mut _) }
;
2244 let (range
, value
) = focus
.chunk_at(self.back_index
);
2245 self.back_index
= range
.start
;
2250 impl<'a
, A
: Clone
> FusedIterator
for ChunksMut
<'a
, A
> {}
2253 #[cfg(any(test, feature = "proptest"))]
2258 note
= "proptest strategies have moved to im::proptest"
2260 pub use crate::proptest
::vector
;
2268 use crate::proptest
::vector
;
2269 use ::proptest
::collection
::vec
;
2270 use ::proptest
::num
::{i32, usize}
;
2271 use ::proptest
::proptest
;
2274 fn macro_allows_trailing_comma() {
2275 let vec1
= vector
![1, 2, 3];
2276 let vec2
= vector
![1, 2, 3,];
2277 assert_eq
!(vec1
, vec2
);
2282 let mut vec
= vector
![0, 1, 2, 3, 4, 5];
2284 assert_eq
!(0, *vec
.get(0).unwrap());
2285 assert_eq
!(0, vec
[0]);
2289 fn large_vector_focus() {
2290 let input
= (0..100_000).collect
::<Vector
<_
>>();
2291 let vec
= input
.clone();
2292 let mut sum
: i64 = 0;
2293 let mut focus
= vec
.focus();
2294 for i
in 0..input
.len() {
2295 sum
+= *focus
.index(i
);
2297 let expected
: i64 = (0..100_000).sum();
2298 assert_eq
!(expected
, sum
);
2302 fn large_vector_focus_mut() {
2303 let input
= (0..100_000).collect
::<Vector
<_
>>();
2304 let mut vec
= input
.clone();
2306 let mut focus
= vec
.focus_mut();
2307 for i
in 0..input
.len() {
2308 let p
= focus
.index_mut(i
);
2312 let expected
: Vector
<i32> = input
.into_iter().map(|i
| i
+ 1).collect();
2313 assert_eq
!(expected
, vec
);
2318 let mut l
= Vector
::new();
2320 l
.append(Vector
::unit(i
));
2322 l
.append(Vector
::unit(4098));
2323 assert_eq
!(Some(&4097), l
.get(4097));
2324 assert_eq
!(Some(&4096), l
.get(4096));
2328 fn issue_55_back() {
2329 let mut l
= Vector
::unit(0);
2331 let mut tmp
= Vector
::unit(i
+ 1);
2335 assert_eq
!(Some(&4098), l
.get(1));
2336 assert_eq
!(Some(&4097), l
.get(2));
2342 fn issue_55_append() {
2343 let mut vec1
= (0..92).collect
::<Vector
<_
>>();
2344 let vec2
= (0..165).collect
::<Vector
<_
>>();
2350 let mut x
= Vector
::new();
2357 for &offset
in &[160, 163, 160] {
2363 // At this point middle contains three chunks of size 64, 64 and 1
2364 // respectively. Previously the next `push_back()` would append another
2365 // zero-sized chunk to middle even though there is enough space left.
2367 VectorInner
::Full(_
, ref tree
) => {
2368 assert_eq
!(129, tree
.middle
.len());
2369 assert_eq
!(3, tree
.middle
.number_of_children());
2371 _
=> unreachable
!(),
2375 VectorInner
::Full(_
, ref tree
) => {
2376 assert_eq
!(131, tree
.middle
.len());
2377 assert_eq
!(3, tree
.middle
.number_of_children())
2379 _
=> unreachable
!(),
2384 for _
in x
.iter() {}
2389 let mut l
= Vector
::unit(4100);
2390 for i
in (0..4099).rev() {
2391 let mut tmp
= Vector
::unit(i
);
2395 assert_eq
!(4100, l
.len());
2397 let tail
= l
.slice(1..len
);
2398 assert_eq
!(1, l
.len());
2399 assert_eq
!(4099, tail
.len());
2400 assert_eq
!(Some(&0), l
.get(0));
2401 assert_eq
!(Some(&1), tail
.get(0));
2405 fn issue_74_simple_size() {
2406 use crate::nodes
::rrb
::NODE_SIZE
;
2407 let mut x
= Vector
::new();
2408 for _
in 0..(CHUNK_SIZE
2411 + (2 * NODE_SIZE
) // middle: two full Entry::Nodes (4096 elements each)
2419 let middle_first_node_start
= CHUNK_SIZE
;
2420 let middle_second_node_start
= middle_first_node_start
+ NODE_SIZE
* CHUNK_SIZE
;
2421 // This reduces the size of the second node to 4095.
2422 x
.remove(middle_second_node_start
);
2423 // As outer_b is full, this will cause inner_b (length 64) to be pushed
2424 // to middle. The first element will be merged into the second node, the
2425 // remaining 63 elements will end up in a new node.
2428 VectorInner
::Full(_
, tree
) => {
2429 assert_eq
!(3, tree
.middle
.number_of_children());
2431 2 * NODE_SIZE
* CHUNK_SIZE
+ CHUNK_SIZE
- 1,
2435 _
=> unreachable
!(),
2441 let mut x
= Vector
::new();
2467 let mut v
= Vector
::new();
2469 for i
in 0..270_000 {
2473 while !v
.is_empty() {
2474 v
= v
.take(v
.len() - 1);
2479 fn issue_107_split_off_causes_overflow() {
2480 let mut vec
= (0..4289).collect
::<Vector
<_
>>();
2481 let mut control
= (0..4289).collect
::<Vec
<_
>>();
2484 while vec
.len() >= chunk
{
2485 vec
= vec
.split_off(chunk
);
2486 control
= control
.split_off(chunk
);
2487 assert_eq
!(vec
.len(), control
.len());
2488 assert_eq
!(control
, vec
.iter().cloned().collect
::<Vec
<_
>>());
2493 fn collect_crash() {
2494 let _vector
: Vector
<i32> = (0..5953).collect();
2495 // let _vector: Vector<i32> = (0..16384).collect();
2500 let vec
= (0..300).collect
::<Vector
<_
>>();
2501 let rev_vec
: Vector
<u32> = vec
.clone().into_iter().rev().collect();
2502 assert_eq
!(vec
.len(), rev_vec
.len());
2507 let smol
= std
::iter
::repeat(42).take(64).collect
::<Vector
<_
>>();
2508 let mut smol2
= smol
.clone();
2509 assert
!(smol
.ptr_eq(&smol2
));
2511 assert
!(!smol
.ptr_eq(&smol2
));
2513 let huge
= std
::iter
::repeat(42).take(65).collect
::<Vector
<_
>>();
2514 let mut huge2
= huge
.clone();
2515 assert
!(huge
.ptr_eq(&huge2
));
2517 assert
!(!huge
.ptr_eq(&huge2
));
2522 for len
in 32..256 {
2523 let input
= std
::iter
::repeat(42).take(len
).collect
::<Vector
<_
>>();
2524 let mut inp2
= input
.clone();
2525 assert
!(input
.ptr_eq(&inp2
));
2526 inp2
.set(len
- 1, 98);
2527 assert_ne
!(inp2
.get(len
- 1), input
.get(len
- 1));
2528 assert
!(!input
.ptr_eq(&inp2
));
2534 fn iter(ref vec
in vec(i32::ANY
, 0..1000)) {
2535 let seq
: Vector
<i32> = vec
.iter().cloned().collect
::<Vector
<_
>>();
2536 for (index
, item
) in seq
.iter().enumerate() {
2537 assert_eq
!(&vec
[index
], item
);
2539 assert_eq
!(vec
.len(), seq
.len());
2543 fn push_front_mut(ref input
in vec(i32::ANY
, 0..1000)) {
2544 let mut vector
= Vector
::new();
2545 for (count
, value
) in input
.iter().cloned().enumerate() {
2546 assert_eq
!(count
, vector
.len());
2547 vector
.push_front(value
);
2548 assert_eq
!(count
+ 1, vector
.len());
2550 let input2
= input
.iter().rev().cloned().collect
::<Vec
<_
>>();
2551 assert_eq
!(input2
, vector
.iter().cloned().collect
::<Vec
<_
>>());
2555 fn push_back_mut(ref input
in vec(i32::ANY
, 0..1000)) {
2556 let mut vector
= Vector
::new();
2557 for (count
, value
) in input
.iter().cloned().enumerate() {
2558 assert_eq
!(count
, vector
.len());
2559 vector
.push_back(value
);
2560 assert_eq
!(count
+ 1, vector
.len());
2562 assert_eq
!(input
, &vector
.iter().cloned().collect
::<Vec
<_
>>());
2566 fn pop_back_mut(ref input
in vec(i32::ANY
, 0..1000)) {
2567 let mut vector
= input
.iter().cloned().collect
::<Vector
<_
>>();
2568 assert_eq
!(input
.len(), vector
.len());
2569 for (index
, value
) in input
.iter().cloned().enumerate().rev() {
2570 match vector
.pop_back() {
2571 None
=> panic
!("vector emptied unexpectedly"),
2573 assert_eq
!(index
, vector
.len());
2574 assert_eq
!(value
, item
);
2578 assert_eq
!(0, vector
.len());
2582 fn pop_front_mut(ref input
in vec(i32::ANY
, 0..1000)) {
2583 let mut vector
= input
.iter().cloned().collect
::<Vector
<_
>>();
2584 assert_eq
!(input
.len(), vector
.len());
2585 for (index
, value
) in input
.iter().cloned().rev().enumerate().rev() {
2586 match vector
.pop_front() {
2587 None
=> panic
!("vector emptied unexpectedly"),
2589 assert_eq
!(index
, vector
.len());
2590 assert_eq
!(value
, item
);
2594 assert_eq
!(0, vector
.len());
2598 // fn push_and_pop(ref input in vec(i32::ANY, 0..1000)) {
2599 // let mut vector = Vector::new();
2600 // for (count, value) in input.iter().cloned().enumerate() {
2601 // assert_eq!(count, vector.len());
2602 // vector.push_back(value);
2603 // assert_eq!(count + 1, vector.len());
2605 // for (index, value) in input.iter().cloned().rev().enumerate().rev() {
2606 // match vector.pop_front() {
2607 // None => panic!("vector emptied unexpectedly"),
2609 // assert_eq!(index, vector.len());
2610 // assert_eq!(value, item);
2614 // assert_eq!(true, vector.is_empty());
2618 fn split(ref vec
in vec(i32::ANY
, 1..2000), split_pos
in usize::ANY
) {
2619 let split_index
= split_pos
% (vec
.len() + 1);
2620 let mut left
= vec
.iter().cloned().collect
::<Vector
<_
>>();
2621 let right
= left
.split_off(split_index
);
2622 assert_eq
!(left
.len(), split_index
);
2623 assert_eq
!(right
.len(), vec
.len() - split_index
);
2624 for (index
, item
) in left
.iter().enumerate() {
2625 assert_eq
!(& vec
[index
], item
);
2627 for (index
, item
) in right
.iter().enumerate() {
2628 assert_eq
!(&vec
[split_index
+ index
], item
);
2633 fn append(ref vec1
in vec(i32::ANY
, 0..1000), ref vec2
in vec(i32::ANY
, 0..1000)) {
2634 let mut seq1
= vec1
.iter().cloned().collect
::<Vector
<_
>>();
2635 let seq2
= vec2
.iter().cloned().collect
::<Vector
<_
>>();
2636 assert_eq
!(seq1
.len(), vec1
.len());
2637 assert_eq
!(seq2
.len(), vec2
.len());
2639 let mut vec
= vec1
.clone();
2641 assert_eq
!(seq1
.len(), vec
.len());
2642 for (index
, item
) in seq1
.into_iter().enumerate() {
2643 assert_eq
!(vec
[index
], item
);
2648 fn iter_mut(ref input
in vector(i32::ANY
, 0..10000)) {
2649 let mut vec
= input
.clone();
2651 for p
in vec
.iter_mut() {
2652 *p
= p
.overflowing_add(1).0;
2655 let expected
: Vector
<i32> = input
.clone().into_iter().map(|i
| i
.overflowing_add(1).0).collect();
2656 assert_eq
!(expected
, vec
);
2660 fn focus(ref input
in vector(i32::ANY
, 0..10000)) {
2661 let mut vec
= input
.clone();
2663 let mut focus
= vec
.focus_mut();
2664 for i
in 0..input
.len() {
2665 let p
= focus
.index_mut(i
);
2666 *p
= p
.overflowing_add(1).0;
2669 let expected
: Vector
<i32> = input
.clone().into_iter().map(|i
| i
.overflowing_add(1).0).collect();
2670 assert_eq
!(expected
, vec
);
2674 fn focus_mut_split(ref input
in vector(i32::ANY
, 0..10000)) {
2675 let mut vec
= input
.clone();
2677 fn split_down(focus
: FocusMut
<'_
, i32>) {
2678 let len
= focus
.len();
2681 *p
= p
.overflowing_add(1).0;
2684 let (left
, right
) = focus
.split_at(len
/ 2);
2690 split_down(vec
.focus_mut());
2692 let expected
: Vector
<i32> = input
.clone().into_iter().map(|i
| i
.overflowing_add(1).0).collect();
2693 assert_eq
!(expected
, vec
);
2697 fn chunks(ref input
in vector(i32::ANY
, 0..10000)) {
2698 let output
: Vector
<_
> = input
.leaves().flatten().cloned().collect();
2699 assert_eq
!(input
, &output
);
2700 let rev_in
: Vector
<_
> = input
.iter().rev().cloned().collect();
2701 let rev_out
: Vector
<_
> = input
.leaves().rev().map(|c
| c
.iter().rev()).flatten().cloned().collect();
2702 assert_eq
!(rev_in
, rev_out
);
2706 fn chunks_mut(ref mut input_src
in vector(i32::ANY
, 0..10000)) {
2707 let mut input
= input_src
.clone();
2708 #[allow(clippy::map_clone)]
2709 let output
: Vector
<_
> = input
.leaves_mut().flatten().map(|v
| *v
).collect();
2710 assert_eq
!(input
, output
);
2711 let rev_in
: Vector
<_
> = input
.iter().rev().cloned().collect();
2712 let rev_out
: Vector
<_
> = input
.leaves_mut().rev().map(|c
| c
.iter().rev()).flatten().cloned().collect();
2713 assert_eq
!(rev_in
, rev_out
);
2716 // The following two tests are very slow and there are unit tests above
2717 // which test for regression of issue #55. It would still be good to
2718 // run them occasionally.
2721 // fn issue55_back(count in 0..10000, slice_at in usize::ANY) {
2722 // let count = count as usize;
2723 // let slice_at = slice_at % count;
2724 // let mut l = Vector::unit(0);
2725 // for _ in 0..count {
2726 // let mut tmp = Vector::unit(0);
2730 // let len = l.len();
2731 // l.slice(slice_at..len);
2735 // fn issue55_fwd(count in 0..10000, slice_at in usize::ANY) {
2736 // let count = count as usize;
2737 // let slice_at = slice_at % count;
2738 // let mut l = Vector::new();
2739 // for i in 0..count {
2740 // l.append(Vector::unit(i));
2742 // assert_eq!(Some(&slice_at), l.get(slice_at));