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::{PartialEq, PartialOrd, Eq, Ord, Ordering, Less, Equal, Greater, Equiv};
45 use option::{None, Option, Some};
50 use kinds::{Sized, marker};
52 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
53 use raw::Slice as RawSlice;
60 /// Extension methods for slices.
61 #[unstable = "may merge with other traits"]
62 pub trait SlicePrelude<T> for Sized? {
63 /// Returns a subslice spanning the interval [`start`, `end`).
65 /// Panics when the end of the new slice lies beyond the end of the
66 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
68 /// Slicing with `start` equal to `end` yields an empty slice.
69 #[unstable = "waiting on final error conventions/slicing syntax"]
70 fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T];
72 /// Returns a subslice from `start` to the end of the slice.
74 /// Panics when `start` is strictly greater than the length of the original slice.
76 /// Slicing from `self.len()` yields an empty slice.
77 #[unstable = "waiting on final error conventions/slicing syntax"]
78 fn slice_from<'a>(&'a self, start: uint) -> &'a [T];
80 /// Returns a subslice from the start of the slice to `end`.
82 /// Panics when `end` is strictly greater than the length of the original slice.
84 /// Slicing to `0` yields an empty slice.
85 #[unstable = "waiting on final error conventions/slicing syntax"]
86 fn slice_to<'a>(&'a self, end: uint) -> &'a [T];
88 /// Divides one slice into two at an index.
90 /// The first will contain all indices from `[0, mid)` (excluding
91 /// the index `mid` itself) and the second will contain all
92 /// indices from `[mid, len)` (excluding the index `len` itself).
94 /// Panics if `mid > len`.
95 #[unstable = "waiting on final error conventions"]
96 fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]);
98 /// Returns an iterator over the slice
99 #[unstable = "iterator type may change"]
100 fn iter<'a>(&'a self) -> Items<'a, T>;
102 /// Returns an iterator over subslices separated by elements that match
103 /// `pred`. The matched element is not contained in the subslices.
104 #[unstable = "iterator type may change, waiting on unboxed closures"]
105 fn split<'a>(&'a self, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
107 /// Returns an iterator over subslices separated by elements that match
108 /// `pred`, limited to splitting at most `n` times. The matched element is
109 /// not contained in the subslices.
110 #[unstable = "iterator type may change"]
111 fn splitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>>;
113 /// Returns an iterator over subslices separated by elements that match
114 /// `pred` limited to splitting at most `n` times. This starts at the end of
115 /// the slice and works backwards. The matched element is not contained in
117 #[unstable = "iterator type may change"]
118 fn rsplitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>>;
120 /// Returns an iterator over all contiguous windows of length
121 /// `size`. The windows overlap. If the slice is shorter than
122 /// `size`, the iterator returns no values.
126 /// Panics if `size` is 0.
130 /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
134 /// let v = &[1i, 2, 3, 4];
135 /// for win in v.windows(2) {
136 /// println!("{}", win);
139 #[unstable = "iterator type may change"]
140 fn windows<'a>(&'a self, size: uint) -> Windows<'a, T>;
142 /// Returns an iterator over `size` elements of the slice at a
143 /// time. The chunks do not overlap. If `size` does not divide the
144 /// length of the slice, then the last chunk will not have length
149 /// Panics if `size` is 0.
153 /// Print the slice two elements at a time (i.e. `[1,2]`,
157 /// let v = &[1i, 2, 3, 4, 5];
158 /// for win in v.chunks(2) {
159 /// println!("{}", win);
162 #[unstable = "iterator type may change"]
163 fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T>;
165 /// Returns the element of a slice at the given index, or `None` if the
166 /// index is out of bounds.
167 #[unstable = "waiting on final collection conventions"]
168 fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
170 /// Returns the first element of a slice, or `None` if it is empty.
171 #[unstable = "name may change"]
172 fn head<'a>(&'a self) -> Option<&'a T>;
174 /// Returns all but the first element of a slice.
175 #[unstable = "name may change"]
176 fn tail<'a>(&'a self) -> &'a [T];
178 /// Returns all but the last element of a slice.
179 #[unstable = "name may change"]
180 fn init<'a>(&'a self) -> &'a [T];
182 /// Returns the last element of a slice, or `None` if it is empty.
183 #[unstable = "name may change"]
184 fn last<'a>(&'a self) -> Option<&'a T>;
186 /// Returns a pointer to the element at the given index, without doing
189 unsafe fn unsafe_get<'a>(&'a self, index: uint) -> &'a T;
191 /// Returns an unsafe pointer to the slice's buffer
193 /// The caller must ensure that the slice outlives the pointer this
194 /// function returns, or else it will end up pointing to garbage.
196 /// Modifying the slice may cause its buffer to be reallocated, which
197 /// would also make any pointers to it invalid.
199 fn as_ptr(&self) -> *const T;
201 /// Binary search a sorted slice with a comparator function.
203 /// The comparator function should implement an order consistent
204 /// with the sort order of the underlying slice, returning an
205 /// order code that indicates whether its argument is `Less`,
206 /// `Equal` or `Greater` the desired target.
208 /// If a matching value is found then returns `Found`, containing
209 /// the index for the matched element; if no match is found then
210 /// `NotFound` is returned, containing the index where a matching
211 /// element could be inserted while maintaining sorted order.
215 /// Looks up a series of four elements. The first is found, with a
216 /// uniquely determined position; the second and third are not
217 /// found; the fourth could match any position in `[1,4]`.
220 /// use std::slice::BinarySearchResult::{Found, NotFound};
221 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
222 /// let s = s.as_slice();
225 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), Found(9));
227 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(7));
229 /// assert_eq!(s.binary_search(|probe| probe.cmp(&seek)), NotFound(13));
231 /// let r = s.binary_search(|probe| probe.cmp(&seek));
232 /// assert!(match r { Found(1...4) => true, _ => false, });
234 #[unstable = "waiting on unboxed closures"]
235 fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult;
237 /// Return the number of elements in the slice
242 /// let a = [1i, 2, 3];
243 /// assert_eq!(a.len(), 3);
245 #[experimental = "not triaged yet"]
246 fn len(&self) -> uint;
248 /// Returns true if the slice has a length of 0
253 /// let a = [1i, 2, 3];
254 /// assert!(!a.is_empty());
257 #[experimental = "not triaged yet"]
258 fn is_empty(&self) -> bool { self.len() == 0 }
259 /// Returns a mutable reference to the element at the given index,
260 /// or `None` if the index is out of bounds
261 #[unstable = "waiting on final error conventions"]
262 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
264 /// Work with `self` as a mut slice.
265 /// Primarily intended for getting a &mut [T] from a [T, ..N].
266 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
268 /// Returns a mutable subslice spanning the interval [`start`, `end`).
270 /// Panics when the end of the new slice lies beyond the end of the
271 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
273 /// Slicing with `start` equal to `end` yields an empty slice.
274 #[unstable = "waiting on final error conventions"]
275 fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T];
277 /// Returns a mutable subslice from `start` to the end of the slice.
279 /// Panics when `start` is strictly greater than the length of the original slice.
281 /// Slicing from `self.len()` yields an empty slice.
282 #[unstable = "waiting on final error conventions"]
283 fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T];
285 /// Returns a mutable subslice from the start of the slice to `end`.
287 /// Panics when `end` is strictly greater than the length of the original slice.
289 /// Slicing to `0` yields an empty slice.
290 #[unstable = "waiting on final error conventions"]
291 fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T];
293 /// Returns an iterator that allows modifying each value
294 #[unstable = "waiting on iterator type name conventions"]
295 fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T>;
297 /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
298 #[unstable = "name may change"]
299 fn head_mut<'a>(&'a mut self) -> Option<&'a mut T>;
301 /// Returns all but the first element of a mutable slice
302 #[unstable = "name may change"]
303 fn tail_mut<'a>(&'a mut self) -> &'a mut [T];
305 /// Returns all but the last element of a mutable slice
306 #[unstable = "name may change"]
307 fn init_mut<'a>(&'a mut self) -> &'a mut [T];
309 /// Returns a mutable pointer to the last item in the slice.
310 #[unstable = "name may change"]
311 fn last_mut<'a>(&'a mut self) -> Option<&'a mut T>;
313 /// Returns an iterator over mutable subslices separated by elements that
314 /// match `pred`. The matched element is not contained in the subslices.
315 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
316 fn split_mut<'a>(&'a mut self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T>;
318 /// Returns an iterator over subslices separated by elements that match
319 /// `pred`, limited to splitting at most `n` times. The matched element is
320 /// not contained in the subslices.
321 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
322 fn splitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>>;
324 /// Returns an iterator over subslices separated by elements that match
325 /// `pred` limited to splitting at most `n` times. This starts at the end of
326 /// the slice and works backwards. The matched element is not contained in
328 #[unstable = "waiting on unboxed closures, iterator type name conventions"]
329 fn rsplitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>>;
331 /// Returns an iterator over `chunk_size` elements of the slice at a time.
332 /// The chunks are mutable and do not overlap. If `chunk_size` does
333 /// not divide the length of the slice, then the last chunk will not
334 /// have length `chunk_size`.
338 /// Panics if `chunk_size` is 0.
339 #[unstable = "waiting on iterator type name conventions"]
340 fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> MutChunks<'a, T>;
342 /// Swaps two elements in a slice.
344 /// Panics if `a` or `b` are out of bounds.
348 /// * a - The index of the first element
349 /// * b - The index of the second element
354 /// let mut v = ["a", "b", "c", "d"];
356 /// assert!(v == ["a", "d", "c", "b"]);
358 #[unstable = "waiting on final error conventions"]
359 fn swap(&mut self, a: uint, b: uint);
361 /// Divides one `&mut` into two at an index.
363 /// The first will contain all indices from `[0, mid)` (excluding
364 /// the index `mid` itself) and the second will contain all
365 /// indices from `[mid, len)` (excluding the index `len` itself).
367 /// Panics if `mid > len`.
372 /// let mut v = [1i, 2, 3, 4, 5, 6];
374 /// // scoped to restrict the lifetime of the borrows
376 /// let (left, right) = v.split_at_mut(0);
377 /// assert!(left == []);
378 /// assert!(right == [1i, 2, 3, 4, 5, 6]);
382 /// let (left, right) = v.split_at_mut(2);
383 /// assert!(left == [1i, 2]);
384 /// assert!(right == [3i, 4, 5, 6]);
388 /// let (left, right) = v.split_at_mut(6);
389 /// assert!(left == [1i, 2, 3, 4, 5, 6]);
390 /// assert!(right == []);
393 #[unstable = "waiting on final error conventions"]
394 fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]);
396 /// Reverse the order of elements in a slice, in place.
401 /// let mut v = [1i, 2, 3];
403 /// assert!(v == [3i, 2, 1]);
405 #[experimental = "may be moved to iterators instead"]
406 fn reverse(&mut self);
408 /// Returns an unsafe mutable pointer to the element in index
409 #[experimental = "waiting on unsafe conventions"]
410 unsafe fn unsafe_mut<'a>(&'a mut self, index: uint) -> &'a mut T;
412 /// Return an unsafe mutable pointer to the slice's buffer.
414 /// The caller must ensure that the slice outlives the pointer this
415 /// function returns, or else it will end up pointing to garbage.
417 /// Modifying the slice may cause its buffer to be reallocated, which
418 /// would also make any pointers to it invalid.
421 fn as_mut_ptr(&mut self) -> *mut T;
425 impl<T> SlicePrelude<T> for [T] {
427 fn slice(&self, start: uint, end: uint) -> &[T] {
428 assert!(start <= end);
429 assert!(end <= self.len());
432 data: self.as_ptr().offset(start as int),
439 fn slice_from(&self, start: uint) -> &[T] {
440 self.slice(start, self.len())
444 fn slice_to(&self, end: uint) -> &[T] {
449 fn split_at(&self, mid: uint) -> (&[T], &[T]) {
450 (self[..mid], self[mid..])
454 fn iter<'a>(&'a self) -> Items<'a, T> {
456 let p = self.as_ptr();
457 if mem::size_of::<T>() == 0 {
459 end: (p as uint + self.len()) as *const T,
460 marker: marker::ContravariantLifetime::<'a>}
463 end: p.offset(self.len() as int),
464 marker: marker::ContravariantLifetime::<'a>}
470 fn split<'a>(&'a self, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
479 fn splitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>> {
481 iter: self.split(pred),
488 fn rsplitn<'a>(&'a self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<Splits<'a, T>> {
490 iter: self.split(pred),
497 fn windows(&self, size: uint) -> Windows<T> {
499 Windows { v: self, size: size }
503 fn chunks(&self, size: uint) -> Chunks<T> {
505 Chunks { v: self, size: size }
509 fn get(&self, index: uint) -> Option<&T> {
510 if index < self.len() { Some(&self[index]) } else { None }
514 fn head(&self) -> Option<&T> {
515 if self.len() == 0 { None } else { Some(&self[0]) }
519 fn tail(&self) -> &[T] { self[1..] }
522 fn init(&self) -> &[T] {
523 self[..self.len() - 1]
527 fn last(&self) -> Option<&T> {
528 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
532 unsafe fn unsafe_get(&self, index: uint) -> &T {
533 transmute(self.repr().data.offset(index as int))
537 fn as_ptr(&self) -> *const T {
542 fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult {
543 let mut base : uint = 0;
544 let mut lim : uint = self.len();
547 let ix = base + (lim >> 1);
549 Equal => return BinarySearchResult::Found(ix),
558 return BinarySearchResult::NotFound(base);
562 fn len(&self) -> uint { self.repr().len }
565 fn get_mut(&mut self, index: uint) -> Option<&mut T> {
566 if index < self.len() { Some(&mut self[index]) } else { None }
570 fn as_mut_slice(&mut self) -> &mut [T] { self }
572 fn slice_mut(&mut self, start: uint, end: uint) -> &mut [T] {
577 fn slice_from_mut(&mut self, start: uint) -> &mut [T] {
582 fn slice_to_mut(&mut self, end: uint) -> &mut [T] {
587 fn split_at_mut(&mut self, mid: uint) -> (&mut [T], &mut [T]) {
589 let self2: &mut [T] = mem::transmute_copy(&self);
590 (self[mut ..mid], self2[mut mid..])
595 fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
597 let p = self.as_mut_ptr();
598 if mem::size_of::<T>() == 0 {
600 end: (p as uint + self.len()) as *mut T,
601 marker: marker::ContravariantLifetime::<'a>,
602 marker2: marker::NoCopy}
605 end: p.offset(self.len() as int),
606 marker: marker::ContravariantLifetime::<'a>,
607 marker2: marker::NoCopy}
613 fn last_mut(&mut self) -> Option<&mut T> {
614 let len = self.len();
615 if len == 0 { return None; }
616 Some(&mut self[len - 1])
620 fn head_mut(&mut self) -> Option<&mut T> {
621 if self.len() == 0 { None } else { Some(&mut self[0]) }
625 fn tail_mut(&mut self) -> &mut [T] {
626 let len = self.len();
631 fn init_mut(&mut self) -> &mut [T] {
632 let len = self.len();
637 fn split_mut<'a>(&'a mut self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T> {
638 MutSplits { v: self, pred: pred, finished: false }
642 fn splitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>> {
644 iter: self.split_mut(pred),
651 fn rsplitn_mut<'a>(&'a mut self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<MutSplits<'a, T>> {
653 iter: self.split_mut(pred),
660 fn chunks_mut(&mut self, chunk_size: uint) -> MutChunks<T> {
661 assert!(chunk_size > 0);
662 MutChunks { v: self, chunk_size: chunk_size }
665 fn swap(&mut self, a: uint, b: uint) {
667 // Can't take two mutable loans from one vector, so instead just cast
668 // them to their raw pointers to do the swap
669 let pa: *mut T = &mut self[a];
670 let pb: *mut T = &mut self[b];
675 fn reverse(&mut self) {
679 // Unsafe swap to avoid the bounds check in safe swap.
681 let pa: *mut T = self.unsafe_mut(i);
682 let pb: *mut T = self.unsafe_mut(ln - i - 1);
690 unsafe fn unsafe_mut(&mut self, index: uint) -> &mut T {
691 transmute((self.repr().data as *mut T).offset(index as int))
695 fn as_mut_ptr(&mut self) -> *mut T {
696 self.repr().data as *mut T
700 impl<T> ops::Index<uint, T> for [T] {
701 fn index(&self, &index: &uint) -> &T {
702 assert!(index < self.len());
704 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
708 impl<T> ops::IndexMut<uint, T> for [T] {
709 fn index_mut(&mut self, &index: &uint) -> &mut T {
710 assert!(index < self.len());
712 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
716 impl<T> ops::Slice<uint, [T]> for [T] {
718 fn as_slice_<'a>(&'a self) -> &'a [T] {
723 fn slice_from_or_fail<'a>(&'a self, start: &uint) -> &'a [T] {
724 self.slice_or_fail(start, &self.len())
728 fn slice_to_or_fail<'a>(&'a self, end: &uint) -> &'a [T] {
729 self.slice_or_fail(&0, end)
732 fn slice_or_fail<'a>(&'a self, start: &uint, end: &uint) -> &'a [T] {
733 assert!(*start <= *end);
734 assert!(*end <= self.len());
737 data: self.as_ptr().offset(*start as int),
744 impl<T> ops::SliceMut<uint, [T]> for [T] {
746 fn as_mut_slice_<'a>(&'a mut self) -> &'a mut [T] {
751 fn slice_from_or_fail_mut<'a>(&'a mut self, start: &uint) -> &'a mut [T] {
752 let len = &self.len();
753 self.slice_or_fail_mut(start, len)
757 fn slice_to_or_fail_mut<'a>(&'a mut self, end: &uint) -> &'a mut [T] {
758 self.slice_or_fail_mut(&0, end)
761 fn slice_or_fail_mut<'a>(&'a mut self, start: &uint, end: &uint) -> &'a mut [T] {
762 assert!(*start <= *end);
763 assert!(*end <= self.len());
766 data: self.as_ptr().offset(*start as int),
773 /// Extension methods for slices containing `PartialEq` elements.
774 #[unstable = "may merge with other traits"]
775 pub trait PartialEqSlicePrelude<T: PartialEq> for Sized? {
776 /// Find the first index containing a matching value.
777 fn position_elem(&self, t: &T) -> Option<uint>;
779 /// Find the last index containing a matching value.
780 fn rposition_elem(&self, t: &T) -> Option<uint>;
782 /// Return true if the slice contains an element with the given value.
783 fn contains(&self, x: &T) -> bool;
785 /// Returns true if `needle` is a prefix of the slice.
786 fn starts_with(&self, needle: &[T]) -> bool;
788 /// Returns true if `needle` is a suffix of the slice.
789 fn ends_with(&self, needle: &[T]) -> bool;
792 #[unstable = "trait is unstable"]
793 impl<T: PartialEq> PartialEqSlicePrelude<T> for [T] {
795 fn position_elem(&self, x: &T) -> Option<uint> {
796 self.iter().position(|y| *x == *y)
800 fn rposition_elem(&self, t: &T) -> Option<uint> {
801 self.iter().rposition(|x| *x == *t)
805 fn contains(&self, x: &T) -> bool {
806 self.iter().any(|elt| *x == *elt)
810 fn starts_with(&self, needle: &[T]) -> bool {
811 let n = needle.len();
812 self.len() >= n && needle == self[..n]
816 fn ends_with(&self, needle: &[T]) -> bool {
817 let (m, n) = (self.len(), needle.len());
818 m >= n && needle == self[m-n..]
822 /// Extension methods for slices containing `Ord` elements.
823 #[unstable = "may merge with other traits"]
824 pub trait OrdSlicePrelude<T: Ord> for Sized? {
825 /// Binary search a sorted slice for a given element.
827 /// If the value is found then `Found` is returned, containing the
828 /// index of the matching element; if the value is not found then
829 /// `NotFound` is returned, containing the index where a matching
830 /// element could be inserted while maintaining sorted order.
834 /// Looks up a series of four elements. The first is found, with a
835 /// uniquely determined position; the second and third are not
836 /// found; the fourth could match any position in `[1,4]`.
839 /// use std::slice::BinarySearchResult::{Found, NotFound};
840 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
841 /// let s = s.as_slice();
843 /// assert_eq!(s.binary_search_elem(&13), Found(9));
844 /// assert_eq!(s.binary_search_elem(&4), NotFound(7));
845 /// assert_eq!(s.binary_search_elem(&100), NotFound(13));
846 /// let r = s.binary_search_elem(&1);
847 /// assert!(match r { Found(1...4) => true, _ => false, });
849 #[unstable = "name likely to change"]
850 fn binary_search_elem(&self, x: &T) -> BinarySearchResult;
852 /// Mutates the slice to the next lexicographic permutation.
854 /// Returns `true` if successful and `false` if the slice is at the
855 /// last-ordered permutation.
860 /// let v: &mut [_] = &mut [0i, 1, 2];
861 /// v.next_permutation();
862 /// let b: &mut [_] = &mut [0i, 2, 1];
864 /// v.next_permutation();
865 /// let b: &mut [_] = &mut [1i, 0, 2];
869 fn next_permutation(&mut self) -> bool;
871 /// Mutates the slice to the previous lexicographic permutation.
873 /// Returns `true` if successful and `false` if the slice is at the
874 /// first-ordered permutation.
879 /// let v: &mut [_] = &mut [1i, 0, 2];
880 /// v.prev_permutation();
881 /// let b: &mut [_] = &mut [0i, 2, 1];
883 /// v.prev_permutation();
884 /// let b: &mut [_] = &mut [0i, 1, 2];
888 fn prev_permutation(&mut self) -> bool;
891 #[unstable = "trait is unstable"]
892 impl<T: Ord> OrdSlicePrelude<T> for [T] {
894 fn binary_search_elem(&self, x: &T) -> BinarySearchResult {
895 self.binary_search(|p| p.cmp(x))
899 fn next_permutation(&mut self) -> bool {
900 // These cases only have 1 permutation each, so we can't do anything.
901 if self.len() < 2 { return false; }
903 // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
904 let mut i = self.len() - 1;
905 while i > 0 && self[i-1] >= self[i] {
909 // If that is the entire vector, this is the last-ordered permutation.
914 // Step 2: Find the rightmost element larger than the pivot (i-1)
915 let mut j = self.len() - 1;
916 while j >= i && self[j] <= self[i-1] {
920 // Step 3: Swap that element with the pivot
923 // Step 4: Reverse the (previously) weakly decreasing part
924 self[mut i..].reverse();
930 fn prev_permutation(&mut self) -> bool {
931 // These cases only have 1 permutation each, so we can't do anything.
932 if self.len() < 2 { return false; }
934 // Step 1: Identify the longest, rightmost weakly increasing part of the vector
935 let mut i = self.len() - 1;
936 while i > 0 && self[i-1] <= self[i] {
940 // If that is the entire vector, this is the first-ordered permutation.
945 // Step 2: Reverse the weakly increasing part
946 self[mut i..].reverse();
948 // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
949 let mut j = self.len() - 1;
950 while j >= i && self[j-1] < self[i-1] {
954 // Step 4: Swap that element with the pivot
961 /// Extension methods for slices on Clone elements
962 #[unstable = "may merge with other traits"]
963 pub trait CloneSlicePrelude<T> for Sized? {
964 /// Copies as many elements from `src` as it can into `self` (the
965 /// shorter of `self.len()` and `src.len()`). Returns the number
966 /// of elements copied.
971 /// use std::slice::CloneSlicePrelude;
973 /// let mut dst = [0i, 0, 0];
974 /// let src = [1i, 2];
976 /// assert!(dst.clone_from_slice(&src) == 2);
977 /// assert!(dst == [1, 2, 0]);
979 /// let src2 = [3i, 4, 5, 6];
980 /// assert!(dst.clone_from_slice(&src2) == 3);
981 /// assert!(dst == [3i, 4, 5]);
983 fn clone_from_slice(&mut self, &[T]) -> uint;
986 #[unstable = "trait is unstable"]
987 impl<T: Clone> CloneSlicePrelude<T> for [T] {
989 fn clone_from_slice(&mut self, src: &[T]) -> uint {
990 let min = cmp::min(self.len(), src.len());
991 let dst = self.slice_to_mut(min);
992 let src = src.slice_to(min);
993 for i in range(0, min) {
994 dst[i].clone_from(&src[i]);
1007 /// Data that is viewable as a slice.
1008 #[unstable = "may merge with other traits"]
1009 pub trait AsSlice<T> for Sized? {
1010 /// Work with `self` as a slice.
1011 fn as_slice<'a>(&'a self) -> &'a [T];
1014 #[unstable = "trait is unstable"]
1015 impl<T> AsSlice<T> for [T] {
1017 fn as_slice<'a>(&'a self) -> &'a [T] { self }
1020 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U {
1022 fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
1025 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U {
1027 fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
1030 #[unstable = "waiting for DST"]
1031 impl<'a, T> Default for &'a [T] {
1032 fn default() -> &'a [T] { &[] }
1039 // The shared definition of the `Item` and `MutItems` iterators
1040 macro_rules! iterator {
1041 (struct $name:ident -> $ptr:ty, $elem:ty) => {
1042 #[experimental = "needs review"]
1043 impl<'a, T> Iterator<$elem> for $name<'a, T> {
1045 fn next(&mut self) -> Option<$elem> {
1046 // could be implemented with slices, but this avoids bounds checks
1048 if self.ptr == self.end {
1051 if mem::size_of::<T>() == 0 {
1052 // purposefully don't use 'ptr.offset' because for
1053 // vectors with 0-size elements this would return the
1055 self.ptr = transmute(self.ptr as uint + 1);
1057 // Use a non-null pointer value
1061 self.ptr = self.ptr.offset(1);
1063 Some(transmute(old))
1070 fn size_hint(&self) -> (uint, Option<uint>) {
1071 let diff = (self.end as uint) - (self.ptr as uint);
1072 let size = mem::size_of::<T>();
1073 let exact = diff / (if size == 0 {1} else {size});
1074 (exact, Some(exact))
1078 #[experimental = "needs review"]
1079 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
1081 fn next_back(&mut self) -> Option<$elem> {
1082 // could be implemented with slices, but this avoids bounds checks
1084 if self.end == self.ptr {
1087 if mem::size_of::<T>() == 0 {
1088 // See above for why 'ptr.offset' isn't used
1089 self.end = transmute(self.end as uint - 1);
1091 // Use a non-null pointer value
1094 self.end = self.end.offset(-1);
1096 Some(transmute(self.end))
1105 macro_rules! make_slice {
1106 ($t: ty -> $result: ty: $start: expr, $end: expr) => {{
1107 let diff = $end as uint - $start as uint;
1108 let len = if mem::size_of::<T>() == 0 {
1111 diff / mem::size_of::<$t>()
1114 transmute::<_, $result>(RawSlice { data: $start as *const T, len: len })
1120 /// Immutable slice iterator
1121 #[experimental = "needs review"]
1122 pub struct Items<'a, T: 'a> {
1125 marker: marker::ContravariantLifetime<'a>
1129 impl<'a, T> ops::Slice<uint, [T]> for Items<'a, T> {
1130 fn as_slice_(&self) -> &[T] {
1133 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
1135 self.as_slice().slice_from_or_fail(from)
1137 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
1139 self.as_slice().slice_to_or_fail(to)
1141 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
1143 self.as_slice().slice_or_fail(from, to)
1147 impl<'a, T> Items<'a, T> {
1148 /// View the underlying data as a subslice of the original data.
1150 /// This has the same lifetime as the original slice, and so the
1151 /// iterator can continue to be used while this exists.
1153 pub fn as_slice(&self) -> &'a [T] {
1154 make_slice!(T -> &'a [T]: self.ptr, self.end)
1158 iterator!{struct Items -> *const T, &'a T}
1160 #[experimental = "needs review"]
1161 impl<'a, T> ExactSizeIterator<&'a T> for Items<'a, T> {}
1163 #[experimental = "needs review"]
1164 impl<'a, T> Clone for Items<'a, T> {
1165 fn clone(&self) -> Items<'a, T> { *self }
1168 #[experimental = "needs review"]
1169 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
1171 fn indexable(&self) -> uint {
1172 let (exact, _) = self.size_hint();
1177 fn idx(&mut self, index: uint) -> Option<&'a T> {
1179 if index < self.indexable() {
1180 if mem::size_of::<T>() == 0 {
1181 // Use a non-null pointer value
1184 Some(transmute(self.ptr.offset(index as int)))
1193 /// Mutable slice iterator.
1194 #[experimental = "needs review"]
1195 pub struct MutItems<'a, T: 'a> {
1198 marker: marker::ContravariantLifetime<'a>,
1199 marker2: marker::NoCopy
1203 impl<'a, T> ops::Slice<uint, [T]> for MutItems<'a, T> {
1204 fn as_slice_<'b>(&'b self) -> &'b [T] {
1205 make_slice!(T -> &'b [T]: self.ptr, self.end)
1207 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
1209 self.as_slice_().slice_from_or_fail(from)
1211 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
1213 self.as_slice_().slice_to_or_fail(to)
1215 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
1217 self.as_slice_().slice_or_fail(from, to)
1222 impl<'a, T> ops::SliceMut<uint, [T]> for MutItems<'a, T> {
1223 fn as_mut_slice_<'b>(&'b mut self) -> &'b mut [T] {
1224 make_slice!(T -> &'b mut [T]: self.ptr, self.end)
1226 fn slice_from_or_fail_mut<'b>(&'b mut self, from: &uint) -> &'b mut [T] {
1228 self.as_mut_slice_().slice_from_or_fail_mut(from)
1230 fn slice_to_or_fail_mut<'b>(&'b mut self, to: &uint) -> &'b mut [T] {
1232 self.as_mut_slice_().slice_to_or_fail_mut(to)
1234 fn slice_or_fail_mut<'b>(&'b mut self, from: &uint, to: &uint) -> &'b mut [T] {
1236 self.as_mut_slice_().slice_or_fail_mut(from, to)
1240 impl<'a, T> MutItems<'a, T> {
1241 /// View the underlying data as a subslice of the original data.
1243 /// To avoid creating `&mut` references that alias, this is forced
1244 /// to consume the iterator. Consider using the `Slice` and
1245 /// `SliceMut` implementations for obtaining slices with more
1246 /// restricted lifetimes that do not consume the iterator.
1248 pub fn into_slice(self) -> &'a mut [T] {
1249 make_slice!(T -> &'a mut [T]: self.ptr, self.end)
1253 iterator!{struct MutItems -> *mut T, &'a mut T}
1255 #[experimental = "needs review"]
1256 impl<'a, T> ExactSizeIterator<&'a mut T> for MutItems<'a, T> {}
1258 /// An abstraction over the splitting iterators, so that splitn, splitn_mut etc
1259 /// can be implemented once.
1260 trait SplitsIter<E>: DoubleEndedIterator<E> {
1261 /// Mark the underlying iterator as complete, extracting the remaining
1262 /// portion of the slice.
1263 fn finish(&mut self) -> Option<E>;
1266 /// An iterator over subslices separated by elements that match a predicate
1268 #[experimental = "needs review"]
1269 pub struct Splits<'a, T:'a> {
1271 pred: |t: &T|: 'a -> bool,
1275 #[experimental = "needs review"]
1276 impl<'a, T> Iterator<&'a [T]> for Splits<'a, T> {
1278 fn next(&mut self) -> Option<&'a [T]> {
1279 if self.finished { return None; }
1281 match self.v.iter().position(|x| (self.pred)(x)) {
1282 None => self.finish(),
1284 let ret = Some(self.v[..idx]);
1285 self.v = self.v[idx + 1..];
1292 fn size_hint(&self) -> (uint, Option<uint>) {
1296 (1, Some(self.v.len() + 1))
1301 #[experimental = "needs review"]
1302 impl<'a, T> DoubleEndedIterator<&'a [T]> for Splits<'a, T> {
1304 fn next_back(&mut self) -> Option<&'a [T]> {
1305 if self.finished { return None; }
1307 match self.v.iter().rposition(|x| (self.pred)(x)) {
1308 None => self.finish(),
1310 let ret = Some(self.v[idx + 1..]);
1311 self.v = self.v[..idx];
1318 impl<'a, T> SplitsIter<&'a [T]> for Splits<'a, T> {
1320 fn finish(&mut self) -> Option<&'a [T]> {
1321 if self.finished { None } else { self.finished = true; Some(self.v) }
1325 /// An iterator over the subslices of the vector which are separated
1326 /// by elements that match `pred`.
1327 #[experimental = "needs review"]
1328 pub struct MutSplits<'a, T:'a> {
1330 pred: |t: &T|: 'a -> bool,
1334 impl<'a, T> SplitsIter<&'a mut [T]> for MutSplits<'a, T> {
1336 fn finish(&mut self) -> Option<&'a mut [T]> {
1340 self.finished = true;
1341 Some(mem::replace(&mut self.v, &mut []))
1346 #[experimental = "needs review"]
1347 impl<'a, T> Iterator<&'a mut [T]> for MutSplits<'a, T> {
1349 fn next(&mut self) -> Option<&'a mut [T]> {
1350 if self.finished { return None; }
1352 let idx_opt = { // work around borrowck limitations
1353 let pred = &mut self.pred;
1354 self.v.iter().position(|x| (*pred)(x))
1357 None => self.finish(),
1359 let tmp = mem::replace(&mut self.v, &mut []);
1360 let (head, tail) = tmp.split_at_mut(idx);
1361 self.v = tail[mut 1..];
1368 fn size_hint(&self) -> (uint, Option<uint>) {
1372 // if the predicate doesn't match anything, we yield one slice
1373 // if it matches every element, we yield len+1 empty slices.
1374 (1, Some(self.v.len() + 1))
1379 #[experimental = "needs review"]
1380 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T> {
1382 fn next_back(&mut self) -> Option<&'a mut [T]> {
1383 if self.finished { return None; }
1385 let idx_opt = { // work around borrowck limitations
1386 let pred = &mut self.pred;
1387 self.v.iter().rposition(|x| (*pred)(x))
1390 None => self.finish(),
1392 let tmp = mem::replace(&mut self.v, &mut []);
1393 let (head, tail) = tmp.split_at_mut(idx);
1401 /// An iterator over subslices separated by elements that match a predicate
1402 /// function, splitting at most a fixed number of times.
1403 #[experimental = "needs review"]
1404 pub struct SplitsN<I> {
1410 #[experimental = "needs review"]
1411 impl<E, I: SplitsIter<E>> Iterator<E> for SplitsN<I> {
1413 fn next(&mut self) -> Option<E> {
1414 if self.count == 0 {
1418 if self.invert { self.iter.next_back() } else { self.iter.next() }
1423 fn size_hint(&self) -> (uint, Option<uint>) {
1424 let (lower, upper_opt) = self.iter.size_hint();
1425 (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper)))
1429 /// An iterator over overlapping subslices of length `size`.
1431 #[experimental = "needs review"]
1432 pub struct Windows<'a, T:'a> {
1437 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
1439 fn next(&mut self) -> Option<&'a [T]> {
1440 if self.size > self.v.len() {
1443 let ret = Some(self.v[..self.size]);
1444 self.v = self.v[1..];
1450 fn size_hint(&self) -> (uint, Option<uint>) {
1451 if self.size > self.v.len() {
1454 let x = self.v.len() - self.size;
1455 (x.saturating_add(1), x.checked_add(1u))
1460 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1463 /// When the slice len is not evenly divided by the chunk size, the last slice
1464 /// of the iteration will be the remainder.
1466 #[experimental = "needs review"]
1467 pub struct Chunks<'a, T:'a> {
1472 #[experimental = "needs review"]
1473 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
1475 fn next(&mut self) -> Option<&'a [T]> {
1476 if self.v.len() == 0 {
1479 let chunksz = cmp::min(self.v.len(), self.size);
1480 let (fst, snd) = self.v.split_at(chunksz);
1487 fn size_hint(&self) -> (uint, Option<uint>) {
1488 if self.v.len() == 0 {
1491 let n = self.v.len() / self.size;
1492 let rem = self.v.len() % self.size;
1493 let n = if rem > 0 { n+1 } else { n };
1499 #[experimental = "needs review"]
1500 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
1502 fn next_back(&mut self) -> Option<&'a [T]> {
1503 if self.v.len() == 0 {
1506 let remainder = self.v.len() % self.size;
1507 let chunksz = if remainder != 0 { remainder } else { self.size };
1508 let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1515 #[experimental = "needs review"]
1516 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
1518 fn indexable(&self) -> uint {
1519 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1523 fn idx(&mut self, index: uint) -> Option<&'a [T]> {
1524 if index < self.indexable() {
1525 let lo = index * self.size;
1526 let mut hi = lo + self.size;
1527 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1529 Some(self.v[lo..hi])
1536 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1537 /// elements at a time). When the slice len is not evenly divided by the chunk
1538 /// size, the last slice of the iteration will be the remainder.
1539 #[experimental = "needs review"]
1540 pub struct MutChunks<'a, T:'a> {
1545 #[experimental = "needs review"]
1546 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
1548 fn next(&mut self) -> Option<&'a mut [T]> {
1549 if self.v.len() == 0 {
1552 let sz = cmp::min(self.v.len(), self.chunk_size);
1553 let tmp = mem::replace(&mut self.v, &mut []);
1554 let (head, tail) = tmp.split_at_mut(sz);
1561 fn size_hint(&self) -> (uint, Option<uint>) {
1562 if self.v.len() == 0 {
1565 let n = self.v.len() / self.chunk_size;
1566 let rem = self.v.len() % self.chunk_size;
1567 let n = if rem > 0 { n + 1 } else { n };
1573 #[experimental = "needs review"]
1574 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
1576 fn next_back(&mut self) -> Option<&'a mut [T]> {
1577 if self.v.len() == 0 {
1580 let remainder = self.v.len() % self.chunk_size;
1581 let sz = if remainder != 0 { remainder } else { self.chunk_size };
1582 let tmp = mem::replace(&mut self.v, &mut []);
1583 let tmp_len = tmp.len();
1584 let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1593 /// The result of calling `binary_search`.
1595 /// `Found` means the search succeeded, and the contained value is the
1596 /// index of the matching element. `NotFound` means the search
1597 /// succeeded, and the contained value is an index where a matching
1598 /// value could be inserted while maintaining sort order.
1599 #[deriving(PartialEq, Show)]
1600 #[experimental = "needs review"]
1601 pub enum BinarySearchResult {
1602 /// The index of the found value.
1604 /// The index where the value should have been found.
1608 #[experimental = "needs review"]
1609 impl BinarySearchResult {
1610 /// Converts a `Found` to `Some`, `NotFound` to `None`.
1611 /// Similar to `Result::ok`.
1612 pub fn found(&self) -> Option<uint> {
1614 BinarySearchResult::Found(i) => Some(i),
1615 BinarySearchResult::NotFound(_) => None
1619 /// Convert a `Found` to `None`, `NotFound` to `Some`.
1620 /// Similar to `Result::err`.
1621 pub fn not_found(&self) -> Option<uint> {
1623 BinarySearchResult::Found(_) => None,
1624 BinarySearchResult::NotFound(i) => Some(i)
1635 /// Converts a pointer to A into a slice of length 1 (without copying).
1636 #[unstable = "waiting for DST"]
1637 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1639 transmute(RawSlice { data: s, len: 1 })
1643 /// Converts a pointer to A into a slice of length 1 (without copying).
1644 #[unstable = "waiting for DST"]
1645 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1647 let ptr: *const A = transmute(s);
1648 transmute(RawSlice { data: ptr, len: 1 })
1652 /// Forms a slice from a pointer and a length.
1654 /// The pointer given is actually a reference to the base of the slice. This
1655 /// reference is used to give a concrete lifetime to tie the returned slice to.
1656 /// Typically this should indicate that the slice is valid for as long as the
1657 /// pointer itself is valid.
1659 /// The `len` argument is the number of **elements**, not the number of bytes.
1661 /// This function is unsafe as there is no guarantee that the given pointer is
1662 /// valid for `len` elements, nor whether the lifetime provided is a suitable
1663 /// lifetime for the returned slice.
1670 /// // manifest a slice out of thin air!
1671 /// let ptr = 0x1234 as *const uint;
1674 /// let slice = slice::from_raw_buf(&ptr, amt);
1678 #[unstable = "just renamed from `mod raw`"]
1679 pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] {
1680 transmute(RawSlice { data: *p, len: len })
1683 /// Performs the same functionality as `from_raw_buf`, except that a mutable
1684 /// slice is returned.
1686 /// This function is unsafe for the same reasons as `from_raw_buf`, as well as
1687 /// not being able to provide a non-aliasing guarantee of the returned mutable
1690 #[unstable = "just renamed from `mod raw`"]
1691 pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] {
1692 transmute(RawSlice { data: *p as *const T, len: len })
1699 /// Unsafe operations
1705 use option::{None, Option, Some};
1707 /// Form a slice from a pointer and length (as a number of units,
1710 #[deprecated = "renamed to slice::from_raw_buf"]
1711 pub unsafe fn buf_as_slice<T,U>(p: *const T, len: uint, f: |v: &[T]| -> U)
1719 /// Form a slice from a pointer and length (as a number of units,
1722 #[deprecated = "renamed to slice::from_raw_mut_buf"]
1723 pub unsafe fn mut_buf_as_slice<T,
1727 f: |v: &mut [T]| -> U)
1730 data: p as *const T,
1735 /// Returns a pointer to first element in slice and adjusts
1736 /// slice so it no longer contains that element. Returns None
1737 /// if the slice is empty. O(1).
1739 #[deprecated = "inspect `Slice::{data, len}` manually (increment data by 1)"]
1740 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1741 if slice.len == 0 { return None; }
1742 let head: *const T = slice.data;
1743 slice.data = slice.data.offset(1);
1748 /// Returns a pointer to last element in slice and adjusts
1749 /// slice so it no longer contains that element. Returns None
1750 /// if the slice is empty. O(1).
1752 #[deprecated = "inspect `Slice::{data, len}` manually (decrement len by 1)"]
1753 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1754 if slice.len == 0 { return None; }
1755 let tail: *const T = slice.data.offset((slice.len - 1) as int);
1761 /// Operations on `[u8]`.
1762 #[experimental = "needs review"]
1766 use slice::SlicePrelude;
1768 /// A trait for operations on mutable `[u8]`s.
1769 pub trait MutableByteVector for Sized? {
1770 /// Sets all bytes of the receiver to the given value.
1771 fn set_memory(&mut self, value: u8);
1774 impl MutableByteVector for [u8] {
1776 #[allow(experimental)]
1777 fn set_memory(&mut self, value: u8) {
1778 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1782 /// Copies data from `src` to `dst`
1784 /// `src` and `dst` must not overlap. Panics if the length of `dst`
1785 /// is less than the length of `src`.
1787 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1788 let len_src = src.len();
1789 assert!(dst.len() >= len_src);
1791 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(),
1801 // Boilerplate traits
1804 #[unstable = "waiting for DST"]
1805 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1806 fn eq(&self, other: &[B]) -> bool {
1807 self.len() == other.len() &&
1808 order::eq(self.iter(), other.iter())
1810 fn ne(&self, other: &[B]) -> bool {
1811 self.len() != other.len() ||
1812 order::ne(self.iter(), other.iter())
1816 #[unstable = "waiting for DST"]
1817 impl<T: Eq> Eq for [T] {}
1819 #[allow(deprecated)]
1820 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1821 impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
1823 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1826 #[allow(deprecated)]
1827 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1828 impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
1830 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1833 #[unstable = "waiting for DST"]
1834 impl<T: Ord> Ord for [T] {
1835 fn cmp(&self, other: &[T]) -> Ordering {
1836 order::cmp(self.iter(), other.iter())
1840 #[unstable = "waiting for DST"]
1841 impl<T: PartialOrd> PartialOrd for [T] {
1843 fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1844 order::partial_cmp(self.iter(), other.iter())
1847 fn lt(&self, other: &[T]) -> bool {
1848 order::lt(self.iter(), other.iter())
1851 fn le(&self, other: &[T]) -> bool {
1852 order::le(self.iter(), other.iter())
1855 fn ge(&self, other: &[T]) -> bool {
1856 order::ge(self.iter(), other.iter())
1859 fn gt(&self, other: &[T]) -> bool {
1860 order::gt(self.iter(), other.iter())
1864 /// Extension methods for immutable slices containing integers.
1866 pub trait ImmutableIntSlice<U, S> for Sized? {
1867 /// Converts the slice to an immutable slice of unsigned integers with the same width.
1868 fn as_unsigned<'a>(&'a self) -> &'a [U];
1869 /// Converts the slice to an immutable slice of signed integers with the same width.
1870 fn as_signed<'a>(&'a self) -> &'a [S];
1873 /// Extension methods for mutable slices containing integers.
1875 pub trait MutableIntSlice<U, S> for Sized?: ImmutableIntSlice<U, S> {
1876 /// Converts the slice to a mutable slice of unsigned integers with the same width.
1877 fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1878 /// Converts the slice to a mutable slice of signed integers with the same width.
1879 fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1882 macro_rules! impl_immut_int_slice {
1883 ($u:ty, $s:ty, $t:ty) => {
1885 impl ImmutableIntSlice<$u, $s> for [$t] {
1887 fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1889 fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1893 macro_rules! impl_mut_int_slice {
1894 ($u:ty, $s:ty, $t:ty) => {
1896 impl MutableIntSlice<$u, $s> for [$t] {
1898 fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1900 fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1905 macro_rules! impl_int_slice {
1907 impl_immut_int_slice!($u, $s, $u)
1908 impl_immut_int_slice!($u, $s, $s)
1909 impl_mut_int_slice!($u, $s, $u)
1910 impl_mut_int_slice!($u, $s, $s)
1914 impl_int_slice!(u8, i8)
1915 impl_int_slice!(u16, i16)
1916 impl_int_slice!(u32, i32)
1917 impl_int_slice!(u64, i64)
1918 impl_int_slice!(uint, int)