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};
46 use ops::{FnMut, mod};
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 #[allow(missing_docs)] // docs in libcollections
65 pub trait SliceExt<T> for Sized? {
66 fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T];
67 fn slice_from<'a>(&'a self, start: uint) -> &'a [T];
68 fn slice_to<'a>(&'a self, end: uint) -> &'a [T];
69 fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]);
70 fn iter<'a>(&'a self) -> Iter<'a, T>;
71 fn split<'a, P>(&'a self, pred: P) -> Splits<'a, T, P>
72 where P: FnMut(&T) -> bool;
73 fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>>
74 where P: FnMut(&T) -> bool;
75 fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>>
76 where P: FnMut(&T) -> bool;
77 fn windows<'a>(&'a self, size: uint) -> Windows<'a, T>;
78 fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T>;
79 fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
80 fn head<'a>(&'a self) -> Option<&'a T>;
81 fn tail<'a>(&'a self) -> &'a [T];
82 fn init<'a>(&'a self) -> &'a [T];
83 fn last<'a>(&'a self) -> Option<&'a T>;
84 unsafe fn unsafe_get<'a>(&'a self, index: uint) -> &'a T;
85 fn as_ptr(&self) -> *const T;
86 fn binary_search<F>(&self, f: F) -> BinarySearchResult
87 where F: FnMut(&T) -> Ordering;
88 fn len(&self) -> uint;
89 fn is_empty(&self) -> bool { self.len() == 0 }
90 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
91 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
92 fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T];
93 fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T];
94 fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T];
95 fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T>;
96 fn head_mut<'a>(&'a mut self) -> Option<&'a mut T>;
97 fn tail_mut<'a>(&'a mut self) -> &'a mut [T];
98 fn init_mut<'a>(&'a mut self) -> &'a mut [T];
99 fn last_mut<'a>(&'a mut self) -> Option<&'a mut T>;
100 fn split_mut<'a, P>(&'a mut self, pred: P) -> MutSplits<'a, T, P>
101 where P: FnMut(&T) -> bool;
102 fn splitn_mut<P>(&mut self, n: uint, pred: P) -> SplitsN<MutSplits<T, P>>
103 where P: FnMut(&T) -> bool;
104 fn rsplitn_mut<P>(&mut self, n: uint, pred: P) -> SplitsN<MutSplits<T, P>>
105 where P: FnMut(&T) -> bool;
106 fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> MutChunks<'a, T>;
107 fn swap(&mut self, a: uint, b: uint);
108 fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]);
109 fn reverse(&mut self);
110 unsafe fn unsafe_mut<'a>(&'a mut self, index: uint) -> &'a mut T;
111 fn as_mut_ptr(&mut self) -> *mut T;
115 impl<T> SliceExt<T> for [T] {
117 fn slice(&self, start: uint, end: uint) -> &[T] {
118 assert!(start <= end);
119 assert!(end <= self.len());
122 data: self.as_ptr().offset(start as int),
129 fn slice_from(&self, start: uint) -> &[T] {
130 self.slice(start, self.len())
134 fn slice_to(&self, end: uint) -> &[T] {
139 fn split_at(&self, mid: uint) -> (&[T], &[T]) {
140 (self[..mid], self[mid..])
144 fn iter<'a>(&'a self) -> Iter<'a, T> {
146 let p = self.as_ptr();
147 if mem::size_of::<T>() == 0 {
149 end: (p as uint + self.len()) as *const T,
150 marker: marker::ContravariantLifetime::<'a>}
153 end: p.offset(self.len() as int),
154 marker: marker::ContravariantLifetime::<'a>}
160 fn split<'a, P>(&'a self, pred: P) -> Splits<'a, T, P> where P: FnMut(&T) -> bool {
169 fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> where
170 P: FnMut(&T) -> bool,
173 iter: self.split(pred),
180 fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> SplitsN<Splits<'a, T, P>> where
181 P: FnMut(&T) -> bool,
184 iter: self.split(pred),
191 fn windows(&self, size: uint) -> Windows<T> {
193 Windows { v: self, size: size }
197 fn chunks(&self, size: uint) -> Chunks<T> {
199 Chunks { v: self, size: size }
203 fn get(&self, index: uint) -> Option<&T> {
204 if index < self.len() { Some(&self[index]) } else { None }
208 fn head(&self) -> Option<&T> {
209 if self.len() == 0 { None } else { Some(&self[0]) }
213 fn tail(&self) -> &[T] { self[1..] }
216 fn init(&self) -> &[T] {
217 self[..self.len() - 1]
221 fn last(&self) -> Option<&T> {
222 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
226 unsafe fn unsafe_get(&self, index: uint) -> &T {
227 transmute(self.repr().data.offset(index as int))
231 fn as_ptr(&self) -> *const T {
236 fn binary_search<F>(&self, mut f: F) -> BinarySearchResult where F: FnMut(&T) -> Ordering {
237 let mut base : uint = 0;
238 let mut lim : uint = self.len();
241 let ix = base + (lim >> 1);
243 Equal => return BinarySearchResult::Found(ix),
252 return BinarySearchResult::NotFound(base);
256 fn len(&self) -> uint { self.repr().len }
259 fn get_mut(&mut self, index: uint) -> Option<&mut T> {
260 if index < self.len() { Some(&mut self[index]) } else { None }
264 fn as_mut_slice(&mut self) -> &mut [T] { self }
266 fn slice_mut(&mut self, start: uint, end: uint) -> &mut [T] {
267 ops::SliceMut::slice_or_fail_mut(self, &start, &end)
271 fn slice_from_mut(&mut self, start: uint) -> &mut [T] {
272 ops::SliceMut::slice_from_or_fail_mut(self, &start)
276 fn slice_to_mut(&mut self, end: uint) -> &mut [T] {
277 ops::SliceMut::slice_to_or_fail_mut(self, &end)
281 fn split_at_mut(&mut self, mid: uint) -> (&mut [T], &mut [T]) {
283 let self2: &mut [T] = mem::transmute_copy(&self);
285 (ops::SliceMut::slice_to_or_fail_mut(self, &mid),
286 ops::SliceMut::slice_from_or_fail_mut(self2, &mid))
291 fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
293 let p = self.as_mut_ptr();
294 if mem::size_of::<T>() == 0 {
296 end: (p as uint + self.len()) as *mut T,
297 marker: marker::ContravariantLifetime::<'a>}
300 end: p.offset(self.len() as int),
301 marker: marker::ContravariantLifetime::<'a>}
307 fn last_mut(&mut self) -> Option<&mut T> {
308 let len = self.len();
309 if len == 0 { return None; }
310 Some(&mut self[len - 1])
314 fn head_mut(&mut self) -> Option<&mut T> {
315 if self.len() == 0 { None } else { Some(&mut self[0]) }
319 fn tail_mut(&mut self) -> &mut [T] {
320 self.slice_from_mut(1)
324 fn init_mut(&mut self) -> &mut [T] {
325 let len = self.len();
326 self.slice_to_mut(len-1)
330 fn split_mut<'a, P>(&'a mut self, pred: P) -> MutSplits<'a, T, P> where P: FnMut(&T) -> bool {
331 MutSplits { v: self, pred: pred, finished: false }
335 fn splitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitsN<MutSplits<'a, T, P>> where
339 iter: self.split_mut(pred),
346 fn rsplitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitsN<MutSplits<'a, T, P>> where
347 P: FnMut(&T) -> bool,
350 iter: self.split_mut(pred),
357 fn chunks_mut(&mut self, chunk_size: uint) -> MutChunks<T> {
358 assert!(chunk_size > 0);
359 MutChunks { v: self, chunk_size: chunk_size }
362 fn swap(&mut self, a: uint, b: uint) {
364 // Can't take two mutable loans from one vector, so instead just cast
365 // them to their raw pointers to do the swap
366 let pa: *mut T = &mut self[a];
367 let pb: *mut T = &mut self[b];
372 fn reverse(&mut self) {
376 // Unsafe swap to avoid the bounds check in safe swap.
378 let pa: *mut T = self.unsafe_mut(i);
379 let pb: *mut T = self.unsafe_mut(ln - i - 1);
387 unsafe fn unsafe_mut(&mut self, index: uint) -> &mut T {
388 transmute((self.repr().data as *mut T).offset(index as int))
392 fn as_mut_ptr(&mut self) -> *mut T {
393 self.repr().data as *mut T
397 impl<T> ops::Index<uint, T> for [T] {
398 fn index(&self, &index: &uint) -> &T {
399 assert!(index < self.len());
401 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
405 impl<T> ops::IndexMut<uint, T> for [T] {
406 fn index_mut(&mut self, &index: &uint) -> &mut T {
407 assert!(index < self.len());
409 unsafe { mem::transmute(self.repr().data.offset(index as int)) }
413 impl<T> ops::Slice<uint, [T]> for [T] {
415 fn as_slice_<'a>(&'a self) -> &'a [T] {
420 fn slice_from_or_fail<'a>(&'a self, start: &uint) -> &'a [T] {
421 self.slice_or_fail(start, &self.len())
425 fn slice_to_or_fail<'a>(&'a self, end: &uint) -> &'a [T] {
426 self.slice_or_fail(&0, end)
429 fn slice_or_fail<'a>(&'a self, start: &uint, end: &uint) -> &'a [T] {
430 assert!(*start <= *end);
431 assert!(*end <= self.len());
434 data: self.as_ptr().offset(*start as int),
441 impl<T> ops::SliceMut<uint, [T]> for [T] {
443 fn as_mut_slice_<'a>(&'a mut self) -> &'a mut [T] {
448 fn slice_from_or_fail_mut<'a>(&'a mut self, start: &uint) -> &'a mut [T] {
449 let len = &self.len();
450 self.slice_or_fail_mut(start, len)
454 fn slice_to_or_fail_mut<'a>(&'a mut self, end: &uint) -> &'a mut [T] {
455 self.slice_or_fail_mut(&0, end)
458 fn slice_or_fail_mut<'a>(&'a mut self, start: &uint, end: &uint) -> &'a mut [T] {
459 assert!(*start <= *end);
460 assert!(*end <= self.len());
463 data: self.as_ptr().offset(*start as int),
470 /// Extension methods for slices containing `PartialEq` elements.
471 #[unstable = "may merge with other traits"]
472 pub trait PartialEqSliceExt<T: PartialEq> for Sized? {
473 /// Find the first index containing a matching value.
474 fn position_elem(&self, t: &T) -> Option<uint>;
476 /// Find the last index containing a matching value.
477 fn rposition_elem(&self, t: &T) -> Option<uint>;
479 /// Return true if the slice contains an element with the given value.
480 fn contains(&self, x: &T) -> bool;
482 /// Returns true if `needle` is a prefix of the slice.
483 fn starts_with(&self, needle: &[T]) -> bool;
485 /// Returns true if `needle` is a suffix of the slice.
486 fn ends_with(&self, needle: &[T]) -> bool;
489 #[unstable = "trait is unstable"]
490 impl<T: PartialEq> PartialEqSliceExt<T> for [T] {
492 fn position_elem(&self, x: &T) -> Option<uint> {
493 self.iter().position(|y| *x == *y)
497 fn rposition_elem(&self, t: &T) -> Option<uint> {
498 self.iter().rposition(|x| *x == *t)
502 fn contains(&self, x: &T) -> bool {
503 self.iter().any(|elt| *x == *elt)
507 fn starts_with(&self, needle: &[T]) -> bool {
508 let n = needle.len();
509 self.len() >= n && needle == self[..n]
513 fn ends_with(&self, needle: &[T]) -> bool {
514 let (m, n) = (self.len(), needle.len());
515 m >= n && needle == self[m-n..]
519 /// Extension methods for slices containing `Ord` elements.
520 #[unstable = "may merge with other traits"]
521 #[allow(missing_docs)] // docs in libcollections
522 pub trait OrdSliceExt<T: Ord> for Sized? {
523 #[unstable = "name likely to change"]
524 fn binary_search_elem(&self, x: &T) -> BinarySearchResult;
526 fn next_permutation(&mut self) -> bool;
528 fn prev_permutation(&mut self) -> bool;
531 #[unstable = "trait is unstable"]
532 impl<T: Ord> OrdSliceExt<T> for [T] {
534 fn binary_search_elem(&self, x: &T) -> BinarySearchResult {
535 self.binary_search(|p| p.cmp(x))
539 fn next_permutation(&mut self) -> bool {
540 // These cases only have 1 permutation each, so we can't do anything.
541 if self.len() < 2 { return false; }
543 // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
544 let mut i = self.len() - 1;
545 while i > 0 && self[i-1] >= self[i] {
549 // If that is the entire vector, this is the last-ordered permutation.
554 // Step 2: Find the rightmost element larger than the pivot (i-1)
555 let mut j = self.len() - 1;
556 while j >= i && self[j] <= self[i-1] {
560 // Step 3: Swap that element with the pivot
563 // Step 4: Reverse the (previously) weakly decreasing part
564 self.slice_from_mut(i).reverse();
570 fn prev_permutation(&mut self) -> bool {
571 // These cases only have 1 permutation each, so we can't do anything.
572 if self.len() < 2 { return false; }
574 // Step 1: Identify the longest, rightmost weakly increasing part of the vector
575 let mut i = self.len() - 1;
576 while i > 0 && self[i-1] <= self[i] {
580 // If that is the entire vector, this is the first-ordered permutation.
585 // Step 2: Reverse the weakly increasing part
586 self.slice_from_mut(i).reverse();
588 // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
589 let mut j = self.len() - 1;
590 while j >= i && self[j-1] < self[i-1] {
594 // Step 4: Swap that element with the pivot
601 /// Extension methods for slices on Clone elements
602 #[unstable = "may merge with other traits"]
603 #[allow(missing_docs)] // docs in libcollections
604 pub trait CloneSliceExt<T> for Sized? {
605 fn clone_from_slice(&mut self, &[T]) -> uint;
608 #[unstable = "trait is unstable"]
609 impl<T: Clone> CloneSliceExt<T> for [T] {
611 fn clone_from_slice(&mut self, src: &[T]) -> uint {
612 let min = cmp::min(self.len(), src.len());
613 let dst = self.slice_to_mut(min);
614 let src = src.slice_to(min);
615 for i in range(0, min) {
616 dst[i].clone_from(&src[i]);
626 /// Data that is viewable as a slice.
627 #[unstable = "may merge with other traits"]
628 pub trait AsSlice<T> for Sized? {
629 /// Work with `self` as a slice.
630 fn as_slice<'a>(&'a self) -> &'a [T];
633 #[unstable = "trait is unstable"]
634 impl<T> AsSlice<T> for [T] {
636 fn as_slice<'a>(&'a self) -> &'a [T] { self }
639 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U {
641 fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) }
644 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U {
646 fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) }
650 impl<'a, T> Default for &'a [T] {
652 fn default() -> &'a [T] { &[] }
659 // The shared definition of the `Item` and `IterMut` iterators
660 macro_rules! iterator {
661 (struct $name:ident -> $ptr:ty, $elem:ty) => {
662 #[experimental = "needs review"]
663 impl<'a, T> Iterator<$elem> for $name<'a, T> {
665 fn next(&mut self) -> Option<$elem> {
666 // could be implemented with slices, but this avoids bounds checks
668 if self.ptr == self.end {
671 if mem::size_of::<T>() == 0 {
672 // purposefully don't use 'ptr.offset' because for
673 // vectors with 0-size elements this would return the
675 self.ptr = transmute(self.ptr as uint + 1);
677 // Use a non-null pointer value
681 self.ptr = self.ptr.offset(1);
690 fn size_hint(&self) -> (uint, Option<uint>) {
691 let diff = (self.end as uint) - (self.ptr as uint);
692 let size = mem::size_of::<T>();
693 let exact = diff / (if size == 0 {1} else {size});
698 #[experimental = "needs review"]
699 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
701 fn next_back(&mut self) -> Option<$elem> {
702 // could be implemented with slices, but this avoids bounds checks
704 if self.end == self.ptr {
707 if mem::size_of::<T>() == 0 {
708 // See above for why 'ptr.offset' isn't used
709 self.end = transmute(self.end as uint - 1);
711 // Use a non-null pointer value
714 self.end = self.end.offset(-1);
716 Some(transmute(self.end))
725 macro_rules! make_slice {
726 ($t: ty -> $result: ty: $start: expr, $end: expr) => {{
727 let diff = $end as uint - $start as uint;
728 let len = if mem::size_of::<T>() == 0 {
731 diff / mem::size_of::<$t>()
734 transmute::<_, $result>(RawSlice { data: $start as *const T, len: len })
740 /// Immutable slice iterator
741 #[experimental = "needs review"]
742 pub struct Iter<'a, T: 'a> {
745 marker: marker::ContravariantLifetime<'a>
749 impl<'a, T> ops::Slice<uint, [T]> for Iter<'a, T> {
750 fn as_slice_(&self) -> &[T] {
753 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
755 self.as_slice().slice_from_or_fail(from)
757 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
759 self.as_slice().slice_to_or_fail(to)
761 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
763 self.as_slice().slice_or_fail(from, to)
767 impl<'a, T> Iter<'a, T> {
768 /// View the underlying data as a subslice of the original data.
770 /// This has the same lifetime as the original slice, and so the
771 /// iterator can continue to be used while this exists.
773 pub fn as_slice(&self) -> &'a [T] {
774 make_slice!(T -> &'a [T]: self.ptr, self.end)
778 impl<'a,T> Copy for Iter<'a,T> {}
780 iterator!{struct Iter -> *const T, &'a T}
782 #[experimental = "needs review"]
783 impl<'a, T> ExactSizeIterator<&'a T> for Iter<'a, T> {}
786 impl<'a, T> Clone for Iter<'a, T> {
787 fn clone(&self) -> Iter<'a, T> { *self }
790 #[experimental = "needs review"]
791 impl<'a, T> RandomAccessIterator<&'a T> for Iter<'a, T> {
793 fn indexable(&self) -> uint {
794 let (exact, _) = self.size_hint();
799 fn idx(&mut self, index: uint) -> Option<&'a T> {
801 if index < self.indexable() {
802 if mem::size_of::<T>() == 0 {
803 // Use a non-null pointer value
806 Some(transmute(self.ptr.offset(index as int)))
815 /// Mutable slice iterator.
816 #[experimental = "needs review"]
817 pub struct IterMut<'a, T: 'a> {
820 marker: marker::ContravariantLifetime<'a>,
824 impl<'a, T> ops::Slice<uint, [T]> for IterMut<'a, T> {
825 fn as_slice_<'b>(&'b self) -> &'b [T] {
826 make_slice!(T -> &'b [T]: self.ptr, self.end)
828 fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
830 self.as_slice_().slice_from_or_fail(from)
832 fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
834 self.as_slice_().slice_to_or_fail(to)
836 fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
838 self.as_slice_().slice_or_fail(from, to)
843 impl<'a, T> ops::SliceMut<uint, [T]> for IterMut<'a, T> {
844 fn as_mut_slice_<'b>(&'b mut self) -> &'b mut [T] {
845 make_slice!(T -> &'b mut [T]: self.ptr, self.end)
847 fn slice_from_or_fail_mut<'b>(&'b mut self, from: &uint) -> &'b mut [T] {
849 self.as_mut_slice_().slice_from_or_fail_mut(from)
851 fn slice_to_or_fail_mut<'b>(&'b mut self, to: &uint) -> &'b mut [T] {
853 self.as_mut_slice_().slice_to_or_fail_mut(to)
855 fn slice_or_fail_mut<'b>(&'b mut self, from: &uint, to: &uint) -> &'b mut [T] {
857 self.as_mut_slice_().slice_or_fail_mut(from, to)
861 impl<'a, T> IterMut<'a, T> {
862 /// View the underlying data as a subslice of the original data.
864 /// To avoid creating `&mut` references that alias, this is forced
865 /// to consume the iterator. Consider using the `Slice` and
866 /// `SliceMut` implementations for obtaining slices with more
867 /// restricted lifetimes that do not consume the iterator.
869 pub fn into_slice(self) -> &'a mut [T] {
870 make_slice!(T -> &'a mut [T]: self.ptr, self.end)
874 iterator!{struct IterMut -> *mut T, &'a mut T}
876 #[experimental = "needs review"]
877 impl<'a, T> ExactSizeIterator<&'a mut T> for IterMut<'a, T> {}
879 /// An abstraction over the splitting iterators, so that splitn, splitn_mut etc
880 /// can be implemented once.
881 trait SplitsIter<E>: DoubleEndedIterator<E> {
882 /// Mark the underlying iterator as complete, extracting the remaining
883 /// portion of the slice.
884 fn finish(&mut self) -> Option<E>;
887 /// An iterator over subslices separated by elements that match a predicate
889 #[experimental = "needs review"]
890 pub struct Splits<'a, T:'a, P> where P: FnMut(&T) -> bool {
896 // FIXME(#19839) Remove in favor of `#[deriving(Clone)]`
898 impl<'a, T, P> Clone for Splits<'a, T, P> where P: Clone + FnMut(&T) -> bool {
899 fn clone(&self) -> Splits<'a, T, P> {
902 pred: self.pred.clone(),
903 finished: self.finished,
908 #[experimental = "needs review"]
909 impl<'a, T, P> Iterator<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool {
911 fn next(&mut self) -> Option<&'a [T]> {
912 if self.finished { return None; }
914 match self.v.iter().position(|x| (self.pred)(x)) {
915 None => self.finish(),
917 let ret = Some(self.v[..idx]);
918 self.v = self.v[idx + 1..];
925 fn size_hint(&self) -> (uint, Option<uint>) {
929 (1, Some(self.v.len() + 1))
934 #[experimental = "needs review"]
935 impl<'a, T, P> DoubleEndedIterator<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool {
937 fn next_back(&mut self) -> Option<&'a [T]> {
938 if self.finished { return None; }
940 match self.v.iter().rposition(|x| (self.pred)(x)) {
941 None => self.finish(),
943 let ret = Some(self.v[idx + 1..]);
944 self.v = self.v[..idx];
951 impl<'a, T, P> SplitsIter<&'a [T]> for Splits<'a, T, P> where P: FnMut(&T) -> bool {
953 fn finish(&mut self) -> Option<&'a [T]> {
954 if self.finished { None } else { self.finished = true; Some(self.v) }
958 /// An iterator over the subslices of the vector which are separated
959 /// by elements that match `pred`.
960 #[experimental = "needs review"]
961 pub struct MutSplits<'a, T:'a, P> where P: FnMut(&T) -> bool {
967 impl<'a, T, P> SplitsIter<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T) -> bool {
969 fn finish(&mut self) -> Option<&'a mut [T]> {
973 self.finished = true;
974 Some(mem::replace(&mut self.v, &mut []))
979 #[experimental = "needs review"]
980 impl<'a, T, P> Iterator<&'a mut [T]> for MutSplits<'a, T, P> where P: FnMut(&T) -> bool {
982 fn next(&mut self) -> Option<&'a mut [T]> {
983 if self.finished { return None; }
985 let idx_opt = { // work around borrowck limitations
986 let pred = &mut self.pred;
987 self.v.iter().position(|x| (*pred)(x))
990 None => self.finish(),
992 let tmp = mem::replace(&mut self.v, &mut []);
993 let (head, tail) = tmp.split_at_mut(idx);
994 self.v = tail.slice_from_mut(1);
1001 fn size_hint(&self) -> (uint, Option<uint>) {
1005 // if the predicate doesn't match anything, we yield one slice
1006 // if it matches every element, we yield len+1 empty slices.
1007 (1, Some(self.v.len() + 1))
1012 #[experimental = "needs review"]
1013 impl<'a, T, P> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T, P> where
1014 P: FnMut(&T) -> bool,
1017 fn next_back(&mut self) -> Option<&'a mut [T]> {
1018 if self.finished { return None; }
1020 let idx_opt = { // work around borrowck limitations
1021 let pred = &mut self.pred;
1022 self.v.iter().rposition(|x| (*pred)(x))
1025 None => self.finish(),
1027 let tmp = mem::replace(&mut self.v, &mut []);
1028 let (head, tail) = tmp.split_at_mut(idx);
1030 Some(tail.slice_from_mut(1))
1036 /// An iterator over subslices separated by elements that match a predicate
1037 /// function, splitting at most a fixed number of times.
1038 #[experimental = "needs review"]
1039 pub struct SplitsN<I> {
1045 #[experimental = "needs review"]
1046 impl<E, I: SplitsIter<E>> Iterator<E> for SplitsN<I> {
1048 fn next(&mut self) -> Option<E> {
1049 if self.count == 0 {
1053 if self.invert { self.iter.next_back() } else { self.iter.next() }
1058 fn size_hint(&self) -> (uint, Option<uint>) {
1059 let (lower, upper_opt) = self.iter.size_hint();
1060 (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper)))
1064 /// An iterator over overlapping subslices of length `size`.
1066 #[experimental = "needs review"]
1067 pub struct Windows<'a, T:'a> {
1072 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
1074 fn next(&mut self) -> Option<&'a [T]> {
1075 if self.size > self.v.len() {
1078 let ret = Some(self.v[..self.size]);
1079 self.v = self.v[1..];
1085 fn size_hint(&self) -> (uint, Option<uint>) {
1086 if self.size > self.v.len() {
1089 let x = self.v.len() - self.size;
1090 (x.saturating_add(1), x.checked_add(1u))
1095 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1098 /// When the slice len is not evenly divided by the chunk size, the last slice
1099 /// of the iteration will be the remainder.
1101 #[experimental = "needs review"]
1102 pub struct Chunks<'a, T:'a> {
1107 #[experimental = "needs review"]
1108 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
1110 fn next(&mut self) -> Option<&'a [T]> {
1111 if self.v.len() == 0 {
1114 let chunksz = cmp::min(self.v.len(), self.size);
1115 let (fst, snd) = self.v.split_at(chunksz);
1122 fn size_hint(&self) -> (uint, Option<uint>) {
1123 if self.v.len() == 0 {
1126 let n = self.v.len() / self.size;
1127 let rem = self.v.len() % self.size;
1128 let n = if rem > 0 { n+1 } else { n };
1134 #[experimental = "needs review"]
1135 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
1137 fn next_back(&mut self) -> Option<&'a [T]> {
1138 if self.v.len() == 0 {
1141 let remainder = self.v.len() % self.size;
1142 let chunksz = if remainder != 0 { remainder } else { self.size };
1143 let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1150 #[experimental = "needs review"]
1151 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
1153 fn indexable(&self) -> uint {
1154 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1158 fn idx(&mut self, index: uint) -> Option<&'a [T]> {
1159 if index < self.indexable() {
1160 let lo = index * self.size;
1161 let mut hi = lo + self.size;
1162 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1164 Some(self.v[lo..hi])
1171 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1172 /// elements at a time). When the slice len is not evenly divided by the chunk
1173 /// size, the last slice of the iteration will be the remainder.
1174 #[experimental = "needs review"]
1175 pub struct MutChunks<'a, T:'a> {
1180 #[experimental = "needs review"]
1181 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
1183 fn next(&mut self) -> Option<&'a mut [T]> {
1184 if self.v.len() == 0 {
1187 let sz = cmp::min(self.v.len(), self.chunk_size);
1188 let tmp = mem::replace(&mut self.v, &mut []);
1189 let (head, tail) = tmp.split_at_mut(sz);
1196 fn size_hint(&self) -> (uint, Option<uint>) {
1197 if self.v.len() == 0 {
1200 let n = self.v.len() / self.chunk_size;
1201 let rem = self.v.len() % self.chunk_size;
1202 let n = if rem > 0 { n + 1 } else { n };
1208 #[experimental = "needs review"]
1209 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
1211 fn next_back(&mut self) -> Option<&'a mut [T]> {
1212 if self.v.len() == 0 {
1215 let remainder = self.v.len() % self.chunk_size;
1216 let sz = if remainder != 0 { remainder } else { self.chunk_size };
1217 let tmp = mem::replace(&mut self.v, &mut []);
1218 let tmp_len = tmp.len();
1219 let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1228 /// The result of calling `binary_search`.
1230 /// `Found` means the search succeeded, and the contained value is the
1231 /// index of the matching element. `NotFound` means the search
1232 /// succeeded, and the contained value is an index where a matching
1233 /// value could be inserted while maintaining sort order.
1234 #[deriving(Copy, PartialEq, Show)]
1235 #[experimental = "needs review"]
1236 pub enum BinarySearchResult {
1237 /// The index of the found value.
1239 /// The index where the value should have been found.
1243 #[experimental = "needs review"]
1244 impl BinarySearchResult {
1245 /// Converts a `Found` to `Some`, `NotFound` to `None`.
1246 /// Similar to `Result::ok`.
1247 pub fn found(&self) -> Option<uint> {
1249 BinarySearchResult::Found(i) => Some(i),
1250 BinarySearchResult::NotFound(_) => None
1254 /// Convert a `Found` to `None`, `NotFound` to `Some`.
1255 /// Similar to `Result::err`.
1256 pub fn not_found(&self) -> Option<uint> {
1258 BinarySearchResult::Found(_) => None,
1259 BinarySearchResult::NotFound(i) => Some(i)
1270 /// Converts a pointer to A into a slice of length 1 (without copying).
1271 #[unstable = "waiting for DST"]
1272 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1274 transmute(RawSlice { data: s, len: 1 })
1278 /// Converts a pointer to A into a slice of length 1 (without copying).
1279 #[unstable = "waiting for DST"]
1280 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1282 let ptr: *const A = transmute(s);
1283 transmute(RawSlice { data: ptr, len: 1 })
1287 /// Forms a slice from a pointer and a length.
1289 /// The pointer given is actually a reference to the base of the slice. This
1290 /// reference is used to give a concrete lifetime to tie the returned slice to.
1291 /// Typically this should indicate that the slice is valid for as long as the
1292 /// pointer itself is valid.
1294 /// The `len` argument is the number of **elements**, not the number of bytes.
1296 /// This function is unsafe as there is no guarantee that the given pointer is
1297 /// valid for `len` elements, nor whether the lifetime provided is a suitable
1298 /// lifetime for the returned slice.
1305 /// // manifest a slice out of thin air!
1306 /// let ptr = 0x1234 as *const uint;
1309 /// let slice = slice::from_raw_buf(&ptr, amt);
1313 #[unstable = "just renamed from `mod raw`"]
1314 pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] {
1315 transmute(RawSlice { data: *p, len: len })
1318 /// Performs the same functionality as `from_raw_buf`, except that a mutable
1319 /// slice is returned.
1321 /// This function is unsafe for the same reasons as `from_raw_buf`, as well as
1322 /// not being able to provide a non-aliasing guarantee of the returned mutable
1325 #[unstable = "just renamed from `mod raw`"]
1326 pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] {
1327 transmute(RawSlice { data: *p as *const T, len: len })
1334 /// Unsafe operations
1342 use option::Option::{None, Some};
1344 /// Form a slice from a pointer and length (as a number of units,
1347 #[deprecated = "renamed to slice::from_raw_buf"]
1348 pub unsafe fn buf_as_slice<T, U, F>(p: *const T, len: uint, f: F) -> U where
1349 F: FnOnce(&[T]) -> U,
1357 /// Form a slice from a pointer and length (as a number of units,
1360 #[deprecated = "renamed to slice::from_raw_mut_buf"]
1361 pub unsafe fn mut_buf_as_slice<T, U, F>(p: *mut T, len: uint, f: F) -> U where
1362 F: FnOnce(&mut [T]) -> U,
1365 data: p as *const T,
1370 /// Returns a pointer to first element in slice and adjusts
1371 /// slice so it no longer contains that element. Returns None
1372 /// if the slice is empty. O(1).
1374 #[deprecated = "inspect `Slice::{data, len}` manually (increment data by 1)"]
1375 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1376 if slice.len == 0 { return None; }
1377 let head: *const T = slice.data;
1378 slice.data = slice.data.offset(1);
1383 /// Returns a pointer to last element in slice and adjusts
1384 /// slice so it no longer contains that element. Returns None
1385 /// if the slice is empty. O(1).
1387 #[deprecated = "inspect `Slice::{data, len}` manually (decrement len by 1)"]
1388 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1389 if slice.len == 0 { return None; }
1390 let tail: *const T = slice.data.offset((slice.len - 1) as int);
1396 /// Operations on `[u8]`.
1397 #[experimental = "needs review"]
1401 use slice::SliceExt;
1403 /// A trait for operations on mutable `[u8]`s.
1404 pub trait MutableByteVector for Sized? {
1405 /// Sets all bytes of the receiver to the given value.
1406 fn set_memory(&mut self, value: u8);
1409 impl MutableByteVector for [u8] {
1411 #[allow(experimental)]
1412 fn set_memory(&mut self, value: u8) {
1413 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1417 /// Copies data from `src` to `dst`
1419 /// Panics if the length of `dst` is less than the length of `src`.
1421 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1422 let len_src = src.len();
1423 assert!(dst.len() >= len_src);
1424 // `dst` is unaliasable, so we know statically it doesn't overlap
1427 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(),
1437 // Boilerplate traits
1440 #[unstable = "waiting for DST"]
1441 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1442 fn eq(&self, other: &[B]) -> bool {
1443 self.len() == other.len() &&
1444 order::eq(self.iter(), other.iter())
1446 fn ne(&self, other: &[B]) -> bool {
1447 self.len() != other.len() ||
1448 order::ne(self.iter(), other.iter())
1452 #[unstable = "waiting for DST"]
1453 impl<T: Eq> Eq for [T] {}
1455 #[allow(deprecated)]
1456 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1457 impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
1459 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1462 #[allow(deprecated)]
1463 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1464 impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
1466 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1469 #[unstable = "waiting for DST"]
1470 impl<T: Ord> Ord for [T] {
1471 fn cmp(&self, other: &[T]) -> Ordering {
1472 order::cmp(self.iter(), other.iter())
1476 #[unstable = "waiting for DST"]
1477 impl<T: PartialOrd> PartialOrd for [T] {
1479 fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1480 order::partial_cmp(self.iter(), other.iter())
1483 fn lt(&self, other: &[T]) -> bool {
1484 order::lt(self.iter(), other.iter())
1487 fn le(&self, other: &[T]) -> bool {
1488 order::le(self.iter(), other.iter())
1491 fn ge(&self, other: &[T]) -> bool {
1492 order::ge(self.iter(), other.iter())
1495 fn gt(&self, other: &[T]) -> bool {
1496 order::gt(self.iter(), other.iter())
1500 /// Extension methods for immutable slices containing integers.
1502 pub trait ImmutableIntSlice<U, S> for Sized? {
1503 /// Converts the slice to an immutable slice of unsigned integers with the same width.
1504 fn as_unsigned<'a>(&'a self) -> &'a [U];
1505 /// Converts the slice to an immutable slice of signed integers with the same width.
1506 fn as_signed<'a>(&'a self) -> &'a [S];
1509 /// Extension methods for mutable slices containing integers.
1511 pub trait MutableIntSlice<U, S> for Sized?: ImmutableIntSlice<U, S> {
1512 /// Converts the slice to a mutable slice of unsigned integers with the same width.
1513 fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1514 /// Converts the slice to a mutable slice of signed integers with the same width.
1515 fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1518 macro_rules! impl_immut_int_slice {
1519 ($u:ty, $s:ty, $t:ty) => {
1521 impl ImmutableIntSlice<$u, $s> for [$t] {
1523 fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1525 fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1529 macro_rules! impl_mut_int_slice {
1530 ($u:ty, $s:ty, $t:ty) => {
1532 impl MutableIntSlice<$u, $s> for [$t] {
1534 fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1536 fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1541 macro_rules! impl_int_slice {
1543 impl_immut_int_slice! { $u, $s, $u }
1544 impl_immut_int_slice! { $u, $s, $s }
1545 impl_mut_int_slice! { $u, $s, $u }
1546 impl_mut_int_slice! { $u, $s, $s }
1550 impl_int_slice! { u8, i8 }
1551 impl_int_slice! { u16, i16 }
1552 impl_int_slice! { u32, i32 }
1553 impl_int_slice! { u64, i64 }
1554 impl_int_slice! { uint, int }