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