vendor/im-rc/src/vector/focus.rs

   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 use std::mem::{replace, swap};
   6 use std::ops::{Range, RangeBounds};
   7 use std::ptr::null;
   8 use std::sync::atomic::{AtomicPtr, Ordering};
   9
  10 use nodes::chunk::Chunk;
  11 use sync::Lock;
  12 use util::{to_range, Ref};
  13 use vector::{Iter, IterMut, Vector, RRB};
  14
  15 /// Focused indexing over a [`Vector`][Vector].
  16 ///
  17 /// By remembering the last tree node accessed through an index lookup and the
  18 /// path we took to get there, we can speed up lookups for adjacent indices
  19 /// tremendously. Lookups on indices in the same node are instantaneous, and
  20 /// lookups on sibling nodes are also very fast.
  21 ///
  22 /// A `Focus` can also be used as a restricted view into a vector, using the
  23 /// [`narrow`][narrow] and [`split_at`][split_at] methods.
  24 ///
  25 /// # When should I use a `Focus` for better performance?
  26 ///
  27 /// `Focus` is useful when you need to perform a large number of index lookups
  28 /// that are more likely than not to be close to each other. It's usually worth
  29 /// using a `Focus` in any situation where you're batching a lot of index
  30 /// lookups together, even if they're not obviously adjacent - there's likely
  31 /// to be some performance gain for even completely random access.
  32 ///
  33 /// If you're just iterating forwards or backwards over the [`Vector`][Vector]
  34 /// in order, you're better off with a regular iterator, which, in fact, is
  35 /// implemented using a `Focus`, but provides a simpler interface.
  36 ///
  37 /// If you're just doing a very small number of index lookups, the setup cost
  38 /// for the `Focus` is probably not worth it.
  39 ///
  40 /// A `Focus` is never faster than an index lookup on a small [`Vector`][Vector]
  41 /// with a length below the internal RRB tree's branching factor of 64.
  42 ///
  43 /// # Examples
  44 ///
  45 /// This example is contrived, as the better way to iterate forwards or
  46 /// backwards over a vector is with an actual iterator. Even so, the version
  47 /// using a `Focus` should run nearly an order of magnitude faster than the
  48 /// version using index lookups at a length of 1000. It should also be noted
  49 /// that [`vector::Iter`][Iter] is actually implemented using a `Focus` behind
  50 /// the scenes, so the performance of the two should be identical.
  51 ///
  52 /// ```rust
  53 /// # #[macro_use] extern crate im_rc as im;
  54 /// # use im::vector::Vector;
  55 /// # use std::iter::FromIterator;
  56 /// # fn main() {
  57 /// let mut vec: Vector<i64> = Vector::from_iter(0..1000);
  58 ///
  59 /// // Summing a vector, the slow way:
  60 /// let mut sum = 0;
  61 /// for i in 0..1000 {
  62 ///     sum += *vec.get(i).unwrap();
  63 /// }
  64 /// assert_eq!(499500, sum);
  65 ///
  66 /// // Summing a vector faster using a Focus:
  67 /// let mut sum = 0;
  68 /// let mut focus = vec.focus();
  69 /// for i in 0..1000 {
  70 ///     sum += *focus.get(i).unwrap();
  71 /// }
  72 /// assert_eq!(499500, sum);
  73 ///
  74 /// // And the easy way, for completeness:
  75 /// let sum: i64 = vec.iter().sum();
  76 /// assert_eq!(499500, sum);
  77 /// # }
  78 /// ```
  79 ///
  80 /// [Vector]: enum.Vector.html
  81 /// [Iter]: struct.Iter.html
  82 /// [narrow]: #method.narrow
  83 /// [split_at]: #method.split_at
  84 pub enum Focus<'a, A>
  85 where
  86     A: 'a,
  87 {
  88     #[doc(hidden)]
  89     Single(&'a [A]),
  90     #[doc(hidden)]
  91     Full(TreeFocus<A>),
  92 }
  93
  94 impl<'a, A> Focus<'a, A>
  95 where
  96     A: Clone + 'a,
  97 {
  98     /// Construct a `Focus` for a [`Vector`][Vector].
  99     ///
 100     /// [Vector]: enum.Vector.html
 101     pub fn new(vector: &'a Vector<A>) -> Self {
 102         match vector {
 103             Vector::Single(chunk) => Focus::Single(chunk),
 104             Vector::Full(tree) => Focus::Full(TreeFocus::new(tree)),
 105         }
 106     }
 107
 108     /// Get the length of the focused [`Vector`][Vector].
 109     ///
 110     /// [Vector]: enum.Vector.html
 111     pub fn len(&self) -> usize {
 112         match self {
 113             Focus::Single(chunk) => chunk.len(),
 114             Focus::Full(tree) => tree.len(),
 115         }
 116     }
 117
 118     /// Test if the focused [`Vector`][Vector] is empty.
 119     ///
 120     /// [Vector]: enum.Vector.html
 121     pub fn is_empty(&self) -> bool {
 122         self.len() == 0
 123     }
 124
 125     /// Get a reference to the value at a given index.
 126     pub fn get(&mut self, index: usize) -> Option<&A> {
 127         match self {
 128             Focus::Single(chunk) => chunk.get(index),
 129             Focus::Full(tree) => tree.get(index),
 130         }
 131     }
 132
 133     /// Get a reference to the value at a given index.
 134     ///
 135     /// Panics if the index is out of bounds.
 136     pub fn index(&mut self, index: usize) -> &A {
 137         self.get(index).expect("index out of bounds")
 138     }
 139
 140     /// Get the chunk for the given index.
 141     ///
 142     /// This gives you a reference to the leaf node that contains the index,
 143     /// along with its start and end indices.
 144     pub fn chunk_at(&mut self, index: usize) -> (Range<usize>, &[A]) {
 145         let len = self.len();
 146         if index >= len {
 147             panic!("vector::Focus::chunk_at: index out of bounds");
 148         }
 149         match self {
 150             Focus::Single(chunk) => (0..len, chunk),
 151             Focus::Full(tree) => tree.get_chunk(index),
 152         }
 153     }
 154
 155     /// Narrow the focus onto a subslice of the vector.
 156     ///
 157     /// `Focus::narrow(range)` has the same effect as `&slice[range]`, without
 158     /// actually modifying the underlying vector.
 159     ///
 160     /// Panics if the range isn't fully inside the current focus.
 161     ///
 162     /// ## Examples
 163     ///
 164     /// ```rust
 165     /// # #[macro_use] extern crate im_rc as im;
 166     /// # use im::vector::Vector;
 167     /// # use std::iter::FromIterator;
 168     /// # fn main() {
 169     /// let vec = Vector::from_iter(0..1000);
 170     /// let narrowed = vec.focus().narrow(100..200);
 171     /// let narrowed_vec = narrowed.into_iter().cloned().collect();
 172     /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
 173     /// # }
 174     /// ```
 175     ///
 176     /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
 177     /// [Vector::split_at]: enum.Vector.html#method.split_at
 178     pub fn narrow<R>(self, range: R) -> Self
 179     where
 180         R: RangeBounds<usize>,
 181     {
 182         let r = to_range(&range, self.len());
 183         if r.start >= r.end || r.start >= self.len() {
 184             panic!("vector::Focus::narrow: range out of bounds");
 185         }
 186         match self {
 187             Focus::Single(chunk) => Focus::Single(&chunk[r]),
 188             Focus::Full(tree) => Focus::Full(tree.narrow(r)),
 189         }
 190     }
 191
 192     /// Split the focus into two.
 193     ///
 194     /// Given an index `index`, consume the focus and produce two new foci, the
 195     /// left onto indices `0..index`, and the right onto indices `index..N`
 196     /// where `N` is the length of the current focus.
 197     ///
 198     /// Panics if the index is out of bounds.
 199     ///
 200     /// This is the moral equivalent of [`slice::split_at`][slice::split_at], in
 201     /// that it leaves the underlying data structure unchanged, unlike
 202     /// [`Vector::split_at`][Vector::split_at].
 203     ///
 204     /// ## Examples
 205     ///
 206     /// ```rust
 207     /// # #[macro_use] extern crate im_rc as im;
 208     /// # use im::vector::Vector;
 209     /// # use std::iter::FromIterator;
 210     /// # fn main() {
 211     /// let vec = Vector::from_iter(0..1000);
 212     /// let (left, right) = vec.focus().split_at(500);
 213     /// let left_vec = left.into_iter().cloned().collect();
 214     /// let right_vec = right.into_iter().cloned().collect();
 215     /// assert_eq!(Vector::from_iter(0..500), left_vec);
 216     /// assert_eq!(Vector::from_iter(500..1000), right_vec);
 217     /// # }
 218     /// ```
 219     ///
 220     /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
 221     /// [Vector::split_at]: enum.Vector.html#method.split_at
 222     pub fn split_at(self, index: usize) -> (Self, Self) {
 223         if index >= self.len() {
 224             panic!("vector::Focus::split_at: index out of bounds");
 225         }
 226         match self {
 227             Focus::Single(chunk) => {
 228                 let (left, right) = chunk.split_at(index);
 229                 (Focus::Single(left), Focus::Single(right))
 230             }
 231             Focus::Full(tree) => {
 232                 let (left, right) = tree.split_at(index);
 233                 (Focus::Full(left), Focus::Full(right))
 234             }
 235         }
 236     }
 237 }
 238
 239 impl<'a, A> IntoIterator for Focus<'a, A>
 240 where
 241     A: Clone + 'a,
 242 {
 243     type Item = &'a A;
 244     type IntoIter = Iter<'a, A>;
 245
 246     fn into_iter(self) -> Self::IntoIter {
 247         Iter::from_focus(self)
 248     }
 249 }
 250
 251 impl<'a, A> Clone for Focus<'a, A>
 252 where
 253     A: Clone + 'a,
 254 {
 255     fn clone(&self) -> Self {
 256         match self {
 257             Focus::Single(chunk) => Focus::Single(chunk),
 258             Focus::Full(tree) => Focus::Full(tree.clone()),
 259         }
 260     }
 261 }
 262
 263 pub struct TreeFocus<A> {
 264     tree: RRB<A>,
 265     view: Range<usize>,
 266     middle_range: Range<usize>,
 267     target_range: Range<usize>,
 268     target_ptr: *const Chunk<A>,
 269 }
 270
 271 impl<A> Clone for TreeFocus<A> {
 272     fn clone(&self) -> Self {
 273         let tree = self.tree.clone();
 274         TreeFocus {
 275             view: self.view.clone(),
 276             middle_range: self.middle_range.clone(),
 277             target_range: 0..0,
 278             target_ptr: null(),
 279             tree,
 280         }
 281     }
 282 }
 283
 284 #[allow(unsafe_code)]
 285 #[cfg(threadsafe)]
 286 unsafe impl<A> Send for TreeFocus<A> {}
 287 #[allow(unsafe_code)]
 288 #[cfg(threadsafe)]
 289 unsafe impl<A> Sync for TreeFocus<A> {}
 290
 291 #[inline]
 292 fn contains<A: Ord>(range: &Range<A>, index: &A) -> bool {
 293     *index >= range.start && *index < range.end
 294 }
 295
 296 impl<A> TreeFocus<A>
 297 where
 298     A: Clone,
 299 {
 300     fn new(tree: &RRB<A>) -> Self {
 301         let middle_start = tree.outer_f.len() + tree.inner_f.len();
 302         let middle_end = middle_start + tree.middle.len();
 303         TreeFocus {
 304             tree: tree.clone(),
 305             view: 0..tree.length,
 306             middle_range: middle_start..middle_end,
 307             target_range: 0..0,
 308             target_ptr: null(),
 309         }
 310     }
 311
 312     fn len(&self) -> usize {
 313         self.view.end - self.view.start
 314     }
 315
 316     fn narrow(self, mut view: Range<usize>) -> Self {
 317         view.start += self.view.start;
 318         view.end += self.view.start;
 319         TreeFocus {
 320             view,
 321             middle_range: self.middle_range.clone(),
 322             target_range: 0..0,
 323             target_ptr: null(),
 324             tree: self.tree,
 325         }
 326     }
 327
 328     fn split_at(self, index: usize) -> (Self, Self) {
 329         let len = self.len();
 330         let left = self.clone().narrow(0..index);
 331         let right = self.narrow(index..len);
 332         (left, right)
 333     }
 334
 335     fn physical_index(&self, index: usize) -> usize {
 336         debug_assert!(index < self.view.end);
 337         self.view.start + index
 338     }
 339
 340     fn logical_range(&self, range: &Range<usize>) -> Range<usize> {
 341         (range.start - self.view.start)..(range.end - self.view.start)
 342     }
 343
 344     fn set_focus(&mut self, index: usize) {
 345         if index < self.middle_range.start {
 346             let outer_len = self.tree.outer_f.len();
 347             if index < outer_len {
 348                 self.target_range = 0..outer_len;
 349                 self.target_ptr = &*self.tree.outer_f;
 350             } else {
 351                 self.target_range = outer_len..self.middle_range.start;
 352                 self.target_ptr = &*self.tree.inner_f;
 353             }
 354         } else if index >= self.middle_range.end {
 355             let outer_start = self.middle_range.end + self.tree.inner_b.len();
 356             if index < outer_start {
 357                 self.target_range = self.middle_range.end..outer_start;
 358                 self.target_ptr = &*self.tree.inner_b;
 359             } else {
 360                 self.target_range = outer_start..self.tree.length;
 361                 self.target_ptr = &*self.tree.outer_b;
 362             }
 363         } else {
 364             let tree_index = index - self.middle_range.start;
 365             let (range, ptr) = self
 366                 .tree
 367                 .middle
 368                 .lookup_chunk(self.tree.middle_level, 0, tree_index);
 369             self.target_range =
 370                 (range.start + self.middle_range.start)..(range.end + self.middle_range.start);
 371             self.target_ptr = ptr;
 372         }
 373     }
 374
 375     #[allow(unsafe_code)]
 376     fn get_focus(&self) -> &Chunk<A> {
 377         unsafe { &*self.target_ptr }
 378     }
 379
 380     pub fn get(&mut self, index: usize) -> Option<&A> {
 381         if index >= self.len() {
 382             return None;
 383         }
 384         let phys_index = self.physical_index(index);
 385         if !contains(&self.target_range, &phys_index) {
 386             self.set_focus(phys_index);
 387         }
 388         let target_phys_index = phys_index - self.target_range.start;
 389         Some(&self.get_focus()[target_phys_index])
 390     }
 391
 392     pub fn get_chunk(&mut self, index: usize) -> (Range<usize>, &[A]) {
 393         let phys_index = self.physical_index(index);
 394         if !contains(&self.target_range, &phys_index) {
 395             self.set_focus(phys_index);
 396         }
 397         let mut slice: &[A] = self.get_focus();
 398         let mut left = 0;
 399         let mut right = 0;
 400         if self.target_range.start < self.view.start {
 401             left = self.view.start - self.target_range.start;
 402         }
 403         if self.target_range.end > self.view.end {
 404             right = self.target_range.end - self.view.end;
 405         }
 406         slice = &slice[left..(slice.len() - right)];
 407         let phys_range = (self.target_range.start + left)..(self.target_range.end - right);
 408         (self.logical_range(&phys_range), slice)
 409     }
 410 }
 411
 412 /// A mutable version of [`Focus`][Focus].
 413 ///
 414 /// See [`Focus`][Focus] for more details.
 415 ///
 416 /// You can only build one `FocusMut` at a time for a vector, effectively
 417 /// keeping a lock on the vector until you're done with the focus, which relies
 418 /// on the structure of the vector not changing while it exists.
 419 ///
 420 /// ```rust,compile_fail
 421 /// # #[macro_use] extern crate im_rc as im;
 422 /// # use im::vector::Vector;
 423 /// # use std::iter::FromIterator;
 424 /// # fn main() {
 425 /// let mut vec = Vector::from_iter(0..1000);
 426 /// let focus1 = vec.focus_mut();
 427 /// // Fails here because you already have a focus
 428 /// let focus2 = vec.focus_mut();
 429 /// # }
 430 /// ```
 431 ///
 432 /// On the other hand, you can split that one focus into multiple sub-foci,
 433 /// which is safe because they can't overlap:
 434 ///
 435 /// ```rust
 436 /// # #[macro_use] extern crate im_rc as im;
 437 /// # use im::vector::Vector;
 438 /// # use std::iter::FromIterator;
 439 /// # fn main() {
 440 /// let mut vec = Vector::from_iter(0..1000);
 441 /// let focus = vec.focus_mut();
 442 /// let (left, right) = focus.split_at(500);
 443 /// # }
 444 /// ```
 445 ///
 446 /// These sub-foci also work as a lock on the vector, even if the focus they
 447 /// were created from goes out of scope.
 448 ///
 449 /// ```rust,compile_fail
 450 /// # #[macro_use] extern crate im_rc as im;
 451 /// # use im::vector::Vector;
 452 /// # use std::iter::FromIterator;
 453 /// # fn main() {
 454 /// let mut vec = Vector::from_iter(0..1000);
 455 /// let (left, right) = {
 456 ///     let focus = vec.focus_mut();
 457 ///     focus.split_at(500)
 458 /// };
 459 /// // `left` and `right` are still in scope even if `focus` isn't, so we can't
 460 /// // create another focus:
 461 /// let focus2 = vec.focus_mut();
 462 /// # }
 463 /// ```
 464 ///
 465 /// [Focus]: enum.Focus.html
 466 pub enum FocusMut<'a, A>
 467 where
 468     A: 'a,
 469 {
 470     #[doc(hidden)]
 471     Single(&'a mut [A]),
 472     #[doc(hidden)]
 473     Full(TreeFocusMut<'a, A>),
 474 }
 475
 476 impl<'a, A> FocusMut<'a, A>
 477 where
 478     A: Clone + 'a,
 479 {
 480     /// Construct a `FocusMut` for a `Vector`.
 481     pub fn new(vector: &'a mut Vector<A>) -> Self {
 482         match vector {
 483             Vector::Single(chunk) => FocusMut::Single(Ref::make_mut(chunk).as_mut_slice()),
 484             Vector::Full(tree) => FocusMut::Full(TreeFocusMut::new(tree)),
 485         }
 486     }
 487
 488     /// Get the length of the focused `Vector`.
 489     pub fn len(&self) -> usize {
 490         match self {
 491             FocusMut::Single(chunk) => chunk.len(),
 492             FocusMut::Full(tree) => tree.len(),
 493         }
 494     }
 495
 496     /// Test if the focused `Vector` is empty.
 497     pub fn is_empty(&self) -> bool {
 498         self.len() == 0
 499     }
 500
 501     /// Get a reference to the value at a given index.
 502     pub fn get(&mut self, index: usize) -> Option<&A> {
 503         self.get_mut(index).map(|r| &*r)
 504     }
 505
 506     /// Get a mutable reference to the value at a given index.
 507     pub fn get_mut(&mut self, index: usize) -> Option<&mut A> {
 508         match self {
 509             FocusMut::Single(chunk) => chunk.get_mut(index),
 510             FocusMut::Full(tree) => tree.get(index),
 511         }
 512     }
 513
 514     /// Get a reference to the value at a given index.
 515     ///
 516     /// Panics if the index is out of bounds.
 517     pub fn index(&mut self, index: usize) -> &A {
 518         &*self.index_mut(index)
 519     }
 520
 521     /// Get a mutable reference to the value at a given index.
 522     ///
 523     /// Panics if the index is out of bounds.
 524     #[allow(clippy::should_implement_trait)] // would if I could
 525     pub fn index_mut(&mut self, index: usize) -> &mut A {
 526         self.get_mut(index).expect("index out of bounds")
 527     }
 528
 529     /// Update the value at a given index.
 530     ///
 531     /// Returns `None` if the index is out of bounds, or the replaced value
 532     /// otherwise.
 533     pub fn set(&mut self, index: usize, value: A) -> Option<A> {
 534         match self.get_mut(index) {
 535             Some(ref mut pos) => Some(replace(pos, value)),
 536             None => None,
 537         }
 538     }
 539
 540     /// Swap the values at two given indices.
 541     ///
 542     /// Panics if either index is out of bounds.
 543     ///
 544     /// If the indices are equal, this function returns without doing anything.
 545     pub fn swap(&mut self, a: usize, b: usize) {
 546         if a == b {
 547             return;
 548         }
 549         self.pair(a, b, |left, right| swap(left, right));
 550     }
 551
 552     /// Lookup two indices simultaneously and run a function over them.
 553     ///
 554     /// Useful because the borrow checker won't let you have more than one
 555     /// mutable reference into the same data structure at any given time.
 556     ///
 557     /// Panics if either index is out of bounds, or if they are the same index.
 558     ///
 559     /// # Examples
 560     ///
 561     /// ```rust
 562     /// # #[macro_use] extern crate im_rc as im;
 563     /// # use im::vector::Vector;
 564     /// # use std::iter::FromIterator;
 565     /// # fn main() {
 566     /// let mut vec = vector![1, 2, 3, 4, 5];
 567     /// vec.focus_mut().pair(1, 3, |a, b| *a += *b);
 568     /// assert_eq!(vector![1, 6, 3, 4, 5], vec);
 569     /// # }
 570     /// ```
 571     #[allow(unsafe_code)]
 572     pub fn pair<F, B>(&mut self, a: usize, b: usize, mut f: F) -> B
 573     where
 574         F: FnMut(&mut A, &mut A) -> B,
 575     {
 576         if a == b {
 577             panic!("vector::FocusMut::pair: indices cannot be equal!");
 578         }
 579         let pa: *mut A = self.index_mut(a);
 580         let pb: *mut A = self.index_mut(b);
 581         unsafe { f(&mut *pa, &mut *pb) }
 582     }
 583
 584     /// Lookup three indices simultaneously and run a function over them.
 585     ///
 586     /// Useful because the borrow checker won't let you have more than one
 587     /// mutable reference into the same data structure at any given time.
 588     ///
 589     /// Panics if any index is out of bounds, or if any indices are equal.
 590     ///
 591     /// # Examples
 592     ///
 593     /// ```rust
 594     /// # #[macro_use] extern crate im_rc as im;
 595     /// # use im::vector::Vector;
 596     /// # use std::iter::FromIterator;
 597     /// # fn main() {
 598     /// let mut vec = vector![1, 2, 3, 4, 5];
 599     /// vec.focus_mut().triplet(0, 2, 4, |a, b, c| *a += *b + *c);
 600     /// assert_eq!(vector![9, 2, 3, 4, 5], vec);
 601     /// # }
 602     /// ```
 603     #[allow(unsafe_code)]
 604     pub fn triplet<F, B>(&mut self, a: usize, b: usize, c: usize, mut f: F) -> B
 605     where
 606         F: FnMut(&mut A, &mut A, &mut A) -> B,
 607     {
 608         if a == b || b == c || a == c {
 609             panic!("vector::FocusMut::triplet: indices cannot be equal!");
 610         }
 611         let pa: *mut A = self.index_mut(a);
 612         let pb: *mut A = self.index_mut(b);
 613         let pc: *mut A = self.index_mut(c);
 614         unsafe { f(&mut *pa, &mut *pb, &mut *pc) }
 615     }
 616
 617     /// Get the chunk for the given index.
 618     ///
 619     /// This gives you a reference to the leaf node that contains the index,
 620     /// along with its start and end indices.
 621     pub fn chunk_at(&mut self, index: usize) -> (Range<usize>, &mut [A]) {
 622         let len = self.len();
 623         if index >= len {
 624             panic!("vector::FocusMut::chunk_at: index out of bounds");
 625         }
 626         match self {
 627             FocusMut::Single(chunk) => (0..len, chunk),
 628             FocusMut::Full(tree) => {
 629                 let (range, chunk) = tree.get_chunk(index);
 630                 (range, chunk)
 631             }
 632         }
 633     }
 634
 635     /// Narrow the focus onto a subslice of the vector.
 636     ///
 637     /// `FocusMut::narrow(range)` has the same effect as `&slice[range]`, without
 638     /// actually modifying the underlying vector.
 639     ///
 640     /// Panics if the range isn't fully inside the current focus.
 641     ///
 642     /// ## Examples
 643     ///
 644     /// ```rust
 645     /// # #[macro_use] extern crate im_rc as im;
 646     /// # use im::vector::Vector;
 647     /// # use std::iter::FromIterator;
 648     /// # fn main() {
 649     /// let mut vec = Vector::from_iter(0..1000);
 650     /// let narrowed = vec.focus_mut().narrow(100..200);
 651     /// let narrowed_vec = narrowed.unmut().into_iter().cloned().collect();
 652     /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
 653     /// # }
 654     /// ```
 655     ///
 656     /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
 657     /// [Vector::split_at]: enum.Vector.html#method.split_at
 658     pub fn narrow<R>(self, range: R) -> Self
 659     where
 660         R: RangeBounds<usize>,
 661     {
 662         let r = to_range(&range, self.len());
 663         if r.start > r.end || r.start > self.len() {
 664             panic!("vector::FocusMut::narrow: range out of bounds");
 665         }
 666         match self {
 667             FocusMut::Single(chunk) => FocusMut::Single(&mut chunk[r]),
 668             FocusMut::Full(tree) => FocusMut::Full(tree.narrow(r)),
 669         }
 670     }
 671
 672     /// Split the focus into two.
 673     ///
 674     /// Given an index `index`, consume the focus and produce two new foci, the
 675     /// left onto indices `0..index`, and the right onto indices `index..N`
 676     /// where `N` is the length of the current focus.
 677     ///
 678     /// Panics if the index is out of bounds.
 679     ///
 680     /// This is the moral equivalent of [`slice::split_at`][slice::split_at], in
 681     /// that it leaves the underlying data structure unchanged, unlike
 682     /// [`Vector::split_at`][Vector::split_at].
 683     ///
 684     /// ## Examples
 685     ///
 686     /// ```rust
 687     /// # #[macro_use] extern crate im_rc as im;
 688     /// # use im::vector::Vector;
 689     /// # use std::iter::FromIterator;
 690     /// # fn main() {
 691     /// let mut vec = Vector::from_iter(0..1000);
 692     /// {
 693     ///     let (left, right) = vec.focus_mut().split_at(500);
 694     ///     for ptr in left {
 695     ///         *ptr += 100;
 696     ///     }
 697     ///     for ptr in right {
 698     ///         *ptr -= 100;
 699     ///     }
 700     /// }
 701     /// let expected = Vector::from_iter(100..600)
 702     ///              + Vector::from_iter(400..900);
 703     /// assert_eq!(expected, vec);
 704     /// # }
 705     /// ```
 706     ///
 707     /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
 708     /// [Vector::split_at]: enum.Vector.html#method.split_at
 709     pub fn split_at(self, index: usize) -> (Self, Self) {
 710         if index > self.len() {
 711             panic!("vector::FocusMut::split_at: index out of bounds");
 712         }
 713         match self {
 714             FocusMut::Single(chunk) => {
 715                 let (left, right) = chunk.split_at_mut(index);
 716                 (FocusMut::Single(left), FocusMut::Single(right))
 717             }
 718             FocusMut::Full(tree) => {
 719                 let (left, right) = tree.split_at(index);
 720                 (FocusMut::Full(left), FocusMut::Full(right))
 721             }
 722         }
 723     }
 724
 725     /// Convert a `FocusMut` into a `Focus`.
 726     pub fn unmut(self) -> Focus<'a, A> {
 727         match self {
 728             FocusMut::Single(chunk) => Focus::Single(chunk),
 729             FocusMut::Full(mut tree) => Focus::Full(TreeFocus {
 730                 tree: {
 731                     let t = tree.tree.lock().unwrap();
 732                     (*t).clone()
 733                 },
 734                 view: tree.view.clone(),
 735                 middle_range: tree.middle_range.clone(),
 736                 target_range: 0..0,
 737                 target_ptr: null(),
 738             }),
 739         }
 740     }
 741 }
 742
 743 impl<'a, A> IntoIterator for FocusMut<'a, A>
 744 where
 745     A: Clone + 'a,
 746 {
 747     type Item = &'a mut A;
 748     type IntoIter = IterMut<'a, A>;
 749
 750     fn into_iter(self) -> Self::IntoIter {
 751         IterMut::from_focus(self)
 752     }
 753 }
 754
 755 impl<'a, A> Into<Focus<'a, A>> for FocusMut<'a, A>
 756 where
 757     A: Clone + 'a,
 758 {
 759     fn into(self) -> Focus<'a, A> {
 760         self.unmut()
 761     }
 762 }
 763
 764 pub struct TreeFocusMut<'a, A>
 765 where
 766     A: 'a,
 767 {
 768     tree: Lock<&'a mut RRB<A>>,
 769     view: Range<usize>,
 770     middle_range: Range<usize>,
 771     target_range: Range<usize>,
 772     target_ptr: AtomicPtr<Chunk<A>>,
 773 }
 774
 775 impl<'a, A> TreeFocusMut<'a, A>
 776 where
 777     A: Clone + 'a,
 778 {
 779     fn new(tree: &'a mut RRB<A>) -> Self {
 780         let middle_start = tree.outer_f.len() + tree.inner_f.len();
 781         let middle_end = middle_start + tree.middle.len();
 782         TreeFocusMut {
 783             view: 0..tree.length,
 784             tree: Lock::new(tree),
 785             middle_range: middle_start..middle_end,
 786             target_range: 0..0,
 787             target_ptr: AtomicPtr::default(),
 788         }
 789     }
 790
 791     fn len(&self) -> usize {
 792         self.view.end - self.view.start
 793     }
 794
 795     fn narrow(self, mut view: Range<usize>) -> Self {
 796         view.start += self.view.start;
 797         view.end += self.view.start;
 798         TreeFocusMut {
 799             view,
 800             middle_range: self.middle_range.clone(),
 801             target_range: 0..0,
 802             target_ptr: AtomicPtr::default(),
 803             tree: self.tree,
 804         }
 805     }
 806
 807     fn split_at(self, index: usize) -> (Self, Self) {
 808         let len = self.len();
 809         debug_assert!(index <= len);
 810         #[allow(unsafe_code)]
 811         let left = TreeFocusMut {
 812             view: self.view.start..(self.view.start + index),
 813             middle_range: self.middle_range.clone(),
 814             target_range: 0..0,
 815             target_ptr: AtomicPtr::default(),
 816             tree: self.tree.clone(),
 817         };
 818         let right = TreeFocusMut {
 819             view: (self.view.start + index)..(self.view.start + len),
 820             middle_range: self.middle_range.clone(),
 821             target_range: 0..0,
 822             target_ptr: AtomicPtr::default(),
 823             tree: self.tree,
 824         };
 825         (left, right)
 826     }
 827
 828     fn physical_index(&self, index: usize) -> usize {
 829         debug_assert!(index < self.view.end);
 830         self.view.start + index
 831     }
 832
 833     fn logical_range(&self, range: &Range<usize>) -> Range<usize> {
 834         (range.start - self.view.start)..(range.end - self.view.start)
 835     }
 836
 837     fn set_focus(&mut self, index: usize) {
 838         let mut tree = self
 839             .tree
 840             .lock()
 841             .expect("im::vector::Focus::set_focus: unable to acquire exclusive lock on Vector");
 842         if index < self.middle_range.start {
 843             let outer_len = tree.outer_f.len();
 844             if index < outer_len {
 845                 self.target_range = 0..outer_len;
 846                 self.target_ptr
 847                     .store(Ref::make_mut(&mut tree.outer_f), Ordering::Relaxed);
 848             } else {
 849                 self.target_range = outer_len..self.middle_range.start;
 850                 self.target_ptr
 851                     .store(Ref::make_mut(&mut tree.inner_f), Ordering::Relaxed);
 852             }
 853         } else if index >= self.middle_range.end {
 854             let outer_start = self.middle_range.end + tree.inner_b.len();
 855             if index < outer_start {
 856                 self.target_range = self.middle_range.end..outer_start;
 857                 self.target_ptr
 858                     .store(Ref::make_mut(&mut tree.inner_b), Ordering::Relaxed);
 859             } else {
 860                 self.target_range = outer_start..tree.length;
 861                 self.target_ptr
 862                     .store(Ref::make_mut(&mut tree.outer_b), Ordering::Relaxed);
 863             }
 864         } else {
 865             let tree_index = index - self.middle_range.start;
 866             let level = tree.middle_level;
 867             let middle = Ref::make_mut(&mut tree.middle);
 868             let (range, ptr) = middle.lookup_chunk_mut(level, 0, tree_index);
 869             self.target_range =
 870                 (range.start + self.middle_range.start)..(range.end + self.middle_range.start);
 871             self.target_ptr.store(ptr, Ordering::Relaxed);
 872         }
 873     }
 874
 875     #[allow(unsafe_code)]
 876     fn get_focus(&mut self) -> &mut Chunk<A> {
 877         unsafe { &mut *self.target_ptr.load(Ordering::Relaxed) }
 878     }
 879
 880     pub fn get(&mut self, index: usize) -> Option<&mut A> {
 881         if index >= self.len() {
 882             return None;
 883         }
 884         let phys_index = self.physical_index(index);
 885         if !contains(&self.target_range, &phys_index) {
 886             self.set_focus(phys_index);
 887         }
 888         let target_phys_index = phys_index - self.target_range.start;
 889         Some(&mut self.get_focus()[target_phys_index])
 890     }
 891
 892     pub fn get_chunk(&mut self, index: usize) -> (Range<usize>, &mut [A]) {
 893         let phys_index = self.physical_index(index);
 894         if !contains(&self.target_range, &phys_index) {
 895             self.set_focus(phys_index);
 896         }
 897         let mut left = 0;
 898         let mut right = 0;
 899         if self.target_range.start < self.view.start {
 900             left = self.view.start - self.target_range.start;
 901         }
 902         if self.target_range.end > self.view.end {
 903             right = self.target_range.end - self.view.end;
 904         }
 905         let phys_range = (self.target_range.start + left)..(self.target_range.end - right);
 906         let log_range = self.logical_range(&phys_range);
 907         let slice_len = self.get_focus().len();
 908         let slice = &mut (self.get_focus().as_mut_slice())[left..(slice_len - right)];
 909         (log_range, slice)
 910     }
 911 }