diff options
| author | Aaron Turon <aturon@mozilla.com> | 2014-12-17 20:50:16 -0800 |
|---|---|---|
| committer | Aaron Turon <aturon@mozilla.com> | 2014-12-30 12:02:22 -0800 |
| commit | 4f863a338e0a7c33f81a8ac138103f1a0e8b33c5 (patch) | |
| tree | d4c5e6fa5c8cf9468d24b8927b94307425b1a2c5 | |
| parent | 9d919d2302b5df42e3bf8979560e0da21f4b2bad (diff) | |
| download | rust-4f863a338e0a7c33f81a8ac138103f1a0e8b33c5.tar.gz rust-4f863a338e0a7c33f81a8ac138103f1a0e8b33c5.zip | |
Second pass stabilization: slice
This commit takes a second pass through the `slice` module to stabilize its API. The changes are as follows: **Stable**: * `as_mut_slice` * `as_ptr`, `as_mut_ptr` * `binary_search_by` (was: `binary_search`) * `binary_search` (was: `binary_search_elem`) * `chunks`, `chunks_mut` * `contains` * `ends_with` * `first`, `first_mut` (was: `head`) * `get_unchecked`, `get_unchecked_mut` (was: `unsafe_get`) * `get` * `is_empty` * `iter`, `iter_mut` * `len` * `reverse` * `sort_by` * `sort` * `split_at`, `split_at_mut` * `split_mut`, `splitn_mut`, `rsplitn_mut` * `split`, `splitn`, `rsplitn` * `starts_with` * `swap` * `to_vec` * `windows` **Deprecated**: * `head`, `head_mut` (renamed as above) * `unsafe_get`, `unsafe_mut` (renamed as above) * `binary_search_elem` (renamed as above) * `partitioned`, deprecated in favor of a new, more general iterator consumer called `partition`. * `BinarySearchResult`, deprecated in favor of `Result<uint, uint>` [breaking-change]
| -rw-r--r-- | src/libcollections/slice.rs | 1380 | ||||
| -rw-r--r-- | src/libcore/slice.rs | 328 | ||||
| m--------- | src/rust-installer | 0 |
3 files changed, 886 insertions, 822 deletions
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index c55a8ba104e..ec522ae9e5a 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -96,601 +96,26 @@ use core::mem::size_of; use core::mem; use core::ops::{FnMut,SliceMut}; use core::prelude::{Clone, Greater, Iterator, IteratorExt, Less, None, Option}; -use core::prelude::{Ord, Ordering, PtrExt, Some, range}; +use core::prelude::{Ord, Ordering, RawPtr, Some, range, IteratorCloneExt, Result}; use core::ptr; use core::slice as core_slice; use self::Direction::*; use vec::Vec; -pub use core::slice::{Chunks, AsSlice, SplitsN, Windows}; +pub use core::slice::{Chunks, AsSlice, SplitN, Windows}; pub use core::slice::{Iter, IterMut, PartialEqSliceExt}; -pub use core::slice::{ImmutableIntSlice, MutableIntSlice}; -pub use core::slice::{MutSplits, MutChunks, Splits}; +pub use core::slice::{IntSliceExt, SplitMut, ChunksMut, Split}; +pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut}; pub use core::slice::{bytes, mut_ref_slice, ref_slice}; -pub use core::slice::{from_raw_buf, from_raw_mut_buf, BinarySearchResult}; +pub use core::slice::{from_raw_buf, from_raw_mut_buf}; -// Functional utilities - -#[allow(missing_docs)] -pub trait VectorVector<T> for Sized? { - // FIXME #5898: calling these .concat and .connect conflicts with - // StrVector::con{cat,nect}, since they have generic contents. - /// Flattens a vector of vectors of `T` into a single `Vec<T>`. - fn concat_vec(&self) -> Vec<T>; - - /// Concatenate a vector of vectors, placing a given separator between each. - fn connect_vec(&self, sep: &T) -> Vec<T>; -} - -impl<'a, T: Clone, V: AsSlice<T>> VectorVector<T> for [V] { - fn concat_vec(&self) -> Vec<T> { - let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len()); - let mut result = Vec::with_capacity(size); - for v in self.iter() { - result.push_all(v.as_slice()) - } - result - } - - fn connect_vec(&self, sep: &T) -> Vec<T> { - let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len()); - let mut result = Vec::with_capacity(size + self.len()); - let mut first = true; - for v in self.iter() { - if first { first = false } else { result.push(sep.clone()) } - result.push_all(v.as_slice()) - } - result - } -} - -/// An iterator that yields the element swaps needed to produce -/// a sequence of all possible permutations for an indexed sequence of -/// elements. Each permutation is only a single swap apart. -/// -/// The Steinhaus-Johnson-Trotter algorithm is used. -/// -/// Generates even and odd permutations alternately. -/// -/// The last generated swap is always (0, 1), and it returns the -/// sequence to its initial order. -pub struct ElementSwaps { - sdir: Vec<SizeDirection>, - /// If `true`, emit the last swap that returns the sequence to initial - /// state. - emit_reset: bool, - swaps_made : uint, -} - -impl ElementSwaps { - /// Creates an `ElementSwaps` iterator for a sequence of `length` elements. - pub fn new(length: uint) -> ElementSwaps { - // Initialize `sdir` with a direction that position should move in - // (all negative at the beginning) and the `size` of the - // element (equal to the original index). - ElementSwaps{ - emit_reset: true, - sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(), - swaps_made: 0 - } - } -} - -#[deriving(Copy)] -enum Direction { Pos, Neg } - -/// An `Index` and `Direction` together. -#[deriving(Copy)] -struct SizeDirection { - size: uint, - dir: Direction, -} - -impl Iterator<(uint, uint)> for ElementSwaps { - #[inline] - fn next(&mut self) -> Option<(uint, uint)> { - fn new_pos(i: uint, s: Direction) -> uint { - i + match s { Pos => 1, Neg => -1 } - } - - // Find the index of the largest mobile element: - // The direction should point into the vector, and the - // swap should be with a smaller `size` element. - let max = self.sdir.iter().map(|&x| x).enumerate() - .filter(|&(i, sd)| - new_pos(i, sd.dir) < self.sdir.len() && - self.sdir[new_pos(i, sd.dir)].size < sd.size) - .max_by(|&(_, sd)| sd.size); - match max { - Some((i, sd)) => { - let j = new_pos(i, sd.dir); - self.sdir.swap(i, j); - - // Swap the direction of each larger SizeDirection - for x in self.sdir.iter_mut() { - if x.size > sd.size { - x.dir = match x.dir { Pos => Neg, Neg => Pos }; - } - } - self.swaps_made += 1; - Some((i, j)) - }, - None => if self.emit_reset { - self.emit_reset = false; - if self.sdir.len() > 1 { - // The last swap - self.swaps_made += 1; - Some((0, 1)) - } else { - // Vector is of the form [] or [x], and the only permutation is itself - self.swaps_made += 1; - Some((0,0)) - } - } else { None } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option<uint>) { - // For a vector of size n, there are exactly n! permutations. - let n = range(2, self.sdir.len() + 1).product(); - (n - self.swaps_made, Some(n - self.swaps_made)) - } -} - -/// An iterator that uses `ElementSwaps` to iterate through -/// all possible permutations of a vector. -/// -/// The first iteration yields a clone of the vector as it is, -/// then each successive element is the vector with one -/// swap applied. -/// -/// Generates even and odd permutations alternately. -pub struct Permutations<T> { - swaps: ElementSwaps, - v: Vec<T>, -} - -impl<T: Clone> Iterator<Vec<T>> for Permutations<T> { - #[inline] - fn next(&mut self) -> Option<Vec<T>> { - match self.swaps.next() { - None => None, - Some((0,0)) => Some(self.v.clone()), - Some((a, b)) => { - let elt = self.v.clone(); - self.v.swap(a, b); - Some(elt) - } - } - } - - #[inline] - fn size_hint(&self) -> (uint, Option<uint>) { - self.swaps.size_hint() - } -} - -/// Extension methods for boxed slices. -pub trait BoxedSliceExt<T> { - /// Convert `self` into a vector without clones or allocation. - fn into_vec(self) -> Vec<T>; -} - -impl<T> BoxedSliceExt<T> for Box<[T]> { - #[experimental] - fn into_vec(mut self) -> Vec<T> { - unsafe { - let xs = Vec::from_raw_parts(self.as_mut_ptr(), self.len(), self.len()); - mem::forget(self); - xs - } - } -} - -/// Allocating extension methods for slices containing `Clone` elements. -pub trait CloneSliceExt<T> for Sized? { - /// Copies `self` into a new `Vec`. - fn to_vec(&self) -> Vec<T>; - - /// Partitions the vector into two vectors `(a, b)`, where all - /// elements of `a` satisfy `f` and all elements of `b` do not. - fn partitioned<F>(&self, f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool; - - /// Creates an iterator that yields every possible permutation of the - /// vector in succession. - /// - /// # Examples - /// - /// ```rust - /// let v = [1i, 2, 3]; - /// let mut perms = v.permutations(); - /// - /// for p in perms { - /// println!("{}", p); - /// } - /// ``` - /// - /// Iterating through permutations one by one. - /// - /// ```rust - /// let v = [1i, 2, 3]; - /// let mut perms = v.permutations(); - /// - /// assert_eq!(Some(vec![1i, 2, 3]), perms.next()); - /// assert_eq!(Some(vec![1i, 3, 2]), perms.next()); - /// assert_eq!(Some(vec![3i, 1, 2]), perms.next()); - /// ``` - fn permutations(&self) -> Permutations<T>; - - /// Copies as many elements from `src` as it can into `self` (the - /// shorter of `self.len()` and `src.len()`). Returns the number - /// of elements copied. - /// - /// # Example - /// - /// ```rust - /// let mut dst = [0i, 0, 0]; - /// let src = [1i, 2]; - /// - /// assert!(dst.clone_from_slice(&src) == 2); - /// assert!(dst == [1, 2, 0]); - /// - /// let src2 = [3i, 4, 5, 6]; - /// assert!(dst.clone_from_slice(&src2) == 3); - /// assert!(dst == [3i, 4, 5]); - /// ``` - fn clone_from_slice(&mut self, &[T]) -> uint; -} - -impl<T: Clone> CloneSliceExt<T> for [T] { - /// Returns a copy of `v`. - #[inline] - fn to_vec(&self) -> Vec<T> { - let mut vector = Vec::with_capacity(self.len()); - vector.push_all(self); - vector - } - - - #[inline] - fn partitioned<F>(&self, mut f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool { - let mut lefts = Vec::new(); - let mut rights = Vec::new(); - - for elt in self.iter() { - if f(elt) { - lefts.push((*elt).clone()); - } else { - rights.push((*elt).clone()); - } - } - - (lefts, rights) - } - - /// Returns an iterator over all permutations of a vector. - fn permutations(&self) -> Permutations<T> { - Permutations{ - swaps: ElementSwaps::new(self.len()), - v: self.to_vec(), - } - } - - fn clone_from_slice(&mut self, src: &[T]) -> uint { - core_slice::CloneSliceExt::clone_from_slice(self, src) - } -} - -fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering { - let len = v.len() as int; - let buf_v = v.as_mut_ptr(); - - // 1 <= i < len; - for i in range(1, len) { - // j satisfies: 0 <= j <= i; - let mut j = i; - unsafe { - // `i` is in bounds. - let read_ptr = buf_v.offset(i) as *const T; - - // find where to insert, we need to do strict <, - // rather than <=, to maintain stability. - - // 0 <= j - 1 < len, so .offset(j - 1) is in bounds. - while j > 0 && - compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less { - j -= 1; - } - - // shift everything to the right, to make space to - // insert this value. - - // j + 1 could be `len` (for the last `i`), but in - // that case, `i == j` so we don't copy. The - // `.offset(j)` is always in bounds. - - if i != j { - let tmp = ptr::read(read_ptr); - ptr::copy_memory(buf_v.offset(j + 1), - &*buf_v.offset(j), - (i - j) as uint); - ptr::copy_nonoverlapping_memory(buf_v.offset(j), - &tmp as *const T, - 1); - mem::forget(tmp); - } - } - } -} - -fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering { - // warning: this wildly uses unsafe. - static BASE_INSERTION: uint = 32; - static LARGE_INSERTION: uint = 16; - - // FIXME #12092: smaller insertion runs seems to make sorting - // vectors of large elements a little faster on some platforms, - // but hasn't been tested/tuned extensively - let insertion = if size_of::<T>() <= 16 { - BASE_INSERTION - } else { - LARGE_INSERTION - }; - - let len = v.len(); - - // short vectors get sorted in-place via insertion sort to avoid allocations - if len <= insertion { - insertion_sort(v, compare); - return; - } - - // allocate some memory to use as scratch memory, we keep the - // length 0 so we can keep shallow copies of the contents of `v` - // without risking the dtors running on an object twice if - // `compare` panics. - let mut working_space = Vec::with_capacity(2 * len); - // these both are buffers of length `len`. - let mut buf_dat = working_space.as_mut_ptr(); - let mut buf_tmp = unsafe {buf_dat.offset(len as int)}; - - // length `len`. - let buf_v = v.as_ptr(); - - // step 1. sort short runs with insertion sort. This takes the - // values from `v` and sorts them into `buf_dat`, leaving that - // with sorted runs of length INSERTION. - - // We could hardcode the sorting comparisons here, and we could - // manipulate/step the pointers themselves, rather than repeatedly - // .offset-ing. - for start in range_step(0, len, insertion) { - // start <= i < len; - for i in range(start, cmp::min(start + insertion, len)) { - // j satisfies: start <= j <= i; - let mut j = i as int; - unsafe { - // `i` is in bounds. - let read_ptr = buf_v.offset(i as int); - - // find where to insert, we need to do strict <, - // rather than <=, to maintain stability. - - // start <= j - 1 < len, so .offset(j - 1) is in - // bounds. - while j > start as int && - compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less { - j -= 1; - } - - // shift everything to the right, to make space to - // insert this value. - - // j + 1 could be `len` (for the last `i`), but in - // that case, `i == j` so we don't copy. The - // `.offset(j)` is always in bounds. - ptr::copy_memory(buf_dat.offset(j + 1), - &*buf_dat.offset(j), - i - j as uint); - ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1); - } - } - } - - // step 2. merge the sorted runs. - let mut width = insertion; - while width < len { - // merge the sorted runs of length `width` in `buf_dat` two at - // a time, placing the result in `buf_tmp`. - - // 0 <= start <= len. - for start in range_step(0, len, 2 * width) { - // manipulate pointers directly for speed (rather than - // using a `for` loop with `range` and `.offset` inside - // that loop). - unsafe { - // the end of the first run & start of the - // second. Offset of `len` is defined, since this is - // precisely one byte past the end of the object. - let right_start = buf_dat.offset(cmp::min(start + width, len) as int); - // end of the second. Similar reasoning to the above re safety. - let right_end_idx = cmp::min(start + 2 * width, len); - let right_end = buf_dat.offset(right_end_idx as int); - - // the pointers to the elements under consideration - // from the two runs. - - // both of these are in bounds. - let mut left = buf_dat.offset(start as int); - let mut right = right_start; - - // where we're putting the results, it is a run of - // length `2*width`, so we step it once for each step - // of either `left` or `right`. `buf_tmp` has length - // `len`, so these are in bounds. - let mut out = buf_tmp.offset(start as int); - let out_end = buf_tmp.offset(right_end_idx as int); - - while out < out_end { - // Either the left or the right run are exhausted, - // so just copy the remainder from the other run - // and move on; this gives a huge speed-up (order - // of 25%) for mostly sorted vectors (the best - // case). - if left == right_start { - // the number remaining in this run. - let elems = (right_end as uint - right as uint) / mem::size_of::<T>(); - ptr::copy_nonoverlapping_memory(out, &*right, elems); - break; - } else if right == right_end { - let elems = (right_start as uint - left as uint) / mem::size_of::<T>(); - ptr::copy_nonoverlapping_memory(out, &*left, elems); - break; - } - - // check which side is smaller, and that's the - // next element for the new run. - - // `left < right_start` and `right < right_end`, - // so these are valid. - let to_copy = if compare(&*left, &*right) == Greater { - step(&mut right) - } else { - step(&mut left) - }; - ptr::copy_nonoverlapping_memory(out, &*to_copy, 1); - step(&mut out); - } - } - } - - mem::swap(&mut buf_dat, &mut buf_tmp); - - width *= 2; - } - - // write the result to `v` in one go, so that there are never two copies - // of the same object in `v`. - unsafe { - ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len); - } - - // increment the pointer, returning the old pointer. - #[inline(always)] - unsafe fn step<T>(ptr: &mut *mut T) -> *mut T { - let old = *ptr; - *ptr = ptr.offset(1); - old - } -} - -/// Allocating extension methods for slices on Ord values. -#[experimental = "likely to merge with other traits"] -pub trait OrdSliceExt<T> for Sized? { - /// Sorts the slice, in place. - /// - /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`. - /// - /// # Examples - /// - /// ```rust - /// let mut v = [-5i, 4, 1, -3, 2]; - /// - /// v.sort(); - /// assert!(v == [-5i, -3, 1, 2, 4]); - /// ``` - #[experimental] - fn sort(&mut self); - - /// Binary search a sorted slice for a given element. - /// - /// If the value is found then `Found` is returned, containing the - /// index of the matching element; if the value is not found then - /// `NotFound` is returned, containing the index where a matching - /// element could be inserted while maintaining sorted order. - /// - /// # Example - /// - /// Looks up a series of four elements. The first is found, with a - /// uniquely determined position; the second and third are not - /// found; the fourth could match any position in `[1,4]`. - /// - /// ```rust - /// use std::slice::BinarySearchResult::{Found, NotFound}; - /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; - /// let s = s.as_slice(); - /// - /// assert_eq!(s.binary_search_elem(&13), Found(9)); - /// assert_eq!(s.binary_search_elem(&4), NotFound(7)); - /// assert_eq!(s.binary_search_elem(&100), NotFound(13)); - /// let r = s.binary_search_elem(&1); - /// assert!(match r { Found(1...4) => true, _ => false, }); - /// ``` - #[unstable = "name likely to change"] - fn binary_search_elem(&self, x: &T) -> BinarySearchResult; - - /// Mutates the slice to the next lexicographic permutation. - /// - /// Returns `true` if successful and `false` if the slice is at the - /// last-ordered permutation. - /// - /// # Example - /// - /// ```rust - /// let v: &mut [_] = &mut [0i, 1, 2]; - /// v.next_permutation(); - /// let b: &mut [_] = &mut [0i, 2, 1]; - /// assert!(v == b); - /// v.next_permutation(); - /// let b: &mut [_] = &mut [1i, 0, 2]; - /// assert!(v == b); - /// ``` - #[experimental] - fn next_permutation(&mut self) -> bool; - - /// Mutates the slice to the previous lexicographic permutation. - /// - /// Returns `true` if successful and `false` if the slice is at the - /// first-ordered permutation. - /// - /// # Example - /// - /// ```rust - /// let v: &mut [_] = &mut [1i, 0, 2]; - /// v.prev_permutation(); - /// let b: &mut [_] = &mut [0i, 2, 1]; - /// assert!(v == b); - /// v.prev_permutation(); - /// let b: &mut [_] = &mut [0i, 1, 2]; - /// assert!(v == b); - /// ``` - #[experimental] - fn prev_permutation(&mut self) -> bool; -} - -impl<T: Ord> OrdSliceExt<T> for [T] { - #[inline] - fn sort(&mut self) { - self.sort_by(|a, b| a.cmp(b)) - } - - fn binary_search_elem(&self, x: &T) -> BinarySearchResult { - core_slice::OrdSliceExt::binary_search_elem(self, x) - } - - fn next_permutation(&mut self) -> bool { - core_slice::OrdSliceExt::next_permutation(self) - } - - fn prev_permutation(&mut self) -> bool { - core_slice::OrdSliceExt::prev_permutation(self) - } -} +//////////////////////////////////////////////////////////////////////////////// +// Basic slice extension methods +//////////////////////////////////////////////////////////////////////////////// /// Allocating extension methods for slices. -#[experimental = "likely to merge with other traits"] +#[unstable = "needs associated types, may merge with other traits"] pub trait SliceExt<T> for Sized? { /// Sorts the slice, in place, using `compare` to compare /// elements. @@ -709,6 +134,7 @@ pub trait SliceExt<T> for Sized? { /// v.sort_by(|a, b| b.cmp(a)); /// assert!(v == [5, 4, 3, 2, 1]); /// ``` + #[stable] fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering; /// Consumes `src` and moves as many elements as it can into `self` @@ -732,6 +158,7 @@ pub trait SliceExt<T> for Sized? { /// assert_eq!(num_moved, 3); /// assert!(a == [6i, 7, 8, 4, 5]); /// ``` + #[experimental = "uncertain about this API approach"] fn move_from(&mut self, src: Vec<T>, start: uint, end: uint) -> uint; /// Returns a subslice spanning the interval [`start`, `end`). @@ -740,7 +167,7 @@ pub trait SliceExt<T> for Sized? { /// original slice (i.e. when `end > self.len()`) or when `start > end`. /// /// Slicing with `start` equal to `end` yields an empty slice. - #[unstable = "waiting on final error conventions/slicing syntax"] + #[experimental = "will be replaced by slice syntax"] fn slice(&self, start: uint, end: uint) -> &[T]; /// Returns a subslice from `start` to the end of the slice. @@ -748,7 +175,7 @@ pub trait SliceExt<T> for Sized? { /// Panics when `start` is strictly greater than the length of the original slice. /// /// Slicing from `self.len()` yields an empty slice. - #[unstable = "waiting on final error conventions/slicing syntax"] + #[experimental = "will be replaced by slice syntax"] fn slice_from(&self, start: uint) -> &[T]; /// Returns a subslice from the start of the slice to `end`. @@ -756,7 +183,7 @@ pub trait SliceExt<T> for Sized? { /// Panics when `end` is strictly greater than the length of the original slice. /// /// Slicing to `0` yields an empty slice. - #[unstable = "waiting on final error conventions/slicing syntax"] + #[experimental = "will be replaced by slice syntax"] fn slice_to(&self, end: uint) -> &[T]; /// Divides one slice into two at an index. @@ -766,32 +193,32 @@ pub trait SliceExt<T> for Sized? { /// indices from `[mid, len)` (excluding the index `len` itself). /// /// Panics if `mid > len`. - #[unstable = "waiting on final error conventions"] + #[stable] fn split_at(&self, mid: uint) -> (&[T], &[T]); /// Returns an iterator over the slice - #[unstable = "iterator type may change"] + #[stable] fn iter(&self) -> Iter<T>; /// Returns an iterator over subslices separated by elements that match /// `pred`. The matched element is not contained in the subslices. - #[unstable = "iterator type may change, waiting on unboxed closures"] - fn split<F>(&self, pred: F) -> Splits<T, F> + #[stable] + fn split<F>(&self, pred: F) -> Split<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over subslices separated by elements that match /// `pred`, limited to splitting at most `n` times. The matched element is /// not contained in the subslices. - #[unstable = "iterator type may change"] - fn splitn<F>(&self, n: uint, pred: F) -> SplitsN<Splits<T, F>> + #[stable] + fn splitn<F>(&self, n: uint, pred: F) -> SplitN<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over subslices separated by elements that match /// `pred` limited to splitting at most `n` times. This starts at the end of /// the slice and works backwards. The matched element is not contained in /// the subslices. - #[unstable = "iterator type may change"] - fn rsplitn<F>(&self, n: uint, pred: F) -> SplitsN<Splits<T, F>> + #[stable] + fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over all contiguous windows of length @@ -813,7 +240,7 @@ pub trait SliceExt<T> for Sized? { /// println!("{}", win); /// } /// ``` - #[unstable = "iterator type may change"] + #[stable] fn windows(&self, size: uint) -> Windows<T>; /// Returns an iterator over `size` elements of the slice at a @@ -836,34 +263,44 @@ pub trait SliceExt<T> for Sized? { /// println!("{}", win); /// } /// ``` - #[unstable = "iterator type may change"] + #[stable] fn chunks(&self, size: uint) -> Chunks<T>; /// Returns the element of a slice at the given index, or `None` if the /// index is out of bounds. - #[unstable = "waiting on final collection conventions"] + #[stable] fn get(&self, index: uint) -> Option<&T>; /// Returns the first element of a slice, or `None` if it is empty. - #[unstable = "name may change"] - fn head(&self) -> Option<&T>; + #[stable] + fn first(&self) -> Option<&T>; + + /// Deprecated: renamed to `first`. + #[deprecated = "renamed to `first`"] + fn head(&self) -> Option<&T> { self.first() } /// Returns all but the first element of a slice. - #[unstable = "name may change"] + #[experimental = "likely to be renamed"] fn tail(&self) -> &[T]; /// Returns all but the last element of a slice. - #[unstable = "name may change"] + #[experimental = "likely to be renamed"] fn init(&self) -> &[T]; /// Returns the last element of a slice, or `None` if it is empty. - #[unstable = "name may change"] + #[stable] fn last(&self) -> Option<&T>; /// Returns a pointer to the element at the given index, without doing /// bounds checking. - #[unstable] - unsafe fn unsafe_get(&self, index: uint) -> &T; + #[stable] + unsafe fn get_unchecked(&self, index: uint) -> &T; + + /// Deprecated: renamed to `get_unchecked`. + #[deprecated = "renamed to get_unchecked"] + unsafe fn unsafe_get(&self, index: uint) -> &T { + self.get_unchecked(index) + } /// Returns an unsafe pointer to the slice's buffer /// @@ -872,7 +309,7 @@ pub trait SliceExt<T> for Sized? { /// /// Modifying the slice may cause its buffer to be reallocated, which /// would also make any pointers to it invalid. - #[unstable] + #[stable] fn as_ptr(&self) -> *const T; /// Binary search a sorted slice with a comparator function. @@ -882,9 +319,9 @@ pub trait SliceExt<T> for Sized? { /// order code that indicates whether its argument is `Less`, /// `Equal` or `Greater` the desired target. /// - /// If a matching value is found then returns `Found`, containing + /// If a matching value is found then returns `Ok`, containing /// the index for the matched element; if no match is found then - /// `NotFound` is returned, containing the index where a matching + /// `Err` is returned, containing the index where a matching /// element could be inserted while maintaining sorted order. /// /// # Example @@ -894,23 +331,22 @@ pub trait SliceExt<T> for Sized? { /// found; the fourth could match any position in `[1,4]`. /// /// ```rust - /// use std::slice::BinarySearchResult::{Found, NotFound}; /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; /// let s = s.as_slice(); /// /// let seek = 13; - /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), Found(9)); + /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9)); /// let seek = 4; - /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(7)); + /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7)); /// let seek = 100; - /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(13)); + /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13)); /// let seek = 1; - /// let r = s.binary_search(|probe| probe.cmp(&seek)); - /// assert!(match r { Found(1...4) => true, _ => false, }); + /// let r = s.binary_search_by(|probe| probe.cmp(&seek)); + /// assert!(match r { Ok(1...4) => true, _ => false, }); /// ``` - #[unstable = "waiting on unboxed closures"] - fn binary_search<F>(&self, f: F) -> BinarySearchResult - where F: FnMut(&T) -> Ordering; + #[stable] + fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where + F: FnMut(&T) -> Ordering; /// Return the number of elements in the slice /// @@ -920,7 +356,7 @@ pub trait SliceExt<T> for Sized? { /// let a = [1i, 2, 3]; /// assert_eq!(a.len(), 3); /// ``` - #[experimental = "not triaged yet"] + #[stable] fn len(&self) -> uint; /// Returns true if the slice has a length of 0 @@ -932,15 +368,16 @@ pub trait SliceExt<T> for Sized? { /// assert!(!a.is_empty()); /// ``` #[inline] - #[experimental = "not triaged yet"] + #[stable] fn is_empty(&self) -> bool { self.len() == 0 } /// Returns a mutable reference to the element at the given index, /// or `None` if the index is out of bounds - #[unstable = "waiting on final error conventions"] + #[stable] fn get_mut(&mut self, index: uint) -> Option<&mut T>; /// Work with `self` as a mut slice. /// Primarily intended for getting a &mut [T] from a [T, ..N]. + #[stable] fn as_mut_slice(&mut self) -> &mut [T]; /// Returns a mutable subslice spanning the interval [`start`, `end`). @@ -949,7 +386,7 @@ pub trait SliceExt<T> for Sized? { /// original slice (i.e. when `end > self.len()`) or when `start > end`. /// /// Slicing with `start` equal to `end` yields an empty slice. - #[unstable = "waiting on final error conventions"] + #[experimental = "will be replaced by slice syntax"] fn slice_mut(&mut self, start: uint, end: uint) -> &mut [T]; /// Returns a mutable subslice from `start` to the end of the slice. @@ -957,7 +394,7 @@ pub trait SliceExt<T> for Sized? { /// Panics when `start` is strictly greater than the length of the original slice. /// /// Slicing from `self.len()` yields an empty slice. - #[unstable = "waiting on final error conventions"] + #[experimental = "will be replaced by slice syntax"] fn slice_from_mut(&mut self, start: uint) -> &mut [T]; /// Returns a mutable subslice from the start of the slice to `end`. @@ -965,48 +402,54 @@ pub trait SliceExt<T> for Sized? { /// Panics when `end` is strictly greater than the length of the original slice. /// /// Slicing to `0` yields an empty slice. - #[unstable = "waiting on final error conventions"] + #[experimental = "will be replaced by slice syntax"] fn slice_to_mut(&mut self, end: uint) -> &mut [T]; /// Returns an iterator that allows modifying each value - #[unstable = "waiting on iterator type name conventions"] + #[stable] fn iter_mut(&mut self) -> IterMut<T>; /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty - #[unstable = "name may change"] - fn head_mut(&mut self) -> Option<&mut T>; + #[stable] + fn first_mut(&mut self) -> Option<&mut T>; + + /// Depreated: renamed to `first_mut`. + #[deprecated = "renamed to first_mut"] + fn head_mut(&mut self) -> Option<&mut T> { + self.first_mut() + } /// Returns all but the first element of a mutable slice - #[unstable = "name may change"] + #[experimental = "likely to be renamed or removed"] fn tail_mut(&mut self) -> &mut [T]; /// Returns all but the last element of a mutable slice - #[unstable = "name may change"] + #[experimental = "likely to be renamed or removed"] fn init_mut(&mut self) -> &mut [T]; /// Returns a mutable pointer to the last item in the slice. - #[unstable = "name may change"] + #[stable] fn last_mut(&mut self) -> Option<&mut T>; /// Returns an iterator over mutable subslices separated by elements that /// match `pred`. The matched element is not contained in the subslices. - #[unstable = "waiting on unboxed closures, iterator type name conventions"] - fn split_mut<F>(&mut self, pred: F) -> MutSplits<T, F> + #[stable] + fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over subslices separated by elements that match /// `pred`, limited to splitting at most `n` times. The matched element is /// not contained in the subslices. - #[unstable = "waiting on unboxed closures, iterator type name conventions"] - fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitsN<MutSplits<T, F>> + #[stable] + fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over subslices separated by elements that match /// `pred` limited to splitting at most `n` times. This starts at the end of /// the slice and works backwards. The matched element is not contained in /// the subslices. - #[unstable = "waiting on unboxed closures, iterator type name conventions"] - fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> SplitsN<MutSplits<T, F>> + #[stable] + fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> RSplitNMut<T, F> where F: FnMut(&T) -> bool; /// Returns an iterator over `chunk_size` elements of the slice at a time. @@ -1017,18 +460,20 @@ pub trait SliceExt<T> for Sized? { /// # Panics /// /// Panics if `chunk_size` is 0. - #[unstable = "waiting on iterator type name conventions"] - fn chunks_mut(&mut self, chunk_size: uint) -> MutChunks<T>; + #[stable] + fn chunks_mut(&mut self, chunk_size: uint) -> ChunksMut<T>; /// Swaps two elements in a slice. /// - /// Panics if `a` or `b` are out of bounds. - /// /// # Arguments /// /// * a - The index of the first element /// * b - The index of the second element /// + /// # Panics + /// + /// Panics if `a` or `b` are out of bounds. + /// /// # Example /// /// ```rust @@ -1036,7 +481,7 @@ pub trait SliceExt<T> for Sized? { /// v.swap(1, 3); /// assert!(v == ["a", "d", "c", "b"]); /// ``` - #[unstable = "waiting on final error conventions"] + #[stable] fn swap(&mut self, a: uint, b: uint); /// Divides one `&mut` into two at an index. @@ -1045,6 +490,8 @@ pub trait SliceExt<T> for Sized? { /// the index `mid` itself) and the second will contain all /// indices from `[mid, len)` (excluding the index `len` itself). /// + /// # Panics + /// /// Panics if `mid > len`. /// /// # Example @@ -1071,7 +518,7 @@ pub trait SliceExt<T> for Sized? { /// assert!(right == []); /// } /// ``` - #[unstable = "waiting on final error conventions"] + #[stable] fn split_at_mut(&mut self, mid: uint) -> (&mut [T], &mut [T]); /// Reverse the order of elements in a slice, in place. @@ -1083,12 +530,18 @@ pub trait SliceExt<T> for Sized? { /// v.reverse(); /// assert!(v == [3i, 2, 1]); /// ``` - #[experimental = "may be moved to iterators instead"] + #[stable] fn reverse(&mut self); /// Returns an unsafe mutable pointer to the element in index - #[experimental = "waiting on unsafe conventions"] - unsafe fn unsafe_mut(&mut self, index: uint) -> &mut T; + #[stable] + unsafe fn get_unchecked_mut(&mut self, index: uint) -> &mut T; + + /// Deprecated: renamed to `get_unchecked_mut`. + #[deprecated = "renamed to get_unchecked_mut"] + unsafe fn unchecked_mut(&mut self, index: uint) -> &mut T { + self.get_unchecked_mut(index) + } /// Return an unsafe mutable pointer to the slice's buffer. /// @@ -1098,10 +551,11 @@ pub trait SliceExt<T> for Sized? { /// Modifying the slice may cause its buffer to be reallocated, which /// would also make any pointers to it invalid. #[inline] - #[unstable] + #[stable] fn as_mut_ptr(&mut self) -> *mut T; } +#[unstable = "trait is unstable"] impl<T> SliceExt<T> for [T] { #[inline] fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering { @@ -1142,19 +596,19 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn split<F>(&self, pred: F) -> Splits<T, F> + fn split<F>(&self, pred: F) -> Split<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::split(self, pred) } #[inline] - fn splitn<F>(&self, n: uint, pred: F) -> SplitsN<Splits<T, F>> + fn splitn<F>(&self, n: uint, pred: F) -> SplitN<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::splitn(self, n, pred) } #[inline] - fn rsplitn<F>(&self, n: uint, pred: F) -> SplitsN<Splits<T, F>> + fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::rsplitn(self, n, pred) } @@ -1175,8 +629,8 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn head<'a>(&'a self) -> Option<&'a T> { - core_slice::SliceExt::head(self) + fn first<'a>(&'a self) -> Option<&'a T> { + core_slice::SliceExt::first(self) } #[inline] @@ -1195,8 +649,8 @@ impl<T> SliceExt<T> for [T] { } #[inline] - unsafe fn unsafe_get<'a>(&'a self, index: uint) -> &'a T { - core_slice::SliceExt::unsafe_get(self, index) + unsafe fn get_unchecked<'a>(&'a self, index: uint) -> &'a T { + core_slice::SliceExt::get_unchecked(self, index) } #[inline] @@ -1205,9 +659,9 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn binary_search<F>(&self, f: F) -> BinarySearchResult + fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where F: FnMut(&T) -> Ordering { - core_slice::SliceExt::binary_search(self, f) + core_slice::SliceExt::binary_search_by(self, f) } #[inline] @@ -1251,8 +705,8 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn head_mut<'a>(&'a mut self) -> Option<&'a mut T> { - core_slice::SliceExt::head_mut(self) + fn first_mut<'a>(&'a mut self) -> Option<&'a mut T> { + core_slice::SliceExt::first_mut(self) } #[inline] @@ -1271,25 +725,25 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn split_mut<F>(&mut self, pred: F) -> MutSplits<T, F> + fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::split_mut(self, pred) } #[inline] - fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitsN<MutSplits<T, F>> + fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::splitn_mut(self, n, pred) } #[inline] - fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> SplitsN<MutSplits<T, F>> + fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> RSplitNMut<T, F> where F: FnMut(&T) -> bool { core_slice::SliceExt::rsplitn_mut(self, n, pred) } #[inline] - fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> MutChunks<'a, T> { + fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> ChunksMut<'a, T> { core_slice::SliceExt::chunks_mut(self, chunk_size) } @@ -1309,8 +763,8 @@ impl<T> SliceExt<T> for [T] { } #[inline] - unsafe fn unsafe_mut<'a>(&'a mut self, index: uint) -> &'a mut T { - core_slice::SliceExt::unsafe_mut(self, index) + unsafe fn get_unchecked_mut<'a>(&'a mut self, index: uint) -> &'a mut T { + core_slice::SliceExt::get_unchecked_mut(self, index) } #[inline] @@ -1319,6 +773,297 @@ impl<T> SliceExt<T> for [T] { } } +//////////////////////////////////////////////////////////////////////////////// +// Extension traits for slices over specifc kinds of data +//////////////////////////////////////////////////////////////////////////////// + +/// Extension methods for boxed slices. +#[experimental = "likely to merge into SliceExt if it survives"] +pub trait BoxedSliceExt<T> { + /// Convert `self` into a vector without clones or allocation. + #[experimental] + fn into_vec(self) -> Vec<T>; +} + +#[experimental = "trait is experimental"] +impl<T> BoxedSliceExt<T> for Box<[T]> { + fn into_vec(mut self) -> Vec<T> { + unsafe { + let xs = Vec::from_raw_parts(self.as_mut_ptr(), self.len(), self.len()); + mem::forget(self); + xs + } + } +} + +/// Allocating extension methods for slices containing `Clone` elements. +#[unstable = "likely to be merged into SliceExt"] +pub trait CloneSliceExt<T> for Sized? { + /// Copies `self` into a new `Vec`. + #[stable] + fn to_vec(&self) -> Vec<T>; + + /// Deprecated: use `iter().cloned().partition(f)` instead. + #[deprecated = "use iter().cloned().partition(f) instead"] + fn partitioned<F>(&self, f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool; + + /// Creates an iterator that yields every possible permutation of the + /// vector in succession. + /// + /// # Examples + /// + /// ```rust + /// let v = [1i, 2, 3]; + /// let mut perms = v.permutations(); + /// + /// for p in perms { + /// println!("{}", p); + /// } + /// ``` + /// + /// Iterating through permutations one by one. + /// + /// ```rust + /// let v = [1i, 2, 3]; + /// let mut perms = v.permutations(); + /// + /// assert_eq!(Some(vec![1i, 2, 3]), perms.next()); + /// assert_eq!(Some(vec![1i, 3, 2]), perms.next()); + /// assert_eq!(Some(vec![3i, 1, 2]), perms.next()); + /// ``` + #[stable] + fn permutations(&self) -> Permutations<T>; + + /// Copies as many elements from `src` as it can into `self` (the + /// shorter of `self.len()` and `src.len()`). Returns the number + /// of elements copied. + /// + /// # Example + /// + /// ```rust + /// let mut dst = [0i, 0, 0]; + /// let src = [1i, 2]; + /// + /// assert!(dst.clone_from_slice(&src) == 2); + /// assert!(dst == [1, 2, 0]); + /// + /// let src2 = [3i, 4, 5, 6]; + /// assert!(dst.clone_from_slice(&src2) == 3); + /// assert!(dst == [3i, 4, 5]); + /// ``` + #[experimental] + fn clone_from_slice(&mut self, &[T]) -> uint; +} + +#[unstable = "trait is unstable"] +impl<T: Clone> CloneSliceExt<T> for [T] { + /// Returns a copy of `v`. + #[inline] + fn to_vec(&self) -> Vec<T> { + let mut vector = Vec::with_capacity(self.len()); + vector.push_all(self); + vector + } + + + #[inline] + fn partitioned<F>(&self, f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool { + self.iter().cloned().partition(f) + } + + /// Returns an iterator over all permutations of a vector. + fn permutations(&self) -> Permutations<T> { + Permutations{ + swaps: ElementSwaps::new(self.len()), + v: self.to_vec(), + } + } + + fn clone_from_slice(&mut self, src: &[T]) -> uint { + core_slice::CloneSliceExt::clone_from_slice(self, src) + } +} + +/// Allocating extension methods for slices on Ord values. +#[unstable = "likely to merge with SliceExt"] +pub trait OrdSliceExt<T> for Sized? { + /// Sorts the slice, in place. + /// + /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`. + /// + /// # Examples + /// + /// ```rust + /// let mut v = [-5i, 4, 1, -3, 2]; + /// + /// v.sort(); + /// assert!(v == [-5i, -3, 1, 2, 4]); + /// ``` + #[stable] + fn sort(&mut self); + + /// Binary search a sorted slice for a given element. + /// + /// If the value is found then `Ok` is returned, containing the + /// index of the matching element; if the value is not found then + /// `Err` is returned, containing the index where a matching + /// element could be inserted while maintaining sorted order. + /// + /// # Example + /// + /// Looks up a series of four elements. The first is found, with a + /// uniquely determined position; the second and third are not + /// found; the fourth could match any position in `[1,4]`. + /// + /// ```rust + /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; + /// let s = s.as_slice(); + /// + /// assert_eq!(s.binary_search(&13), Ok(9)); + /// assert_eq!(s.binary_search(&4), Err(7)); + /// assert_eq!(s.binary_search(&100), Err(13)); + /// let r = s.binary_search(&1); + /// assert!(match r { Ok(1...4) => true, _ => false, }); + /// ``` + #[stable] + fn binary_search(&self, x: &T) -> Result<uint, uint>; + + /// Deprecated: use `binary_search` instead. + #[deprecated = "use binary_search instead"] + fn binary_search_elem(&self, x: &T) -> Result<uint, uint> { + self.binary_search(x) + } + + /// Mutates the slice to the next lexicographic permutation. + /// + /// Returns `true` if successful and `false` if the slice is at the + /// last-ordered permutation. + /// + /// # Example + /// + /// ```rust + /// let v: &mut [_] = &mut [0i, 1, 2]; + /// v.next_permutation(); + /// let b: &mut [_] = &mut [0i, 2, 1]; + /// assert!(v == b); + /// v.next_permutation(); + /// let b: &mut [_] = &mut [1i, 0, 2]; + /// assert!(v == b); + /// ``` + #[stable] + fn next_permutation(&mut self) -> bool; + + /// Mutates the slice to the previous lexicographic permutation. + /// + /// Returns `true` if successful and `false` if the slice is at the + /// first-ordered permutation. + /// + /// # Example + /// + /// ```rust + /// let v: &mut [_] = &mut [1i, 0, 2]; + /// v.prev_permutation(); + /// let b: &mut [_] = &mut [0i, 2, 1]; + /// assert!(v == b); + /// v.prev_permutation(); + /// let b: &mut [_] = &mut [0i, 1, 2]; + /// assert!(v == b); + /// ``` + #[stable] + fn prev_permutation(&mut self) -> bool; +} + +#[unstable = "trait is unstable"] +impl<T: Ord> OrdSliceExt<T> for [T] { + #[inline] + fn sort(&mut self) { + self.sort_by(|a, b| a.cmp(b)) + } + + fn binary_search(&self, x: &T) -> Result<uint, uint> { + core_slice::OrdSliceExt::binary_search(self, x) + } + + fn next_permutation(&mut self) -> bool { + core_slice::OrdSliceExt::next_permutation(self) + } + + fn prev_permutation(&mut self) -> bool { + core_slice::OrdSliceExt::prev_permutation(self) + } +} + +#[allow(missing_docs)] +pub trait VectorVector<T> for Sized? { + // FIXME #5898: calling these .concat and .connect conflicts with + // StrVector::con{cat,nect}, since they have generic contents. + /// Flattens a vector of vectors of `T` into a single `Vec<T>`. + fn concat_vec(&self) -> Vec<T>; + + /// Concatenate a vector of vectors, placing a given separator between each. + fn connect_vec(&self, sep: &T) -> Vec<T>; +} + +impl<'a, T: Clone, V: AsSlice<T>> VectorVector<T> for [V] { + fn concat_vec(&self) -> Vec<T> { + let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len()); + let mut result = Vec::with_capacity(size); + for v in self.iter() { + result.push_all(v.as_slice()) + } + result + } + + fn connect_vec(&self, sep: &T) -> Vec<T> { + let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len()); + let mut result = Vec::with_capacity(size + self.len()); + let mut first = true; + for v in self.iter() { + if first { first = false } else { result.push(sep.clone()) } + result.push_all(v.as_slice()) + } + result + } +} + +/// An iterator that yields the element swaps needed to produce +/// a sequence of all possible permutations for an indexed sequence of +/// elements. Each permutation is only a single swap apart. +/// +/// The Steinhaus-Johnson-Trotter algorithm is used. +/// +/// Generates even and odd permutations alternately. +/// +/// The last generated swap is always (0, 1), and it returns the +/// sequence to its initial order. +#[experimental] +pub struct ElementSwaps { + sdir: Vec<SizeDirection>, + /// If `true`, emit the last swap that returns the sequence to initial + /// state. + emit_reset: bool, + swaps_made : uint, +} + +impl ElementSwaps { + /// Creates an `ElementSwaps` iterator for a sequence of `length` elements. + #[experimental] + pub fn new(length: uint) -> ElementSwaps { + // Initialize `sdir` with a direction that position should move in + // (all negative at the beginning) and the `size` of the + // element (equal to the original index). + ElementSwaps{ + emit_reset: true, + sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(), + swaps_made: 0 + } + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Standard trait implementations for slices +//////////////////////////////////////////////////////////////////////////////// + #[unstable = "trait is unstable"] impl<T> BorrowFrom<Vec<T>> for [T] { fn borrow_from(owned: &Vec<T>) -> &[T] { owned[] } @@ -1334,7 +1079,316 @@ impl<T: Clone> ToOwned<Vec<T>> for [T] { fn to_owned(&self) -> Vec<T> { self.to_vec() } } -/// Unsafe operations +//////////////////////////////////////////////////////////////////////////////// +// Iterators +//////////////////////////////////////////////////////////////////////////////// + +#[deriving(Copy)] +enum Direction { Pos, Neg } + +/// An `Index` and `Direction` together. +#[deriving(Copy)] +struct SizeDirection { + size: uint, + dir: Direction, +} + +impl Iterator<(uint, uint)> for ElementSwaps { + #[inline] + fn next(&mut self) -> Option<(uint, uint)> { + fn new_pos(i: uint, s: Direction) -> uint { + i + match s { Pos => 1, Neg => -1 } + } + + // Find the index of the largest mobile element: + // The direction should point into the vector, and the + // swap should be with a smaller `size` element. + let max = self.sdir.iter().map(|&x| x).enumerate() + .filter(|&(i, sd)| + new_pos(i, sd.dir) < self.sdir.len() && + self.sdir[new_pos(i, sd.dir)].size < sd.size) + .max_by(|&(_, sd)| sd.size); + match max { + Some((i, sd)) => { + let j = new_pos(i, sd.dir); + self.sdir.swap(i, j); + + // Swap the direction of each larger SizeDirection + for x in self.sdir.iter_mut() { + if x.size > sd.size { + x.dir = match x.dir { Pos => Neg, Neg => Pos }; + } + } + self.swaps_made += 1; + Some((i, j)) + }, + None => if self.emit_reset { + self.emit_reset = false; + if self.sdir.len() > 1 { + // The last swap + self.swaps_made += 1; + Some((0, 1)) + } else { + // Vector is of the form [] or [x], and the only permutation is itself + self.swaps_made += 1; + Some((0,0)) + } + } else { None } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option<uint>) { + // For a vector of size n, there are exactly n! permutations. + let n = range(2, self.sdir.len() + 1).product(); + (n - self.swaps_made, Some(n - self.swaps_made)) + } +} + +/// An iterator that uses `ElementSwaps` to iterate through +/// all possible permutations of a vector. +/// +/// The first iteration yields a clone of the vector as it is, +/// then each successive element is the vector with one +/// swap applied. +/// +/// Generates even and odd permutations alternately. +#[stable] +pub struct Permutations<T> { + swaps: ElementSwaps, + v: Vec<T>, +} + +#[unstable = "trait is unstable"] +impl<T: Clone> Iterator<Vec<T>> for Permutations<T> { + #[inline] + fn next(&mut self) -> Option<Vec<T>> { + match self.swaps.next() { + None => None, + Some((0,0)) => Some(self.v.clone()), + Some((a, b)) => { + let elt = self.v.clone(); + self.v.swap(a, b); + Some(elt) + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option<uint>) { + self.swaps.size_hint() + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Sorting +//////////////////////////////////////////////////////////////////////////////// + +fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering { + let len = v.len() as int; + let buf_v = v.as_mut_ptr(); + + // 1 <= i < len; + for i in range(1, len) { + // j satisfies: 0 <= j <= i; + let mut j = i; + unsafe { + // `i` is in bounds. + let read_ptr = buf_v.offset(i) as *const T; + + // find where to insert, we need to do strict <, + // rather than <=, to maintain stability. + + // 0 <= j - 1 < len, so .offset(j - 1) is in bounds. + while j > 0 && + compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less { + j -= 1; + } + + // shift everything to the right, to make space to + // insert this value. + + // j + 1 could be `len` (for the last `i`), but in + // that case, `i == j` so we don't copy. The + // `.offset(j)` is always in bounds. + + if i != j { + let tmp = ptr::read(read_ptr); + ptr::copy_memory(buf_v.offset(j + 1), + &*buf_v.offset(j), + (i - j) as uint); + ptr::copy_nonoverlapping_memory(buf_v.offset(j), + &tmp as *const T, + 1); + mem::forget(tmp); + } + } + } +} + +fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering { + // warning: this wildly uses unsafe. + static BASE_INSERTION: uint = 32; + static LARGE_INSERTION: uint = 16; + + // FIXME #12092: smaller insertion runs seems to make sorting + // vectors of large elements a little faster on some platforms, + // but hasn't been tested/tuned extensively + let insertion = if size_of::<T>() <= 16 { + BASE_INSERTION + } else { + LARGE_INSERTION + }; + + let len = v.len(); + + // short vectors get sorted in-place via insertion sort to avoid allocations + if len <= insertion { + insertion_sort(v, compare); + return; + } + + // allocate some memory to use as scratch memory, we keep the + // length 0 so we can keep shallow copies of the contents of `v` + // without risking the dtors running on an object twice if + // `compare` panics. + let mut working_space = Vec::with_capacity(2 * len); + // these both are buffers of length `len`. + let mut buf_dat = working_space.as_mut_ptr(); + let mut buf_tmp = unsafe {buf_dat.offset(len as int)}; + + // length `len`. + let buf_v = v.as_ptr(); + + // step 1. sort short runs with insertion sort. This takes the + // values from `v` and sorts them into `buf_dat`, leaving that + // with sorted runs of length INSERTION. + + // We could hardcode the sorting comparisons here, and we could + // manipulate/step the pointers themselves, rather than repeatedly + // .offset-ing. + for start in range_step(0, len, insertion) { + // start <= i < len; + for i in range(start, cmp::min(start + insertion, len)) { + // j satisfies: start <= j <= i; + let mut j = i as int; + unsafe { + // `i` is in bounds. + let read_ptr = buf_v.offset(i as int); + + // find where to insert, we need to do strict <, + // rather than <=, to maintain stability. + + // start <= j - 1 < len, so .offset(j - 1) is in + // bounds. + while j > start as int && + compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less { + j -= 1; + } + + // shift everything to the right, to make space to + // insert this value. + + // j + 1 could be `len` (for the last `i`), but in + // that case, `i == j` so we don't copy. The + // `.offset(j)` is always in bounds. + ptr::copy_memory(buf_dat.offset(j + 1), + &*buf_dat.offset(j), + i - j as uint); + ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1); + } + } + } + + // step 2. merge the sorted runs. + let mut width = insertion; + while width < len { + // merge the sorted runs of length `width` in `buf_dat` two at + // a time, placing the result in `buf_tmp`. + + // 0 <= start <= len. + for start in range_step(0, len, 2 * width) { + // manipulate pointers directly for speed (rather than + // using a `for` loop with `range` and `.offset` inside + // that loop). + unsafe { + // the end of the first run & start of the + // second. Offset of `len` is defined, since this is + // precisely one byte past the end of the object. + let right_start = buf_dat.offset(cmp::min(start + width, len) as int); + // end of the second. Similar reasoning to the above re safety. + let right_end_idx = cmp::min(start + 2 * width, len); + let right_end = buf_dat.offset(right_end_idx as int); + + // the pointers to the elements under consideration + // from the two runs. + + // both of these are in bounds. + let mut left = buf_dat.offset(start as int); + let mut right = right_start; + + // where we're putting the results, it is a run of + // length `2*width`, so we step it once for each step + // of either `left` or `right`. `buf_tmp` has length + // `len`, so these are in bounds. + let mut out = buf_tmp.offset(start as int); + let out_end = buf_tmp.offset(right_end_idx as int); + + while out < out_end { + // Either the left or the right run are exhausted, + // so just copy the remainder from the other run + // and move on; this gives a huge speed-up (order + // of 25%) for mostly sorted vectors (the best + // case). + if left == right_start { + // the number remaining in this run. + let elems = (right_end as uint - right as uint) / mem::size_of::<T>(); + ptr::copy_nonoverlapping_memory(out, &*right, elems); + break; + } else if right == right_end { + let elems = (right_start as uint - left as uint) / mem::size_of::<T>(); + ptr::copy_nonoverlapping_memory(out, &*left, elems); + break; + } + + // check which side is smaller, and that's the + // next element for the new run. + + // `left < right_start` and `right < right_end`, + // so these are valid. + let to_copy = if compare(&*left, &*right) == Greater { + step(&mut right) + } else { + step(&mut left) + }; + ptr::copy_nonoverlapping_memory(out, &*to_copy, 1); + step(&mut out); + } + } + } + + mem::swap(&mut buf_dat, &mut buf_tmp); + + width *= 2; + } + + // write the result to `v` in one go, so that there are never two copies + // of the same object in `v`. + unsafe { + ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len); + } + + // increment the pointer, returning the old pointer. + #[inline(always)] + unsafe fn step<T>(ptr: &mut *mut T) -> *mut T { + let old = *ptr; + *ptr = ptr.offset(1); + old + } +} + +/// Deprecated, unsafe operations +#[deprecated] pub mod raw { pub use core::slice::raw::{buf_as_slice, mut_buf_as_slice}; pub use core::slice::raw::{shift_ptr, pop_ptr}; diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs index f356a0867d2..38d8977c0aa 100644 --- a/src/libcore/slice.rs +++ b/src/libcore/slice.rs @@ -68,23 +68,23 @@ pub trait SliceExt<T> for Sized? { fn slice_to<'a>(&'a self, end: uint) -> &'a [T]; fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]); fn iter<'a>(&'a self) -> Iter<'a, T>; - fn split<'a, P>(&'a self, pred: P) -> Splits<'a, T, P> + fn split<'a, P>(&'a self, pred: P) -> Split<'a, T, P> where P: FnMut(&T) -> bool; - fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> + fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitN<'a, T, P> where P: FnMut(&T) -> bool; - fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> + fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> RSplitN<'a, T, P> where P: FnMut(&T) -> bool; fn windows<'a>(&'a self, size: uint) -> Windows<'a, T>; fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T>; fn get<'a>(&'a self, index: uint) -> Option<&'a T>; - fn head<'a>(&'a self) -> Option<&'a T>; + fn first<'a>(&'a self) -> Option<&'a T>; fn tail<'a>(&'a self) -> &'a [T]; fn init<'a>(&'a self) -> &'a [T]; fn last<'a>(&'a self) -> Option<&'a T>; - unsafe fn unsafe_get<'a>(&'a self, index: uint) -> &'a T; + unsafe fn get_unchecked<'a>(&'a self, index: uint) -> &'a T; fn as_ptr(&self) -> *const T; - fn binary_search<F>(&self, f: F) -> BinarySearchResult - where F: FnMut(&T) -> Ordering; + fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where + F: FnMut(&T) -> Ordering; fn len(&self) -> uint; fn is_empty(&self) -> bool { self.len() == 0 } fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>; @@ -93,21 +93,21 @@ pub trait SliceExt<T> for Sized? { fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T]; fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T]; fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T>; - fn head_mut<'a>(&'a mut self) -> Option<&'a mut T>; + fn first_mut<'a>(&'a mut self) -> Option<&'a mut T>; fn tail_mut<'a>(&'a mut self) -> &'a mut [T]; fn init_mut<'a>(&'a mut self) -> &'a mut [T]; fn last_mut<'a>(&'a mut self) -> Option<&'a mut T>; - fn split_mut<'a, P>(&'a mut self, pred: P) -> MutSplits<'a, T, P> + fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool; - fn splitn_mut<P>(&mut self, n: uint, pred: P) -> SplitsN<MutSplits<T, P>> + fn splitn_mut<P>(&mut self, n: uint, pred: P) -> SplitNMut<T, P> where P: FnMut(&T) -> bool; - fn rsplitn_mut<P>(&mut self, n: uint, pred: P) -> SplitsN<MutSplits<T, P>> + fn rsplitn_mut<P>(&mut self, n: uint, pred: P) -> RSplitNMut<T, P> where P: FnMut(&T) -> bool; - fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> MutChunks<'a, T>; + fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> ChunksMut<'a, T>; fn swap(&mut self, a: uint, b: uint); fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]); fn reverse(&mut self); - unsafe fn unsafe_mut<'a>(&'a mut self, index: uint) -> &'a mut T; + unsafe fn get_unchecked_mut<'a>(&'a mut self, index: uint) -> &'a mut T; fn as_mut_ptr(&mut self) -> *mut T; } @@ -145,11 +145,11 @@ impl<T> SliceExt<T> for [T] { unsafe { let p = self.as_ptr(); if mem::size_of::<T>() == 0 { - Iter{ptr: p, + Iter {ptr: p, end: (p as uint + self.len()) as *const T, marker: marker::ContravariantLifetime::<'a>} } else { - Iter{ptr: p, + Iter {ptr: p, end: p.offset(self.len() as int), marker: marker::ContravariantLifetime::<'a>} } @@ -157,8 +157,8 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn split<'a, P>(&'a self, pred: P) -> Splits<'a, T, P> where P: FnMut(&T) -> bool { - Splits { + fn split<'a, P>(&'a self, pred: P) -> Split<'a, T, P> where P: FnMut(&T) -> bool { + Split { v: self, pred: pred, finished: false @@ -166,24 +166,28 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> where + fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitN<'a, T, P> where P: FnMut(&T) -> bool, { - SplitsN { - iter: self.split(pred), - count: n, - invert: false + SplitN { + inner: GenericSplitN { + iter: self.split(pred), + count: n, + invert: false + } } } #[inline] - fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> where + fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> RSplitN<'a, T, P> where P: FnMut(&T) -> bool, { - SplitsN { - iter: self.split(pred), - count: n, - invert: true + RSplitN { + inner: GenericSplitN { + iter: self.split(pred), + count: n, + invert: true + } } } @@ -205,7 +209,7 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn head(&self) -> Option<&T> { + fn first(&self) -> Option<&T> { if self.len() == 0 { None } else { Some(&self[0]) } } @@ -223,7 +227,7 @@ impl<T> SliceExt<T> for [T] { } #[inline] - unsafe fn unsafe_get(&self, index: uint) -> &T { + unsafe fn get_unchecked(&self, index: uint) -> &T { transmute(self.repr().data.offset(index as int)) } @@ -233,14 +237,16 @@ impl<T> SliceExt<T> for [T] { } #[unstable] - fn binary_search<F>(&self, mut f: F) -> BinarySearchResult where F: FnMut(&T) -> Ordering { + fn binary_search_by<F>(&self, mut f: F) -> Result where + F: FnMut(&T) -> Ordering + { let mut base : uint = 0; let mut lim : uint = self.len(); while lim != 0 { let ix = base + (lim >> 1); match f(&self[ix]) { - Equal => return BinarySearchResult::Found(ix), + Equal => return Ok(ix), Less => { base = ix + 1; lim -= 1; @@ -249,7 +255,7 @@ impl<T> SliceExt<T> for [T] { } lim >>= 1; } - return BinarySearchResult::NotFound(base); + Err(base); } #[inline] @@ -292,11 +298,11 @@ impl<T> SliceExt<T> for [T] { unsafe { let p = self.as_mut_ptr(); if mem::size_of::<T>() == 0 { - IterMut{ptr: p, + IterMut {ptr: p, end: (p as uint + self.len()) as *mut T, marker: marker::ContravariantLifetime::<'a>} } else { - IterMut{ptr: p, + IterMut {ptr: p, end: p.offset(self.len() as int), marker: marker::ContravariantLifetime::<'a>} } @@ -311,7 +317,7 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn head_mut(&mut self) -> Option<&mut T> { + fn first_mut(&mut self) -> Option<&mut T> { if self.len() == 0 { None } else { Some(&mut self[0]) } } @@ -327,36 +333,40 @@ impl<T> SliceExt<T> for [T] { } #[inline] - fn split_mut<'a, P>(&'a mut self, pred: P) -> MutSplits<'a, T, P> where P: FnMut(&T) -> bool { - MutSplits { v: self, pred: pred, finished: false } + fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool { + SplitMut { v: self, pred: pred, finished: false } } #[inline] - fn splitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitsN<MutSplits<'a, T, P>> where + fn splitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitNMut<'a, T, P> where P: FnMut(&T) -> bool { - SplitsN { - iter: self.split_mut(pred), - count: n, - invert: false + SplitNMut { + inner: GenericSplitN { + iter: self.split_mut(pred), + count: n, + invert: false + } } } #[inline] - fn rsplitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitsN<MutSplits<'a, T, P>> where + fn rsplitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> RSplitNMut<'a, T, P> where P: FnMut(&T) -> bool, { - SplitsN { - iter: self.split_mut(pred), - count: n, - invert: true + RSplitNMut { + inner: GenericSplitN { + iter: self.split_mut(pred), + count: n, + invert: true + } } } #[inline] - fn chunks_mut(&mut self, chunk_size: uint) -> MutChunks<T> { + fn chunks_mut(&mut self, chunk_size: uint) -> ChunksMut<T> { assert!(chunk_size > 0); - MutChunks { v: self, chunk_size: chunk_size } + ChunksMut { v: self, chunk_size: chunk_size } } fn swap(&mut self, a: uint, b: uint) { @@ -375,8 +385,8 @@ impl<T> SliceExt<T> for [T] { while i < ln / 2 { // Unsafe swap to avoid the bounds check in safe swap. unsafe { - let pa: *mut T = self.unsafe_mut(i); - let pb: *mut T = self.unsafe_mut(ln - i - 1); + let pa: *mut T = self.get_unchecked_mut(i); + let pb: *mut T = self.get_unchecked_mut(ln - i - 1); ptr::swap(pa, pb); } i += 1; @@ -384,7 +394,7 @@ impl<T> SliceExt<T> for [T] { } #[inline] - unsafe fn unsafe_mut(&mut self, index: uint) -> &mut T { + unsafe fn get_unchecked_mut(&mut self, index: uint) -> &mut T { transmute((self.repr().data as *mut T).offset(index as int)) } @@ -468,21 +478,26 @@ impl<T> ops::SliceMut<uint, [T]> for [T] { } /// Extension methods for slices containing `PartialEq` elements. -#[unstable = "may merge with other traits"] +#[unstable = "may merge with SliceExt"] pub trait PartialEqSliceExt<T: PartialEq> for Sized? { /// Find the first index containing a matching value. + #[experimental] fn position_elem(&self, t: &T) -> Option<uint>; /// Find the last index containing a matching value. + #[experimental] fn rposition_elem(&self, t: &T) -> Option<uint>; /// Return true if the slice contains an element with the given value. + #[stable] fn contains(&self, x: &T) -> bool; /// Returns true if `needle` is a prefix of the slice. + #[stable] fn starts_with(&self, needle: &[T]) -> bool; /// Returns true if `needle` is a suffix of the slice. + #[stable] fn ends_with(&self, needle: &[T]) -> bool; } @@ -520,19 +535,16 @@ impl<T: PartialEq> PartialEqSliceExt<T> for [T] { #[unstable = "may merge with other traits"] #[allow(missing_docs)] // docs in libcollections pub trait OrdSliceExt<T: Ord> for Sized? { - #[unstable = "name likely to change"] - fn binary_search_elem(&self, x: &T) -> BinarySearchResult; - #[experimental] + fn binary_search(&self, x: &T) -> Result<uint, uint>; fn next_permutation(&mut self) -> bool; - #[experimental] fn prev_permutation(&mut self) -> bool; } #[unstable = "trait is unstable"] impl<T: Ord> OrdSliceExt<T> for [T] { #[unstable] - fn binary_search_elem(&self, x: &T) -> BinarySearchResult { - self.binary_search(|p| p.cmp(x)) + fn binary_search(&self, x: &T) -> Result<uint, uint> { + self.binary_search_by(|p| p.cmp(x)) } #[experimental] @@ -619,28 +631,30 @@ impl<T: Clone> CloneSliceExt<T> for [T] { } } -// +//////////////////////////////////////////////////////////////////////////////// // Common traits -// +//////////////////////////////////////////////////////////////////////////////// /// Data that is viewable as a slice. -#[unstable = "may merge with other traits"] +#[experimental = "will be replaced by slice syntax"] pub trait AsSlice<T> for Sized? { /// Work with `self` as a slice. fn as_slice<'a>(&'a self) -> &'a [T]; } -#[unstable = "trait is unstable"] +#[experimental = "trait is experimental"] impl<T> AsSlice<T> for [T] { #[inline(always)] fn as_slice<'a>(&'a self) -> &'a [T] { self } } +#[experimental = "trait is experimental"] impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U { #[inline(always)] fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) } } +#[experimental = "trait is experimental"] impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U { #[inline(always)] fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) } @@ -656,7 +670,7 @@ impl<'a, T> Default for &'a [T] { // Iterators // -// The shared definition of the `Item` and `IterMut` iterators +// The shared definition of the `Iter` and `IterMut` iterators macro_rules! iterator { (struct $name:ident -> $ptr:ty, $elem:ty) => { #[experimental = "needs review"] @@ -736,9 +750,8 @@ macro_rules! make_slice { }} } - /// Immutable slice iterator -#[experimental = "needs review"] +#[stable] pub struct Iter<'a, T: 'a> { ptr: *const T, end: *const T, @@ -813,7 +826,7 @@ impl<'a, T> RandomAccessIterator<&'a T> for Iter<'a, T> { } /// Mutable slice iterator. -#[experimental = "needs review"] +#[stable] pub struct IterMut<'a, T: 'a> { ptr: *mut T, end: *mut T, @@ -876,9 +889,9 @@ iterator!{struct IterMut -> *mut T, &'a mut T} #[experimental = "needs review"] impl<'a, T> ExactSizeIterator<&'a mut T> for IterMut<'a, T> {} -/// An abstraction over the splitting iterators, so that splitn, splitn_mut etc -/// can be implemented once. -trait SplitsIter<E>: DoubleEndedIterator<E> { +/// An internal abstraction over the splitting iterators, so that +/// splitn, splitn_mut etc can be implemented once. +trait SplitIter<E>: DoubleEndedIterator<E> { /// Mark the underlying iterator as complete, extracting the remaining /// portion of the slice. fn finish(&mut self) -> Option<E>; @@ -886,8 +899,8 @@ trait SplitsIter<E>: DoubleEndedIterator<E> { /// An iterator over subslices separated by elements that match a predicate /// function. -#[experimental = "needs review"] -pub struct Splits<'a, T:'a, P> where P: FnMut(&T) -> bool { +#[stable] +pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool { v: &'a [T], pred: P, finished: bool @@ -895,9 +908,9 @@ pub struct Splits<'a, T:'a, P> where P: FnMut(&T) -> bool { // FIXME(#19839) Remove in favor of `#[deriving(Clone)]` #[stable] -impl<'a, T, P> Clone for Splits<'a, T, P> where P: Clone + FnMut(&T) -> bool { - fn clone(&self) -> Splits<'a, T, P> { - Splits { +impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool { + fn clone(&self) -> Split<'a, T, P> { + Split { v: self.v, pred: self.pred.clone(), finished: self.finished, @@ -906,7 +919,7 @@ impl<'a, T, P> Clone for Splits<'a, T, P> where P: Clone + FnMut(&T) -> bool { } #[experimental = "needs review"] -impl<'a, T, P> Iterator<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool { +impl<'a, T, P> Iterator<&'a [T]> for Split<'a, T, P> where P: FnMut(&T) -> bool { #[inline] fn next(&mut self) -> Option<&'a [T]> { if self.finished { return None; } @@ -932,7 +945,7 @@ impl<'a, T, P> Iterator<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool } #[experimental = "needs review"] -impl<'a, T, P> DoubleEndedIterator<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool { +impl<'a, T, P> DoubleEndedIterator<&'a [T]> for Split<'a, T, P> where P: FnMut(&T) -> bool { #[inline] fn next_back(&mut self) -> Option<&'a [T]> { if self.finished { return None; } @@ -948,7 +961,7 @@ impl<'a, T, P> DoubleEndedIterator<&'a [T]> for Splits<'a, T, P> where P: FnMut( } } -impl<'a, T, P> SplitsIter<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool { +impl<'a, T, P> SplitIter<&'a [T]> for Split<'a, T, P> where P: FnMut(&T) -> bool { #[inline] fn finish(&mut self) -> Option<&'a [T]> { if self.finished { None } else { self.finished = true; Some(self.v) } @@ -957,14 +970,14 @@ impl<'a, T, P> SplitsIter<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bo /// An iterator over the subslices of the vector which are separated /// by elements that match `pred`. -#[experimental = "needs review"] -pub struct MutSplits<'a, T:'a, P> where P: FnMut(&T) -> bool { +#[stable] +pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool { v: &'a mut [T], pred: P, finished: bool } -impl<'a, T, P> SplitsIter<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T) -> bool { +impl<'a, T, P> SplitIter<&'a mut [T]> for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { #[inline] fn finish(&mut self) -> Option<&'a mut [T]> { if self.finished { @@ -977,7 +990,7 @@ impl<'a, T, P> SplitsIter<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T } #[experimental = "needs review"] -impl<'a, T, P> Iterator<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T) -> bool { +impl<'a, T, P> Iterator<&'a mut [T]> for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { #[inline] fn next(&mut self) -> Option<&'a mut [T]> { if self.finished { return None; } @@ -1010,7 +1023,7 @@ impl<'a, T, P> Iterator<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T) } #[experimental = "needs review"] -impl<'a, T, P> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T, P> where +impl<'a, T, P> DoubleEndedIterator<&'a mut [T]> for SplitMut<'a, T, P> where P: FnMut(&T) -> bool, { #[inline] @@ -1033,17 +1046,17 @@ impl<'a, T, P> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T, P> where } } -/// An iterator over subslices separated by elements that match a predicate -/// function, splitting at most a fixed number of times. -#[experimental = "needs review"] -pub struct SplitsN<I> { +/// An private iterator over subslices separated by elements that +/// match a predicate function, splitting at most a fixed number of +/// times. +struct GenericSplitN<I> { iter: I, count: uint, invert: bool } #[experimental = "needs review"] -impl<E, I: SplitsIter<E>> Iterator<E> for SplitsN<I> { +impl<E, I: SplitIter<E>> Iterator<E> for GenericSplitN<I> { #[inline] fn next(&mut self) -> Option<E> { if self.count == 0 { @@ -1061,6 +1074,55 @@ impl<E, I: SplitsIter<E>> Iterator<E> for SplitsN<I> { } } +/// An iterator over subslices separated by elements that match a predicate +/// function, limited to a given number of splits. +pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { + inner: GenericSplitN<Split<'a, T, P>> +} + +/// An iterator over subslices separated by elements that match a +/// predicate function, limited to a given number of splits, starting +/// from the end of the slice. +pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { + inner: GenericSplitN<Split<'a, T, P>> +} + +/// An iterator over subslices separated by elements that match a predicate +/// function, limited to a given number of splits. +pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { + inner: GenericSplitN<SplitMut<'a, T, P>> +} + +/// An iterator over subslices separated by elements that match a +/// predicate function, limited to a given number of splits, starting +/// from the end of the slice. +pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { + inner: GenericSplitN<SplitMut<'a, T, P>> +} + +macro_rules! forward_iterator { + ($name:ident: $elem:ident, $iter_of:ty) => { + impl<'a, $elem, P> Iterator<$iter_of> for $name<'a, $elem, P> where + P: FnMut(&T) -> bool + { + #[inline] + fn next(&mut self) -> Option<$iter_of> { + self.inner.next() + } + + #[inline] + fn size_hint(&self) -> (uint, Option<uint>) { + self.inner.size_hint() + } + } + } +} + +forward_iterator! { SplitN: T, &'a [T] } +forward_iterator! { RSplitN: T, &'a [T] } +forward_iterator! { SplitNMut: T, &'a mut [T] } +forward_iterator! { RSplitNMut: T, &'a mut [T] } + /// An iterator over overlapping subslices of length `size`. #[deriving(Clone)] #[experimental = "needs review"] @@ -1172,13 +1234,13 @@ impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> { /// elements at a time). When the slice len is not evenly divided by the chunk /// size, the last slice of the iteration will be the remainder. #[experimental = "needs review"] -pub struct MutChunks<'a, T:'a> { +pub struct ChunksMut<'a, T:'a> { v: &'a mut [T], chunk_size: uint } #[experimental = "needs review"] -impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> { +impl<'a, T> Iterator<&'a mut [T]> for ChunksMut<'a, T> { #[inline] fn next(&mut self) -> Option<&'a mut [T]> { if self.v.len() == 0 { @@ -1206,7 +1268,7 @@ impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> { } #[experimental = "needs review"] -impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> { +impl<'a, T> DoubleEndedIterator<&'a mut [T]> for ChunksMut<'a, T> { #[inline] fn next_back(&mut self) -> Option<&'a mut [T]> { if self.v.len() == 0 { @@ -1224,51 +1286,12 @@ impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> { } - -/// The result of calling `binary_search`. -/// -/// `Found` means the search succeeded, and the contained value is the -/// index of the matching element. `NotFound` means the search -/// succeeded, and the contained value is an index where a matching -/// value could be inserted while maintaining sort order. -#[deriving(Copy, PartialEq, Show)] -#[experimental = "needs review"] -pub enum BinarySearchResult { - /// The index of the found value. - Found(uint), - /// The index where the value should have been found. - NotFound(uint) -} - -#[experimental = "needs review"] -impl BinarySearchResult { - /// Converts a `Found` to `Some`, `NotFound` to `None`. - /// Similar to `Result::ok`. - pub fn found(&self) -> Option<uint> { - match *self { - BinarySearchResult::Found(i) => Some(i), - BinarySearchResult::NotFound(_) => None - } - } - - /// Convert a `Found` to `None`, `NotFound` to `Some`. - /// Similar to `Result::err`. - pub fn not_found(&self) -> Option<uint> { - match *self { - BinarySearchResult::Found(_) => None, - BinarySearchResult::NotFound(i) => Some(i) - } - } -} - - - // // Free functions // /// Converts a pointer to A into a slice of length 1 (without copying). -#[unstable = "waiting for DST"] +#[unstable] pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] { unsafe { transmute(RawSlice { data: s, len: 1 }) @@ -1276,7 +1299,7 @@ pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] { } /// Converts a pointer to A into a slice of length 1 (without copying). -#[unstable = "waiting for DST"] +#[unstable] pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] { unsafe { let ptr: *const A = transmute(s); @@ -1310,7 +1333,7 @@ pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] { /// } /// ``` #[inline] -#[unstable = "just renamed from `mod raw`"] +#[unstable = "should be renamed to from_raw_parts"] pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] { transmute(RawSlice { data: *p, len: len }) } @@ -1322,7 +1345,7 @@ pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] { /// not being able to provide a non-aliasing guarantee of the returned mutable /// slice. #[inline] -#[unstable = "just renamed from `mod raw`"] +#[unstable = "jshould be renamed to from_raw_parts_mut"] pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] { transmute(RawSlice { data: *p as *const T, len: len }) } @@ -1497,39 +1520,28 @@ impl<T: PartialOrd> PartialOrd for [T] { } } -/// Extension methods for immutable slices containing integers. +/// Extension methods for slices containing integers. #[experimental] -pub trait ImmutableIntSlice<U, S> for Sized? { +pub trait IntSliceExt<U, S> for Sized? { /// Converts the slice to an immutable slice of unsigned integers with the same width. fn as_unsigned<'a>(&'a self) -> &'a [U]; /// Converts the slice to an immutable slice of signed integers with the same width. fn as_signed<'a>(&'a self) -> &'a [S]; -} -/// Extension methods for mutable slices containing integers. -#[experimental] -pub trait MutableIntSlice<U, S> for Sized?: ImmutableIntSlice<U, S> { /// Converts the slice to a mutable slice of unsigned integers with the same width. fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U]; /// Converts the slice to a mutable slice of signed integers with the same width. fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S]; } -macro_rules! impl_immut_int_slice { +macro_rules! impl_int_slice { ($u:ty, $s:ty, $t:ty) => { #[experimental] - impl ImmutableIntSlice<$u, $s> for [$t] { + impl IntSliceExt<$u, $s> for [$t] { #[inline] fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } } #[inline] fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } } - } - } -} -macro_rules! impl_mut_int_slice { - ($u:ty, $s:ty, $t:ty) => { - #[experimental] - impl MutableIntSlice<$u, $s> for [$t] { #[inline] fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } } #[inline] @@ -1538,17 +1550,15 @@ macro_rules! impl_mut_int_slice { } } -macro_rules! impl_int_slice { +macro_rules! impl_int_slices { ($u:ty, $s:ty) => { - impl_immut_int_slice! { $u, $s, $u } - impl_immut_int_slice! { $u, $s, $s } - impl_mut_int_slice! { $u, $s, $u } - impl_mut_int_slice! { $u, $s, $s } + impl_int_slice! { $u, $s, $u } + impl_int_slice! { $u, $s, $s } } } -impl_int_slice! { u8, i8 } -impl_int_slice! { u16, i16 } -impl_int_slice! { u32, i32 } -impl_int_slice! { u64, i64 } -impl_int_slice! { uint, int } +impl_int_slices! { u8, i8 } +impl_int_slices! { u16, i16 } +impl_int_slices! { u32, i32 } +impl_int_slices! { u64, i64 } +impl_int_slices! { uint, int } diff --git a/src/rust-installer b/src/rust-installer -Subproject 3a37981744a5af2433fed551f742465c78c9af7 +Subproject aed73472416064642911af790b25d57c9390b6c |