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 num::Int;
  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::{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<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<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<RangeFull> for [T] {
 588     type Output = [T];
 589     #[inline]
 590     fn index_mut(&mut self, _index: &RangeFull) -> &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 impl<'a, T> IntoIterator for &'a [T] {
 637     type Iter = Iter<'a, T>;
 638
 639     fn into_iter(self) -> Iter<'a, T> {
 640         self.iter()
 641     }
 642 }
 643
 644 impl<'a, T> IntoIterator for &'a mut [T] {
 645     type Iter = 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                     if self.ptr == self.end {
 664                         None
 665                     } else {
 666                         if mem::size_of::<T>() == 0 {
 667                             // purposefully don't use 'ptr.offset' because for
 668                             // vectors with 0-size elements this would return the
 669                             // same pointer.
 670                             self.ptr = transmute(self.ptr as uint + 1);
 671
 672                             // Use a non-null pointer value
 673                             Some(&mut *(1 as *mut _))
 674                         } else {
 675                             let old = self.ptr;
 676                             self.ptr = self.ptr.offset(1);
 677
 678                             Some(transmute(old))
 679                         }
 680                     }
 681                 }
 682             }
 683
 684             #[inline]
 685             fn size_hint(&self) -> (uint, Option<uint>) {
 686                 let diff = (self.end as uint) - (self.ptr as uint);
 687                 let size = mem::size_of::<T>();
 688                 let exact = diff / (if size == 0 {1} else {size});
 689                 (exact, Some(exact))
 690             }
 691         }
 692
 693         #[stable(feature = "rust1", since = "1.0.0")]
 694         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
 695             #[inline]
 696             fn next_back(&mut self) -> Option<$elem> {
 697                 // could be implemented with slices, but this avoids bounds checks
 698                 unsafe {
 699                     if self.end == self.ptr {
 700                         None
 701                     } else {
 702                         if mem::size_of::<T>() == 0 {
 703                             // See above for why 'ptr.offset' isn't used
 704                             self.end = transmute(self.end as uint - 1);
 705
 706                             // Use a non-null pointer value
 707                             Some(&mut *(1 as *mut _))
 708                         } else {
 709                             self.end = self.end.offset(-1);
 710
 711                             Some(transmute(self.end))
 712                         }
 713                     }
 714                 }
 715             }
 716         }
 717     }
 718 }
 719
 720 macro_rules! make_slice {
 721     ($t: ty => $result: ty: $start: expr, $end: expr) => {{
 722         let diff = $end as uint - $start as uint;
 723         let len = if mem::size_of::<T>() == 0 {
 724             diff
 725         } else {
 726             diff / mem::size_of::<$t>()
 727         };
 728         unsafe {
 729             transmute::<_, $result>(RawSlice { data: $start, len: len })
 730         }
 731     }}
 732 }
 733
 734 /// Immutable slice iterator
 735 #[stable(feature = "rust1", since = "1.0.0")]
 736 pub struct Iter<'a, T: 'a> {
 737     ptr: *const T,
 738     end: *const T,
 739     marker: marker::ContravariantLifetime<'a>
 740 }
 741
 742 #[unstable(feature = "core")]
 743 impl<'a, T> ops::Index<ops::Range<uint>> for Iter<'a, T> {
 744     type Output = [T];
 745     #[inline]
 746     fn index(&self, index: &ops::Range<uint>) -> &[T] {
 747         self.as_slice().index(index)
 748     }
 749 }
 750
 751 #[unstable(feature = "core")]
 752 impl<'a, T> ops::Index<ops::RangeTo<uint>> for Iter<'a, T> {
 753     type Output = [T];
 754     #[inline]
 755     fn index(&self, index: &ops::RangeTo<uint>) -> &[T] {
 756         self.as_slice().index(index)
 757     }
 758 }
 759
 760 #[unstable(feature = "core")]
 761 impl<'a, T> ops::Index<ops::RangeFrom<uint>> for Iter<'a, T> {
 762     type Output = [T];
 763     #[inline]
 764     fn index(&self, index: &ops::RangeFrom<uint>) -> &[T] {
 765         self.as_slice().index(index)
 766     }
 767 }
 768
 769 #[unstable(feature = "core")]
 770 impl<'a, T> ops::Index<RangeFull> for Iter<'a, T> {
 771     type Output = [T];
 772     #[inline]
 773     fn index(&self, _index: &RangeFull) -> &[T] {
 774         self.as_slice()
 775     }
 776 }
 777
 778 impl<'a, T> Iter<'a, T> {
 779     /// View the underlying data as a subslice of the original data.
 780     ///
 781     /// This has the same lifetime as the original slice, and so the
 782     /// iterator can continue to be used while this exists.
 783     #[unstable(feature = "core")]
 784     pub fn as_slice(&self) -> &'a [T] {
 785         make_slice!(T => &'a [T]: self.ptr, self.end)
 786     }
 787 }
 788
 789 iterator!{struct Iter -> *const T, &'a T}
 790
 791 #[stable(feature = "rust1", since = "1.0.0")]
 792 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
 793
 794 #[stable(feature = "rust1", since = "1.0.0")]
 795 impl<'a, T> Clone for Iter<'a, T> {
 796     fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, marker: self.marker } }
 797 }
 798
 799 #[unstable(feature = "core", reason = "trait is experimental")]
 800 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
 801     #[inline]
 802     fn indexable(&self) -> uint {
 803         let (exact, _) = self.size_hint();
 804         exact
 805     }
 806
 807     #[inline]
 808     fn idx(&mut self, index: uint) -> Option<&'a T> {
 809         unsafe {
 810             if index < self.indexable() {
 811                 if mem::size_of::<T>() == 0 {
 812                     // Use a non-null pointer value
 813                     Some(&mut *(1 as *mut _))
 814                 } else {
 815                     Some(transmute(self.ptr.offset(index as int)))
 816                 }
 817             } else {
 818                 None
 819             }
 820         }
 821     }
 822 }
 823
 824 /// Mutable slice iterator.
 825 #[stable(feature = "rust1", since = "1.0.0")]
 826 pub struct IterMut<'a, T: 'a> {
 827     ptr: *mut T,
 828     end: *mut T,
 829     marker: marker::ContravariantLifetime<'a>,
 830 }
 831
 832
 833 #[unstable(feature = "core")]
 834 impl<'a, T> ops::Index<ops::Range<uint>> for IterMut<'a, T> {
 835     type Output = [T];
 836     #[inline]
 837     fn index(&self, index: &ops::Range<uint>) -> &[T] {
 838         self.index(&RangeFull).index(index)
 839     }
 840 }
 841 #[unstable(feature = "core")]
 842 impl<'a, T> ops::Index<ops::RangeTo<uint>> for IterMut<'a, T> {
 843     type Output = [T];
 844     #[inline]
 845     fn index(&self, index: &ops::RangeTo<uint>) -> &[T] {
 846         self.index(&RangeFull).index(index)
 847     }
 848 }
 849 #[unstable(feature = "core")]
 850 impl<'a, T> ops::Index<ops::RangeFrom<uint>> for IterMut<'a, T> {
 851     type Output = [T];
 852     #[inline]
 853     fn index(&self, index: &ops::RangeFrom<uint>) -> &[T] {
 854         self.index(&RangeFull).index(index)
 855     }
 856 }
 857 #[unstable(feature = "core")]
 858 impl<'a, T> ops::Index<RangeFull> for IterMut<'a, T> {
 859     type Output = [T];
 860     #[inline]
 861     fn index(&self, _index: &RangeFull) -> &[T] {
 862         make_slice!(T => &[T]: self.ptr, self.end)
 863     }
 864 }
 865
 866 #[unstable(feature = "core")]
 867 impl<'a, T> ops::IndexMut<ops::Range<uint>> for IterMut<'a, T> {
 868     type Output = [T];
 869     #[inline]
 870     fn index_mut(&mut self, index: &ops::Range<uint>) -> &mut [T] {
 871         self.index_mut(&RangeFull).index_mut(index)
 872     }
 873 }
 874 #[unstable(feature = "core")]
 875 impl<'a, T> ops::IndexMut<ops::RangeTo<uint>> for IterMut<'a, T> {
 876     type Output = [T];
 877     #[inline]
 878     fn index_mut(&mut self, index: &ops::RangeTo<uint>) -> &mut [T] {
 879         self.index_mut(&RangeFull).index_mut(index)
 880     }
 881 }
 882 #[unstable(feature = "core")]
 883 impl<'a, T> ops::IndexMut<ops::RangeFrom<uint>> for IterMut<'a, T> {
 884     type Output = [T];
 885     #[inline]
 886     fn index_mut(&mut self, index: &ops::RangeFrom<uint>) -> &mut [T] {
 887         self.index_mut(&RangeFull).index_mut(index)
 888     }
 889 }
 890 #[unstable(feature = "core")]
 891 impl<'a, T> ops::IndexMut<RangeFull> for IterMut<'a, T> {
 892     type Output = [T];
 893     #[inline]
 894     fn index_mut(&mut self, _index: &RangeFull) -> &mut [T] {
 895         make_slice!(T => &mut [T]: self.ptr, self.end)
 896     }
 897 }
 898
 899
 900 impl<'a, T> IterMut<'a, T> {
 901     /// View the underlying data as a subslice of the original data.
 902     ///
 903     /// To avoid creating `&mut` references that alias, this is forced
 904     /// to consume the iterator. Consider using the `Slice` and
 905     /// `SliceMut` implementations for obtaining slices with more
 906     /// restricted lifetimes that do not consume the iterator.
 907     #[unstable(feature = "core")]
 908     pub fn into_slice(self) -> &'a mut [T] {
 909         make_slice!(T => &'a mut [T]: self.ptr, self.end)
 910     }
 911 }
 912
 913 iterator!{struct IterMut -> *mut T, &'a mut T}
 914
 915 #[stable(feature = "rust1", since = "1.0.0")]
 916 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
 917
 918 /// An internal abstraction over the splitting iterators, so that
 919 /// splitn, splitn_mut etc can be implemented once.
 920 trait SplitIter: DoubleEndedIterator {
 921     /// Mark the underlying iterator as complete, extracting the remaining
 922     /// portion of the slice.
 923     fn finish(&mut self) -> Option<Self::Item>;
 924 }
 925
 926 /// An iterator over subslices separated by elements that match a predicate
 927 /// function.
 928 #[stable(feature = "rust1", since = "1.0.0")]
 929 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
 930     v: &'a [T],
 931     pred: P,
 932     finished: bool
 933 }
 934
 935 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 936 #[stable(feature = "rust1", since = "1.0.0")]
 937 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
 938     fn clone(&self) -> Split<'a, T, P> {
 939         Split {
 940             v: self.v,
 941             pred: self.pred.clone(),
 942             finished: self.finished,
 943         }
 944     }
 945 }
 946
 947 #[stable(feature = "rust1", since = "1.0.0")]
 948 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
 949     type Item = &'a [T];
 950
 951     #[inline]
 952     fn next(&mut self) -> Option<&'a [T]> {
 953         if self.finished { return None; }
 954
 955         match self.v.iter().position(|x| (self.pred)(x)) {
 956             None => self.finish(),
 957             Some(idx) => {
 958                 let ret = Some(&self.v[..idx]);
 959                 self.v = &self.v[idx + 1..];
 960                 ret
 961             }
 962         }
 963     }
 964
 965     #[inline]
 966     fn size_hint(&self) -> (uint, Option<uint>) {
 967         if self.finished {
 968             (0, Some(0))
 969         } else {
 970             (1, Some(self.v.len() + 1))
 971         }
 972     }
 973 }
 974
 975 #[stable(feature = "rust1", since = "1.0.0")]
 976 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
 977     #[inline]
 978     fn next_back(&mut self) -> Option<&'a [T]> {
 979         if self.finished { return None; }
 980
 981         match self.v.iter().rposition(|x| (self.pred)(x)) {
 982             None => self.finish(),
 983             Some(idx) => {
 984                 let ret = Some(&self.v[idx + 1..]);
 985                 self.v = &self.v[..idx];
 986                 ret
 987             }
 988         }
 989     }
 990 }
 991
 992 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
 993     #[inline]
 994     fn finish(&mut self) -> Option<&'a [T]> {
 995         if self.finished { None } else { self.finished = true; Some(self.v) }
 996     }
 997 }
 998
 999 /// An iterator over the subslices of the vector which are separated
