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