diff options
Diffstat (limited to 'vendor/im-rc/src/vector/mod.rs')
| -rw-r--r-- | vendor/im-rc/src/vector/mod.rs | 2745 |
1 files changed, 2745 insertions, 0 deletions
diff --git a/vendor/im-rc/src/vector/mod.rs b/vendor/im-rc/src/vector/mod.rs new file mode 100644 index 000000000..a2ce0adf7 --- /dev/null +++ b/vendor/im-rc/src/vector/mod.rs @@ -0,0 +1,2745 @@ +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. + +//! A persistent vector. +//! +//! This is a sequence of elements in insertion order - if you need a +//! list of things, any kind of list of things, this is what you're +//! looking for. +//! +//! It's implemented as an [RRB vector][rrbpaper] with [smart +//! head/tail chunking][chunkedseq]. In performance terms, this means +//! that practically every operation is O(log n), except push/pop on +//! both sides, which will be O(1) amortised, and O(log n) in the +//! worst case. In practice, the push/pop operations will be +//! blindingly fast, nearly on par with the native +//! [`VecDeque`][VecDeque], and other operations will have decent, if +//! not high, performance, but they all have more or less the same +//! O(log n) complexity, so you don't need to keep their performance +//! characteristics in mind - everything, even splitting and merging, +//! is safe to use and never too slow. +//! +//! ## Performance Notes +//! +//! Because of the head/tail chunking technique, until you push a +//! number of items above double the tree's branching factor (that's +//! `self.len()` = 2 × *k* (where *k* = 64) = 128) on either side, the +//! data structure is still just a handful of arrays, not yet an RRB +//! tree, so you'll see performance and memory characteristics fairly +//! close to [`Vec`][Vec] or [`VecDeque`][VecDeque]. +//! +//! This means that the structure always preallocates four chunks of +//! size *k* (*k* being the tree's branching factor), equivalent to a +//! [`Vec`][Vec] with an initial capacity of 256. Beyond that, it will +//! allocate tree nodes of capacity *k* as needed. +//! +//! In addition, vectors start out as single chunks, and only expand into the +//! full data structure once you go past the chunk size. This makes them +//! perform identically to [`Vec`][Vec] at small sizes. +//! +//! [rrbpaper]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf +//! [chunkedseq]: http://deepsea.inria.fr/pasl/chunkedseq.pdf +//! [Vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html +//! [VecDeque]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html + +use std::borrow::Borrow; +use std::cmp::Ordering; +use std::fmt::{Debug, Error, Formatter}; +use std::hash::{Hash, Hasher}; +use std::iter::Sum; +use std::iter::{FromIterator, FusedIterator}; +use std::mem::{replace, swap}; +use std::ops::{Add, Index, IndexMut, RangeBounds}; + +use sized_chunks::InlineArray; + +use crate::nodes::chunk::{Chunk, CHUNK_SIZE}; +use crate::nodes::rrb::{Node, PopResult, PushResult, SplitResult}; +use crate::sort; +use crate::util::{clone_ref, swap_indices, to_range, Pool, PoolDefault, PoolRef, Ref, Side}; + +use self::VectorInner::{Full, Inline, Single}; + +mod focus; + +pub use self::focus::{Focus, FocusMut}; + +mod pool; +pub use self::pool::RRBPool; + +#[cfg(all(threadsafe, any(test, feature = "rayon")))] +pub mod rayon; + +/// Construct a vector from a sequence of elements. +/// +/// # Examples +/// +/// ``` +/// # #[macro_use] extern crate im_rc as im; +/// # use im::vector::Vector; +/// # fn main() { +/// assert_eq!( +/// vector![1, 2, 3], +/// Vector::from(vec![1, 2, 3]) +/// ); +/// # } +/// ``` +#[macro_export] +macro_rules! vector { + () => { $crate::vector::Vector::new() }; + + ( $($x:expr),* ) => {{ + let mut l = $crate::vector::Vector::new(); + $( + l.push_back($x); + )* + l + }}; + + ( $($x:expr ,)* ) => {{ + let mut l = $crate::vector::Vector::new(); + $( + l.push_back($x); + )* + l + }}; +} + +/// A persistent vector. +/// +/// This is a sequence of elements in insertion order - if you need a list of +/// things, any kind of list of things, this is what you're looking for. +/// +/// It's implemented as an [RRB vector][rrbpaper] with [smart head/tail +/// chunking][chunkedseq]. In performance terms, this means that practically +/// every operation is O(log n), except push/pop on both sides, which will be +/// O(1) amortised, and O(log n) in the worst case. In practice, the push/pop +/// operations will be blindingly fast, nearly on par with the native +/// [`VecDeque`][VecDeque], and other operations will have decent, if not high, +/// performance, but they all have more or less the same O(log n) complexity, so +/// you don't need to keep their performance characteristics in mind - +/// everything, even splitting and merging, is safe to use and never too slow. +/// +/// ## Performance Notes +/// +/// Because of the head/tail chunking technique, until you push a number of +/// items above double the tree's branching factor (that's `self.len()` = 2 × +/// *k* (where *k* = 64) = 128) on either side, the data structure is still just +/// a handful of arrays, not yet an RRB tree, so you'll see performance and +/// memory characteristics similar to [`Vec`][Vec] or [`VecDeque`][VecDeque]. +/// +/// This means that the structure always preallocates four chunks of size *k* +/// (*k* being the tree's branching factor), equivalent to a [`Vec`][Vec] with +/// an initial capacity of 256. Beyond that, it will allocate tree nodes of +/// capacity *k* as needed. +/// +/// In addition, vectors start out as single chunks, and only expand into the +/// full data structure once you go past the chunk size. This makes them +/// perform identically to [`Vec`][Vec] at small sizes. +/// +/// [rrbpaper]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf +/// [chunkedseq]: http://deepsea.inria.fr/pasl/chunkedseq.pdf +/// [Vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html +/// [VecDeque]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html +pub struct Vector<A> { + vector: VectorInner<A>, +} + +enum VectorInner<A> { + Inline(RRBPool<A>, InlineArray<A, Rrb<A>>), + Single(RRBPool<A>, PoolRef<Chunk<A>>), + Full(RRBPool<A>, Rrb<A>), +} + +#[doc(hidden)] +pub struct Rrb<A> { + length: usize, + middle_level: usize, + outer_f: PoolRef<Chunk<A>>, + inner_f: PoolRef<Chunk<A>>, + middle: Ref<Node<A>>, + inner_b: PoolRef<Chunk<A>>, + outer_b: PoolRef<Chunk<A>>, +} + +impl<A> Clone for Rrb<A> { + fn clone(&self) -> Self { + Rrb { + length: self.length, + middle_level: self.middle_level, + outer_f: self.outer_f.clone(), + inner_f: self.inner_f.clone(), + middle: self.middle.clone(), + inner_b: self.inner_b.clone(), + outer_b: self.outer_b.clone(), + } + } +} + +impl<A: Clone> Vector<A> { + /// Get a reference to the memory pool this `Vector` is using. + /// + /// Note that if you didn't specifically construct it with a pool, you'll + /// get back a reference to a pool of size 0. + #[cfg_attr(not(feature = "pool"), doc(hidden))] + pub fn pool(&self) -> &RRBPool<A> { + match self.vector { + Inline(ref pool, _) => pool, + Single(ref pool, _) => pool, + Full(ref pool, _) => pool, + } + } + + /// True if a vector is a full inline or single chunk, ie. must be promoted + /// to grow further. + fn needs_promotion(&self) -> bool { + match &self.vector { + Inline(_, chunk) if chunk.is_full() => true, + Single(_, chunk) if chunk.is_full() => true, + _ => false, + } + } + + /// Promote an inline to a single. + fn promote_inline(&mut self) { + if let Inline(pool, chunk) = &mut self.vector { + self.vector = Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into())); + } + } + + /// Promote a single to a full, with the single chunk becoming inner_f, or + /// promote an inline to a single. + fn promote_front(&mut self) { + self.vector = match &mut self.vector { + Inline(pool, chunk) => { + Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into())) + } + Single(pool, chunk) => { + let chunk = chunk.clone(); + Full( + pool.clone(), + Rrb { + length: chunk.len(), + middle_level: 0, + outer_f: PoolRef::default(&pool.value_pool), + inner_f: chunk, + middle: Ref::new(Node::new()), + inner_b: PoolRef::default(&pool.value_pool), + outer_b: PoolRef::default(&pool.value_pool), + }, + ) + } + Full(_, _) => return, + } + } + + /// Promote a single to a full, with the single chunk becoming inner_b, or + /// promote an inline to a single. + fn promote_back(&mut self) { + self.vector = match &mut self.vector { + Inline(pool, chunk) => { + Single(pool.clone(), PoolRef::new(&pool.value_pool, chunk.into())) + } + Single(pool, chunk) => { + let chunk = chunk.clone(); + Full( + pool.clone(), + Rrb { + length: chunk.len(), + middle_level: 0, + outer_f: PoolRef::default(&pool.value_pool), + inner_f: PoolRef::default(&pool.value_pool), + middle: Ref::new(Node::new()), + inner_b: chunk, + outer_b: PoolRef::default(&pool.value_pool), + }, + ) + } + Full(_, _) => return, + } + } + + /// Construct an empty vector. + #[must_use] + pub fn new() -> Self { + Self { + vector: Inline(RRBPool::default(), InlineArray::new()), + } + } + + /// Construct an empty vector using a specific memory pool. + #[cfg(feature = "pool")] + #[must_use] + pub fn with_pool(pool: &RRBPool<A>) -> Self { + Self { + vector: Inline(pool.clone(), InlineArray::new()), + } + } + + /// Get the length of a vector. + /// + /// Time: O(1) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// assert_eq!(5, vector![1, 2, 3, 4, 5].len()); + /// ``` + #[inline] + #[must_use] + pub fn len(&self) -> usize { + match &self.vector { + Inline(_, chunk) => chunk.len(), + Single(_, chunk) => chunk.len(), + Full(_, tree) => tree.length, + } + } + + /// Test whether a vector is empty. + /// + /// Time: O(1) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let vec = vector!["Joe", "Mike", "Robert"]; + /// assert_eq!(false, vec.is_empty()); + /// assert_eq!(true, Vector::<i32>::new().is_empty()); + /// ``` + #[inline] + #[must_use] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Test whether a vector is currently inlined. + /// + /// Vectors small enough that their contents could be stored entirely inside + /// the space of `std::mem::size_of::<Vector<A>>()` bytes are stored inline on + /// the stack instead of allocating any chunks. This method returns `true` if + /// this vector is currently inlined, or `false` if it currently has chunks allocated + /// on the heap. + /// + /// This may be useful in conjunction with [`ptr_eq()`][ptr_eq], which checks if + /// two vectors' heap allocations are the same, and thus will never return `true` + /// for inlined vectors. + /// + /// Time: O(1) + /// + /// [ptr_eq]: #method.ptr_eq + #[inline] + #[must_use] + pub fn is_inline(&self) -> bool { + matches!(&self.vector, Inline(_, _)) + } + + /// Test whether two vectors refer to the same content in memory. + /// + /// This uses the following rules to determine equality: + /// * If the two sides are references to the same vector, return true. + /// * If the two sides are single chunk vectors pointing to the same chunk, return true. + /// * If the two sides are full trees pointing to the same chunks, return true. + /// + /// This would return true if you're comparing a vector to itself, or + /// if you're comparing a vector to a fresh clone of itself. The exception to this is + /// if you've cloned an inline array (ie. an array with so few elements they can fit + /// inside the space a `Vector` allocates for its pointers, so there are no heap allocations + /// to compare). + /// + /// Time: O(1) + #[must_use] + pub fn ptr_eq(&self, other: &Self) -> bool { + fn cmp_chunk<A>(left: &PoolRef<Chunk<A>>, right: &PoolRef<Chunk<A>>) -> bool { + (left.is_empty() && right.is_empty()) || PoolRef::ptr_eq(left, right) + } + + if std::ptr::eq(self, other) { + return true; + } + + match (&self.vector, &other.vector) { + (Single(_, left), Single(_, right)) => cmp_chunk(left, right), + (Full(_, left), Full(_, right)) => { + cmp_chunk(&left.outer_f, &right.outer_f) + && cmp_chunk(&left.inner_f, &right.inner_f) + && cmp_chunk(&left.inner_b, &right.inner_b) + && cmp_chunk(&left.outer_b, &right.outer_b) + && ((left.middle.is_empty() && right.middle.is_empty()) + || Ref::ptr_eq(&left.middle, &right.middle)) + } + _ => false, + } + } + + /// Get an iterator over a vector. + /// + /// Time: O(1) + #[inline] + #[must_use] + pub fn iter(&self) -> Iter<'_, A> { + Iter::new(self) + } + + /// Get a mutable iterator over a vector. + /// + /// Time: O(1) + #[inline] + #[must_use] + pub fn iter_mut(&mut self) -> IterMut<'_, A> { + IterMut::new(self) + } + + /// Get an iterator over the leaf nodes of a vector. + /// + /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the + /// RRB tree. These are useful for efficient parallelisation of work on + /// the vector, but should not be used for basic iteration. + /// + /// Time: O(1) + /// + /// [Chunk]: ../chunk/struct.Chunk.html + #[inline] + #[must_use] + pub fn leaves(&self) -> Chunks<'_, A> { + Chunks::new(self) + } + + /// Get a mutable iterator over the leaf nodes of a vector. + // + /// This returns an iterator over the [`Chunk`s][Chunk] at the leaves of the + /// RRB tree. These are useful for efficient parallelisation of work on + /// the vector, but should not be used for basic iteration. + /// + /// Time: O(1) + /// + /// [Chunk]: ../chunk/struct.Chunk.html + #[inline] + #[must_use] + pub fn leaves_mut(&mut self) -> ChunksMut<'_, A> { + ChunksMut::new(self) + } + + /// Construct a [`Focus`][Focus] for a vector. + /// + /// Time: O(1) + /// + /// [Focus]: enum.Focus.html + #[inline] + #[must_use] + pub fn focus(&self) -> Focus<'_, A> { + Focus::new(self) + } + + /// Construct a [`FocusMut`][FocusMut] for a vector. + /// + /// Time: O(1) + /// + /// [FocusMut]: enum.FocusMut.html + #[inline] + #[must_use] + pub fn focus_mut(&mut self) -> FocusMut<'_, A> { + FocusMut::new(self) + } + + /// Get a reference to the value at index `index` in a vector. + /// + /// Returns `None` if the index is out of bounds. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let vec = vector!["Joe", "Mike", "Robert"]; + /// assert_eq!(Some(&"Robert"), vec.get(2)); + /// assert_eq!(None, vec.get(5)); + /// ``` + #[must_use] + pub fn get(&self, index: usize) -> Option<&A> { + if index >= self.len() { + return None; + } + + match &self.vector { + Inline(_, chunk) => chunk.get(index), + Single(_, chunk) => chunk.get(index), + Full(_, tree) => { + let mut local_index = index; + + if local_index < tree.outer_f.len() { + return Some(&tree.outer_f[local_index]); + } + local_index -= tree.outer_f.len(); + + if local_index < tree.inner_f.len() { + return Some(&tree.inner_f[local_index]); + } + local_index -= tree.inner_f.len(); + + if local_index < tree.middle.len() { + return Some(tree.middle.index(tree.middle_level, local_index)); + } + local_index -= tree.middle.len(); + + if local_index < tree.inner_b.len() { + return Some(&tree.inner_b[local_index]); + } + local_index -= tree.inner_b.len(); + + Some(&tree.outer_b[local_index]) + } + } + } + + /// Get a mutable reference to the value at index `index` in a + /// vector. + /// + /// Returns `None` if the index is out of bounds. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector!["Joe", "Mike", "Robert"]; + /// { + /// let robert = vec.get_mut(2).unwrap(); + /// assert_eq!(&mut "Robert", robert); + /// *robert = "Bjarne"; + /// } + /// assert_eq!(vector!["Joe", "Mike", "Bjarne"], vec); + /// ``` + #[must_use] + pub fn get_mut(&mut self, index: usize) -> Option<&mut A> { + if index >= self.len() { + return None; + } + + match &mut self.vector { + Inline(_, chunk) => chunk.get_mut(index), + Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).get_mut(index), + Full(pool, tree) => { + let mut local_index = index; + + if local_index < tree.outer_f.len() { + let outer_f = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f); + return Some(&mut outer_f[local_index]); + } + local_index -= tree.outer_f.len(); + + if local_index < tree.inner_f.len() { + let inner_f = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f); + return Some(&mut inner_f[local_index]); + } + local_index -= tree.inner_f.len(); + + if local_index < tree.middle.len() { + let middle = Ref::make_mut(&mut tree.middle); + return Some(middle.index_mut(pool, tree.middle_level, local_index)); + } + local_index -= tree.middle.len(); + + if local_index < tree.inner_b.len() { + let inner_b = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b); + return Some(&mut inner_b[local_index]); + } + local_index -= tree.inner_b.len(); + + let outer_b = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b); + Some(&mut outer_b[local_index]) + } + } + } + + /// Get the first element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// Time: O(log n) + #[inline] + #[must_use] + pub fn front(&self) -> Option<&A> { + self.get(0) + } + + /// Get a mutable reference to the first element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// Time: O(log n) + #[inline] + #[must_use] + pub fn front_mut(&mut self) -> Option<&mut A> { + self.get_mut(0) + } + + /// Get the first element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// This is an alias for the [`front`][front] method. + /// + /// Time: O(log n) + /// + /// [front]: #method.front + #[inline] + #[must_use] + pub fn head(&self) -> Option<&A> { + self.get(0) + } + + /// Get the last element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// Time: O(log n) + #[must_use] + pub fn back(&self) -> Option<&A> { + if self.is_empty() { + None + } else { + self.get(self.len() - 1) + } + } + + /// Get a mutable reference to the last element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// Time: O(log n) + #[must_use] + pub fn back_mut(&mut self) -> Option<&mut A> { + if self.is_empty() { + None + } else { + let len = self.len(); + self.get_mut(len - 1) + } + } + + /// Get the last element of a vector. + /// + /// If the vector is empty, `None` is returned. + /// + /// This is an alias for the [`back`][back] method. + /// + /// Time: O(log n) + /// + /// [back]: #method.back + #[inline] + #[must_use] + pub fn last(&self) -> Option<&A> { + self.back() + } + + /// Get the index of a given element in the vector. + /// + /// Searches the vector for the first occurrence of a given value, + /// and returns the index of the value if it's there. Otherwise, + /// it returns `None`. + /// + /// Time: O(n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3, 4, 5]; + /// assert_eq!(Some(2), vec.index_of(&3)); + /// assert_eq!(None, vec.index_of(&31337)); + /// ``` + #[must_use] + pub fn index_of(&self, value: &A) -> Option<usize> + where + A: PartialEq, + { + for (index, item) in self.iter().enumerate() { + if value == item { + return Some(index); + } + } + None + } + + /// Test if a given element is in the vector. + /// + /// Searches the vector for the first occurrence of a given value, + /// and returns `true` if it's there. If it's nowhere to be found + /// in the vector, it returns `false`. + /// + /// Time: O(n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3, 4, 5]; + /// assert_eq!(true, vec.contains(&3)); + /// assert_eq!(false, vec.contains(&31337)); + /// ``` + #[inline] + #[must_use] + pub fn contains(&self, value: &A) -> bool + where + A: PartialEq, + { + self.index_of(value).is_some() + } + + /// Discard all elements from the vector. + /// + /// This leaves you with an empty vector, and all elements that + /// were previously inside it are dropped. + /// + /// Time: O(n) + pub fn clear(&mut self) { + if !self.is_empty() { + self.vector = Inline(self.pool().clone(), InlineArray::new()); + } + } + + /// Binary search a sorted vector for a given element using a comparator + /// function. + /// + /// Assumes the vector has already been sorted using the same comparator + /// function, eg. by using [`sort_by`][sort_by]. + /// + /// If the value is found, it returns `Ok(index)` where `index` is the index + /// of the element. If the value isn't found, it returns `Err(index)` where + /// `index` is the index at which the element would need to be inserted to + /// maintain sorted order. + /// + /// Time: O(log n) + /// + /// [sort_by]: #method.sort_by + pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> + where + F: FnMut(&A) -> Ordering, + { + let mut size = self.len(); + if size == 0 { + return Err(0); + } + let mut base = 0; + while size > 1 { + let half = size / 2; + let mid = base + half; + base = match f(&self[mid]) { + Ordering::Greater => base, + _ => mid, + }; + size -= half; + } + match f(&self[base]) { + Ordering::Equal => Ok(base), + Ordering::Greater => Err(base), + Ordering::Less => Err(base + 1), + } + } + + /// Binary search a sorted vector for a given element. + /// + /// If the value is found, it returns `Ok(index)` where `index` is the index + /// of the element. If the value isn't found, it returns `Err(index)` where + /// `index` is the index at which the element would need to be inserted to + /// maintain sorted order. + /// + /// Time: O(log n) + pub fn binary_search(&self, value: &A) -> Result<usize, usize> + where + A: Ord, + { + self.binary_search_by(|e| e.cmp(value)) + } + + /// Binary search a sorted vector for a given element with a key extract + /// function. + /// + /// Assumes the vector has already been sorted using the same key extract + /// function, eg. by using [`sort_by_key`][sort_by_key]. + /// + /// If the value is found, it returns `Ok(index)` where `index` is the index + /// of the element. If the value isn't found, it returns `Err(index)` where + /// `index` is the index at which the element would need to be inserted to + /// maintain sorted order. + /// + /// Time: O(log n) + /// + /// [sort_by_key]: #method.sort_by_key + pub fn binary_search_by_key<B, F>(&self, b: &B, mut f: F) -> Result<usize, usize> + where + F: FnMut(&A) -> B, + B: Ord, + { + self.binary_search_by(|k| f(k).cmp(b)) + } +} + +impl<A: Clone> Vector<A> { + /// Construct a vector with a single value. + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let vec = Vector::unit(1337); + /// assert_eq!(1, vec.len()); + /// assert_eq!( + /// vec.get(0), + /// Some(&1337) + /// ); + /// ``` + #[inline] + #[must_use] + pub fn unit(a: A) -> Self { + let pool = RRBPool::default(); + if InlineArray::<A, Rrb<A>>::CAPACITY > 0 { + let mut array = InlineArray::new(); + array.push(a); + Self { + vector: Inline(pool, array), + } + } else { + let chunk = PoolRef::new(&pool.value_pool, Chunk::unit(a)); + Self { + vector: Single(pool, chunk), + } + } + } + + /// Create a new vector with the value at index `index` updated. + /// + /// Panics if the index is out of bounds. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3]; + /// assert_eq!(vector![1, 5, 3], vec.update(1, 5)); + /// ``` + #[must_use] + pub fn update(&self, index: usize, value: A) -> Self { + let mut out = self.clone(); + out[index] = value; + out + } + + /// Update the value at index `index` in a vector. + /// + /// Returns the previous value at the index. + /// + /// Panics if the index is out of bounds. + /// + /// Time: O(log n) + #[inline] + pub fn set(&mut self, index: usize, value: A) -> A { + replace(&mut self[index], value) + } + + /// Swap the elements at indices `i` and `j`. + /// + /// Time: O(log n) + pub fn swap(&mut self, i: usize, j: usize) { + swap_indices(self, i, j) + } + + /// Push a value to the front of a vector. + /// + /// Time: O(1)* + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![5, 6, 7]; + /// vec.push_front(4); + /// assert_eq!(vector![4, 5, 6, 7], vec); + /// ``` + pub fn push_front(&mut self, value: A) { + if self.needs_promotion() { + self.promote_back(); + } + match &mut self.vector { + Inline(_, chunk) => { + chunk.insert(0, value); + } + Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).push_front(value), + Full(pool, tree) => tree.push_front(pool, value), + } + } + + /// Push a value to the back of a vector. + /// + /// Time: O(1)* + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3]; + /// vec.push_back(4); + /// assert_eq!(vector![1, 2, 3, 4], vec); + /// ``` + pub fn push_back(&mut self, value: A) { + if self.needs_promotion() { + self.promote_front(); + } + match &mut self.vector { + Inline(_, chunk) => { + chunk.push(value); + } + Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).push_back(value), + Full(pool, tree) => tree.push_back(pool, value), + } + } + + /// Remove the first element from a vector and return it. + /// + /// Time: O(1)* + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3]; + /// assert_eq!(Some(1), vec.pop_front()); + /// assert_eq!(vector![2, 3], vec); + /// ``` + pub fn pop_front(&mut self) -> Option<A> { + if self.is_empty() { + None + } else { + match &mut self.vector { + Inline(_, chunk) => chunk.remove(0), + Single(pool, chunk) => Some(PoolRef::make_mut(&pool.value_pool, chunk).pop_front()), + Full(pool, tree) => tree.pop_front(pool), + } + } + } + + /// Remove the last element from a vector and return it. + /// + /// Time: O(1)* + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::Vector; + /// let mut vec = vector![1, 2, 3]; + /// assert_eq!(Some(3), vec.pop_back()); + /// assert_eq!(vector![1, 2], vec); + /// ``` + pub fn pop_back(&mut self) -> Option<A> { + if self.is_empty() { + None + } else { + match &mut self.vector { + Inline(_, chunk) => chunk.pop(), + Single(pool, chunk) => Some(PoolRef::make_mut(&pool.value_pool, chunk).pop_back()), + Full(pool, tree) => tree.pop_back(pool), + } + } + } + + /// Append the vector `other` to the end of the current vector. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut vec = vector![1, 2, 3]; + /// vec.append(vector![7, 8, 9]); + /// assert_eq!(vector![1, 2, 3, 7, 8, 9], vec); + /// ``` + pub fn append(&mut self, mut other: Self) { + if other.is_empty() { + return; + } + + if self.is_empty() { + *self = other; + return; + } + + self.promote_inline(); + other.promote_inline(); + + let total_length = self + .len() + .checked_add(other.len()) + .expect("Vector length overflow"); + + match &mut self.vector { + Inline(_, _) => unreachable!("inline vecs should have been promoted"), + Single(pool, left) => { + match &mut other.vector { + Inline(_, _) => unreachable!("inline vecs should have been promoted"), + // If both are single chunks and left has room for right: directly + // memcpy right into left + Single(_, ref mut right) if total_length <= CHUNK_SIZE => { + PoolRef::make_mut(&pool.value_pool, left) + .append(PoolRef::make_mut(&pool.value_pool, right)); + return; + } + // If only left is a single chunk and has room for right: push + // right's elements into left + _ if total_length <= CHUNK_SIZE => { + while let Some(value) = other.pop_front() { + PoolRef::make_mut(&pool.value_pool, left).push_back(value); + } + return; + } + _ => {} + } + } + Full(pool, left) => { + if let Full(_, mut right) = other.vector { + // If left and right are trees with empty middles, left has no back + // buffers, and right has no front buffers: copy right's back + // buffers over to left + if left.middle.is_empty() + && right.middle.is_empty() + && left.outer_b.is_empty() + && left.inner_b.is_empty() + && right.outer_f.is_empty() + && right.inner_f.is_empty() + { + left.inner_b = right.inner_b; + left.outer_b = right.outer_b; + left.length = total_length; + return; + } + // If left and right are trees with empty middles and left's buffers + // can fit right's buffers: push right's elements onto left + if left.middle.is_empty() + && right.middle.is_empty() + && total_length <= CHUNK_SIZE * 4 + { + while let Some(value) = right.pop_front(pool) { + left.push_back(pool, value); + } + return; + } + // Both are full and big: do the full RRB join + let inner_b1 = left.inner_b.clone(); + left.push_middle(pool, Side::Right, inner_b1); + let outer_b1 = left.outer_b.clone(); + left.push_middle(pool, Side::Right, outer_b1); + let inner_f2 = right.inner_f.clone(); + right.push_middle(pool, Side::Left, inner_f2); + let outer_f2 = right.outer_f.clone(); + right.push_middle(pool, Side::Left, outer_f2); + + let mut middle1 = clone_ref(replace(&mut left.middle, Ref::from(Node::new()))); + let mut middle2 = clone_ref(right.middle); + let normalised_middle = match left.middle_level.cmp(&right.middle_level) { + Ordering::Greater => { + middle2 = middle2.elevate(pool, left.middle_level - right.middle_level); + left.middle_level + } + Ordering::Less => { + middle1 = middle1.elevate(pool, right.middle_level - left.middle_level); + right.middle_level + } + Ordering::Equal => left.middle_level, + }; + left.middle = Ref::new(Node::merge(pool, middle1, middle2, normalised_middle)); + left.middle_level = normalised_middle + 1; + + left.inner_b = right.inner_b; + left.outer_b = right.outer_b; + left.length = total_length; + left.prune(); + return; + } + } + } + // No optimisations available, and either left, right or both are + // single: promote both to full and retry + self.promote_front(); + other.promote_back(); + self.append(other) + } + + /// Retain only the elements specified by the predicate. + /// + /// Remove all elements for which the provided function `f` + /// returns false from the vector. + /// + /// Time: O(n) + pub fn retain<F>(&mut self, mut f: F) + where + F: FnMut(&A) -> bool, + { + let len = self.len(); + let mut del = 0; + { + let mut focus = self.focus_mut(); + for i in 0..len { + if !f(focus.index(i)) { + del += 1; + } else if del > 0 { + focus.swap(i - del, i); + } + } + } + if del > 0 { + self.split_off(len - del); + } + } + + /// Split a vector at a given index. + /// + /// Split a vector at a given index, consuming the vector and + /// returning a pair of the left hand side and the right hand side + /// of the split. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut vec = vector![1, 2, 3, 7, 8, 9]; + /// let (left, right) = vec.split_at(3); + /// assert_eq!(vector![1, 2, 3], left); + /// assert_eq!(vector![7, 8, 9], right); + /// ``` + pub fn split_at(mut self, index: usize) -> (Self, Self) { + let right = self.split_off(index); + (self, right) + } + + /// Split a vector at a given index. + /// + /// Split a vector at a given index, leaving the left hand side in + /// the current vector and returning a new vector containing the + /// right hand side. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut left = vector![1, 2, 3, 7, 8, 9]; + /// let right = left.split_off(3); + /// assert_eq!(vector![1, 2, 3], left); + /// assert_eq!(vector![7, 8, 9], right); + /// ``` + pub fn split_off(&mut self, index: usize) -> Self { + assert!(index <= self.len()); + + match &mut self.vector { + Inline(pool, chunk) => Self { + vector: Inline(pool.clone(), chunk.split_off(index)), + }, + Single(pool, chunk) => Self { + vector: Single( + pool.clone(), + PoolRef::new( + &pool.value_pool, + PoolRef::make_mut(&pool.value_pool, chunk).split_off(index), + ), + ), + }, + Full(pool, tree) => { + let mut local_index = index; + + if local_index < tree.outer_f.len() { + let of2 = PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f) + .split_off(local_index); + let right = Rrb { + length: tree.length - index, + middle_level: tree.middle_level, + outer_f: PoolRef::new(&pool.value_pool, of2), + inner_f: replace_pool_def(&pool.value_pool, &mut tree.inner_f), + middle: std::mem::take(&mut tree.middle), + inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b), + outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b), + }; + tree.length = index; + tree.middle_level = 0; + return Self { + vector: Full(pool.clone(), right), + }; + } + + local_index -= tree.outer_f.len(); + + if local_index < tree.inner_f.len() { + let if2 = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f) + .split_off(local_index); + let right = Rrb { + length: tree.length - index, + middle_level: tree.middle_level, + outer_f: PoolRef::new(&pool.value_pool, if2), + inner_f: PoolRef::<Chunk<A>>::default(&pool.value_pool), + middle: std::mem::take(&mut tree.middle), + inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b), + outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b), + }; + tree.length = index; + tree.middle_level = 0; + swap(&mut tree.outer_b, &mut tree.inner_f); + return Self { + vector: Full(pool.clone(), right), + }; + } + + local_index -= tree.inner_f.len(); + + if local_index < tree.middle.len() { + let mut right_middle = tree.middle.clone(); + let (c1, c2) = { + let m1 = Ref::make_mut(&mut tree.middle); + let m2 = Ref::make_mut(&mut right_middle); + match m1.split(pool, tree.middle_level, Side::Right, local_index) { + SplitResult::Dropped(_) => (), + SplitResult::OutOfBounds => unreachable!(), + }; + match m2.split(pool, tree.middle_level, Side::Left, local_index) { + SplitResult::Dropped(_) => (), + SplitResult::OutOfBounds => unreachable!(), + }; + let c1 = match m1.pop_chunk(pool, tree.middle_level, Side::Right) { + PopResult::Empty => PoolRef::default(&pool.value_pool), + PopResult::Done(chunk) => chunk, + PopResult::Drained(chunk) => { + m1.clear_node(); + chunk + } + }; + let c2 = match m2.pop_chunk(pool, tree.middle_level, Side::Left) { + PopResult::Empty => PoolRef::default(&pool.value_pool), + PopResult::Done(chunk) => chunk, + PopResult::Drained(chunk) => { + m2.clear_node(); + chunk + } + }; + (c1, c2) + }; + let mut right = Rrb { + length: tree.length - index, + middle_level: tree.middle_level, + outer_f: c2, + inner_f: PoolRef::<Chunk<A>>::default(&pool.value_pool), + middle: right_middle, + inner_b: replace_pool_def(&pool.value_pool, &mut tree.inner_b), + outer_b: replace(&mut tree.outer_b, c1), + }; + tree.length = index; + tree.prune(); + right.prune(); + return Self { + vector: Full(pool.clone(), right), + }; + } + + local_index -= tree.middle.len(); + + if local_index < tree.inner_b.len() { + let ib2 = PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b) + .split_off(local_index); + let right = Rrb { + length: tree.length - index, + outer_b: replace_pool_def(&pool.value_pool, &mut tree.outer_b), + outer_f: PoolRef::new(&pool.value_pool, ib2), + ..Rrb::new(pool) + }; + tree.length = index; + swap(&mut tree.outer_b, &mut tree.inner_b); + return Self { + vector: Full(pool.clone(), right), + }; + } + + local_index -= tree.inner_b.len(); + + let ob2 = + PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b).split_off(local_index); + tree.length = index; + Self { + vector: Single(pool.clone(), PoolRef::new(&pool.value_pool, ob2)), + } + } + } + } + + /// Construct a vector with `count` elements removed from the + /// start of the current vector. + /// + /// Time: O(log n) + #[must_use] + pub fn skip(&self, count: usize) -> Self { + // FIXME can be made more efficient by dropping the unwanted side without constructing it + self.clone().split_off(count) + } + + /// Construct a vector of the first `count` elements from the + /// current vector. + /// + /// Time: O(log n) + #[must_use] + pub fn take(&self, count: usize) -> Self { + // FIXME can be made more efficient by dropping the unwanted side without constructing it + let mut left = self.clone(); + left.split_off(count); + left + } + + /// Truncate a vector to the given size. + /// + /// Discards all elements in the vector beyond the given length. + /// + /// Panics if the new length is greater than the current length. + /// + /// Time: O(log n) + pub fn truncate(&mut self, len: usize) { + // FIXME can be made more efficient by dropping the unwanted side without constructing it + self.split_off(len); + } + + /// Extract a slice from a vector. + /// + /// Remove the elements from `start_index` until `end_index` in + /// the current vector and return the removed slice as a new + /// vector. + /// + /// Time: O(log n) + pub fn slice<R>(&mut self, range: R) -> Self + where + R: RangeBounds<usize>, + { + let r = to_range(&range, self.len()); + if r.start >= r.end || r.start >= self.len() { + return Vector::new(); + } + let mut middle = self.split_off(r.start); + let right = middle.split_off(r.end - r.start); + self.append(right); + middle + } + + /// Insert an element into a vector. + /// + /// Insert an element at position `index`, shifting all elements + /// after it to the right. + /// + /// ## Performance Note + /// + /// While `push_front` and `push_back` are heavily optimised + /// operations, `insert` in the middle of a vector requires a + /// split, a push, and an append. Thus, if you want to insert + /// many elements at the same location, instead of `insert`ing + /// them one by one, you should rather create a new vector + /// containing the elements to insert, split the vector at the + /// insertion point, and append the left hand, the new vector and + /// the right hand in order. + /// + /// Time: O(log n) + pub fn insert(&mut self, index: usize, value: A) { + if index == 0 { + return self.push_front(value); + } + if index == self.len() { + return self.push_back(value); + } + assert!(index < self.len()); + if if let Inline(_, chunk) = &self.vector { + chunk.is_full() + } else { + false + } { + self.promote_inline(); + } + match &mut self.vector { + Inline(_, chunk) => { + chunk.insert(index, value); + } + Single(pool, chunk) if chunk.len() < CHUNK_SIZE => { + PoolRef::make_mut(&pool.value_pool, chunk).insert(index, value) + } + // TODO a lot of optimisations still possible here + _ => { + let right = self.split_off(index); + self.push_back(value); + self.append(right); + } + } + } + + /// Remove an element from a vector. + /// + /// Remove the element from position 'index', shifting all + /// elements after it to the left, and return the removed element. + /// + /// ## Performance Note + /// + /// While `pop_front` and `pop_back` are heavily optimised + /// operations, `remove` in the middle of a vector requires a + /// split, a pop, and an append. Thus, if you want to remove many + /// elements from the same location, instead of `remove`ing them + /// one by one, it is much better to use [`slice`][slice]. + /// + /// Time: O(log n) + /// + /// [slice]: #method.slice + pub fn remove(&mut self, index: usize) -> A { + assert!(index < self.len()); + match &mut self.vector { + Inline(_, chunk) => chunk.remove(index).unwrap(), + Single(pool, chunk) => PoolRef::make_mut(&pool.value_pool, chunk).remove(index), + _ => { + if index == 0 { + return self.pop_front().unwrap(); + } + if index == self.len() - 1 { + return self.pop_back().unwrap(); + } + // TODO a lot of optimisations still possible here + let mut right = self.split_off(index); + let value = right.pop_front().unwrap(); + self.append(right); + value + } + } + } + + /// Insert an element into a sorted vector. + /// + /// Insert an element into a vector in sorted order, assuming the vector is + /// already in sorted order. + /// + /// Time: O(log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut vec = vector![1, 2, 3, 7, 8, 9]; + /// vec.insert_ord(5); + /// assert_eq!(vector![1, 2, 3, 5, 7, 8, 9], vec); + /// ``` + pub fn insert_ord(&mut self, item: A) + where + A: Ord, + { + match self.binary_search(&item) { + Ok(index) => self.insert(index, item), + Err(index) => self.insert(index, item), + } + } + + /// Sort a vector. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut vec = vector![3, 2, 5, 4, 1]; + /// vec.sort(); + /// assert_eq!(vector![1, 2, 3, 4, 5], vec); + /// ``` + pub fn sort(&mut self) + where + A: Ord, + { + self.sort_by(Ord::cmp) + } + + /// Sort a vector using a comparator function. + /// + /// Time: O(n log n) + /// + /// # Examples + /// + /// ``` + /// # #[macro_use] extern crate im_rc as im; + /// # use im::vector::Vector; + /// let mut vec = vector![3, 2, 5, 4, 1]; + /// vec.sort_by(|left, right| left.cmp(right)); + /// assert_eq!(vector![1, 2, 3, 4, 5], vec); + /// ``` + pub fn sort_by<F>(&mut self, cmp: F) + where + F: Fn(&A, &A) -> Ordering, + { + let len = self.len(); + if len > 1 { + sort::quicksort(self.focus_mut(), &cmp); + } + } + + /// Verify the internal consistency of a vector. + /// + /// This method walks the RRB tree making up the current `Vector` + /// (if it has one) and verifies that all the invariants hold. + /// If something is wrong, it will panic. + /// + /// This method requires the `debug` feature flag. + #[cfg(any(test, feature = "debug"))] + pub fn assert_invariants(&self) { + if let Full(_, ref tree) = self.vector { + tree.assert_invariants(); + } + } +} + +// Implementation details + +impl<A: Clone> Rrb<A> { + fn new(pool: &RRBPool<A>) -> Self { + Rrb { + length: 0, + middle_level: 0, + outer_f: PoolRef::default(&pool.value_pool), + inner_f: PoolRef::default(&pool.value_pool), + middle: Ref::new(Node::new()), + inner_b: PoolRef::default(&pool.value_pool), + outer_b: PoolRef::default(&pool.value_pool), + } + } + + #[cfg(any(test, feature = "debug"))] + fn assert_invariants(&self) { + let ml = self.middle.assert_invariants(self.middle_level); + assert_eq!( + self.length, + self.outer_f.len() + self.inner_f.len() + ml + self.inner_b.len() + self.outer_b.len() + ); + } + + fn prune(&mut self) { + if self.middle.is_empty() { + self.middle = Ref::new(Node::new()); + self.middle_level = 0; + } else { + while self.middle_level > 0 && self.middle.is_single() { + // FIXME could be optimised, cloning the node is expensive + self.middle = Ref::new(self.middle.first_child().clone()); + self.middle_level -= 1; + } + } + } + + fn pop_front(&mut self, pool: &RRBPool<A>) -> Option<A> { + if self.length == 0 { + return None; + } + if self.outer_f.is_empty() { + if self.inner_f.is_empty() { + if self.middle.is_empty() { + if self.inner_b.is_empty() { + swap(&mut self.outer_f, &mut self.outer_b); + } else { + swap(&mut self.outer_f, &mut self.inner_b); + } + } else { + self.outer_f = self.pop_middle(pool, Side::Left).unwrap(); + } + } else { + swap(&mut self.outer_f, &mut self.inner_f); + } + } + self.length -= 1; + let outer_f = PoolRef::make_mut(&pool.value_pool, &mut self.outer_f); + Some(outer_f.pop_front()) + } + + fn pop_back(&mut self, pool: &RRBPool<A>) -> Option<A> { + if self.length == 0 { + return None; + } + if self.outer_b.is_empty() { + if self.inner_b.is_empty() { + if self.middle.is_empty() { + if self.inner_f.is_empty() { + swap(&mut self.outer_b, &mut self.outer_f); + } else { + swap(&mut self.outer_b, &mut self.inner_f); + } + } else { + self.outer_b = self.pop_middle(pool, Side::Right).unwrap(); + } + } else { + swap(&mut self.outer_b, &mut self.inner_b); + } + } + self.length -= 1; + let outer_b = PoolRef::make_mut(&pool.value_pool, &mut self.outer_b); + Some(outer_b.pop_back()) + } + + fn push_front(&mut self, pool: &RRBPool<A>, value: A) { + if self.outer_f.is_full() { + swap(&mut self.outer_f, &mut self.inner_f); + if !self.outer_f.is_empty() { + let mut chunk = PoolRef::new(&pool.value_pool, Chunk::new()); + swap(&mut chunk, &mut self.outer_f); + self.push_middle(pool, Side::Left, chunk); + } + } + self.length = self.length.checked_add(1).expect("Vector length overflow"); + let outer_f = PoolRef::make_mut(&pool.value_pool, &mut self.outer_f); + outer_f.push_front(value) + } + + fn push_back(&mut self, pool: &RRBPool<A>, value: A) { + if self.outer_b.is_full() { + swap(&mut self.outer_b, &mut self.inner_b); + if !self.outer_b.is_empty() { + let mut chunk = PoolRef::new(&pool.value_pool, Chunk::new()); + swap(&mut chunk, &mut self.outer_b); + self.push_middle(pool, Side::Right, chunk); + } + } + self.length = self.length.checked_add(1).expect("Vector length overflow"); + let outer_b = PoolRef::make_mut(&pool.value_pool, &mut self.outer_b); + outer_b.push_back(value) + } + + fn push_middle(&mut self, pool: &RRBPool<A>, side: Side, chunk: PoolRef<Chunk<A>>) { + if chunk.is_empty() { + return; + } + let new_middle = { + let middle = Ref::make_mut(&mut self.middle); + match middle.push_chunk(pool, self.middle_level, side, chunk) { + PushResult::Done => return, + PushResult::Full(chunk, _num_drained) => Ref::from({ + match side { + Side::Left => Node::from_chunk(pool, self.middle_level, chunk) + .join_branches(pool, middle.clone(), self.middle_level), + Side::Right => middle.clone().join_branches( + pool, + Node::from_chunk(pool, self.middle_level, chunk), + self.middle_level, + ), + } + }), + } + }; + self.middle_level += 1; + self.middle = new_middle; + } + + fn pop_middle(&mut self, pool: &RRBPool<A>, side: Side) -> Option<PoolRef<Chunk<A>>> { + let chunk = { + let middle = Ref::make_mut(&mut self.middle); + match middle.pop_chunk(pool, self.middle_level, side) { + PopResult::Empty => return None, + PopResult::Done(chunk) => chunk, + PopResult::Drained(chunk) => { + middle.clear_node(); + self.middle_level = 0; + chunk + } + } + }; + Some(chunk) + } +} + +#[inline] +fn replace_pool_def<A: PoolDefault>(pool: &Pool<A>, dest: &mut PoolRef<A>) -> PoolRef<A> { + replace(dest, PoolRef::default(pool)) +} + +// Core traits + +impl<A: Clone> Default for Vector<A> { + fn default() -> Self { + Self::new() + } +} + +impl<A: Clone> Clone for Vector<A> { + /// Clone a vector. + /// + /// Time: O(1), or O(n) with a very small, bounded *n* for an inline vector. + fn clone(&self) -> Self { + Self { + vector: match &self.vector { + Inline(pool, chunk) => Inline(pool.clone(), chunk.clone()), + Single(pool, chunk) => Single(pool.clone(), chunk.clone()), + Full(pool, tree) => Full(pool.clone(), tree.clone()), + }, + } + } +} + +impl<A: Clone + Debug> Debug for Vector<A> { + fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { + f.debug_list().entries(self.iter()).finish() + // match self { + // Full(rrb) => { + // writeln!(f, "Head: {:?} {:?}", rrb.outer_f, rrb.inner_f)?; + // rrb.middle.print(f, 0, rrb.middle_level)?; + // writeln!(f, "Tail: {:?} {:?}", rrb.inner_b, rrb.outer_b) + // } + // Single(_) => write!(f, "nowt"), + // } + } +} + +#[cfg(not(has_specialisation))] +impl<A: Clone + PartialEq> PartialEq for Vector<A> { + fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other.iter()) + } +} + +#[cfg(has_specialisation)] +impl<A: Clone + PartialEq> PartialEq for Vector<A> { + default fn eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.iter().eq(other.iter()) + } +} + +#[cfg(has_specialisation)] +impl<A: Clone + Eq> PartialEq for Vector<A> { + fn eq(&self, other: &Self) -> bool { + fn cmp_chunk<A>(left: &PoolRef<Chunk<A>>, right: &PoolRef<Chunk<A>>) -> bool { + (left.is_empty() && right.is_empty()) || PoolRef::ptr_eq(left, right) + } + + if std::ptr::eq(self, other) { + return true; + } + + match (&self.vector, &other.vector) { + (Single(_, left), Single(_, right)) => { + if cmp_chunk(left, right) { + return true; + } + self.iter().eq(other.iter()) + } + (Full(_, left), Full(_, right)) => { + if left.length != right.length { + return false; + } + + if cmp_chunk(&left.outer_f, &right.outer_f) + && cmp_chunk(&left.inner_f, &right.inner_f) + && cmp_chunk(&left.inner_b, &right.inner_b) + && cmp_chunk(&left.outer_b, &right.outer_b) + && ((left.middle.is_empty() && right.middle.is_empty()) + || Ref::ptr_eq(&left.middle, &right.middle)) + { + return true; + } + self.iter().eq(other.iter()) + } + _ => self.len() == other.len() && self.iter().eq(other.iter()), + } + } +} + +impl<A: Clone + Eq> Eq for Vector<A> {} + +impl<A: Clone + PartialOrd> PartialOrd for Vector<A> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.iter().partial_cmp(other.iter()) + } +} + +impl<A: Clone + Ord> Ord for Vector<A> { + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other.iter()) + } +} + +impl<A: Clone + Hash> Hash for Vector<A> { + fn hash<H: Hasher>(&self, state: &mut H) { + for i in self { + i.hash(state) + } + } +} + +impl<A: Clone> Sum for Vector<A> { + fn sum<I>(it: I) -> Self + where + I: Iterator<Item = Self>, + { + it.fold(Self::new(), |a, b| a + b) + } +} + +impl<A: Clone> Add for Vector<A> { + type Output = Vector<A>; + + /// Concatenate two vectors. + /// + /// Time: O(log n) + fn add(mut self, other: Self) -> Self::Output { + self.append(other); + self + } +} + +impl<'a, A: Clone> Add for &'a Vector<A> { + type Output = Vector<A>; + + /// Concatenate two vectors. + /// + /// Time: O(log n) + fn add(self, other: Self) -> Self::Output { + let mut out = self.clone(); + out.append(other.clone()); + out + } +} + +impl<A: Clone> Extend<A> for Vector<A> { + /// Add values to the end of a vector by consuming an iterator. + /// + /// Time: O(n) + fn extend<I>(&mut self, iter: I) + where + I: IntoIterator<Item = A>, + { + for item in iter { + self.push_back(item) + } + } +} + +impl<A: Clone> Index<usize> for Vector<A> { + type Output = A; + /// Get a reference to the value at index `index` in the vector. + /// + /// Time: O(log n) + fn index(&self, index: usize) -> &Self::Output { + match self.get(index) { + Some(value) => value, + None => panic!( + "Vector::index: index out of bounds: {} < {}", + index, + self.len() + ), + } + } +} + +impl<A: Clone> IndexMut<usize> for Vector<A> { + /// Get a mutable reference to the value at index `index` in the + /// vector. + /// + /// Time: O(log n) + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + match self.get_mut(index) { + Some(value) => value, + None => panic!("Vector::index_mut: index out of bounds"), + } + } +} + +// Conversions + +impl<'a, A: Clone> IntoIterator for &'a Vector<A> { + type Item = &'a A; + type IntoIter = Iter<'a, A>; + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<A: Clone> IntoIterator for Vector<A> { + type Item = A; + type IntoIter = ConsumingIter<A>; + fn into_iter(self) -> Self::IntoIter { + ConsumingIter::new(self) + } +} + +impl<A: Clone> FromIterator<A> for Vector<A> { + /// Create a vector from an iterator. + /// + /// Time: O(n) + fn from_iter<I>(iter: I) -> Self + where + I: IntoIterator<Item = A>, + { + let mut seq = Self::new(); + for item in iter { + seq.push_back(item) + } + seq + } +} + +impl<'s, 'a, A, OA> From<&'s Vector<&'a A>> for Vector<OA> +where + A: ToOwned<Owned = OA>, + OA: Borrow<A> + Clone, +{ + fn from(vec: &Vector<&A>) -> Self { + vec.iter().map(|a| (*a).to_owned()).collect() + } +} + +impl<'a, A: Clone> From<&'a [A]> for Vector<A> { + fn from(slice: &[A]) -> Self { + slice.iter().cloned().collect() + } +} + +impl<A: Clone> From<Vec<A>> for Vector<A> { + /// Create a vector from a [`std::vec::Vec`][vec]. + /// + /// Time: O(n) + /// + /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html + fn from(vec: Vec<A>) -> Self { + vec.into_iter().collect() + } +} + +impl<'a, A: Clone> From<&'a Vec<A>> for Vector<A> { + /// Create a vector from a [`std::vec::Vec`][vec]. + /// + /// Time: O(n) + /// + /// [vec]: https://doc.rust-lang.org/std/vec/struct.Vec.html + fn from(vec: &Vec<A>) -> Self { + vec.iter().cloned().collect() + } +} + +// Iterators + +/// An iterator over vectors with values of type `A`. +/// +/// To obtain one, use [`Vector::iter()`][iter]. +/// +/// [iter]: enum.Vector.html#method.iter +pub struct Iter<'a, A> { + focus: Focus<'a, A>, + front_index: usize, + back_index: usize, +} + +impl<'a, A: Clone> Iter<'a, A> { + fn new(seq: &'a Vector<A>) -> Self { + Iter { + focus: seq.focus(), + front_index: 0, + back_index: seq.len(), + } + } + + fn from_focus(focus: Focus<'a, A>) -> Self { + Iter { + front_index: 0, + back_index: focus.len(), + focus, + } + } +} + +impl<'a, A: Clone> Iterator for Iter<'a, A> { + type Item = &'a A; + + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + #[allow(unsafe_code)] + let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let value = focus.get(self.front_index); + self.front_index += 1; + value + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let remaining = self.back_index - self.front_index; + (remaining, Some(remaining)) + } +} + +impl<'a, A: Clone> DoubleEndedIterator for Iter<'a, A> { + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next_back(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + self.back_index -= 1; + #[allow(unsafe_code)] + let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + focus.get(self.back_index) + } +} + +impl<'a, A: Clone> ExactSizeIterator for Iter<'a, A> {} + +impl<'a, A: Clone> FusedIterator for Iter<'a, A> {} + +/// A mutable iterator over vectors with values of type `A`. +/// +/// To obtain one, use [`Vector::iter_mut()`][iter_mut]. +/// +/// [iter_mut]: enum.Vector.html#method.iter_mut +pub struct IterMut<'a, A> { + focus: FocusMut<'a, A>, + front_index: usize, + back_index: usize, +} + +impl<'a, A> IterMut<'a, A> +where + A: Clone, +{ + fn new(seq: &'a mut Vector<A>) -> Self { + let focus = seq.focus_mut(); + let len = focus.len(); + IterMut { + focus, + front_index: 0, + back_index: len, + } + } + + fn from_focus(focus: FocusMut<'a, A>) -> Self { + IterMut { + front_index: 0, + back_index: focus.len(), + focus, + } + } +} + +impl<'a, A> Iterator for IterMut<'a, A> +where + A: 'a + Clone, +{ + type Item = &'a mut A; + + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + #[allow(unsafe_code)] + let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let value = focus.get_mut(self.front_index); + self.front_index += 1; + value + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let remaining = self.back_index - self.front_index; + (remaining, Some(remaining)) + } +} + +impl<'a, A> DoubleEndedIterator for IterMut<'a, A> +where + A: 'a + Clone, +{ + /// Remove and return an element from the back of the iterator. + /// + /// Time: O(1)* + fn next_back(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + self.back_index -= 1; + #[allow(unsafe_code)] + let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + focus.get_mut(self.back_index) + } +} + +impl<'a, A: Clone> ExactSizeIterator for IterMut<'a, A> {} + +impl<'a, A: Clone> FusedIterator for IterMut<'a, A> {} + +/// A consuming iterator over vectors with values of type `A`. +pub struct ConsumingIter<A> { + vector: Vector<A>, +} + +impl<A: Clone> ConsumingIter<A> { + fn new(vector: Vector<A>) -> Self { + Self { vector } + } +} + +impl<A: Clone> Iterator for ConsumingIter<A> { + type Item = A; + + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next(&mut self) -> Option<Self::Item> { + self.vector.pop_front() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let len = self.vector.len(); + (len, Some(len)) + } +} + +impl<A: Clone> DoubleEndedIterator for ConsumingIter<A> { + /// Remove and return an element from the back of the iterator. + /// + /// Time: O(1)* + fn next_back(&mut self) -> Option<Self::Item> { + self.vector.pop_back() + } +} + +impl<A: Clone> ExactSizeIterator for ConsumingIter<A> {} + +impl<A: Clone> FusedIterator for ConsumingIter<A> {} + +/// An iterator over the leaf nodes of a vector. +/// +/// To obtain one, use [`Vector::chunks()`][chunks]. +/// +/// [chunks]: enum.Vector.html#method.chunks +pub struct Chunks<'a, A> { + focus: Focus<'a, A>, + front_index: usize, + back_index: usize, +} + +impl<'a, A: Clone> Chunks<'a, A> { + fn new(seq: &'a Vector<A>) -> Self { + Chunks { + focus: seq.focus(), + front_index: 0, + back_index: seq.len(), + } + } +} + +impl<'a, A: Clone> Iterator for Chunks<'a, A> { + type Item = &'a [A]; + + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + #[allow(unsafe_code)] + let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let (range, value) = focus.chunk_at(self.front_index); + self.front_index = range.end; + Some(value) + } +} + +impl<'a, A: Clone> DoubleEndedIterator for Chunks<'a, A> { + /// Remove and return an element from the back of the iterator. + /// + /// Time: O(1)* + fn next_back(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + self.back_index -= 1; + #[allow(unsafe_code)] + let focus: &'a mut Focus<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let (range, value) = focus.chunk_at(self.back_index); + self.back_index = range.start; + Some(value) + } +} + +impl<'a, A: Clone> FusedIterator for Chunks<'a, A> {} + +/// A mutable iterator over the leaf nodes of a vector. +/// +/// To obtain one, use [`Vector::chunks_mut()`][chunks_mut]. +/// +/// [chunks_mut]: enum.Vector.html#method.chunks_mut +pub struct ChunksMut<'a, A> { + focus: FocusMut<'a, A>, + front_index: usize, + back_index: usize, +} + +impl<'a, A: Clone> ChunksMut<'a, A> { + fn new(seq: &'a mut Vector<A>) -> Self { + let len = seq.len(); + ChunksMut { + focus: seq.focus_mut(), + front_index: 0, + back_index: len, + } + } +} + +impl<'a, A: Clone> Iterator for ChunksMut<'a, A> { + type Item = &'a mut [A]; + + /// Advance the iterator and return the next value. + /// + /// Time: O(1)* + fn next(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + #[allow(unsafe_code)] + let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let (range, value) = focus.chunk_at(self.front_index); + self.front_index = range.end; + Some(value) + } +} + +impl<'a, A: Clone> DoubleEndedIterator for ChunksMut<'a, A> { + /// Remove and return an element from the back of the iterator. + /// + /// Time: O(1)* + fn next_back(&mut self) -> Option<Self::Item> { + if self.front_index >= self.back_index { + return None; + } + self.back_index -= 1; + #[allow(unsafe_code)] + let focus: &'a mut FocusMut<'a, A> = unsafe { &mut *(&mut self.focus as *mut _) }; + let (range, value) = focus.chunk_at(self.back_index); + self.back_index = range.start; + Some(value) + } +} + +impl<'a, A: Clone> FusedIterator for ChunksMut<'a, A> {} + +// Proptest +#[cfg(any(test, feature = "proptest"))] +#[doc(hidden)] +pub mod proptest { + #[deprecated( + since = "14.3.0", + note = "proptest strategies have moved to im::proptest" + )] + pub use crate::proptest::vector; +} + +// Tests + +#[cfg(test)] +mod test { + use super::*; + use crate::proptest::vector; + use ::proptest::collection::vec; + use ::proptest::num::{i32, usize}; + use ::proptest::proptest; + + #[test] + fn macro_allows_trailing_comma() { + let vec1 = vector![1, 2, 3]; + let vec2 = vector![1, 2, 3,]; + assert_eq!(vec1, vec2); + } + + #[test] + fn indexing() { + let mut vec = vector![0, 1, 2, 3, 4, 5]; + vec.push_front(0); + assert_eq!(0, *vec.get(0).unwrap()); + assert_eq!(0, vec[0]); + } + + #[test] + fn large_vector_focus() { + let input = (0..100_000).collect::<Vector<_>>(); + let vec = input.clone(); + let mut sum: i64 = 0; + let mut focus = vec.focus(); + for i in 0..input.len() { + sum += *focus.index(i); + } + let expected: i64 = (0..100_000).sum(); + assert_eq!(expected, sum); + } + + #[test] + fn large_vector_focus_mut() { + let input = (0..100_000).collect::<Vector<_>>(); + let mut vec = input.clone(); + { + let mut focus = vec.focus_mut(); + for i in 0..input.len() { + let p = focus.index_mut(i); + *p += 1; + } + } + let expected: Vector<i32> = input.into_iter().map(|i| i + 1).collect(); + assert_eq!(expected, vec); + } + + #[test] + fn issue_55_fwd() { + let mut l = Vector::new(); + for i in 0..4098 { + l.append(Vector::unit(i)); + } + l.append(Vector::unit(4098)); + assert_eq!(Some(&4097), l.get(4097)); + assert_eq!(Some(&4096), l.get(4096)); + } + + #[test] + fn issue_55_back() { + let mut l = Vector::unit(0); + for i in 0..4099 { + let mut tmp = Vector::unit(i + 1); + tmp.append(l); + l = tmp; + } + assert_eq!(Some(&4098), l.get(1)); + assert_eq!(Some(&4097), l.get(2)); + let len = l.len(); + l.slice(2..len); + } + + #[test] + fn issue_55_append() { + let mut vec1 = (0..92).collect::<Vector<_>>(); + let vec2 = (0..165).collect::<Vector<_>>(); + vec1.append(vec2); + } + + #[test] + fn issue_70() { + let mut x = Vector::new(); + for _ in 0..262 { + x.push_back(0); + } + for _ in 0..97 { + x.pop_front(); + } + for &offset in &[160, 163, 160] { + x.remove(offset); + } + for _ in 0..64 { + x.push_back(0); + } + // At this point middle contains three chunks of size 64, 64 and 1 + // respectively. Previously the next `push_back()` would append another + // zero-sized chunk to middle even though there is enough space left. + match x.vector { + VectorInner::Full(_, ref tree) => { + assert_eq!(129, tree.middle.len()); + assert_eq!(3, tree.middle.number_of_children()); + } + _ => unreachable!(), + } + x.push_back(0); + match x.vector { + VectorInner::Full(_, ref tree) => { + assert_eq!(131, tree.middle.len()); + assert_eq!(3, tree.middle.number_of_children()) + } + _ => unreachable!(), + } + for _ in 0..64 { + x.push_back(0); + } + for _ in x.iter() {} + } + + #[test] + fn issue_67() { + let mut l = Vector::unit(4100); + for i in (0..4099).rev() { + let mut tmp = Vector::unit(i); + tmp.append(l); + l = tmp; + } + assert_eq!(4100, l.len()); + let len = l.len(); + let tail = l.slice(1..len); + assert_eq!(1, l.len()); + assert_eq!(4099, tail.len()); + assert_eq!(Some(&0), l.get(0)); + assert_eq!(Some(&1), tail.get(0)); + } + + #[test] + fn issue_74_simple_size() { + use crate::nodes::rrb::NODE_SIZE; + let mut x = Vector::new(); + for _ in 0..(CHUNK_SIZE + * ( + 1 // inner_f + + (2 * NODE_SIZE) // middle: two full Entry::Nodes (4096 elements each) + + 1 // inner_b + + 1 + // outer_b + )) + { + x.push_back(0u32); + } + let middle_first_node_start = CHUNK_SIZE; + let middle_second_node_start = middle_first_node_start + NODE_SIZE * CHUNK_SIZE; + // This reduces the size of the second node to 4095. + x.remove(middle_second_node_start); + // As outer_b is full, this will cause inner_b (length 64) to be pushed + // to middle. The first element will be merged into the second node, the + // remaining 63 elements will end up in a new node. + x.push_back(0u32); + match x.vector { + VectorInner::Full(_, tree) => { + assert_eq!(3, tree.middle.number_of_children()); + assert_eq!( + 2 * NODE_SIZE * CHUNK_SIZE + CHUNK_SIZE - 1, + tree.middle.len() + ); + } + _ => unreachable!(), + } + } + + #[test] + fn issue_77() { + let mut x = Vector::new(); + for _ in 0..44 { + x.push_back(0); + } + for _ in 0..20 { + x.insert(0, 0); + } + x.insert(1, 0); + for _ in 0..441 { + x.push_back(0); + } + for _ in 0..58 { + x.insert(0, 0); + } + x.insert(514, 0); + for _ in 0..73 { + x.push_back(0); + } + for _ in 0..10 { + x.insert(0, 0); + } + x.insert(514, 0); + } + + #[test] + fn issue_105() { + let mut v = Vector::new(); + + for i in 0..270_000 { + v.push_front(i); + } + + while !v.is_empty() { + v = v.take(v.len() - 1); + } + } + + #[test] + fn issue_107_split_off_causes_overflow() { + let mut vec = (0..4289).collect::<Vector<_>>(); + let mut control = (0..4289).collect::<Vec<_>>(); + let chunk = 64; + + while vec.len() >= chunk { + vec = vec.split_off(chunk); + control = control.split_off(chunk); + assert_eq!(vec.len(), control.len()); + assert_eq!(control, vec.iter().cloned().collect::<Vec<_>>()); + } + } + + #[test] + fn collect_crash() { + let _vector: Vector<i32> = (0..5953).collect(); + // let _vector: Vector<i32> = (0..16384).collect(); + } + + #[test] + fn issue_116() { + let vec = (0..300).collect::<Vector<_>>(); + let rev_vec: Vector<u32> = vec.clone().into_iter().rev().collect(); + assert_eq!(vec.len(), rev_vec.len()); + } + + #[test] + fn issue_131() { + let smol = std::iter::repeat(42).take(64).collect::<Vector<_>>(); + let mut smol2 = smol.clone(); + assert!(smol.ptr_eq(&smol2)); + smol2.set(63, 420); + assert!(!smol.ptr_eq(&smol2)); + + let huge = std::iter::repeat(42).take(65).collect::<Vector<_>>(); + let mut huge2 = huge.clone(); + assert!(huge.ptr_eq(&huge2)); + huge2.set(63, 420); + assert!(!huge.ptr_eq(&huge2)); + } + + #[test] + fn ptr_eq() { + for len in 32..256 { + let input = std::iter::repeat(42).take(len).collect::<Vector<_>>(); + let mut inp2 = input.clone(); + assert!(input.ptr_eq(&inp2)); + inp2.set(len - 1, 98); + assert_ne!(inp2.get(len - 1), input.get(len - 1)); + assert!(!input.ptr_eq(&inp2)); + } + } + + proptest! { + #[test] + fn iter(ref vec in vec(i32::ANY, 0..1000)) { + let seq: Vector<i32> = vec.iter().cloned().collect::<Vector<_>>(); + for (index, item) in seq.iter().enumerate() { + assert_eq!(&vec[index], item); + } + assert_eq!(vec.len(), seq.len()); + } + + #[test] + fn push_front_mut(ref input in vec(i32::ANY, 0..1000)) { + let mut vector = Vector::new(); + for (count, value) in input.iter().cloned().enumerate() { + assert_eq!(count, vector.len()); + vector.push_front(value); + assert_eq!(count + 1, vector.len()); + } + let input2 = input.iter().rev().cloned().collect::<Vec<_>>(); + assert_eq!(input2, vector.iter().cloned().collect::<Vec<_>>()); + } + + #[test] + fn push_back_mut(ref input in vec(i32::ANY, 0..1000)) { + let mut vector = Vector::new(); + for (count, value) in input.iter().cloned().enumerate() { + assert_eq!(count, vector.len()); + vector.push_back(value); + assert_eq!(count + 1, vector.len()); + } + assert_eq!(input, &vector.iter().cloned().collect::<Vec<_>>()); + } + + #[test] + fn pop_back_mut(ref input in vec(i32::ANY, 0..1000)) { + let mut vector = input.iter().cloned().collect::<Vector<_>>(); + assert_eq!(input.len(), vector.len()); + for (index, value) in input.iter().cloned().enumerate().rev() { + match vector.pop_back() { + None => panic!("vector emptied unexpectedly"), + Some(item) => { + assert_eq!(index, vector.len()); + assert_eq!(value, item); + } + } + } + assert_eq!(0, vector.len()); + } + + #[test] + fn pop_front_mut(ref input in vec(i32::ANY, 0..1000)) { + let mut vector = input.iter().cloned().collect::<Vector<_>>(); + assert_eq!(input.len(), vector.len()); + for (index, value) in input.iter().cloned().rev().enumerate().rev() { + match vector.pop_front() { + None => panic!("vector emptied unexpectedly"), + Some(item) => { + assert_eq!(index, vector.len()); + assert_eq!(value, item); + } + } + } + assert_eq!(0, vector.len()); + } + + // #[test] + // fn push_and_pop(ref input in vec(i32::ANY, 0..1000)) { + // let mut vector = Vector::new(); + // for (count, value) in input.iter().cloned().enumerate() { + // assert_eq!(count, vector.len()); + // vector.push_back(value); + // assert_eq!(count + 1, vector.len()); + // } + // for (index, value) in input.iter().cloned().rev().enumerate().rev() { + // match vector.pop_front() { + // None => panic!("vector emptied unexpectedly"), + // Some(item) => { + // assert_eq!(index, vector.len()); + // assert_eq!(value, item); + // } + // } + // } + // assert_eq!(true, vector.is_empty()); + // } + + #[test] + fn split(ref vec in vec(i32::ANY, 1..2000), split_pos in usize::ANY) { + let split_index = split_pos % (vec.len() + 1); + let mut left = vec.iter().cloned().collect::<Vector<_>>(); + let right = left.split_off(split_index); + assert_eq!(left.len(), split_index); + assert_eq!(right.len(), vec.len() - split_index); + for (index, item) in left.iter().enumerate() { + assert_eq!(& vec[index], item); + } + for (index, item) in right.iter().enumerate() { + assert_eq!(&vec[split_index + index], item); + } + } + + #[test] + fn append(ref vec1 in vec(i32::ANY, 0..1000), ref vec2 in vec(i32::ANY, 0..1000)) { + let mut seq1 = vec1.iter().cloned().collect::<Vector<_>>(); + let seq2 = vec2.iter().cloned().collect::<Vector<_>>(); + assert_eq!(seq1.len(), vec1.len()); + assert_eq!(seq2.len(), vec2.len()); + seq1.append(seq2); + let mut vec = vec1.clone(); + vec.extend(vec2); + assert_eq!(seq1.len(), vec.len()); + for (index, item) in seq1.into_iter().enumerate() { + assert_eq!(vec[index], item); + } + } + + #[test] + fn iter_mut(ref input in vector(i32::ANY, 0..10000)) { + let mut vec = input.clone(); + { + for p in vec.iter_mut() { + *p = p.overflowing_add(1).0; + } + } + let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect(); + assert_eq!(expected, vec); + } + + #[test] + fn focus(ref input in vector(i32::ANY, 0..10000)) { + let mut vec = input.clone(); + { + let mut focus = vec.focus_mut(); + for i in 0..input.len() { + let p = focus.index_mut(i); + *p = p.overflowing_add(1).0; + } + } + let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect(); + assert_eq!(expected, vec); + } + + #[test] + fn focus_mut_split(ref input in vector(i32::ANY, 0..10000)) { + let mut vec = input.clone(); + + fn split_down(focus: FocusMut<'_, i32>) { + let len = focus.len(); + if len < 8 { + for p in focus { + *p = p.overflowing_add(1).0; + } + } else { + let (left, right) = focus.split_at(len / 2); + split_down(left); + split_down(right); + } + } + + split_down(vec.focus_mut()); + + let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect(); + assert_eq!(expected, vec); + } + + #[test] + fn chunks(ref input in vector(i32::ANY, 0..10000)) { + let output: Vector<_> = input.leaves().flatten().cloned().collect(); + assert_eq!(input, &output); + let rev_in: Vector<_> = input.iter().rev().cloned().collect(); + let rev_out: Vector<_> = input.leaves().rev().map(|c| c.iter().rev()).flatten().cloned().collect(); + assert_eq!(rev_in, rev_out); + } + + #[test] + fn chunks_mut(ref mut input_src in vector(i32::ANY, 0..10000)) { + let mut input = input_src.clone(); + #[allow(clippy::map_clone)] + let output: Vector<_> = input.leaves_mut().flatten().map(|v| *v).collect(); + assert_eq!(input, output); + let rev_in: Vector<_> = input.iter().rev().cloned().collect(); + let rev_out: Vector<_> = input.leaves_mut().rev().map(|c| c.iter().rev()).flatten().cloned().collect(); + assert_eq!(rev_in, rev_out); + } + + // The following two tests are very slow and there are unit tests above + // which test for regression of issue #55. It would still be good to + // run them occasionally. + + // #[test] + // fn issue55_back(count in 0..10000, slice_at in usize::ANY) { + // let count = count as usize; + // let slice_at = slice_at % count; + // let mut l = Vector::unit(0); + // for _ in 0..count { + // let mut tmp = Vector::unit(0); + // tmp.append(l); + // l = tmp; + // } + // let len = l.len(); + // l.slice(slice_at..len); + // } + + // #[test] + // fn issue55_fwd(count in 0..10000, slice_at in usize::ANY) { + // let count = count as usize; + // let slice_at = slice_at % count; + // let mut l = Vector::new(); + // for i in 0..count { + // l.append(Vector::unit(i)); + // } + // assert_eq!(Some(&slice_at), l.get(slice_at)); + // } + } +} |