]> git.lizzy.rs Git - rust.git/blob - src/libcore/slice.rs
core: use assoc types in Iterator et al
[rust.git] / src / libcore / slice.rs
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.
4 //
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.
10
11 //! Slice management and manipulation
12 //!
13 //! For more details `std::slice`.
14
15 #![stable]
16 #![doc(primitive = "slice")]
17
18 // How this module is organized.
19 //
20 // The library infrastructure for slices is fairly messy. There's
21 // a lot of stuff defined here. Let's keep it clean.
22 //
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.
26 //
27 // The layout of this file is thus:
28 //
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.
33 // * Free functions.
34 // * The `raw` and `bytes` submodules.
35 // * Boilerplate trait implementations.
36
37 use mem::transmute;
38 use clone::Clone;
39 use cmp::{Ordering, PartialEq, PartialOrd, Eq, Ord, Equiv};
40 use cmp::Ordering::{Less, Equal, Greater};
41 use cmp;
42 use default::Default;
43 use iter::*;
44 use kinds::Copy;
45 use num::Int;
46 use ops::{FnMut, mod};
47 use option::Option;
48 use option::Option::{None, Some};
49 use result::Result;
50 use result::Result::{Ok, Err};
51 use ptr;
52 use ptr::PtrExt;
53 use mem;
54 use mem::size_of;
55 use kinds::{Sized, marker};
56 use raw::Repr;
57 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
58 use raw::Slice as RawSlice;
59
60
61 //
62 // Extension traits
63 //
64
65 /// Extension methods for slices.
66 #[allow(missing_docs)] // docs in libcollections
67 pub trait SliceExt for Sized? {
68     type Item;
69
70     fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [Self::Item];
71     fn slice_from<'a>(&'a self, start: uint) -> &'a [Self::Item];
72     fn slice_to<'a>(&'a self, end: uint) -> &'a [Self::Item];
73     fn split_at<'a>(&'a self, mid: uint) -> (&'a [Self::Item], &'a [Self::Item]);
74     fn iter<'a>(&'a self) -> Iter<'a, Self::Item>;
75     fn split<'a, P>(&'a self, pred: P) -> Split<'a, Self::Item, P>
76                     where P: FnMut(&Self::Item) -> bool;
77     fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitN<'a, Self::Item, P>
78                      where P: FnMut(&Self::Item) -> bool;
79     fn rsplitn<'a, P>(&'a self,  n: uint, pred: P) -> RSplitN<'a, Self::Item, P>
80                       where P: FnMut(&Self::Item) -> bool;
81     fn windows<'a>(&'a self, size: uint) -> Windows<'a, Self::Item>;
82     fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, Self::Item>;
83     fn get<'a>(&'a self, index: uint) -> Option<&'a Self::Item>;
84     fn first<'a>(&'a self) -> Option<&'a Self::Item>;
85     fn tail<'a>(&'a self) -> &'a [Self::Item];
86     fn init<'a>(&'a self) -> &'a [Self::Item];
87     fn last<'a>(&'a self) -> Option<&'a Self::Item>;
88     unsafe fn get_unchecked<'a>(&'a self, index: uint) -> &'a Self::Item;
89     fn as_ptr(&self) -> *const Self::Item;
90     fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where
91         F: FnMut(&Self::Item) -> Ordering;
92     fn len(&self) -> uint;
93     fn is_empty(&self) -> bool { self.len() == 0 }
94     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut Self::Item>;
95     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [Self::Item];
96     fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [Self::Item];
97     fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [Self::Item];
98     fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [Self::Item];
99     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, Self::Item>;
100     fn first_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>;
101     fn tail_mut<'a>(&'a mut self) -> &'a mut [Self::Item];
102     fn init_mut<'a>(&'a mut self) -> &'a mut [Self::Item];
103     fn last_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>;
104     fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, Self::Item, P>
105                         where P: FnMut(&Self::Item) -> bool;
106     fn splitn_mut<P>(&mut self, n: uint, pred: P) -> SplitNMut<Self::Item, P>
107                      where P: FnMut(&Self::Item) -> bool;
108     fn rsplitn_mut<P>(&mut self,  n: uint, pred: P) -> RSplitNMut<Self::Item, P>
109                       where P: FnMut(&Self::Item) -> bool;
110     fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> ChunksMut<'a, Self::Item>;
111     fn swap(&mut self, a: uint, b: uint);
112     fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [Self::Item], &'a mut [Self::Item]);
113     fn reverse(&mut self);
114     unsafe fn get_unchecked_mut<'a>(&'a mut self, index: uint) -> &'a mut Self::Item;
115     fn as_mut_ptr(&mut self) -> *mut Self::Item;
116
117     fn position_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
118
119     fn rposition_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
120
121     fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq;
122
123     fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
124
125     fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
126
127     fn binary_search(&self, x: &Self::Item) -> Result<uint, uint> where Self::Item: Ord;
128     fn next_permutation(&mut self) -> bool where Self::Item: Ord;
129     fn prev_permutation(&mut self) -> bool where Self::Item: Ord;
130
131     fn clone_from_slice(&mut self, &[Self::Item]) -> uint where Self::Item: Clone;
132 }
133
134 #[unstable]
135 impl<T> SliceExt for [T] {
136     type Item = T;
137
138     #[inline]
139     fn slice(&self, start: uint, end: uint) -> &[T] {
140         assert!(start <= end);
141         assert!(end <= self.len());
142         unsafe {
143             transmute(RawSlice {
144                 data: self.as_ptr().offset(start as int),
145                 len: (end - start)
146             })
147         }
148     }
149
150     #[inline]
151     fn slice_from(&self, start: uint) -> &[T] {
152         self.slice(start, self.len())
153     }
154
155     #[inline]
156     fn slice_to(&self, end: uint) -> &[T] {
157         self.slice(0, end)
158     }
159
160     #[inline]
161     fn split_at(&self, mid: uint) -> (&[T], &[T]) {
162         (self[..mid], self[mid..])
163     }
164
165     #[inline]
166     fn iter<'a>(&'a self) -> Iter<'a, T> {
167         unsafe {
168             let p = self.as_ptr();
169             if mem::size_of::<T>() == 0 {
170                 Iter {ptr: p,
171                       end: (p as uint + self.len()) as *const T,
172                       marker: marker::ContravariantLifetime::<'a>}
173             } else {
174                 Iter {ptr: p,
175                       end: p.offset(self.len() as int),
176                       marker: marker::ContravariantLifetime::<'a>}
177             }
178         }
179     }
180
181     #[inline]
182     fn split<'a, P>(&'a self, pred: P) -> Split<'a, T, P> where P: FnMut(&T) -> bool {
183         Split {
184             v: self,
185             pred: pred,
186             finished: false
187         }
188     }
189
190     #[inline]
191     fn splitn<'a, P>(&'a self, n: uint, pred: P) -> SplitN<'a, T, P> where
192         P: FnMut(&T) -> bool,
193     {
194         SplitN {
195             inner: GenericSplitN {
196                 iter: self.split(pred),
197                 count: n,
198                 invert: false
199             }
200         }
201     }
202
203     #[inline]
204     fn rsplitn<'a, P>(&'a self, n: uint, pred: P) -> RSplitN<'a, T, P> where
205         P: FnMut(&T) -> bool,
206     {
207         RSplitN {
208             inner: GenericSplitN {
209                 iter: self.split(pred),
210                 count: n,
211                 invert: true
212             }
213         }
214     }
215
216     #[inline]
217     fn windows(&self, size: uint) -> Windows<T> {
218         assert!(size != 0);
219         Windows { v: self, size: size }
220     }
221
222     #[inline]
223     fn chunks(&self, size: uint) -> Chunks<T> {
224         assert!(size != 0);
225         Chunks { v: self, size: size }
226     }
227
228     #[inline]
229     fn get(&self, index: uint) -> Option<&T> {
230         if index < self.len() { Some(&self[index]) } else { None }
231     }
232
233     #[inline]
234     fn first(&self) -> Option<&T> {
235         if self.len() == 0 { None } else { Some(&self[0]) }
236     }
237
238     #[inline]
239     fn tail(&self) -> &[T] { self[1..] }
240
241     #[inline]
242     fn init(&self) -> &[T] {
243         self[..self.len() - 1]
244     }
245
246     #[inline]
247     fn last(&self) -> Option<&T> {
248         if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
249     }
250
251     #[inline]
252     unsafe fn get_unchecked(&self, index: uint) -> &T {
253         transmute(self.repr().data.offset(index as int))
254     }
255
256     #[inline]
257     fn as_ptr(&self) -> *const T {
258         self.repr().data
259     }
260
261     #[unstable]
262     fn binary_search_by<F>(&self, mut f: F) -> Result<uint, uint> where
263         F: FnMut(&T) -> Ordering
264     {
265         let mut base : uint = 0;
266         let mut lim : uint = self.len();
267
268         while lim != 0 {
269             let ix = base + (lim >> 1);
270             match f(&self[ix]) {
271                 Equal => return Ok(ix),
272                 Less => {
273                     base = ix + 1;
274                     lim -= 1;
275                 }
276                 Greater => ()
277             }
278             lim >>= 1;
279         }
280         Err(base)
281     }
282
283     #[inline]
284     fn len(&self) -> uint { self.repr().len }
285
286     #[inline]
287     fn get_mut(&mut self, index: uint) -> Option<&mut T> {
288         if index < self.len() { Some(&mut self[index]) } else { None }
289     }
290
291     #[inline]
292     fn as_mut_slice(&mut self) -> &mut [T] { self }
293
294     fn slice_mut(&mut self, start: uint, end: uint) -> &mut [T] {
295         ops::SliceMut::slice_or_fail_mut(self, &start, &end)
296     }
297
298     #[inline]
299     fn slice_from_mut(&mut self, start: uint) -> &mut [T] {
300         ops::SliceMut::slice_from_or_fail_mut(self, &start)
301     }
302
303     #[inline]
304     fn slice_to_mut(&mut self, end: uint) -> &mut [T] {
305         ops::SliceMut::slice_to_or_fail_mut(self, &end)
306     }
307
308     #[inline]
309     fn split_at_mut(&mut self, mid: uint) -> (&mut [T], &mut [T]) {
310         unsafe {
311             let self2: &mut [T] = mem::transmute_copy(&self);
312
313             (ops::SliceMut::slice_to_or_fail_mut(self, &mid),
314              ops::SliceMut::slice_from_or_fail_mut(self2, &mid))
315         }
316     }
317
318     #[inline]
319     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
320         unsafe {
321             let p = self.as_mut_ptr();
322             if mem::size_of::<T>() == 0 {
323                 IterMut {ptr: p,
324                          end: (p as uint + self.len()) as *mut T,
325                          marker: marker::ContravariantLifetime::<'a>}
326             } else {
327                 IterMut {ptr: p,
328                          end: p.offset(self.len() as int),
329                          marker: marker::ContravariantLifetime::<'a>}
330             }
331         }
332     }
333
334     #[inline]
335     fn last_mut(&mut self) -> Option<&mut T> {
336         let len = self.len();
337         if len == 0 { return None; }
338         Some(&mut self[len - 1])
339     }
340
341     #[inline]
342     fn first_mut(&mut self) -> Option<&mut T> {
343         if self.len() == 0 { None } else { Some(&mut self[0]) }
344     }
345
346     #[inline]
347     fn tail_mut(&mut self) -> &mut [T] {
348         self.slice_from_mut(1)
349     }
350
351     #[inline]
352     fn init_mut(&mut self) -> &mut [T] {
353         let len = self.len();
354         self.slice_to_mut(len-1)
355     }
356
357     #[inline]
358     fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
359         SplitMut { v: self, pred: pred, finished: false }
360     }
361
362     #[inline]
363     fn splitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> SplitNMut<'a, T, P> where
364         P: FnMut(&T) -> bool
365     {
366         SplitNMut {
367             inner: GenericSplitN {
368                 iter: self.split_mut(pred),
369                 count: n,
370                 invert: false
371             }
372         }
373     }
374
375     #[inline]
376     fn rsplitn_mut<'a, P>(&'a mut self, n: uint, pred: P) -> RSplitNMut<'a, T, P> where
377         P: FnMut(&T) -> bool,
378     {
379         RSplitNMut {
380             inner: GenericSplitN {
381                 iter: self.split_mut(pred),
382                 count: n,
383                 invert: true
384             }
385         }
386    }
387
388     #[inline]
389     fn chunks_mut(&mut self, chunk_size: uint) -> ChunksMut<T> {
390         assert!(chunk_size > 0);
391         ChunksMut { v: self, chunk_size: chunk_size }
392     }
393
394     fn swap(&mut self, a: uint, b: uint) {
395         unsafe {
396             // Can't take two mutable loans from one vector, so instead just cast
397             // them to their raw pointers to do the swap
398             let pa: *mut T = &mut self[a];
399             let pb: *mut T = &mut self[b];
400             ptr::swap(pa, pb);
401         }
402     }
403
404     fn reverse(&mut self) {
405         let mut i: uint = 0;
406         let ln = self.len();
407         while i < ln / 2 {
408             // Unsafe swap to avoid the bounds check in safe swap.
409             unsafe {
410                 let pa: *mut T = self.get_unchecked_mut(i);
411                 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
412                 ptr::swap(pa, pb);
413             }
414             i += 1;
415         }
416     }
417
418     #[inline]
419     unsafe fn get_unchecked_mut(&mut self, index: uint) -> &mut T {
420         transmute((self.repr().data as *mut T).offset(index as int))
421     }
422
423     #[inline]
424     fn as_mut_ptr(&mut self) -> *mut T {
425         self.repr().data as *mut T
426     }
427
428     #[inline]
429     fn position_elem(&self, x: &T) -> Option<uint> where T: PartialEq {
430         self.iter().position(|y| *x == *y)
431     }
432
433     #[inline]
434     fn rposition_elem(&self, t: &T) -> Option<uint> where T: PartialEq {
435         self.iter().rposition(|x| *x == *t)
436     }
437
438     #[inline]
439     fn contains(&self, x: &T) -> bool where T: PartialEq {
440         self.iter().any(|elt| *x == *elt)
441     }
442
443     #[inline]
444     fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq {
445         let n = needle.len();
446         self.len() >= n && needle == self[..n]
447     }
448
449     #[inline]
450     fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq {
451         let (m, n) = (self.len(), needle.len());
452         m >= n && needle == self[m-n..]
453     }
454
455     #[unstable]
456     fn binary_search(&self, x: &T) -> Result<uint, uint> where T: Ord {
457         self.binary_search_by(|p| p.cmp(x))
458     }
459
460     #[experimental]
461     fn next_permutation(&mut self) -> bool where T: Ord {
462         // These cases only have 1 permutation each, so we can't do anything.
463         if self.len() < 2 { return false; }
464
465         // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
466         let mut i = self.len() - 1;
467         while i > 0 && self[i-1] >= self[i] {
468             i -= 1;
469         }
470
471         // If that is the entire vector, this is the last-ordered permutation.
472         if i == 0 {
473             return false;
474         }
475
476         // Step 2: Find the rightmost element larger than the pivot (i-1)
477         let mut j = self.len() - 1;
478         while j >= i && self[j] <= self[i-1]  {
479             j -= 1;
480         }
481
482         // Step 3: Swap that element with the pivot
483         self.swap(j, i-1);
484
485         // Step 4: Reverse the (previously) weakly decreasing part
486         self.slice_from_mut(i).reverse();
487
488         true
489     }
490
491     #[experimental]
492     fn prev_permutation(&mut self) -> bool where T: Ord {
493         // These cases only have 1 permutation each, so we can't do anything.
494         if self.len() < 2 { return false; }
495
496         // Step 1: Identify the longest, rightmost weakly increasing part of the vector
497         let mut i = self.len() - 1;
498         while i > 0 && self[i-1] <= self[i] {
499             i -= 1;
500         }
501
502         // If that is the entire vector, this is the first-ordered permutation.
503         if i == 0 {
504             return false;
505         }
506
507         // Step 2: Reverse the weakly increasing part
508         self.slice_from_mut(i).reverse();
509
510         // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
511         let mut j = self.len() - 1;
512         while j >= i && self[j-1] < self[i-1]  {
513             j -= 1;
514         }
515
516         // Step 4: Swap that element with the pivot
517         self.swap(i-1, j);
518
519         true
520     }
521
522     #[inline]
523     fn clone_from_slice(&mut self, src: &[T]) -> uint where T: Clone {
524         let min = cmp::min(self.len(), src.len());
525         let dst = self.slice_to_mut(min);
526         let src = src.slice_to(min);
527         for i in range(0, min) {
528             dst[i].clone_from(&src[i]);
529         }
530         min
531     }
532 }
533
534 impl<T> ops::Index<uint, T> for [T] {
535     fn index(&self, &index: &uint) -> &T {
536         assert!(index < self.len());
537
538         unsafe { mem::transmute(self.repr().data.offset(index as int)) }
539     }
540 }
541
542 impl<T> ops::IndexMut<uint, T> for [T] {
543     fn index_mut(&mut self, &index: &uint) -> &mut T {
544         assert!(index < self.len());
545
546         unsafe { mem::transmute(self.repr().data.offset(index as int)) }
547     }
548 }
549
550 impl<T> ops::Slice<uint, [T]> for [T] {
551     #[inline]
552     fn as_slice_<'a>(&'a self) -> &'a [T] {
553         self
554     }
555
556     #[inline]
557     fn slice_from_or_fail<'a>(&'a self, start: &uint) -> &'a [T] {
558         self.slice_or_fail(start, &self.len())
559     }
560
561     #[inline]
562     fn slice_to_or_fail<'a>(&'a self, end: &uint) -> &'a [T] {
563         self.slice_or_fail(&0, end)
564     }
565     #[inline]
566     fn slice_or_fail<'a>(&'a self, start: &uint, end: &uint) -> &'a [T] {
567         assert!(*start <= *end);
568         assert!(*end <= self.len());
569         unsafe {
570             transmute(RawSlice {
571                     data: self.as_ptr().offset(*start as int),
572                     len: (*end - *start)
573                 })
574         }
575     }
576 }
577
578 impl<T> ops::SliceMut<uint, [T]> for [T] {
579     #[inline]
580     fn as_mut_slice_<'a>(&'a mut self) -> &'a mut [T] {
581         self
582     }
583
584     #[inline]
585     fn slice_from_or_fail_mut<'a>(&'a mut self, start: &uint) -> &'a mut [T] {
586         let len = &self.len();
587         self.slice_or_fail_mut(start, len)
588     }
589
590     #[inline]
591     fn slice_to_or_fail_mut<'a>(&'a mut self, end: &uint) -> &'a mut [T] {
592         self.slice_or_fail_mut(&0, end)
593     }
594     #[inline]
595     fn slice_or_fail_mut<'a>(&'a mut self, start: &uint, end: &uint) -> &'a mut [T] {
596         assert!(*start <= *end);
597         assert!(*end <= self.len());
598         unsafe {
599             transmute(RawSlice {
600                     data: self.as_ptr().offset(*start as int),
601                     len: (*end - *start)
602                 })
603         }
604     }
605 }
606
607 ////////////////////////////////////////////////////////////////////////////////
608 // Common traits
609 ////////////////////////////////////////////////////////////////////////////////
610
611 /// Data that is viewable as a slice.
612 #[experimental = "will be replaced by slice syntax"]
613 pub trait AsSlice<T> for Sized? {
614     /// Work with `self` as a slice.
615     fn as_slice<'a>(&'a self) -> &'a [T];
616 }
617
618 #[experimental = "trait is experimental"]
619 impl<T> AsSlice<T> for [T] {
620     #[inline(always)]
621     fn as_slice<'a>(&'a self) -> &'a [T] { self }
622 }
623
624 #[experimental = "trait is experimental"]
625 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U {
626     #[inline(always)]
627     fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) }
628 }
629
630 #[experimental = "trait is experimental"]
631 impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U {
632     #[inline(always)]
633     fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) }
634 }
635
636 #[stable]
637 impl<'a, T> Default for &'a [T] {
638     #[stable]
639     fn default() -> &'a [T] { &[] }
640 }
641
642 //
643 // Iterators
644 //
645
646 // The shared definition of the `Iter` and `IterMut` iterators
647 macro_rules! iterator {
648     (struct $name:ident -> $ptr:ty, $elem:ty) => {
649         #[experimental = "needs review"]
650         impl<'a, T> Iterator for $name<'a, T> {
651             type Item = $elem;
652
653             #[inline]
654             fn next(&mut self) -> Option<$elem> {
655                 // could be implemented with slices, but this avoids bounds checks
656                 unsafe {
657                     if self.ptr == self.end {
658                         None
659                     } else {
660                         if mem::size_of::<T>() == 0 {
661                             // purposefully don't use 'ptr.offset' because for
662                             // vectors with 0-size elements this would return the
663                             // same pointer.
664                             self.ptr = transmute(self.ptr as uint + 1);
665
666                             // Use a non-null pointer value
667                             Some(transmute(1u))
668                         } else {
669                             let old = self.ptr;
670                             self.ptr = self.ptr.offset(1);
671
672                             Some(transmute(old))
673                         }
674                     }
675                 }
676             }
677
678             #[inline]
679             fn size_hint(&self) -> (uint, Option<uint>) {
680                 let diff = (self.end as uint) - (self.ptr as uint);
681                 let size = mem::size_of::<T>();
682                 let exact = diff / (if size == 0 {1} else {size});
683                 (exact, Some(exact))
684             }
685         }
686
687         #[experimental = "needs review"]
688         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
689             #[inline]
690             fn next_back(&mut self) -> Option<$elem> {
691                 // could be implemented with slices, but this avoids bounds checks
692                 unsafe {
693                     if self.end == self.ptr {
694                         None
695                     } else {
696                         if mem::size_of::<T>() == 0 {
697                             // See above for why 'ptr.offset' isn't used
698                             self.end = transmute(self.end as uint - 1);
699
700                             // Use a non-null pointer value
701                             Some(transmute(1u))
702                         } else {
703                             self.end = self.end.offset(-1);
704
705                             Some(transmute(self.end))
706                         }
707                     }
708                 }
709             }
710         }
711     }
712 }
713
714 macro_rules! make_slice {
715     ($t: ty -> $result: ty: $start: expr, $end: expr) => {{
716         let diff = $end as uint - $start as uint;
717         let len = if mem::size_of::<T>() == 0 {
718             diff
719         } else {
720             diff / mem::size_of::<$t>()
721         };
722         unsafe {
723             transmute::<_, $result>(RawSlice { data: $start as *const T, len: len })
724         }
725     }}
726 }
727
728 /// Immutable slice iterator
729 #[stable]
730 pub struct Iter<'a, T: 'a> {
731     ptr: *const T,
732     end: *const T,
733     marker: marker::ContravariantLifetime<'a>
734 }
735
736 #[experimental]
737 impl<'a, T> ops::Slice<uint, [T]> for Iter<'a, T> {
738     fn as_slice_(&self) -> &[T] {
739         self.as_slice()
740     }
741     fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
742         use ops::Slice;
743         self.as_slice().slice_from_or_fail(from)
744     }
745     fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
746         use ops::Slice;
747         self.as_slice().slice_to_or_fail(to)
748     }
749     fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
750         use ops::Slice;
751         self.as_slice().slice_or_fail(from, to)
752     }
753 }
754
755 impl<'a, T> Iter<'a, T> {
756     /// View the underlying data as a subslice of the original data.
757     ///
758     /// This has the same lifetime as the original slice, and so the
759     /// iterator can continue to be used while this exists.
760     #[experimental]
761     pub fn as_slice(&self) -> &'a [T] {
762         make_slice!(T -> &'a [T]: self.ptr, self.end)
763     }
764 }
765
766 impl<'a,T> Copy for Iter<'a,T> {}
767
768 iterator!{struct Iter -> *const T, &'a T}
769
770 #[experimental = "needs review"]
771 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
772
773 #[stable]
774 impl<'a, T> Clone for Iter<'a, T> {
775     fn clone(&self) -> Iter<'a, T> { *self }
776 }
777
778 #[experimental = "needs review"]
779 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
780     #[inline]
781     fn indexable(&self) -> uint {
782         let (exact, _) = self.size_hint();
783         exact
784     }
785
786     #[inline]
787     fn idx(&mut self, index: uint) -> Option<&'a T> {
788         unsafe {
789             if index < self.indexable() {
790                 if mem::size_of::<T>() == 0 {
791                     // Use a non-null pointer value
792                     Some(transmute(1u))
793                 } else {
794                     Some(transmute(self.ptr.offset(index as int)))
795                 }
796             } else {
797                 None
798             }
799         }
800     }
801 }
802
803 /// Mutable slice iterator.
804 #[stable]
805 pub struct IterMut<'a, T: 'a> {
806     ptr: *mut T,
807     end: *mut T,
808     marker: marker::ContravariantLifetime<'a>,
809 }
810
811 #[experimental]
812 impl<'a, T> ops::Slice<uint, [T]> for IterMut<'a, T> {
813     fn as_slice_<'b>(&'b self) -> &'b [T] {
814         make_slice!(T -> &'b [T]: self.ptr, self.end)
815     }
816     fn slice_from_or_fail<'b>(&'b self, from: &uint) -> &'b [T] {
817         use ops::Slice;
818         self.as_slice_().slice_from_or_fail(from)
819     }
820     fn slice_to_or_fail<'b>(&'b self, to: &uint) -> &'b [T] {
821         use ops::Slice;
822         self.as_slice_().slice_to_or_fail(to)
823     }
824     fn slice_or_fail<'b>(&'b self, from: &uint, to: &uint) -> &'b [T] {
825         use ops::Slice;
826         self.as_slice_().slice_or_fail(from, to)
827     }
828 }
829
830 #[experimental]
831 impl<'a, T> ops::SliceMut<uint, [T]> for IterMut<'a, T> {
832     fn as_mut_slice_<'b>(&'b mut self) -> &'b mut [T] {
833         make_slice!(T -> &'b mut [T]: self.ptr, self.end)
834     }
835     fn slice_from_or_fail_mut<'b>(&'b mut self, from: &uint) -> &'b mut [T] {
836         use ops::SliceMut;
837         self.as_mut_slice_().slice_from_or_fail_mut(from)
838     }
839     fn slice_to_or_fail_mut<'b>(&'b mut self, to: &uint) -> &'b mut [T] {
840         use ops::SliceMut;
841         self.as_mut_slice_().slice_to_or_fail_mut(to)
842     }
843     fn slice_or_fail_mut<'b>(&'b mut self, from: &uint, to: &uint) -> &'b mut [T] {
844         use ops::SliceMut;
845         self.as_mut_slice_().slice_or_fail_mut(from, to)
846     }
847 }
848
849 impl<'a, T> IterMut<'a, T> {
850     /// View the underlying data as a subslice of the original data.
851     ///
852     /// To avoid creating `&mut` references that alias, this is forced
853     /// to consume the iterator. Consider using the `Slice` and
854     /// `SliceMut` implementations for obtaining slices with more
855     /// restricted lifetimes that do not consume the iterator.
856     #[experimental]
857     pub fn into_slice(self) -> &'a mut [T] {
858         make_slice!(T -> &'a mut [T]: self.ptr, self.end)
859     }
860 }
861
862 iterator!{struct IterMut -> *mut T, &'a mut T}
863
864 #[experimental = "needs review"]
865 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
866
867 /// An internal abstraction over the splitting iterators, so that
868 /// splitn, splitn_mut etc can be implemented once.
869 trait SplitIter: DoubleEndedIterator {
870     /// Mark the underlying iterator as complete, extracting the remaining
871     /// portion of the slice.
872     fn finish(&mut self) -> Option< <Self as Iterator>::Item>;
873 }
874
875 /// An iterator over subslices separated by elements that match a predicate
876 /// function.
877 #[stable]
878 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
879     v: &'a [T],
880     pred: P,
881     finished: bool
882 }
883
884 // FIXME(#19839) Remove in favor of `#[deriving(Clone)]`
885 #[stable]
886 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
887     fn clone(&self) -> Split<'a, T, P> {
888         Split {
889             v: self.v,
890             pred: self.pred.clone(),
891             finished: self.finished,
892         }
893     }
894 }
895
896 #[experimental = "needs review"]
897 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
898     type Item = &'a [T];
899
900     #[inline]
901     fn next(&mut self) -> Option<&'a [T]> {
902         if self.finished { return None; }
903
904         match self.v.iter().position(|x| (self.pred)(x)) {
905             None => self.finish(),
906             Some(idx) => {
907                 let ret = Some(self.v[..idx]);
908                 self.v = self.v[idx + 1..];
909                 ret
910             }
911         }
912     }
913
914     #[inline]
915     fn size_hint(&self) -> (uint, Option<uint>) {
916         if self.finished {
917             (0, Some(0))
918         } else {
919             (1, Some(self.v.len() + 1))
920         }
921     }
922 }
923
924 #[experimental = "needs review"]
925 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
926     #[inline]
927     fn next_back(&mut self) -> Option<&'a [T]> {
928         if self.finished { return None; }
929
930         match self.v.iter().rposition(|x| (self.pred)(x)) {
931             None => self.finish(),
932             Some(idx) => {
933                 let ret = Some(self.v[idx + 1..]);
934                 self.v = self.v[..idx];
935                 ret
936             }
937         }
938     }
939 }
940
941 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
942     #[inline]
943     fn finish(&mut self) -> Option<&'a [T]> {
944         if self.finished { None } else { self.finished = true; Some(self.v) }
945     }
946 }
947
948 /// An iterator over the subslices of the vector which are separated
949 /// by elements that match `pred`.
950 #[stable]
951 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
952     v: &'a mut [T],
953     pred: P,
954     finished: bool
955 }
956
957 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
958     #[inline]
959     fn finish(&mut self) -> Option<&'a mut [T]> {
960         if self.finished {
961             None
962         } else {
963             self.finished = true;
964             Some(mem::replace(&mut self.v, &mut []))
965         }
966     }
967 }
968
969 #[experimental = "needs review"]
970 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
971     type Item = &'a mut [T];
972
973     #[inline]
974     fn next(&mut self) -> Option<&'a mut [T]> {
975         if self.finished { return None; }
976
977         let idx_opt = { // work around borrowck limitations
978             let pred = &mut self.pred;
979             self.v.iter().position(|x| (*pred)(x))
980         };
981         match idx_opt {
982             None => self.finish(),
983             Some(idx) => {
984                 let tmp = mem::replace(&mut self.v, &mut []);
985                 let (head, tail) = tmp.split_at_mut(idx);
986                 self.v = tail.slice_from_mut(1);
987                 Some(head)
988             }
989         }
990     }
991
992     #[inline]
993     fn size_hint(&self) -> (uint, Option<uint>) {
994         if self.finished {
995             (0, Some(0))
996         } else {
997             // if the predicate doesn't match anything, we yield one slice
998             // if it matches every element, we yield len+1 empty slices.
999             (1, Some(self.v.len() + 1))
1000         }
1001     }
1002 }
1003
1004 #[experimental = "needs review"]
1005 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
1006     P: FnMut(&T) -> bool,
1007 {
1008     #[inline]
1009     fn next_back(&mut self) -> Option<&'a mut [T]> {
1010         if self.finished { return None; }
1011
1012         let idx_opt = { // work around borrowck limitations
1013             let pred = &mut self.pred;
1014             self.v.iter().rposition(|x| (*pred)(x))
1015         };
1016         match idx_opt {
1017             None => self.finish(),
1018             Some(idx) => {
1019                 let tmp = mem::replace(&mut self.v, &mut []);
1020                 let (head, tail) = tmp.split_at_mut(idx);
1021                 self.v = head;
1022                 Some(tail.slice_from_mut(1))
1023             }
1024         }
1025     }
1026 }
1027
1028 /// An private iterator over subslices separated by elements that
1029 /// match a predicate function, splitting at most a fixed number of
1030 /// times.
1031 struct GenericSplitN<I> {
1032     iter: I,
1033     count: uint,
1034     invert: bool
1035 }
1036
1037 #[experimental = "needs review"]
1038 impl<T, I: SplitIter + Iterator<Item=T>> Iterator for GenericSplitN<I> {
1039     type Item = T;
1040
1041     #[inline]
1042     fn next(&mut self) -> Option<T> {
1043         if self.count == 0 {
1044             self.iter.finish()
1045         } else {
1046             self.count -= 1;
1047             if self.invert { self.iter.next_back() } else { self.iter.next() }
1048         }
1049     }
1050
1051     #[inline]
1052     fn size_hint(&self) -> (uint, Option<uint>) {
1053         let (lower, upper_opt) = self.iter.size_hint();
1054         (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper)))
1055     }
1056 }
1057
1058 /// An iterator over subslices separated by elements that match a predicate
1059 /// function, limited to a given number of splits.
1060 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1061     inner: GenericSplitN<Split<'a, T, P>>
1062 }
1063
1064 /// An iterator over subslices separated by elements that match a
1065 /// predicate function, limited to a given number of splits, starting
1066 /// from the end of the slice.
1067 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1068     inner: GenericSplitN<Split<'a, T, P>>
1069 }
1070
1071 /// An iterator over subslices separated by elements that match a predicate
1072 /// function, limited to a given number of splits.
1073 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1074     inner: GenericSplitN<SplitMut<'a, T, P>>
1075 }
1076
1077 /// An iterator over subslices separated by elements that match a
1078 /// predicate function, limited to a given number of splits, starting
1079 /// from the end of the slice.
1080 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1081     inner: GenericSplitN<SplitMut<'a, T, P>>
1082 }
1083
1084 macro_rules! forward_iterator {
1085     ($name:ident: $elem:ident, $iter_of:ty) => {
1086         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
1087             P: FnMut(&T) -> bool
1088         {
1089             type Item = $iter_of;
1090
1091             #[inline]
1092             fn next(&mut self) -> Option<$iter_of> {
1093                 self.inner.next()
1094             }
1095
1096             #[inline]
1097             fn size_hint(&self) -> (uint, Option<uint>) {
1098                 self.inner.size_hint()
1099             }
1100         }
1101     }
1102 }
1103
1104 forward_iterator! { SplitN: T, &'a [T] }
1105 forward_iterator! { RSplitN: T, &'a [T] }
1106 forward_iterator! { SplitNMut: T, &'a mut [T] }
1107 forward_iterator! { RSplitNMut: T, &'a mut [T] }
1108
1109 /// An iterator over overlapping subslices of length `size`.
1110 #[deriving(Clone)]
1111 #[experimental = "needs review"]
1112 pub struct Windows<'a, T:'a> {
1113     v: &'a [T],
1114     size: uint
1115 }
1116
1117 impl<'a, T> Iterator for Windows<'a, T> {
1118     type Item = &'a [T];
1119
1120     #[inline]
1121     fn next(&mut self) -> Option<&'a [T]> {
1122         if self.size > self.v.len() {
1123             None
1124         } else {
1125             let ret = Some(self.v[..self.size]);
1126             self.v = self.v[1..];
1127             ret
1128         }
1129     }
1130
1131     #[inline]
1132     fn size_hint(&self) -> (uint, Option<uint>) {
1133         if self.size > self.v.len() {
1134             (0, Some(0))
1135         } else {
1136             let x = self.v.len() - self.size;
1137             (x.saturating_add(1), x.checked_add(1u))
1138         }
1139     }
1140 }
1141
1142 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1143 /// time).
1144 ///
1145 /// When the slice len is not evenly divided by the chunk size, the last slice
1146 /// of the iteration will be the remainder.
1147 #[deriving(Clone)]
1148 #[experimental = "needs review"]
1149 pub struct Chunks<'a, T:'a> {
1150     v: &'a [T],
1151     size: uint
1152 }
1153
1154 #[experimental = "needs review"]
1155 impl<'a, T> Iterator for Chunks<'a, T> {
1156     type Item = &'a [T];
1157
1158     #[inline]
1159     fn next(&mut self) -> Option<&'a [T]> {
1160         if self.v.len() == 0 {
1161             None
1162         } else {
1163             let chunksz = cmp::min(self.v.len(), self.size);
1164             let (fst, snd) = self.v.split_at(chunksz);
1165             self.v = snd;
1166             Some(fst)
1167         }
1168     }
1169
1170     #[inline]
1171     fn size_hint(&self) -> (uint, Option<uint>) {
1172         if self.v.len() == 0 {
1173             (0, Some(0))
1174         } else {
1175             let n = self.v.len() / self.size;
1176             let rem = self.v.len() % self.size;
1177             let n = if rem > 0 { n+1 } else { n };
1178             (n, Some(n))
1179         }
1180     }
1181 }
1182
1183 #[experimental = "needs review"]
1184 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
1185     #[inline]
1186     fn next_back(&mut self) -> Option<&'a [T]> {
1187         if self.v.len() == 0 {
1188             None
1189         } else {
1190             let remainder = self.v.len() % self.size;
1191             let chunksz = if remainder != 0 { remainder } else { self.size };
1192             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1193             self.v = fst;
1194             Some(snd)
1195         }
1196     }
1197 }
1198
1199 #[experimental = "needs review"]
1200 impl<'a, T> RandomAccessIterator for Chunks<'a, T> {
1201     #[inline]
1202     fn indexable(&self) -> uint {
1203         self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1204     }
1205
1206     #[inline]
1207     fn idx(&mut self, index: uint) -> Option<&'a [T]> {
1208         if index < self.indexable() {
1209             let lo = index * self.size;
1210             let mut hi = lo + self.size;
1211             if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1212
1213             Some(self.v[lo..hi])
1214         } else {
1215             None
1216         }
1217     }
1218 }
1219
1220 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1221 /// elements at a time). When the slice len is not evenly divided by the chunk
1222 /// size, the last slice of the iteration will be the remainder.
1223 #[experimental = "needs review"]
1224 pub struct ChunksMut<'a, T:'a> {
1225     v: &'a mut [T],
1226     chunk_size: uint
1227 }
1228
1229 #[experimental = "needs review"]
1230 impl<'a, T> Iterator for ChunksMut<'a, T> {
1231     type Item = &'a mut [T];
1232
1233     #[inline]
1234     fn next(&mut self) -> Option<&'a mut [T]> {
1235         if self.v.len() == 0 {
1236             None
1237         } else {
1238             let sz = cmp::min(self.v.len(), self.chunk_size);
1239             let tmp = mem::replace(&mut self.v, &mut []);
1240             let (head, tail) = tmp.split_at_mut(sz);
1241             self.v = tail;
1242             Some(head)
1243         }
1244     }
1245
1246     #[inline]
1247     fn size_hint(&self) -> (uint, Option<uint>) {
1248         if self.v.len() == 0 {
1249             (0, Some(0))
1250         } else {
1251             let n = self.v.len() / self.chunk_size;
1252             let rem = self.v.len() % self.chunk_size;
1253             let n = if rem > 0 { n + 1 } else { n };
1254             (n, Some(n))
1255         }
1256     }
1257 }
1258
1259 #[experimental = "needs review"]
1260 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
1261     #[inline]
1262     fn next_back(&mut self) -> Option<&'a mut [T]> {
1263         if self.v.len() == 0 {
1264             None
1265         } else {
1266             let remainder = self.v.len() % self.chunk_size;
1267             let sz = if remainder != 0 { remainder } else { self.chunk_size };
1268             let tmp = mem::replace(&mut self.v, &mut []);
1269             let tmp_len = tmp.len();
1270             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1271             self.v = head;
1272             Some(tail)
1273         }
1274     }
1275 }
1276
1277
1278 //
1279 // Free functions
1280 //
1281
1282 /// Converts a pointer to A into a slice of length 1 (without copying).
1283 #[unstable]
1284 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1285     unsafe {
1286         transmute(RawSlice { data: s, len: 1 })
1287     }
1288 }
1289
1290 /// Converts a pointer to A into a slice of length 1 (without copying).
1291 #[unstable]
1292 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1293     unsafe {
1294         let ptr: *const A = transmute(s);
1295         transmute(RawSlice { data: ptr, len: 1 })
1296     }
1297 }
1298
1299 /// Forms a slice from a pointer and a length.
1300 ///
1301 /// The pointer given is actually a reference to the base of the slice. This
1302 /// reference is used to give a concrete lifetime to tie the returned slice to.
1303 /// Typically this should indicate that the slice is valid for as long as the
1304 /// pointer itself is valid.
1305 ///
1306 /// The `len` argument is the number of **elements**, not the number of bytes.
1307 ///
1308 /// This function is unsafe as there is no guarantee that the given pointer is
1309 /// valid for `len` elements, nor whether the lifetime provided is a suitable
1310 /// lifetime for the returned slice.
1311 ///
1312 /// # Example
1313 ///
1314 /// ```rust
1315 /// use std::slice;
1316 ///
1317 /// // manifest a slice out of thin air!
1318 /// let ptr = 0x1234 as *const uint;
1319 /// let amt = 10;
1320 /// unsafe {
1321 ///     let slice = slice::from_raw_buf(&ptr, amt);
1322 /// }
1323 /// ```
1324 #[inline]
1325 #[unstable = "should be renamed to from_raw_parts"]
1326 pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] {
1327     transmute(RawSlice { data: *p, len: len })
1328 }
1329
1330 /// Performs the same functionality as `from_raw_buf`, except that a mutable
1331 /// slice is returned.
1332 ///
1333 /// This function is unsafe for the same reasons as `from_raw_buf`, as well as
1334 /// not being able to provide a non-aliasing guarantee of the returned mutable
1335 /// slice.
1336 #[inline]
1337 #[unstable = "jshould be renamed to from_raw_parts_mut"]
1338 pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] {
1339     transmute(RawSlice { data: *p as *const T, len: len })
1340 }
1341
1342 //
1343 // Submodules
1344 //
1345
1346 /// Unsafe operations
1347 #[deprecated]
1348 pub mod raw {
1349     use mem::transmute;
1350     use ptr::PtrExt;
1351     use raw::Slice;
1352     use ops::FnOnce;
1353     use option::Option;
1354     use option::Option::{None, Some};
1355
1356     /// Form a slice from a pointer and length (as a number of units,
1357     /// not bytes).
1358     #[inline]
1359     #[deprecated = "renamed to slice::from_raw_buf"]
1360     pub unsafe fn buf_as_slice<T, U, F>(p: *const T, len: uint, f: F) -> U where
1361         F: FnOnce(&[T]) -> U,
1362     {
1363         f(transmute(Slice {
1364             data: p,
1365             len: len
1366         }))
1367     }
1368
1369     /// Form a slice from a pointer and length (as a number of units,
1370     /// not bytes).
1371     #[inline]
1372     #[deprecated = "renamed to slice::from_raw_mut_buf"]
1373     pub unsafe fn mut_buf_as_slice<T, U, F>(p: *mut T, len: uint, f: F) -> U where
1374         F: FnOnce(&mut [T]) -> U,
1375     {
1376         f(transmute(Slice {
1377             data: p as *const T,
1378             len: len
1379         }))
1380     }
1381
1382     /// Returns a pointer to first element in slice and adjusts
1383     /// slice so it no longer contains that element. Returns None
1384     /// if the slice is empty. O(1).
1385     #[inline]
1386     #[deprecated = "inspect `Slice::{data, len}` manually (increment data by 1)"]
1387     pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1388         if slice.len == 0 { return None; }
1389         let head: *const T = slice.data;
1390         slice.data = slice.data.offset(1);
1391         slice.len -= 1;
1392         Some(head)
1393     }
1394
1395     /// Returns a pointer to last element in slice and adjusts
1396     /// slice so it no longer contains that element. Returns None
1397     /// if the slice is empty. O(1).
1398     #[inline]
1399     #[deprecated = "inspect `Slice::{data, len}` manually (decrement len by 1)"]
1400     pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> Option<*const T> {
1401         if slice.len == 0 { return None; }
1402         let tail: *const T = slice.data.offset((slice.len - 1) as int);
1403         slice.len -= 1;
1404         Some(tail)
1405     }
1406 }
1407
1408 /// Operations on `[u8]`.
1409 #[experimental = "needs review"]
1410 pub mod bytes {
1411     use kinds::Sized;
1412     use ptr;
1413     use slice::SliceExt;
1414
1415     /// A trait for operations on mutable `[u8]`s.
1416     pub trait MutableByteVector for Sized? {
1417         /// Sets all bytes of the receiver to the given value.
1418         fn set_memory(&mut self, value: u8);
1419     }
1420
1421     impl MutableByteVector for [u8] {
1422         #[inline]
1423         #[allow(experimental)]
1424         fn set_memory(&mut self, value: u8) {
1425             unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1426         }
1427     }
1428
1429     /// Copies data from `src` to `dst`
1430     ///
1431     /// Panics if the length of `dst` is less than the length of `src`.
1432     #[inline]
1433     pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1434         let len_src = src.len();
1435         assert!(dst.len() >= len_src);
1436         // `dst` is unaliasable, so we know statically it doesn't overlap
1437         // with `src`.
1438         unsafe {
1439             ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(),
1440                                             src.as_ptr(),
1441                                             len_src);
1442         }
1443     }
1444 }
1445
1446
1447
1448 //
1449 // Boilerplate traits
1450 //
1451
1452 #[stable]
1453 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1454     fn eq(&self, other: &[B]) -> bool {
1455         self.len() == other.len() &&
1456             order::eq(self.iter(), other.iter())
1457     }
1458     fn ne(&self, other: &[B]) -> bool {
1459         self.len() != other.len() ||
1460             order::ne(self.iter(), other.iter())
1461     }
1462 }
1463
1464 #[stable]
1465 impl<T: Eq> Eq for [T] {}
1466
1467 #[allow(deprecated)]
1468 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1469 impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
1470     #[inline]
1471     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1472 }
1473
1474 #[allow(deprecated)]
1475 #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
1476 impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
1477     #[inline]
1478     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
1479 }
1480
1481 #[stable]
1482 impl<T: Ord> Ord for [T] {
1483     fn cmp(&self, other: &[T]) -> Ordering {
1484         order::cmp(self.iter(), other.iter())
1485     }
1486 }
1487
1488 #[stable]
1489 impl<T: PartialOrd> PartialOrd for [T] {
1490     #[inline]
1491     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1492         order::partial_cmp(self.iter(), other.iter())
1493     }
1494     #[inline]
1495     fn lt(&self, other: &[T]) -> bool {
1496         order::lt(self.iter(), other.iter())
1497     }
1498     #[inline]
1499     fn le(&self, other: &[T]) -> bool {
1500         order::le(self.iter(), other.iter())
1501     }
1502     #[inline]
1503     fn ge(&self, other: &[T]) -> bool {
1504         order::ge(self.iter(), other.iter())
1505     }
1506     #[inline]
1507     fn gt(&self, other: &[T]) -> bool {
1508         order::gt(self.iter(), other.iter())
1509     }
1510 }
1511
1512 /// Extension methods for slices containing integers.
1513 #[experimental]
1514 pub trait IntSliceExt<U, S> for Sized? {
1515     /// Converts the slice to an immutable slice of unsigned integers with the same width.
1516     fn as_unsigned<'a>(&'a self) -> &'a [U];
1517     /// Converts the slice to an immutable slice of signed integers with the same width.
1518     fn as_signed<'a>(&'a self) -> &'a [S];
1519
1520     /// Converts the slice to a mutable slice of unsigned integers with the same width.
1521     fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1522     /// Converts the slice to a mutable slice of signed integers with the same width.
1523     fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1524 }
1525
1526 macro_rules! impl_int_slice {
1527     ($u:ty, $s:ty, $t:ty) => {
1528         #[experimental]
1529         impl IntSliceExt<$u, $s> for [$t] {
1530             #[inline]
1531             fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1532             #[inline]
1533             fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1534             #[inline]
1535             fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1536             #[inline]
1537             fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1538         }
1539     }
1540 }
1541
1542 macro_rules! impl_int_slices {
1543     ($u:ty, $s:ty) => {
1544         impl_int_slice! { $u, $s, $u }
1545         impl_int_slice! { $u, $s, $s }
1546     }
1547 }
1548
1549 impl_int_slices! { u8,   i8  }
1550 impl_int_slices! { u16,  i16 }
1551 impl_int_slices! { u32,  i32 }
1552 impl_int_slices! { u64,  i64 }
1553 impl_int_slices! { uint, int }