src/libcore/slice.rs

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