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