src/libcore/slice.rs

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