1000 /// by elements that match `pred`.
1001 #[stable(feature = "rust1", since = "1.0.0")]
1002 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
1003     v: &'a mut [T],
1004     pred: P,
1005     finished: bool
1006 }
1007
1008 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1009     #[inline]
1010     fn finish(&mut self) -> Option<&'a mut [T]> {
1011         if self.finished {
1012             None
1013         } else {
1014             self.finished = true;
1015             Some(mem::replace(&mut self.v, &mut []))
1016         }
1017     }
1018 }
1019
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1022     type Item = &'a mut [T];
1023
1024     #[inline]
1025     fn next(&mut self) -> Option<&'a mut [T]> {
1026         if self.finished { return None; }
1027
1028         let idx_opt = { // work around borrowck limitations
1029             let pred = &mut self.pred;
1030             self.v.iter().position(|x| (*pred)(x))
1031         };
1032         match idx_opt {
1033             None => self.finish(),
1034             Some(idx) => {
1035                 let tmp = mem::replace(&mut self.v, &mut []);
1036                 let (head, tail) = tmp.split_at_mut(idx);
1037                 self.v = &mut tail[1..];
1038                 Some(head)
1039             }
1040         }
1041     }
1042
1043     #[inline]
1044     fn size_hint(&self) -> (uint, Option<uint>) {
1045         if self.finished {
1046             (0, Some(0))
1047         } else {
1048             // if the predicate doesn't match anything, we yield one slice
1049             // if it matches every element, we yield len+1 empty slices.
1050             (1, Some(self.v.len() + 1))
1051         }
1052     }
1053 }
1054
1055 #[stable(feature = "rust1", since = "1.0.0")]
1056 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
1057     P: FnMut(&T) -> bool,
1058 {
1059     #[inline]
1060     fn next_back(&mut self) -> Option<&'a mut [T]> {
1061         if self.finished { return None; }
1062
1063         let idx_opt = { // work around borrowck limitations
1064             let pred = &mut self.pred;
1065             self.v.iter().rposition(|x| (*pred)(x))
1066         };
1067         match idx_opt {
1068             None => self.finish(),
1069             Some(idx) => {
1070                 let tmp = mem::replace(&mut self.v, &mut []);
1071                 let (head, tail) = tmp.split_at_mut(idx);
1072                 self.v = head;
1073                 Some(&mut tail[1..])
1074             }
1075         }
1076     }
1077 }
1078
1079 /// An private iterator over subslices separated by elements that
1080 /// match a predicate function, splitting at most a fixed number of
1081 /// times.
1082 struct GenericSplitN<I> {
1083     iter: I,
1084     count: uint,
1085     invert: bool
1086 }
1087
1088 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
1089     type Item = T;
1090
1091     #[inline]
1092     fn next(&mut self) -> Option<T> {
1093         if self.count == 0 {
1094             self.iter.finish()
1095         } else {
1096             self.count -= 1;
1097             if self.invert { self.iter.next_back() } else { self.iter.next() }
1098         }
1099     }
1100
1101     #[inline]
1102     fn size_hint(&self) -> (uint, Option<uint>) {
1103         let (lower, upper_opt) = self.iter.size_hint();
1104         (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper)))
1105     }
1106 }
1107
1108 /// An iterator over subslices separated by elements that match a predicate
1109 /// function, limited to a given number of splits.
1110 #[stable(feature = "rust1", since = "1.0.0")]
1111 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1112     inner: GenericSplitN<Split<'a, T, P>>
1113 }
1114
1115 /// An iterator over subslices separated by elements that match a
1116 /// predicate function, limited to a given number of splits, starting
1117 /// from the end of the slice.
1118 #[stable(feature = "rust1", since = "1.0.0")]
1119 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1120     inner: GenericSplitN<Split<'a, T, P>>
1121 }
1122
1123 /// An iterator over subslices separated by elements that match a predicate
1124 /// function, limited to a given number of splits.
1125 #[stable(feature = "rust1", since = "1.0.0")]
1126 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1127     inner: GenericSplitN<SplitMut<'a, T, P>>
1128 }
1129
1130 /// An iterator over subslices separated by elements that match a
1131 /// predicate function, limited to a given number of splits, starting
1132 /// from the end of the slice.
1133 #[stable(feature = "rust1", since = "1.0.0")]
1134 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1135     inner: GenericSplitN<SplitMut<'a, T, P>>
1136 }
1137
1138 macro_rules! forward_iterator {
1139     ($name:ident: $elem:ident, $iter_of:ty) => {
1140         #[stable(feature = "rust1", since = "1.0.0")]
1141         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
1142             P: FnMut(&T) -> bool
1143         {
1144             type Item = $iter_of;
1145
1146             #[inline]
1147             fn next(&mut self) -> Option<$iter_of> {
1148                 self.inner.next()
1149             }
1150
1151             #[inline]
1152             fn size_hint(&self) -> (uint, Option<uint>) {
1153                 self.inner.size_hint()
1154             }
1155         }
1156     }
1157 }
1158
1159 forward_iterator! { SplitN: T, &'a [T] }
1160 forward_iterator! { RSplitN: T, &'a [T] }
1161 forward_iterator! { SplitNMut: T, &'a mut [T] }
1162 forward_iterator! { RSplitNMut: T, &'a mut [T] }
1163
1164 /// An iterator over overlapping subslices of length `size`.
1165 #[derive(Clone)]
1166 #[stable(feature = "rust1", since = "1.0.0")]
1167 pub struct Windows<'a, T:'a> {
1168     v: &'a [T],
1169     size: uint
1170 }
1171
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 impl<'a, T> Iterator for Windows<'a, T> {
1174     type Item = &'a [T];
1175
1176     #[inline]
1177     fn next(&mut self) -> Option<&'a [T]> {
1178         if self.size > self.v.len() {
1179             None
1180         } else {
1181             let ret = Some(&self.v[..self.size]);
1182             self.v = &self.v[1..];
1183             ret
1184         }
1185     }
1186
1187     #[inline]
1188     fn size_hint(&self) -> (uint, Option<uint>) {
1189         if self.size > self.v.len() {
1190             (0, Some(0))
1191         } else {
1192             let x = self.v.len() - self.size;
1193             (x.saturating_add(1), x.checked_add(1))
1194         }
1195     }
1196 }
1197
1198 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1199 /// time).
1200 ///
1201 /// When the slice len is not evenly divided by the chunk size, the last slice
1202 /// of the iteration will be the remainder.
1203 #[derive(Clone)]
1204 #[stable(feature = "rust1", since = "1.0.0")]
1205 pub struct Chunks<'a, T:'a> {
1206     v: &'a [T],
1207     size: uint
1208 }
1209
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 impl<'a, T> Iterator for Chunks<'a, T> {
1212     type Item = &'a [T];
1213
1214     #[inline]
1215     fn next(&mut self) -> Option<&'a [T]> {
1216         if self.v.len() == 0 {
1217             None
1218         } else {
1219             let chunksz = cmp::min(self.v.len(), self.size);
1220             let (fst, snd) = self.v.split_at(chunksz);
1221             self.v = snd;
1222             Some(fst)
1223         }
1224     }
1225
1226     #[inline]
1227     fn size_hint(&self) -> (uint, Option<uint>) {
1228         if self.v.len() == 0 {
1229             (0, Some(0))
1230         } else {
1231             let n = self.v.len() / self.size;
1232             let rem = self.v.len() % self.size;
1233             let n = if rem > 0 { n+1 } else { n };
1234             (n, Some(n))
1235         }
1236     }
1237 }
1238
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
1241     #[inline]
1242     fn next_back(&mut self) -> Option<&'a [T]> {
1243         if self.v.len() == 0 {
1244             None
1245         } else {
1246             let remainder = self.v.len() % self.size;
1247             let chunksz = if remainder != 0 { remainder } else { self.size };
1248             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1249             self.v = fst;
1250             Some(snd)
1251         }
1252     }
1253 }
1254
1255 #[stable(feature = "rust1", since = "1.0.0")]
1256 impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
1257
1258 #[unstable(feature = "core", reason = "trait is experimental")]
1259 impl<'a, T> RandomAccessIterator for Chunks<'a, T> {
1260     #[inline]
1261     fn indexable(&self) -> uint {
1262         self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1263     }
1264
1265     #[inline]
1266     fn idx(&mut self, index: uint) -> Option<&'a [T]> {
1267         if index < self.indexable() {
1268             let lo = index * self.size;
1269             let mut hi = lo + self.size;
1270             if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1271
1272             Some(&self.v[lo..hi])
1273         } else {
1274             None
1275         }
1276     }
1277 }
1278
1279 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1280 /// elements at a time). When the slice len is not evenly divided by the chunk
1281 /// size, the last slice of the iteration will be the remainder.
1282 #[stable(feature = "rust1", since = "1.0.0")]
1283 pub struct ChunksMut<'a, T:'a> {
1284     v: &'a mut [T],
1285     chunk_size: uint
1286 }
1287
1288 #[stable(feature = "rust1", since = "1.0.0")]
1289 impl<'a, T> Iterator for ChunksMut<'a, T> {
1290     type Item = &'a mut [T];
1291
1292     #[inline]
1293     fn next(&mut self) -> Option<&'a mut [T]> {
1294         if self.v.len() == 0 {
1295             None
1296         } else {
1297             let sz = cmp::min(self.v.len(), self.chunk_size);
1298             let tmp = mem::replace(&mut self.v, &mut []);
1299             let (head, tail) = tmp.split_at_mut(sz);
1300             self.v = tail;
1301             Some(head)
1302         }
1303     }
1304
1305     #[inline]
1306     fn size_hint(&self) -> (uint, Option<uint>) {
1307         if self.v.len() == 0 {
1308             (0, Some(0))
1309         } else {
1310             let n = self.v.len() / self.chunk_size;
1311             let rem = self.v.len() % self.chunk_size;
1312             let n = if rem > 0 { n + 1 } else { n };
1313             (n, Some(n))
1314         }
1315     }
1316 }
1317
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
1320     #[inline]
1321     fn next_back(&mut self) -> Option<&'a mut [T]> {
1322         if self.v.len() == 0 {
1323             None
1324         } else {
1325             let remainder = self.v.len() % self.chunk_size;
1326             let sz = if remainder != 0 { remainder } else { self.chunk_size };
1327             let tmp = mem::replace(&mut self.v, &mut []);
1328             let tmp_len = tmp.len();
1329             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1330             self.v = head;
1331             Some(tail)
1332         }
1333     }
1334 }
1335
1336 #[stable(feature = "rust1", since = "1.0.0")]
1337 impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
1338
1339 //
1340 // Free functions
1341 //
1342
1343 /// Converts a pointer to A into a slice of length 1 (without copying).
1344 #[unstable(feature = "core")]
1345 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1346     unsafe {
1347         transmute(RawSlice { data: s, len: 1 })
1348     }
1349 }
1350
1351 /// Converts a pointer to A into a slice of length 1 (without copying).
1352 #[unstable(feature = "core")]
1353 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1354     unsafe {
1355         let ptr: *const A = transmute(s);
1356         transmute(RawSlice { data: ptr, len: 1 })
1357     }
1358 }
1359
1360 /// Forms a slice from a pointer and a length.
1361 ///
1362 /// The pointer given is actually a reference to the base of the slice. This
1363 /// reference is used to give a concrete lifetime to tie the returned slice to.
1364 /// Typically this should indicate that the slice is valid for as long as the
1365 /// pointer itself is valid.
1366 ///
1367 /// The `len` argument is the number of **elements**, not the number of bytes.
1368 ///
1369 /// This function is unsafe as there is no guarantee that the given pointer is
1370 /// valid for `len` elements, nor whether the lifetime provided is a suitable
1371 /// lifetime for the returned slice.
1372 ///
1373 /// # Example
1374 ///
1375 /// ```rust
1376 /// use std::slice;
1377 ///
1378 /// // manifest a slice out of thin air!
1379 /// let ptr = 0x1234 as *const uint;
1380 /// let amt = 10;
1381 /// unsafe {
1382 ///     let slice = slice::from_raw_buf(&ptr, amt);
1383 /// }
1384 /// ```
1385 #[inline]
1386 #[unstable(feature = "core",
1387            reason = "should be renamed to from_raw_parts")]
1388 pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: uint) -> &'a [T] {
1389     transmute(RawSlice { data: *p, len: len })
1390 }
1391
1392 /// Performs the same functionality as `from_raw_buf`, except that a mutable
1393 /// slice is returned.
1394 ///
1395 /// This function is unsafe for the same reasons as `from_raw_buf`, as well as
1396 /// not being able to provide a non-aliasing guarantee of the returned mutable
1397 /// slice.
1398 #[inline]
1399 #[unstable(feature = "core",
1400            reason = "should be renamed to from_raw_parts_mut")]
1401 pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: uint) -> &'a mut [T] {
1402     transmute(RawSlice { data: *p, len: len })
1403 }
1404
1405 //
1406 // Submodules
1407 //
1408
1409 /// Operations on `[u8]`.
1410 #[unstable(feature = "core", reason = "needs review")]
1411 pub mod bytes {
1412     use ptr;
1413     use slice::SliceExt;
1414
1415     /// A trait for operations on mutable `[u8]`s.
1416     pub trait MutableByteVector {
1417         /// Sets all bytes of the receiver to the given value.
1418         fn set_memory(&mut self, value: u8);
1419     }
1420
1421     impl MutableByteVector for [u8] {
1422         #[inline]
1423         fn set_memory(&mut self, value: u8) {
1424             unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1425         }
1426     }
1427
1428     /// Copies data from `src` to `dst`
1429     ///
1430     /// Panics if the length of `dst` is less than the length of `src`.
1431     #[inline]
1432     pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1433         let len_src = src.len();
1434         assert!(dst.len() >= len_src);
1435         // `dst` is unaliasable, so we know statically it doesn't overlap
1436         // with `src`.
1437         unsafe {
1438             ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(),
1439                                             src.as_ptr(),
1440                                             len_src);
1441         }
1442     }
1443 }
1444
1445
1446
1447 //
1448 // Boilerplate traits
1449 //
1450
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1453     fn eq(&self, other: &[B]) -> bool {
1454         self.len() == other.len() &&
1455             order::eq(self.iter(), other.iter())
1456     }
1457     fn ne(&self, other: &[B]) -> bool {
1458         self.len() != other.len() ||
1459             order::ne(self.iter(), other.iter())
1460     }
1461 }
1462
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<T: Eq> Eq for [T] {}
1465
1466 #[stable(feature = "rust1", since = "1.0.0")]
1467 impl<T: Ord> Ord for [T] {
1468     fn cmp(&self, other: &[T]) -> Ordering {
1469         order::cmp(self.iter(), other.iter())
1470     }
1471 }
1472
1473 #[stable(feature = "rust1", since = "1.0.0")]
1474 impl<T: PartialOrd> PartialOrd for [T] {
1475     #[inline]
1476     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1477         order::partial_cmp(self.iter(), other.iter())
1478     }
1479     #[inline]
1480     fn lt(&self, other: &[T]) -> bool {
1481         order::lt(self.iter(), other.iter())
1482     }
1483     #[inline]
1484     fn le(&self, other: &[T]) -> bool {
1485         order::le(self.iter(), other.iter())
1486     }
1487     #[inline]
1488     fn ge(&self, other: &[T]) -> bool {
1489         order::ge(self.iter(), other.iter())
1490     }
1491     #[inline]
1492     fn gt(&self, other: &[T]) -> bool {
1493         order::gt(self.iter(), other.iter())
1494     }
1495 }
1496
1497 /// Extension methods for slices containing integers.
1498 #[unstable(feature = "core")]
1499 pub trait IntSliceExt<U, S> {
1500     /// Converts the slice to an immutable slice of unsigned integers with the same width.
1501     fn as_unsigned<'a>(&'a self) -> &'a [U];
1502     /// Converts the slice to an immutable slice of signed integers with the same width.
1503     fn as_signed<'a>(&'a self) -> &'a [S];
1504
1505     /// Converts the slice to a mutable slice of unsigned integers with the same width.
1506     fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1507     /// Converts the slice to a mutable slice of signed integers with the same width.
1508     fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1509 }
1510
1511 macro_rules! impl_int_slice {
1512     ($u:ty, $s:ty, $t:ty) => {
1513         #[unstable(feature = "core")]
1514         impl IntSliceExt<$u, $s> for [$t] {
1515             #[inline]
1516             fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1517             #[inline]
1518             fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1519             #[inline]
1520             fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1521             #[inline]
1522             fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1523         }
1524     }
1525 }
1526
1527 macro_rules! impl_int_slices {
1528     ($u:ty, $s:ty) => {
1529         impl_int_slice! { $u, $s, $u }
1530         impl_int_slice! { $u, $s, $s }
1531     }
1532 }
1533
1534 impl_int_slices! { u8,   i8  }
1535 impl_int_slices! { u16,  i16 }
1536 impl_int_slices! { u32,  i32 }
1537 impl_int_slices! { u64,  i64 }
1538 impl_int_slices! { uint, int }