1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Slice management and manipulation
13 //! For more details `std::slice`.
16 #![doc(primitive = "slice")]
18 // How this module is organized.
20 // The library infrastructure for slices is fairly messy. There's
21 // a lot of stuff defined here. Let's keep it clean.
23 // Since slices don't support inherent methods; all operations
24 // on them are defined on traits, which are then reexported from
25 // the prelude for convenience. So there are a lot of traits here.
27 // The layout of this file is thus:
29 // * Slice-specific 'extension' traits and their implementations. This
30 // is where most of the slice API resides.
31 // * Implementations of a few common traits with important slice ops.
32 // * Definitions of a bunch of iterators.
34 // * The `raw` and `bytes` submodules.
35 // * Boilerplate trait implementations.
39 use cmp::{Ordering, PartialEq, PartialOrd, Eq, Ord, Equiv};
40 use cmp::Ordering::{Less, Equal, Greater};
48 use option::Option::{None, Some};
53 use kinds::{Sized, marker};
55 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
56 use raw::Slice as RawSlice;
63 /// Extension methods for slices.
64 #[unstable = "may merge with other traits"]
65 pub trait SlicePrelude<T> for Sized? {
66 /// Returns a subslice spanning the interval [`start`, `end`).
68 /// Panics when the end of the new slice lies beyond the end of the
69 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
71 /// Slicing with `start` equal to `end` yields an empty slice.
72 #[unstable = "waiting on final error conventions/slicing syntax"]
73 fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T];
75 /// Returns a subslice from `start` to the end of the slice.
77 /// Panics when `start` is strictly greater than the length of the original slice.
79 /// Slicing from `self.len()` yields an empty slice.
80 #[unstable = "waiting on final error conventions/slicing syntax"]
81 fn slice_from<'a>(&'a self, start: uint) -> &'a [T];
83 /// Returns a subslice from the start of the slice to `end`.
85 /// Panics when `end` is strictly greater than the length of the original slice.
87 /// Slicing to `0` yields an empty slice.
88 #[unstable = "waiting on final error conventions/slicing syntax"]
89 fn slice_to<'a>(&'a self, end: uint) -> &'a [T];
91 /// Divides one slice into two at an index.
93 /// The first will contain all indices from `[0, mid)` (excluding
94 /// the index `mid` itself) and the second will contain all
95 /// indices from `[mid, len)` (excluding the index `len` itself).
97 /// Panics if `mid > len`.
98 #[unstable = "waiting on final error conventions"]
99 fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]);
101 /// Returns an iterator over the slice
102 #[unstable = "iterator type may change"]
103 fn iter<'a>(&'a self) -> Items<'a, T>;
105 /// Returns an iterator over subslices separated by elements that match
106 /// `pred`. The matched element is not contained in the subslices.
107 #[unstable = "iterator type may change, waiting on unboxed closures"]
108 fn split<'a>(&'a self, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
110 /// Returns an iterator over subslices separated by elements that match
111 /// `pred`, limited to splitting at most `n` times. The matched element is
112 /// not contained in the subslices.
113 #[unstable = "iterator type may change"]
114 fn splitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>>;
116 /// Returns an iterator over subslices separated by elements that match
117 /// `pred` limited to splitting at most `n` times. This starts at the end of
118 /// the slice and works backwards. The matched element is not contained in
120 #[unstable = "iterator type may change"]
121 fn rsplitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>>;
123 /// Returns an iterator over all contiguous windows of length
124 /// `size`. The windows overlap. If the slice is shorter than
125 /// `size`, the iterator returns no values.
129 /// Panics if `size` is 0.
133 /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
137 /// let v = &[1i, 2, 3, 4];
138 /// for win in v.windows(2) {
139 /// println!("{}", win);
142 #[unstable = "iterator type may change"]
143 fn windows<'a>(&'a self, size: uint) -> Windows<'a, T>;
145 /// Returns an iterator over `size` elements of the slice at a
146 /// time. The chunks do not overlap. If `size` does not divide the
147 /// length of the slice, then the last chunk will not have length
152 /// Panics if `size` is 0.
156 /// Print the slice two elements at a time (i.e. `[1,2]`,
160 /// let v = &[1i, 2, 3, 4, 5];
161 /// for win in v.chunks(2) {
162 /// println!("{}", win);
165 #[unstable = "iterator type may change"]
166 fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T>;
168 /// Returns the element of a slice at the given index, or `None` if the
169 /// index is out of bounds.
170 #[unstable = "waiting on final collection conventions"]
171 fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
173 /// Returns the first element of a slice, or `None` if it is empty.
174 #[unstable = "name may change"]
175 fn head<'a>(&'a self) -> Option<&'a T>;
177 /// Returns all but the first element of a slice.
178 #[unstable = "name may change"]
179 fn tail<'a>(&'a self) -> &'a [T];
181 /// Returns all but the last element of a slice.
182 #[unstable = "name may change"]
183 fn init<'a>(&'a self) -> &'a [T];
185 /// Returns the last element of a slice, or `None` if it is empty.
186 #[unstable = "name may change"]
187 fn last<'a>(&'a self) -> Option<&'a T>;
189 /// Returns a pointer to the element at the given index, without doing
192 unsafe fn unsafe_get<'a>(&'a self, index: uint) -> &'a T;
194 /// Returns an unsafe pointer to the slice's buffer
196 /// The caller must ensure that the slice outlives the pointer this
197 /// function returns, or else it will end up pointing to garbage.
199 /// Modifying the slice may cause its buffer to be reallocated, which
200 /// would also make any pointers to it invalid.
202 fn as_ptr(&self) -> *const T;
204 /// Binary search a sorted slice with a comparator function.
206 /// The comparator function should implement an order consistent
207 /// with the sort order of the underlying slice, returning an
208 /// order code that indicates whether its argument is `Less`,
209 /// `Equal` or `Greater` the desired target.
211 /// If a matching value is found then returns `Found`, containing
212 /// the index for the matched element; if no match is found then
213 /// `NotFound` is returned, containing the index where a matching
214 /// element could be inserted while maintaining sorted order.
218 /// Looks up a series of four elements. The first is found, with a
219 /// uniquely determined position; the second and third are not
220 /// found; the fourth could match any position in `[1,4]`.
223 /// use std::slice::BinarySearchResult::{Found, NotFound};
224 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
225 /// let s = s.as_slice();
228 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), Found(9));
230 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(7));
232 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(13));
234 /// let r = s.binary_search(|probe| probe.cmp(&seek));
235 /// assert!(match r { Found(1...4) => true, _ => false, });
237 #[unstable = "waiting on unboxed closures"]
238 fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult;
240 /// Return the number of elements in the slice
245 /// let a = [1i, 2, 3];
246 /// assert_eq!(a.len(), 3);
248 #[experimental = "not triaged yet"]
249 fn len(&self) -> uint;
251 /// Returns true if the slice has a length of 0
256 /// let a = [1i, 2, 3];
257 /// assert!(!a.is_empty());
260 #[experimental = "not triaged yet"]
261 fn is_empty(&self) -> bool { self.len() == 0 }
262 /// Returns a mutable reference to the element at the given index,
263 /// or `None` if the index is out of bounds
264 #[unstable = "waiting on final error conventions"]
265 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
267 /// Work with `self` as a mut slice.
268 /// Primarily intended for getting a &mut [T] from a [T, ..N].
269 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
271 /// Returns a mutable subslice spanning the interval [`start`, `end`).
273 /// Panics when the end of the new slice lies beyond the end of the
274 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
276 /// Slicing with `start` equal to `end` yields an empty slice.
277 #[unstable = "waiting on final error conventions"]
278 fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T];
280 /// Returns a mutable subslice from `start` to the end of the slice.
282 /// Panics when `start` is strictly greater than the length of the original slice.
284 /// Slicing from `self.len()` yields an empty slice.
285 #[unstable = "waiting on final error conventions"]
286 fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T];
288 /// Returns a mutable subslice from the start of the slice to `end`.
290 /// Panics when `end` is strictly greater than the length of the original slice.
292 /// Slicing to `0` yields an empty slice.
293 #[unstable = "waiting on final error conventions"]
294 fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T];
296 /// Returns an iterator that allows modifying each value
297 #[unstable = "waiting on iterator type name conventions"]
298 fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T>;
300 /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
301 #[unstable = "name may change"]
302 fn head_mut<'a>(&'a mut self) -> Option<&'a mut T>;
304 /// Returns all but the first element of a mutable slice
305 #[unstable = "name may change"]
306 fn tail_mut<'a>(&'a mut self) -> &'a mut [T];
308 /// Returns all but the last element of a mutable slice
309 #[unstable = "name may change"]
310 fn init_mut<'a>(&'a mut self) -> &'a mut [T];
312 /// Returns a mutable pointer to the last item in the slice.
313 #[unstable = "name may change"]
314 fn last_mut<'a>(&'a mut self) -> Option<&'a mut T>;
316 /// Returns an iterator over mutable subslices separated by elements that
317 /// match `pred`. The matched element is not contained in the subslices.
318 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
319 fn split_mut<'a>(&'a mut self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T>;
321 /// Returns an iterator over subslices separated by elements that match
322 /// `pred`, limited to splitting at most `n` times. The matched element is
323 /// not contained in the subslices.
324 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
325 fn splitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>>;
327 /// Returns an iterator over subslices separated by elements that match
328 /// `pred` limited to splitting at most `n` times. This starts at the end of
329 /// the slice and works backwards. The matched element is not contained in
331 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
332 fn rsplitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>>;
334 /// Returns an iterator over `chunk_size` elements of the slice at a time.
335 /// The chunks are mutable and do not overlap. If `chunk_size` does
336 /// not divide the length of the slice, then the last chunk will not
337 /// have length `chunk_size`.
341 /// Panics if `chunk_size` is 0.
342 #[unstable = "waiting on iterator type name conventions"]
343 fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> MutChunks<'a, T>;
345 /// Swaps two elements in a slice.
347 /// Panics if `a` or `b` are out of bounds.
351 /// * a - The index of the first element
352 /// * b - The index of the second element
357 /// let mut v = ["a", "b", "c", "d"];
359 /// assert!(v == ["a", "d", "c", "b"]);
361 #[unstable = "waiting on final error conventions"]
362 fn swap(&mut self, a: uint, b: uint);
364 /// Divides one `&mut` into two at an index.
366 /// The first will contain all indices from `[0, mid)` (excluding
367 /// the index `mid` itself) and the second will contain all
368 /// indices from `[mid, len)` (excluding the index `len` itself).
370 /// Panics if `mid > len`.
375 /// let mut v = [1i, 2, 3, 4, 5, 6];
377 /// // scoped to restrict the lifetime of the borrows
379 /// let (left, right) = v.split_at_mut(0);
380 /// assert!(left == []);
381 /// assert!(right == [1i, 2, 3, 4, 5, 6]);
385 /// let (left, right) = v.split_at_mut(2);
386 /// assert!(left == [1i, 2]);
387 /// assert!(right == [3i, 4, 5, 6]);
391 /// let (left, right) = v.split_at_mut(6);
392 /// assert!(left == [1i, 2, 3, 4, 5, 6]);
393 /// assert!(right == []);
396 #[unstable = "waiting on final error conventions"]
397 fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]);
399 /// Reverse the order of elements in a slice, in place.
404 /// let mut v = [1i, 2, 3];
406 /// assert!(v == [3i, 2, 1]);
408 #[experimental = "may be moved to iterators instead"]
409 fn reverse(&mut self);
411 /// Returns an unsafe mutable pointer to the element in index
412 #[experimental = "waiting on unsafe conventions"]
413 unsafe fn unsafe_mut<'a>(&'a mut self, index: uint) -> &'a mut T;
415 /// Return an unsafe mutable pointer to the slice's buffer.
417 /// The caller must ensure that the slice outlives the pointer this
418 /// function returns, or else it will end up pointing to garbage.
420 /// Modifying the slice may cause its buffer to be reallocated, which
421 /// would also make any pointers to it invalid.
424 fn as_mut_ptr(&mut self) -> *mut T;
428 impl<T> SlicePrelude<T> for [T] {
430 fn slice(&self, start: uint, end: uint) -> &[T] {
431 assert!(start <= end);
432 assert!(end <= self.len());
435 data: self.as_ptr().offset(start as int),
442 fn slice_from(&self, start: uint) -> &[T] {
443 self.slice(start, self.len())
447 fn slice_to(&self, end: uint) -> &[T] {
452 fn split_at(&self, mid: uint) -> (&[T], &[T]) {
453 (self[..mid], self[mid..])
457 fn iter<'a>(&'a self) -> Items<'a, T> {
459 let p = self.as_ptr();
460 if mem::size_of::<T>() == 0 {
462 end: (p as uint + self.len()) as *const T,
463 marker: marker::ContravariantLifetime::<'a>}
466 end: p.offset(self.len() as int),
467 marker: marker::ContravariantLifetime::<'a>}
473 fn split<'a>(&'a self, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
482 fn splitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>> {
484 iter: self.split(pred),
491 fn rsplitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>> {
493 iter: self.split(pred),
500 fn windows(&self, size: uint) -> Windows<T> {
502 Windows { v: self, size: size }
506 fn chunks(&self, size: uint) -> Chunks<T> {
508 Chunks { v: self, size: size }
512 fn get(&self, index: uint) -> Option<&T> {
513 if index < self.len() { Some(&self[index]) } else { None }
517 fn head(&self) -> Option<&T> {
518 if self.len() == 0 { None } else { Some(&self[0]) }
522 fn tail(&self) -> &[T] { self[1..] }
525 fn init(&self) -> &[T] {
526 self[..self.len() - 1]
530 fn last(&self) -> Option<&T> {
531 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
535 unsafe fn unsafe_get(&self, index: uint) -> &T {
536 transmute(self.repr().data.offset(index as int))
540 fn as_ptr(&self) -> *const T {
545 fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult {
546 let mut base : uint = 0;
547 let mut lim : uint = self.len();
550 let ix = base + (lim >> 1);
552 Equal => return BinarySearchResult::Found(ix),
561 return BinarySearchResult::NotFound(base);
565 fn len(&self) -> uint { self.repr().len }
568 fn get_mut(&mut self, index: uint) -> Option<&mut T> {
569 if index < self.len() { Some(&mut self[index]) } else { None }
573 fn as_mut_slice(&mut self) -> &mut [T] { self }
575 fn slice_mut(&mut self, start: uint, end: uint) -> &mut [T] {
580 fn slice_from_mut(&mut self, start: uint) -> &mut [T] {
585 fn slice_to_mut(&mut self, end: uint) -> &mut [T] {
590 fn split_at_mut(&mut self, mid: uint) -> (&mut [T], &mut [T]) {
592 let self2: &mut [T] = mem::transmute_copy(&self);
593 (self[mut ..mid], self2[mut mid..])
598 fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
600 let p = self.as_mut_ptr();
601 if mem::size_of::<T>() == 0 {
603 end: (p as uint + self.len()) as *mut T,
604 marker: marker::ContravariantLifetime::<'a>,
605 marker2: marker::NoCopy}
608 end: p.offset(self.len() as int),
609 marker: marker::ContravariantLifetime::<'a>,
610 marker2: marker::NoCopy}
616 fn last_mut(&mut self) -> Option<&mut T> {
617 let len = self.len();
618 if len == 0 { return None; }
619 Some(&mut self[len - 1])
623 fn head_mut(&mut self) -> Option<&mut T> {
624 if self.len() == 0 { None } else { Some(&mut self[0]) }
628 fn tail_mut(&mut self) -> &mut [T] {
629 let len = self.len();
634 fn init_mut(&mut self) -> &mut [T] {
635 let len = self.len();
640 fn split_mut<'a>(&'a mut self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T> {
641 MutSplits { v: self, pred: pred, finished: false }
645 fn splitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>> {
647 iter: self.split_mut(pred),
654 fn rsplitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>> {
656 iter: self.split_mut(pred),
663 fn chunks_mut(&mut self, chunk_size: uint) -> MutChunks<T> {
664 assert!(chunk_size > 0);
665 MutChunks { v: self, chunk_size: chunk_size }
668 fn swap(&mut self, a: uint, b: uint) {
670 // Can't take two mutable loans from one vector, so instead just cast
671 // them to their raw pointers to do the swap
672 let pa: *mut T = &mut self[a];
673 let pb: *mut T = &mut self[b];
678 fn reverse(&mut self) {
682 // Unsafe swap to avoid the bounds check in safe swap.
684 let pa: *mut T = self.unsafe_mut(i);
685 let pb: *mut T = self.unsafe_mut(ln - i - 1);
693 unsafe fn unsafe_mut(&mut self, index: uint) -> &mut T {
694 transmute((self.repr().data as *mut T).offset(index as int))
698 fn as_mut_ptr(&mut self) -> *mut T {
699 self.repr().data as *mut T
703 impl<T> ops::Index<uint, T> for [T] {
704 fn index(&self, &index: &uint) -> &T {
705 assert!(index < self.len());
707 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
711 impl<T> ops::IndexMut<uint, T> for [T] {
712 fn index_mut(&mut self, &index: &uint) -> &mut T {
713 assert!(index < self.len());
715 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
719 impl<T> ops::Slice<uint, [T]> for [T] {
721 fn as_slice_<'a>(&'a self) -> &'a [T] {
726 fn slice_from_or_fail<'a>(&'a self, start: &uint) -> &'a [T] {
727 self.slice_or_fail(start, &self.len())
731 fn slice_to_or_fail<'a>(&'a self, end: &uint) -> &'a [T] {
732 self.slice_or_fail(&0, end)
735 fn slice_or_fail<'a>(&'a self, start: &uint, end: &uint) -> &'a [T] {
736 assert!(*start <= *end);
737 assert!(*end <= self.len());
740 data: self.as_ptr().offset(*start as int),
747 impl<T> ops::SliceMut<uint, [T]> for [T] {
749 fn as_mut_slice_<'a>(&'a mut self) -> &'a mut [T] {
754 fn slice_from_or_fail_mut<'a>(&'a mut self, start: &uint) -> &'a mut [T] {
755 let len = &self.len();
756 self.slice_or_fail_mut(start, len)
760 fn slice_to_or_fail_mut<'a>(&'a mut self, end: &uint) -> &'a mut [T] {
761 self.slice_or_fail_mut(&0, end)
764 fn slice_or_fail_mut<'a>(&'a mut self, start: &uint, end: &uint) -> &'a mut [T] {
765 assert!(*start <= *end);
766 assert!(*end <= self.len());
769 data: self.as_ptr().offset(*start as int),
776 /// Extension methods for slices containing `PartialEq` elements.
777 #[unstable = "may merge with other traits"]
778 pub trait PartialEqSlicePrelude<T: PartialEq> for Sized? {
779 /// Find the first index containing a matching value.
780 fn position_elem(&self, t: &T) -> Option<uint>;
782 /// Find the last index containing a matching value.
783 fn rposition_elem(&self, t: &T) -> Option<uint>;
785 /// Return true if the slice contains an element with the given value.
786 fn contains(&self, x: &T) -> bool;
788 /// Returns true if `needle` is a prefix of the slice.
789 fn starts_with(&self, needle: &[T]) -> bool;
791 /// Returns true if `needle` is a suffix of the slice.
792 fn ends_with(&self, needle: &[T]) -> bool;
795 #[unstable = "trait is unstable"]
796 impl<T: PartialEq> PartialEqSlicePrelude<T> for [T] {
798 fn position_elem(&self, x: &T) -> Option<uint> {
799 self.iter().position(|y| *x == *y)
803 fn rposition_elem(&self, t: &T) -> Option<uint> {
804 self.iter().rposition(|x| *x == *t)
808 fn contains(&self, x: &T) -> bool {
809 self.iter().any(|elt| *x == *elt)
813 fn starts_with(&self, needle: &[T]) -> bool {
814 let n = needle.len();
815 self.len() >= n && needle == self[..n]
819 fn ends_with(&self, needle: &[T]) -> bool {
820 let (m, n) = (self.len(), needle.len());
821 m >= n && needle == self[m-n..]
825 /// Extension methods for slices containing `Ord` elements.
826 #[unstable = "may merge with other traits"]
827 pub trait OrdSlicePrelude<T: Ord> for Sized? {
828 /// Binary search a sorted slice for a given element.
830 /// If the value is found then `Found` is returned, containing the
831 /// index of the matching element; if the value is not found then
832 /// `NotFound` is returned, containing the index where a matching
833 /// element could be inserted while maintaining sorted order.
837 /// Looks up a series of four elements. The first is found, with a
838 /// uniquely determined position; the second and third are not
839 /// found; the fourth could match any position in `[1,4]`.
842 /// use std::slice::BinarySearchResult::{Found, NotFound};
843 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
844 /// let s = s.as_slice();
846 /// assert_eq!(s.binary_search_elem(&13), Found(9));
847 /// assert_eq!(s.binary_search_elem(&4), NotFound(7));
848 /// assert_eq!(s.binary_search_elem(&100), NotFound(13));
849 /// let r = s.binary_search_elem(&1);
850 /// assert!(match r { Found(1...4) => true, _ => false, });
852 #[unstable = "name likely to change"]
853 fn binary_search_elem(&self, x: &T) -> BinarySearchResult;
855 /// Mutates the slice to the next lexicographic permutation.
857 /// Returns `true` if successful and `false` if the slice is at the
858 /// last-ordered permutation.
863 /// let v: &mut [_] = &mut [0i, 1, 2];
864 /// v.next_permutation();
865 /// let b: &mut [_] = &mut [0i, 2, 1];
867 /// v.next_permutation();
868 /// let b: &mut [_] = &mut [1i, 0, 2];
872 fn next_permutation(&mut self) -> bool;
874 /// Mutates the slice to the previous lexicographic permutation.
876 /// Returns `true` if successful and `false` if the slice is at the
877 /// first-ordered permutation.
882 /// let v: &mut [_] = &mut [1i, 0, 2];
883 /// v.prev_permutation();
884 /// let b: &mut [_] = &mut [0i, 2, 1];
886 /// v.prev_permutation();
887 /// let b: &mut [_] = &mut [0i, 1, 2];
891 fn prev_permutation(&mut self) -> bool;
894 #[unstable = "trait is unstable"]
895 impl<T: Ord> OrdSlicePrelude<T> for [T] {
897 fn binary_search_elem(&self, x: &T) -> BinarySearchResult {
898 self.binary_search(|p| p.cmp(x))
902 fn next_permutation(&mut self) -> bool {
903 // These cases only have 1 permutation each, so we can't do anything.
904 if self.len() < 2 { return false; }
906 // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
907 let mut i = self.len() - 1;
908 while i > 0 && self[i-1] >= self[i] {
912 // If that is the entire vector, this is the last-ordered permutation.
917 // Step 2: Find the rightmost element larger than the pivot (i-1)
918 let mut j = self.len() - 1;
919 while j >= i && self[j] <= self[i-1] {
923 // Step 3: Swap that element with the pivot
926 // Step 4: Reverse the (previously) weakly decreasing part
927 self[mut i..].reverse();
933 fn prev_permutation(&mut self) -> bool {
934 // These cases only have 1 permutation each, so we can't do anything.
935 if self.len() < 2 { return false; }
937 // Step 1: Identify the longest, rightmost weakly increasing part of the vector
938 let mut i = self.len() - 1;
939 while i > 0 && self[i-1] <= self[i] {
943 // If that is the entire vector, this is the first-ordered permutation.
948 // Step 2: Reverse the weakly increasing part
949 self[mut i..].reverse();
951 // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
952 let mut j = self.len() - 1;
953 while j >= i && self[j-1] < self[i-1] {
957 // Step 4: Swap that element with the pivot
964 /// Extension methods for slices on Clone elements
965 #[unstable = "may merge with other traits"]
966 pub trait CloneSlicePrelude<T> for Sized? {
967 /// Copies as many elements from `src` as it can into `self` (the
968 /// shorter of `self.len()` and `src.len()`). Returns the number
969 /// of elements copied.
974 /// use std::slice::CloneSlicePrelude;
976 /// let mut dst = [0i, 0, 0];
977 /// let src = [1i, 2];
979 /// assert!(dst.clone_from_slice(&src) == 2);
980 /// assert!(dst == [1, 2, 0]);
982 /// let src2 = [3i, 4, 5, 6];
983 /// assert!(dst.clone_from_slice(&src2) == 3);
984 /// assert!(dst == [3i, 4, 5]);
986 fn clone_from_slice(&mut self, &[T]) -> uint;
989 #[unstable = "trait is unstable"]
990 impl<T: Clone> CloneSlicePrelude<T> for [T] {
992 fn clone_from_slice(&mut self, src: &[T]) -> uint {
993 let min = cmp::min(self.len(), src.len());
994 let dst = self.slice_to_mut(min);
995 let src = src.slice_to(min);
996 for i in range(0, min) {
997 dst[i].clone_from(&src[i]);
1010 /// Data that is viewable as a slice.
1011 #[unstable = "may merge with other traits"]
1012 pub trait AsSlice<T> for Sized? {
1013 /// Work with `self` as a slice.
1014 fn as_slice<'a>(&'a self) -> &'a [T];
1017 #[unstable = "trait is unstable"]
1018 impl<T> AsSlice<T> for [T] {
1020 fn as_slice<'a>(&'a self) -> &'a [T] { self }
1023 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U {
1025 fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
1028 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U {
1030 fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
1033 #[unstable = "waiting for DST"]
1034 impl<'a, T> Default for &'a [T] {
1035 fn default() -> &'a [T] { &[] }
1042 // The shared definition of the `Item` and `MutItems` iterators
1043 macro_rules! iterator {
1044 (struct $name:ident -> $ptr:ty, $elem:ty) => {
1045 #[experimental = "needs review"]
1046 impl<'a, T> Iterator<$elem> for $name<'a, T> {
1048 fn next(&mut self) -> Option<$elem> {
1049 // could be implemented with slices, but this avoids bounds checks
1051 if self.ptr == self.end {
1054 if mem::size_of::<T>() == 0 {
1055 // purposefully don't use 'ptr.offset' because for
1056 // vectors with 0-size elements this would return the
1058 self.ptr = transmute(self.ptr as uint + 1);
1060 // Use a non-null pointer value
1064 self.ptr = self.ptr.offset(1);
1066 Some(transmute(old))
1073 fn size_hint(&self) -> (uint, Option<uint>) {
1074 let diff = (self.end as uint) - (self.ptr as uint);
1075 let size = mem::size_of::<T>();
1076 let exact = diff / (if size == 0 {1} else {size});
1077 (exact, Some(exact))
1081 #[experimental = "needs review"]
1082 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
1084 fn next_back(&mut self) -> Option<$elem> {
1085 // could be implemented with slices, but this avoids bounds checks
1087 if self.end == self.ptr {
1090 if mem::size_of::<T>() == 0 {
1091 // See above for why 'ptr.offset' isn't used
1092 self.end = transmute(self.end as uint - 1);
1094 // Use a non-null pointer value
1097 self.end = self.end.offset(-1);
1099 Some(transmute(self.end))
1108 macro_rules! make_slice {
1109 ($t: ty -> $result: ty: $start: expr, $end: expr) => {{
1110 let diff = $end as uint - $start as uint;
1111 let len = if mem::size_of::<T>() == 0 {
1114 diff / mem::size_of::<$t>()
1117 transmute::<_, $result>(RawSlice { data: $start as *const T, len: len })
1123 /// Immutable slice iterator
1124 #[experimental = "needs review"]
1125 pub struct Items<'a, T: 'a> {
1128 marker: marker::ContravariantLifetime<'a>
1132 impl<'a, T> ops::Slice<uint, [T]> for Items<'a, T> {
1133 fn as_slice_(&self) -> &[T] {
1136 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
1138 self.as_slice().slice_from_or_fail(from)
1140 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
1142 self.as_slice().slice_to_or_fail(to)
1144 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
1146 self.as_slice().slice_or_fail(from, to)
1150 impl<'a, T> Items<'a, T> {
1151 /// View the underlying data as a subslice of the original data.
1153 /// This has the same lifetime as the original slice, and so the
1154 /// iterator can continue to be used while this exists.
1156 pub fn as_slice(&self) -> &'a [T] {
1157 make_slice!(T -> &'a [T]: self.ptr, self.end)
1161 impl<'a,T> Copy for Items<'a,T> {}
1163 iterator!{struct Items -> *const T, &'a T}
1165 #[experimental = "needs review"]
1166 impl<'a, T> ExactSizeIterator<&'a T> for Items<'a, T> {}
1168 #[experimental = "needs review"]
1169 impl<'a, T> Clone for Items<'a, T> {
1170 fn clone(&self) -> Items<'a, T> { *self }
1173 #[experimental = "needs review"]
1174 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
1176 fn indexable(&self) -> uint {
1177 let (exact, _) = self.size_hint();
1182 fn idx(&mut self, index: uint) -> Option<&'a T> {
1184 if index < self.indexable() {
1185 if mem::size_of::<T>() == 0 {
1186 // Use a non-null pointer value
1189 Some(transmute(self.ptr.offset(index as int)))
1198 /// Mutable slice iterator.
1199 #[experimental = "needs review"]
1200 pub struct MutItems<'a, T: 'a> {
1203 marker: marker::ContravariantLifetime<'a>,
1204 marker2: marker::NoCopy
1208 impl<'a, T> ops::Slice<uint, [T]> for MutItems<'a, T> {
1209 fn as_slice_<'b>(&'b self) -> &'b [T] {
1210 make_slice!(T -> &'b [T]: self.ptr, self.end)
1212 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
1214 self.as_slice_().slice_from_or_fail(from)
1216 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
1218 self.as_slice_().slice_to_or_fail(to)
1220 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
1222 self.as_slice_().slice_or_fail(from, to)
1227 impl<'a, T> ops::SliceMut<uint, [T]> for MutItems<'a, T> {
1228 fn as_mut_slice_<'b>(&'b mut self) -> &'b mut [T] {
1229 make_slice!(T -> &'b mut [T]: self.ptr, self.end)
1231 fn slice_from_or_fail_mut<'b>(&'b mut self, from: &uint) -> &'b mut [T] {
1233 self.as_mut_slice_().slice_from_or_fail_mut(from)
1235 fn slice_to_or_fail_mut<'b>(&'b mut self, to: &uint) -> &'b mut [T] {
1237 self.as_mut_slice_().slice_to_or_fail_mut(to)
1239 fn slice_or_fail_mut<'b>(&'b mut self, from: &uint, to: &uint) -> &'b mut [T] {
1241 self.as_mut_slice_().slice_or_fail_mut(from, to)
1245 impl<'a, T> MutItems<'a, T> {
1246 /// View the underlying data as a subslice of the original data.
1248 /// To avoid creating `&mut` references that alias, this is forced
1249 /// to consume the iterator. Consider using the `Slice` and
1250 /// `SliceMut` implementations for obtaining slices with more
1251 /// restricted lifetimes that do not consume the iterator.
1253 pub fn into_slice(self) -> &'a mut [T] {
1254 make_slice!(T -> &'a mut [T]: self.ptr, self.end)
1258 iterator!{struct MutItems -> *mut T, &'a mut T}
1260 #[experimental = "needs review"]
1261 impl<'a, T> ExactSizeIterator<&'a mut T> for MutItems<'a, T> {}
1263 /// An abstraction over the splitting iterators, so that splitn, splitn_mut etc
1264 /// can be implemented once.
1265 trait SplitsIter<E>: DoubleEndedIterator<E> {
1266 /// Mark the underlying iterator as complete, extracting the remaining
1267 /// portion of the slice.
1268 fn finish(&mut self) -> Option<E>;
1271 /// An iterator over subslices separated by elements that match a predicate
1273 #[experimental = "needs review"]
1274 pub struct Splits<'a, T:'a> {
1276 pred: |t: &T|: 'a -> bool,
1280 #[experimental = "needs review"]
1281 impl<'a, T> Iterator<&'a [T]> for Splits<'a, T> {
1283 fn next(&mut self) -> Option<&'a [T]> {
1284 if self.finished { return None; }
1286 match self.v.iter().position(|x| (self.pred)(x)) {
1287 None => self.finish(),
1289 let ret = Some(self.v[..idx]);
1290 self.v = self.v[idx + 1..];
1297 fn size_hint(&self) -> (uint, Option<uint>) {
1301 (1, Some(self.v.len() + 1))
1306 #[experimental = "needs review"]
1307 impl<'a, T> DoubleEndedIterator<&'a [T]> for Splits<'a, T> {
1309 fn next_back(&mut self) -> Option<&'a [T]> {
1310 if self.finished { return None; }
1312 match self.v.iter().rposition(|x| (self.pred)(x)) {
1313 None => self.finish(),
1315 let ret = Some(self.v[idx + 1..]);
1316 self.v = self.v[..idx];
1323 impl<'a, T> SplitsIter<&'a [T]> for Splits<'a, T> {
1325 fn finish(&mut self) -> Option<&'a [T]> {
1326 if self.finished { None } else { self.finished = true; Some(self.v) }
1330 /// An iterator over the subslices of the vector which are separated
1331 /// by elements that match `pred`.
1332 #[experimental = "needs review"]
1333 pub struct MutSplits<'a, T:'a> {
1335 pred: |t: &T|: 'a -> bool,
1339 impl<'a, T> SplitsIter<&'a mut [T]> for MutSplits<'a, T> {
1341 fn finish(&mut self) -> Option<&'a mut [T]> {
1345 self.finished = true;
1346 Some(mem::replace(&mut self.v, &mut []))
1351 #[experimental = "needs review"]
1352 impl<'a, T> Iterator<&'a mut [T]> for MutSplits<'a, T> {
1354 fn next(&mut self) -> Option<&'a mut [T]> {
1355 if self.finished { return None; }
1357 let idx_opt = { // work around borrowck limitations
1358 let pred = &mut self.pred;
1359 self.v.iter().position(|x| (*pred)(x))
1362 None => self.finish(),
1364 let tmp = mem::replace(&mut self.v, &mut []);
1365 let (head, tail) = tmp.split_at_mut(idx);
1366 self.v = tail[mut 1..];
1373 fn size_hint(&self) -> (uint, Option<uint>) {
1377 // if the predicate doesn't match anything, we yield one slice
1378 // if it matches every element, we yield len+1 empty slices.
1379 (1, Some(self.v.len() + 1))
1384 #[experimental = "needs review"]
1385 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T> {
1387 fn next_back(&mut self) -> Option<&'a mut [T]> {
1388 if self.finished { return None; }
1390 let idx_opt = { // work around borrowck limitations
1391 let pred = &mut self.pred;
1392 self.v.iter().rposition(|x| (*pred)(x))
1395 None => self.finish(),
1397 let tmp = mem::replace(&mut self.v, &mut []);
1398 let (head, tail) = tmp.split_at_mut(idx);
1406 /// An iterator over subslices separated by elements that match a predicate
1407 /// function, splitting at most a fixed number of times.
1408 #[experimental = "needs review"]
1409 pub struct SplitsN<I> {
1415 #[experimental = "needs review"]
1416 impl<E, I: SplitsIter<E>> Iterator<E> for SplitsN<I> {
1418 fn next(&mut self) -> Option<E> {
1419 if self.count == 0 {
1423 if self.invert { self.iter.next_back() } else { self.iter.next() }
1428 fn size_hint(&self) -> (uint, Option<uint>) {
1429 let (lower, upper_opt) = self.iter.size_hint();
1430 (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper)))
1434 /// An iterator over overlapping subslices of length `size`.
1436 #[experimental = "needs review"]
1437 pub struct Windows<'a, T:'a> {
1442 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
1444 fn next(&mut self) -> Option<&'a [T]> {
1445 if self.size > self.v.len() {
1448 let ret = Some(self.v[..self.size]);
1449 self.v = self.v[1..];
1455 fn size_hint(&self) -> (uint, Option<uint>) {
1456 if self.size > self.v.len() {
1459 let x = self.v.len() - self.size;
1460 (x.saturating_add(1), x.checked_add(1u))
1465 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1468 /// When the slice len is not evenly divided by the chunk size, the last slice
1469 /// of the iteration will be the remainder.
1471 #[experimental = "needs review"]
1472 pub struct Chunks<'a, T:'a> {
1477 #[experimental = "needs review"]
1478 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
1480 fn next(&mut self) -> Option<&'a [T]> {
1481 if self.v.len() == 0 {
1484 let chunksz = cmp::min(self.v.len(), self.size);
1485 let (fst, snd) = self.v.split_at(chunksz);
1492 fn size_hint(&self) -> (uint, Option<uint>) {
1493 if self.v.len() == 0 {
1496 let n = self.v.len() / self.size;
1497 let rem = self.v.len() % self.size;
1498 let n = if rem > 0 { n+1 } else { n };
1504 #[experimental = "needs review"]
1505 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
1507 fn next_back(&mut self) -> Option<&'a [T]> {
1508 if self.v.len() == 0 {
1511 let remainder = self.v.len() % self.size;
1512 let chunksz = if remainder != 0 { remainder } else { self.size };
1513 let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1520 #[experimental = "needs review"]
1521 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
1523 fn indexable(&self) -> uint {
1524 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1528 fn idx(&mut self, index: uint) -> Option<&'a [T]> {
1529 if index < self.indexable() {
1530 let lo = index * self.size;
1531 let mut hi = lo + self.size;
1532 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1534 Some(self.v[lo..hi])
1541 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1542 /// elements at a time). When the slice len is not evenly divided by the chunk
1543 /// size, the last slice of the iteration will be the remainder.
1544 #[experimental = "needs review"]
1545 pub struct MutChunks<'a, T:'a> {
1550 #[experimental = "needs review"]
1551 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
1553 fn next(&mut self) -> Option<&'a mut [T]> {
1554 if self.v.len() == 0 {
1557 let sz = cmp::min(self.v.len(), self.chunk_size);
1558 let tmp = mem::replace(&mut self.v, &mut []);
1559 let (head, tail) = tmp.split_at_mut(sz);
1566 fn size_hint(&self) -> (uint, Option<uint>) {
1567 if self.v.len() == 0 {
1570 let n = self.v.len() / self.chunk_size;
1571 let rem = self.v.len() % self.chunk_size;
1572 let n = if rem > 0 { n + 1 } else { n };
1578 #[experimental = "needs review"]
1579 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
1581 fn next_back(&mut self) -> Option<&'a mut [T]> {
1582 if self.v.len() == 0 {
1585 let remainder = self.v.len() % self.chunk_size;
1586 let sz = if remainder != 0 { remainder } else { self.chunk_size };
1587 let tmp = mem::replace(&mut self.v, &mut []);
1588 let tmp_len = tmp.len();
1589 let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1598 /// The result of calling `binary_search`.
1600 /// `Found` means the search succeeded, and the contained value is the
1601 /// index of the matching element. `NotFound` means the search
1602 /// succeeded, and the contained value is an index where a matching
1603 /// value could be inserted while maintaining sort order.
1604 #[deriving(PartialEq, Show)]
1605 #[experimental = "needs review"]
1606 pub enum BinarySearchResult {
1607 /// The index of the found value.
1609 /// The index where the value should have been found.
1613 impl Copy for BinarySearchResult {}
1615 #[experimental = "needs review"]
1616 impl BinarySearchResult {
1617 /// Converts a `Found` to `Some`, `NotFound` to `None`.
1618 /// Similar to `Result::ok`.
1619 pub fn found(&self) -> Option<uint> {
1621 BinarySearchResult::Found(i) => Some(i),
1622 BinarySearchResult::NotFound(_) => None
1626 /// Convert a `Found` to `None`, `NotFound` to `Some`.
1627 /// Similar to `Result::err`.
1628 pub fn not_found(&self) -> Option<uint> {
1630 BinarySearchResult::Found(_) => None,
1631 BinarySearchResult::NotFound(i) => Some(i)
1642 /// Converts a pointer to A into a slice of length 1 (without copying).
1643 #[unstable = "waiting for DST"]
1644 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1646 transmute(RawSlice { data: s, len: 1 })
1650 /// Converts a pointer to A into a slice of length 1 (without copying).
1651 #[unstable = "waiting for DST"]
1652 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1654 let ptr: *const A = transmute(s);
1655 transmute(RawSlice { data: ptr, len: 1 })
1659 /// Forms a slice from a pointer and a length.
1661 /// The pointer given is actually a reference to the base of the slice. This
1662 /// reference is used to give a concrete lifetime to tie the returned slice to.
1663 /// Typically this should indicate that the slice is valid for as long as the
1664 /// pointer itself is valid.
1666 /// The `len` argument is the number of **elements**, not the number of bytes.
1668 /// This function is unsafe as there is no guarantee that the given pointer is
1669 /// valid for `len` elements, nor whether the lifetime provided is a suitable
1670 /// lifetime for the returned slice.
1677 /// // manifest a slice out of thin air!
1678 /// let ptr = 0x1234 as *const uint;
1681 /// let slice = slice::from_raw_buf(&ptr, amt);
1685 #[unstable = "just renamed from `mod raw`"]
1686 pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] {
1687 transmute(RawSlice { data: *p, len: len })
1690 /// Performs the same functionality as `from_raw_buf`, except that a mutable
1691 /// slice is returned.
1693 /// This function is unsafe for the same reasons as `from_raw_buf`, as well as
1694 /// not being able to provide a non-aliasing guarantee of the returned mutable
1697 #[unstable = "just renamed from `mod raw`"]
1698 pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] {
1699 transmute(RawSlice { data: *p as *const T, len: len })
1706 /// Unsafe operations
1713 use option::Option::{None, Some};
1715 /// Form a slice from a pointer and length (as a number of units,
1718 #[deprecated = "renamed to slice::from_raw_buf"]
1719 pub unsafe fn buf_as_slice<T,U>(p: *const T, len: uint, f: |v: &[T]| -> U)
1727 /// Form a slice from a pointer and length (as a number of units,
1730 #[deprecated = "renamed to slice::from_raw_mut_buf"]
1731 pub unsafe fn mut_buf_as_slice<T,
1735 f: |v: &mut [T]| -> U)
1738 data: p as *const T,
1743 /// Returns a pointer to first element in slice and adjusts
1744 /// slice so it no longer contains that element. Returns None
1745 /// if the slice is empty. O(1).
1747 #[deprecated = "inspect `Slice::{data, len}` manually (increment data by 1)"]
1748 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1749 if slice.len == 0 { return None; }
1750 let head: *const T = slice.data;
1751 slice.data = slice.data.offset(1);
1756 /// Returns a pointer to last element in slice and adjusts
1757 /// slice so it no longer contains that element. Returns None
1758 /// if the slice is empty. O(1).
1760 #[deprecated = "inspect `Slice::{data, len}` manually (decrement len by 1)"]
1761 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1762 if slice.len == 0 { return None; }
1763 let tail: *const T = slice.data.offset((slice.len - 1) as int);
1769 /// Operations on `[u8]`.
1770 #[experimental = "needs review"]
1774 use slice::SlicePrelude;
1776 /// A trait for operations on mutable `[u8]`s.
1777 pub trait MutableByteVector for Sized? {
1778 /// Sets all bytes of the receiver to the given value.
1779 fn set_memory(&mut self, value: u8);
1782 impl MutableByteVector for [u8] {
1784 #[allow(experimental)]
1785 fn set_memory(&mut self, value: u8) {
1786 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1790 /// Copies data from `src` to `dst`
1792 /// Panics if the length of `dst` is less than the length of `src`.
1794 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1795 let len_src = src.len();
1796 assert!(dst.len() >= len_src);
1797 // `dst` is unaliasable, so we know statically it doesn't overlap
1800 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(),
1810 // Boilerplate traits
1813 #[unstable = "waiting for DST"]
1814 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1815 fn eq(&self, other: &[B]) -> bool {
1816 self.len() == other.len() &&
1817 order::eq(self.iter(), other.iter())
1819 fn ne(&self, other: &[B]) -> bool {
1820 self.len() != other.len() ||
1821 order::ne(self.iter(), other.iter())
1825 #[unstable = "waiting for DST"]
1826 impl<T: Eq> Eq for [T] {}
1828 #[allow(deprecated)]
1829 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1830 impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
1832 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1835 #[allow(deprecated)]
1836 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1837 impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
1839 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1842 #[unstable = "waiting for DST"]
1843 impl<T: Ord> Ord for [T] {
1844 fn cmp(&self, other: &[T]) -> Ordering {
1845 order::cmp(self.iter(), other.iter())
1849 #[unstable = "waiting for DST"]
1850 impl<T: PartialOrd> PartialOrd for [T] {
1852 fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1853 order::partial_cmp(self.iter(), other.iter())
1856 fn lt(&self, other: &[T]) -> bool {
1857 order::lt(self.iter(), other.iter())
1860 fn le(&self, other: &[T]) -> bool {
1861 order::le(self.iter(), other.iter())
1864 fn ge(&self, other: &[T]) -> bool {
1865 order::ge(self.iter(), other.iter())
1868 fn gt(&self, other: &[T]) -> bool {
1869 order::gt(self.iter(), other.iter())
1873 /// Extension methods for immutable slices containing integers.
1875 pub trait ImmutableIntSlice<U, S> for Sized? {
1876 /// Converts the slice to an immutable slice of unsigned integers with the same width.
1877 fn as_unsigned<'a>(&'a self) -> &'a [U];
1878 /// Converts the slice to an immutable slice of signed integers with the same width.
1879 fn as_signed<'a>(&'a self) -> &'a [S];
1882 /// Extension methods for mutable slices containing integers.
1884 pub trait MutableIntSlice<U, S> for Sized?: ImmutableIntSlice<U, S> {
1885 /// Converts the slice to a mutable slice of unsigned integers with the same width.
1886 fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1887 /// Converts the slice to a mutable slice of signed integers with the same width.
1888 fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1891 macro_rules! impl_immut_int_slice {
1892 ($u:ty, $s:ty, $t:ty) => {
1894 impl ImmutableIntSlice<$u, $s> for [$t] {
1896 fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1898 fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1902 macro_rules! impl_mut_int_slice {
1903 ($u:ty, $s:ty, $t:ty) => {
1905 impl MutableIntSlice<$u, $s> for [$t] {
1907 fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1909 fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1914 macro_rules! impl_int_slice {
1916 impl_immut_int_slice!($u, $s, $u)
1917 impl_immut_int_slice!($u, $s, $s)
1918 impl_mut_int_slice!($u, $s, $u)
1919 impl_mut_int_slice!($u, $s, $s)
1923 impl_int_slice!(u8, i8)
1924 impl_int_slice!(u16, i16)
1925 impl_int_slice!(u32, i32)
1926 impl_int_slice!(u64, i64)
1927 impl_int_slice!(uint, int)