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