src/libcore/slice.rs

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