1 // SPDX-License-Identifier: Apache-2.0 OR MIT
3 //! A dynamically-sized view into a contiguous sequence, `[T]`.
42 //! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`].
43 //! * [`Hash`] - for slices whose element type is [`Hash`].
156 // `core::slice::SliceExt` - we need to supply these functions for the
167     pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {  in into_vec()
177     pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> {  in to_vec()
183         fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A>  in to_vec()
191         default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {  in to_vec()
228         fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {  in to_vec()
246 …/// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-cas…
260     /// non-allocating insertion sort is used instead.
265     /// let mut v = [-5, 4, 1, -3, 2];
268     /// assert!(v == [-5, -3, 1, 2, 4]);
283 …/// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-cas…
313     /// non-allocating insertion sort is used instead.
332         F: FnMut(&T, &T) -> Ordering,  in sort_by()
340     /// worst-case, where the key function is *O*(*m*).
358     /// non-allocating insertion sort is used instead.
363     /// let mut v = [-5i32, 4, 1, -3, 2];
366     /// assert!(v == [1, 2, -3, 4, -5]);
374         F: FnMut(&T) -> K,  in sort_by_key()
388     /// worst-case, where the key function is *O*(*m*).
396     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
408     /// let mut v = [-5i32, 4, 32, -3, 2];
411     /// assert!(v == [-3, -5, 2, 32, 4]);
421         F: FnMut(&T) -> K,  in sort_by_cached_key()
479     pub fn to_vec(&self) -> Vec<T>  in to_vec()
503     pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>  in to_vec_in()
528     pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {  in into_vec()
556     pub fn repeat(&self, n: usize) -> Vec<T>  in repeat()
573         // `2^expn` repetition is done by doubling `buf` `expn`-times.  in repeat()
595         // `rem` (`= n - 2^expn`) repetition is done by copying  in repeat()
597         let rem_len = capacity - buf.len(); // `self.len() * rem`  in repeat()
601                 // This is non-overlapping since `2^expn > rem`.  in repeat()
624     pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output  in concat()
643     pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output  in join()
663     pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output  in connect()
677     /// but non-ASCII letters are unchanged.
679     /// To uppercase the value in-place, use [`make_ascii_uppercase`].
688     pub fn to_ascii_uppercase(&self) -> Vec<u8> {  in to_ascii_uppercase()
698     /// but non-ASCII letters are unchanged.
700     /// To lowercase the value in-place, use [`make_ascii_lowercase`].
709     pub fn to_ascii_lowercase(&self) -> Vec<u8> {  in to_ascii_lowercase()
728 ///    --> src/liballoc/slice.rs:608:6
739 /// pub struct Foo(Vec<u32>, Vec<String>);
741 /// impl std::borrow::Borrow<[u32]> for Foo {
742 ///     fn borrow(&self) -> &[u32] { &self.0 }
745 /// impl std::borrow::Borrow<[String]> for Foo {
746 ///     fn borrow(&self) -> &[String] { &self.1 }
757     fn concat(slice: &Self) -> Self::Output;  in concat()
769     fn join(slice: &Self, sep: Separator) -> Self::Output;  in join()
777     fn concat(slice: &Self) -> Vec<T> {  in concat()
792     fn join(slice: &Self, sep: &T) -> Vec<T> {  in join()
798         let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;  in join()
815     fn join(slice: &Self, sep: &[T]) -> Vec<T> {  in join()
822             slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);  in join()
840     fn borrow(&self) -> &[T] {  in borrow()
847     fn borrow_mut(&mut self) -> &mut [T] {  in borrow_mut()
857     fn to_owned(&self) -> Vec<T> {  in to_owned()
862     fn to_owned(&self) -> Vec<T> {  in to_owned()
871         // slices here are always in-bounds.  in clone_into()
884 /// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted.
890     F: FnMut(&T, &T) -> bool,  in insert_head()
930                 ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);  in insert_head()
952 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
957 /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough
958 /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type.
962     F: FnMut(&T, &T) -> bool,  in merge()
987     if mid <= len - mid {  in merge()
1014             ptr::copy_nonoverlapping(v_mid, buf, len - mid);  in merge()
1015             hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };  in merge()
1027                 let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {  in merge()
1039     unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {  in merge()
1045     unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {  in merge()
1046         *ptr = unsafe { ptr.offset(-1) };  in merge()
1059             // `T` is not a zero-sized type, and these are pointers into a slice's elements.  in merge()
1071 /// The algorithm identifies strictly descending and non-descending subsequences, which are called
1076 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
1077 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
1079 /// The invariants ensure that the total running time is *O*(*n* \* log(*n*)) worst-case.
1083     F: FnMut(&T, &T) -> bool,  in merge_sort()
1090     // Sorting has no meaningful behavior on zero-sized types.  in merge_sort()
1097     // Short arrays get sorted in-place via insertion sort to avoid allocations.  in merge_sort()
1100             for i in (0..len - 1).rev() {  in merge_sort()
1121         let mut start = end - 1;  in merge_sort()
1123             start -= 1;  in merge_sort()
1126                     while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) {  in merge_sort()
1127                         start -= 1;  in merge_sort()
1131                     while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1))  in merge_sort()
1133                         start -= 1;  in merge_sort()
1141         while start > 0 && end - start < MIN_RUN {  in merge_sort()
1142             start -= 1;  in merge_sort()
1147         runs.push(Run { start, len: end - start });  in merge_sort()
1175     // http://envisage-project.eu/timsort-specification-and-verification/  in merge_sort()
1185     fn collapse(runs: &[Run]) -> Option<usize> {  in merge_sort()
1188             && (runs[n - 1].start == 0  in merge_sort()
1189                 || runs[n - 2].len <= runs[n - 1].len  in merge_sort()
1190                 || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)  in merge_sort()
1191                 || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))  in merge_sort()
1193             if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }  in merge_sort()