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