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 use mem::transmute;
  16 use clone::Clone;
  17 use container::Container;
  18 use cmp::{Eq, TotalOrd, Ordering, Less, Equal, Greater};
  19 use cmp;
  20 use default::Default;
  21 use iter::*;
  22 use num::{CheckedAdd, Saturating, div_rem};
  23 use option::{None, Option, Some};
  24 use ptr;
  25 use ptr::RawPtr;
  26 use mem;
  27 use mem::size_of;
  28 use kinds::marker;
  29 use raw::{Repr, Slice};
  30
  31 /**
  32  * Converts a pointer to A into a slice of length 1 (without copying).
  33  */
  34 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
  35     unsafe {
  36         transmute(Slice { data: s, len: 1 })
  37     }
  38 }
  39
  40 /**
  41  * Converts a pointer to A into a slice of length 1 (without copying).
  42  */
  43 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
  44     unsafe {
  45         let ptr: *A = transmute(s);
  46         transmute(Slice { data: ptr, len: 1 })
  47     }
  48 }
  49
  50 /// An iterator over the slices of a vector separated by elements that
  51 /// match a predicate function.
  52 pub struct Splits<'a, T> {
  53     v: &'a [T],
  54     pred: |t: &T|: 'a -> bool,
  55     finished: bool
  56 }
  57
  58 impl<'a, T> Iterator<&'a [T]> for Splits<'a, T> {
  59     #[inline]
  60     fn next(&mut self) -> Option<&'a [T]> {
  61         if self.finished { return None; }
  62
  63         match self.v.iter().position(|x| (self.pred)(x)) {
  64             None => {
  65                 self.finished = true;
  66                 Some(self.v)
  67             }
  68             Some(idx) => {
  69                 let ret = Some(self.v.slice(0, idx));
  70                 self.v = self.v.slice(idx + 1, self.v.len());
  71                 ret
  72             }
  73         }
  74     }
  75
  76     #[inline]
  77     fn size_hint(&self) -> (uint, Option<uint>) {
  78         if self.finished {
  79             (0, Some(0))
  80         } else {
  81             (1, Some(self.v.len() + 1))
  82         }
  83     }
  84 }
  85
  86 impl<'a, T> DoubleEndedIterator<&'a [T]> for Splits<'a, T> {
  87     #[inline]
  88     fn next_back(&mut self) -> Option<&'a [T]> {
  89         if self.finished { return None; }
  90
  91         match self.v.iter().rposition(|x| (self.pred)(x)) {
  92             None => {
  93                 self.finished = true;
  94                 Some(self.v)
  95             }
  96             Some(idx) => {
  97                 let ret = Some(self.v.slice(idx + 1, self.v.len()));
  98                 self.v = self.v.slice(0, idx);
  99                 ret
 100             }
 101         }
 102     }
 103 }
 104
 105 /// An iterator over the slices of a vector separated by elements that
 106 /// match a predicate function, splitting at most a fixed number of times.
 107 pub struct SplitsN<'a, T> {
 108     iter: Splits<'a, T>,
 109     count: uint,
 110     invert: bool
 111 }
 112
 113 impl<'a, T> Iterator<&'a [T]> for SplitsN<'a, T> {
 114     #[inline]
 115     fn next(&mut self) -> Option<&'a [T]> {
 116         if self.count == 0 {
 117             if self.iter.finished {
 118                 None
 119             } else {
 120                 self.iter.finished = true;
 121                 Some(self.iter.v)
 122             }
 123         } else {
 124             self.count -= 1;
 125             if self.invert { self.iter.next_back() } else { self.iter.next() }
 126         }
 127     }
 128
 129     #[inline]
 130     fn size_hint(&self) -> (uint, Option<uint>) {
 131         if self.iter.finished {
 132             (0, Some(0))
 133         } else {
 134             (1, Some(cmp::min(self.count, self.iter.v.len()) + 1))
 135         }
 136     }
 137 }
 138
 139 // Functional utilities
 140
 141 /// An iterator over the (overlapping) slices of length `size` within
 142 /// a vector.
 143 #[deriving(Clone)]
 144 pub struct Windows<'a, T> {
 145     v: &'a [T],
 146     size: uint
 147 }
 148
 149 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
 150     #[inline]
 151     fn next(&mut self) -> Option<&'a [T]> {
 152         if self.size > self.v.len() {
 153             None
 154         } else {
 155             let ret = Some(self.v.slice(0, self.size));
 156             self.v = self.v.slice(1, self.v.len());
 157             ret
 158         }
 159     }
 160
 161     #[inline]
 162     fn size_hint(&self) -> (uint, Option<uint>) {
 163         if self.size > self.v.len() {
 164             (0, Some(0))
 165         } else {
 166             let x = self.v.len() - self.size;
 167             (x.saturating_add(1), x.checked_add(&1u))
 168         }
 169     }
 170 }
 171
 172 /// An iterator over a vector in (non-overlapping) chunks (`size`
 173 /// elements at a time).
 174 ///
 175 /// When the vector len is not evenly divided by the chunk size,
 176 /// the last slice of the iteration will be the remainder.
 177 #[deriving(Clone)]
 178 pub struct Chunks<'a, T> {
 179     v: &'a [T],
 180     size: uint
 181 }
 182
 183 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
 184     #[inline]
 185     fn next(&mut self) -> Option<&'a [T]> {
 186         if self.v.len() == 0 {
 187             None
 188         } else {
 189             let chunksz = cmp::min(self.v.len(), self.size);
 190             let (fst, snd) = (self.v.slice_to(chunksz),
 191                               self.v.slice_from(chunksz));
 192             self.v = snd;
 193             Some(fst)
 194         }
 195     }
 196
 197     #[inline]
 198     fn size_hint(&self) -> (uint, Option<uint>) {
 199         if self.v.len() == 0 {
 200             (0, Some(0))
 201         } else {
 202             let (n, rem) = div_rem(self.v.len(), self.size);
 203             let n = if rem > 0 { n+1 } else { n };
 204             (n, Some(n))
 205         }
 206     }
 207 }
 208
 209 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
 210     #[inline]
 211     fn next_back(&mut self) -> Option<&'a [T]> {
 212         if self.v.len() == 0 {
 213             None
 214         } else {
 215             let remainder = self.v.len() % self.size;
 216             let chunksz = if remainder != 0 { remainder } else { self.size };
 217             let (fst, snd) = (self.v.slice_to(self.v.len() - chunksz),
 218                               self.v.slice_from(self.v.len() - chunksz));
 219             self.v = fst;
 220             Some(snd)
 221         }
 222     }
 223 }
 224
 225 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
 226     #[inline]
 227     fn indexable(&self) -> uint {
 228         self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
 229     }
 230
 231     #[inline]
 232     fn idx(&mut self, index: uint) -> Option<&'a [T]> {
 233         if index < self.indexable() {
 234             let lo = index * self.size;
 235             let mut hi = lo + self.size;
 236             if hi < lo || hi > self.v.len() { hi = self.v.len(); }
 237
 238             Some(self.v.slice(lo, hi))
 239         } else {
 240             None
 241         }
 242     }
 243 }
 244
 245 // Equality
 246
 247 #[cfg(not(test))]
 248 #[allow(missing_doc)]
 249 pub mod traits {
 250     use super::*;
 251
 252     use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equiv};
 253     use iter::{order, Iterator};
 254     use container::Container;
 255
 256     impl<'a,T:Eq> Eq for &'a [T] {
 257         fn eq(&self, other: & &'a [T]) -> bool {
 258             self.len() == other.len() &&
 259                 order::eq(self.iter(), other.iter())
 260         }
 261         fn ne(&self, other: & &'a [T]) -> bool {
 262             self.len() != other.len() ||
 263                 order::ne(self.iter(), other.iter())
 264         }
 265     }
 266
 267     impl<T:Eq> Eq for ~[T] {
 268         #[inline]
 269         fn eq(&self, other: &~[T]) -> bool { self.as_slice() == *other }
 270         #[inline]
 271         fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
 272     }
 273
 274     impl<'a,T:TotalEq> TotalEq for &'a [T] {}
 275
 276     impl<T:TotalEq> TotalEq for ~[T] {}
 277
 278     impl<'a,T:Eq, V: Vector<T>> Equiv<V> for &'a [T] {
 279         #[inline]
 280         fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 281     }
 282
 283     impl<'a,T:Eq, V: Vector<T>> Equiv<V> for ~[T] {
 284         #[inline]
 285         fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 286     }
 287
 288     impl<'a,T:TotalOrd> TotalOrd for &'a [T] {
 289         fn cmp(&self, other: & &'a [T]) -> Ordering {
 290             order::cmp(self.iter(), other.iter())
 291         }
 292     }
 293
 294     impl<T: TotalOrd> TotalOrd for ~[T] {
 295         #[inline]
 296         fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
 297     }
 298
 299     impl<'a, T: Ord> Ord for &'a [T] {
 300         fn lt(&self, other: & &'a [T]) -> bool {
 301             order::lt(self.iter(), other.iter())
 302         }
 303         #[inline]
 304         fn le(&self, other: & &'a [T]) -> bool {
 305             order::le(self.iter(), other.iter())
 306         }
 307         #[inline]
 308         fn ge(&self, other: & &'a [T]) -> bool {
 309             order::ge(self.iter(), other.iter())
 310         }
 311         #[inline]
 312         fn gt(&self, other: & &'a [T]) -> bool {
 313             order::gt(self.iter(), other.iter())
 314         }
 315     }
 316
 317     impl<T: Ord> Ord for ~[T] {
 318         #[inline]
 319         fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
 320         #[inline]
 321         fn le(&self, other: &~[T]) -> bool { self.as_slice() <= other.as_slice() }
 322         #[inline]
 323         fn ge(&self, other: &~[T]) -> bool { self.as_slice() >= other.as_slice() }
 324         #[inline]
 325         fn gt(&self, other: &~[T]) -> bool { self.as_slice() > other.as_slice() }
 326     }
 327 }
 328
 329 #[cfg(test)]
 330 pub mod traits {}
 331
 332 /// Any vector that can be represented as a slice.
 333 pub trait Vector<T> {
 334     /// Work with `self` as a slice.
 335     fn as_slice<'a>(&'a self) -> &'a [T];
 336 }
 337
 338 impl<'a,T> Vector<T> for &'a [T] {
 339     #[inline(always)]
 340     fn as_slice<'a>(&'a self) -> &'a [T] { *self }
 341 }
 342
 343 impl<T> Vector<T> for ~[T] {
 344     #[inline(always)]
 345     fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
 346 }
 347
 348 impl<'a, T> Container for &'a [T] {
 349     /// Returns the length of a vector
 350     #[inline]
 351     fn len(&self) -> uint {
 352         self.repr().len
 353     }
 354 }
 355
 356 impl<T> Container for ~[T] {
 357     /// Returns the length of a vector
 358     #[inline]
 359     fn len(&self) -> uint {
 360         self.as_slice().len()
 361     }
 362 }
 363
 364 /// Extension methods for vectors
 365 pub trait ImmutableVector<'a, T> {
 366     /**
 367      * Returns a slice of self between `start` and `end`.
 368      *
 369      * Fails when `start` or `end` point outside the bounds of self,
 370      * or when `start` > `end`.
 371      */
 372     fn slice(&self, start: uint, end: uint) -> &'a [T];
 373
 374     /**
 375      * Returns a slice of self from `start` to the end of the vec.
 376      *
 377      * Fails when `start` points outside the bounds of self.
 378      */
 379     fn slice_from(&self, start: uint) -> &'a [T];
 380
 381     /**
 382      * Returns a slice of self from the start of the vec to `end`.
 383      *
 384      * Fails when `end` points outside the bounds of self.
 385      */
 386     fn slice_to(&self, end: uint) -> &'a [T];
 387     /// Returns an iterator over the vector
 388     fn iter(self) -> Items<'a, T>;
 389     /// Returns an iterator over the subslices of the vector which are
 390     /// separated by elements that match `pred`.  The matched element
 391     /// is not contained in the subslices.
 392     fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
 393     /// Returns an iterator over the subslices of the vector which are
 394     /// separated by elements that match `pred`, limited to splitting
 395     /// at most `n` times.  The matched element is not contained in
 396     /// the subslices.
 397     fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<'a, T>;
 398     /// Returns an iterator over the subslices of the vector which are
 399     /// separated by elements that match `pred` limited to splitting
 400     /// at most `n` times. This starts at the end of the vector and
 401     /// works backwards.  The matched element is not contained in the
 402     /// subslices.
 403     fn rsplitn(self,  n: uint, pred: |&T|: 'a -> bool) -> SplitsN<'a, T>;
 404
 405     /**
 406      * Returns an iterator over all contiguous windows of length
 407      * `size`. The windows overlap. If the vector is shorter than
 408      * `size`, the iterator returns no values.
 409      *
 410      * # Failure
 411      *
 412      * Fails if `size` is 0.
 413      *
 414      * # Example
 415      *
 416      * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`,
 417      * `[3,4]`):
 418      *
 419      * ```rust
 420      * let v = &[1,2,3,4];
 421      * for win in v.windows(2) {
 422      *     println!("{:?}", win);
 423      * }
 424      * ```
 425      *
 426      */
 427     fn windows(self, size: uint) -> Windows<'a, T>;
 428     /**
 429      *
 430      * Returns an iterator over `size` elements of the vector at a
 431      * time. The chunks do not overlap. If `size` does not divide the
 432      * length of the vector, then the last chunk will not have length
 433      * `size`.
 434      *
 435      * # Failure
 436      *
 437      * Fails if `size` is 0.
 438      *
 439      * # Example
 440      *
 441      * Print the vector two elements at a time (i.e. `[1,2]`,
 442      * `[3,4]`, `[5]`):
 443      *
 444      * ```rust
 445      * let v = &[1,2,3,4,5];
 446      * for win in v.chunks(2) {
 447      *     println!("{:?}", win);
 448      * }
 449      * ```
 450      *
 451      */
 452     fn chunks(self, size: uint) -> Chunks<'a, T>;
 453
 454     /// Returns the element of a vector at the given index, or `None` if the
 455     /// index is out of bounds
 456     fn get(&self, index: uint) -> Option<&'a T>;
 457     /// Returns the first element of a vector, or `None` if it is empty
 458     fn head(&self) -> Option<&'a T>;
 459     /// Returns all but the first element of a vector
 460     fn tail(&self) -> &'a [T];
 461     /// Returns all but the first `n' elements of a vector
 462     fn tailn(&self, n: uint) -> &'a [T];
 463     /// Returns all but the last element of a vector
 464     fn init(&self) -> &'a [T];
 465     /// Returns all but the last `n' elements of a vector
 466     fn initn(&self, n: uint) -> &'a [T];
 467     /// Returns the last element of a vector, or `None` if it is empty.
 468     fn last(&self) -> Option<&'a T>;
 469
 470     /// Returns a pointer to the element at the given index, without doing
 471     /// bounds checking.
 472     unsafe fn unsafe_ref(self, index: uint) -> &'a T;
 473
 474     /**
 475      * Returns an unsafe pointer to the vector's buffer
 476      *
 477      * The caller must ensure that the vector outlives the pointer this
 478      * function returns, or else it will end up pointing to garbage.
 479      *
 480      * Modifying the vector may cause its buffer to be reallocated, which
 481      * would also make any pointers to it invalid.
 482      */
 483     fn as_ptr(&self) -> *T;
 484
 485     /**
 486      * Binary search a sorted vector with a comparator function.
 487      *
 488      * The comparator function should implement an order consistent
 489      * with the sort order of the underlying vector, returning an
 490      * order code that indicates whether its argument is `Less`,
 491      * `Equal` or `Greater` the desired target.
 492      *
 493      * Returns the index where the comparator returned `Equal`, or `None` if
 494      * not found.
 495      */
 496     fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint>;
 497
 498     /**
 499      * Returns an immutable reference to the first element in this slice
 500      * and adjusts the slice in place so that it no longer contains
 501      * that element. O(1).
 502      *
 503      * Equivalent to:
 504      *
 505      * ```ignore
 506      *     if self.len() == 0 { return None }
 507      *     let head = &self[0];
 508      *     *self = self.slice_from(1);
 509      *     Some(head)
 510      * ```
 511      *
 512      * Returns `None` if vector is empty
 513      */
 514     fn shift_ref(&mut self) -> Option<&'a T>;
 515
 516     /**
 517      * Returns an immutable reference to the last element in this slice
 518      * and adjusts the slice in place so that it no longer contains
 519      * that element. O(1).
 520      *
 521      * Equivalent to:
 522      *
 523      * ```ignore
 524      *     if self.len() == 0 { return None; }
 525      *     let tail = &self[self.len() - 1];
 526      *     *self = self.slice_to(self.len() - 1);
 527      *     Some(tail)
 528      * ```
 529      *
 530      * Returns `None` if slice is empty.
 531      */
 532     fn pop_ref(&mut self) -> Option<&'a T>;
 533 }
 534
 535 impl<'a,T> ImmutableVector<'a, T> for &'a [T] {
 536     #[inline]
 537     fn slice(&self, start: uint, end: uint) -> &'a [T] {
 538         assert!(start <= end);
 539         assert!(end <= self.len());
 540         unsafe {
 541             transmute(Slice {
 542                     data: self.as_ptr().offset(start as int),
 543                     len: (end - start)
 544                 })
 545         }
 546     }
 547
 548     #[inline]
 549     fn slice_from(&self, start: uint) -> &'a [T] {
 550         self.slice(start, self.len())
 551     }
 552
 553     #[inline]
 554     fn slice_to(&self, end: uint) -> &'a [T] {
 555         self.slice(0, end)
 556     }
 557
 558     #[inline]
 559     fn iter(self) -> Items<'a, T> {
 560         unsafe {
 561             let p = self.as_ptr();
 562             if mem::size_of::<T>() == 0 {
 563                 Items{ptr: p,
 564                       end: (p as uint + self.len()) as *T,
 565                       marker: marker::ContravariantLifetime::<'a>}
 566             } else {
 567                 Items{ptr: p,
 568                       end: p.offset(self.len() as int),
 569                       marker: marker::ContravariantLifetime::<'a>}
 570             }
 571         }
 572     }
 573
 574     #[inline]
 575     fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
 576         Splits {
 577             v: self,
 578             pred: pred,
 579             finished: false
 580         }
 581     }
 582
 583     #[inline]
 584     fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<'a, T> {
 585         SplitsN {
 586             iter: self.split(pred),
 587             count: n,
 588             invert: false
 589         }
 590     }
 591
 592     #[inline]
 593     fn rsplitn(self, n: uint, pred: |&T|: 'a -> bool) -> SplitsN<'a, T> {
 594         SplitsN {
 595             iter: self.split(pred),
 596             count: n,
 597             invert: true
 598         }
 599     }
 600
 601     #[inline]
 602     fn windows(self, size: uint) -> Windows<'a, T> {
 603         assert!(size != 0);
 604         Windows { v: self, size: size }
 605     }
 606
 607     #[inline]
 608     fn chunks(self, size: uint) -> Chunks<'a, T> {
 609         assert!(size != 0);
 610         Chunks { v: self, size: size }
 611     }
 612
 613     #[inline]
 614     fn get(&self, index: uint) -> Option<&'a T> {
 615         if index < self.len() { Some(&self[index]) } else { None }
 616     }
 617
 618     #[inline]
 619     fn head(&self) -> Option<&'a T> {
 620         if self.len() == 0 { None } else { Some(&self[0]) }
 621     }
 622
 623     #[inline]
 624     fn tail(&self) -> &'a [T] { self.slice(1, self.len()) }
 625
 626     #[inline]
 627     fn tailn(&self, n: uint) -> &'a [T] { self.slice(n, self.len()) }
 628
 629     #[inline]
 630     fn init(&self) -> &'a [T] {
 631         self.slice(0, self.len() - 1)
 632     }
 633
 634     #[inline]
 635     fn initn(&self, n: uint) -> &'a [T] {
 636         self.slice(0, self.len() - n)
 637     }
 638
 639     #[inline]
 640     fn last(&self) -> Option<&'a T> {
 641             if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
 642     }
 643
 644     #[inline]
 645     unsafe fn unsafe_ref(self, index: uint) -> &'a T {
 646         transmute(self.repr().data.offset(index as int))
 647     }
 648
 649     #[inline]
 650     fn as_ptr(&self) -> *T {
 651         self.repr().data
 652     }
 653
 654
 655     fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint> {
 656         let mut base : uint = 0;
 657         let mut lim : uint = self.len();
 658
 659         while lim != 0 {
 660             let ix = base + (lim >> 1);
 661             match f(&self[ix]) {
 662                 Equal => return Some(ix),
 663                 Less => {
 664                     base = ix + 1;
 665                     lim -= 1;
 666                 }
 667                 Greater => ()
 668             }
 669             lim >>= 1;
 670         }
 671         return None;
 672     }
 673
 674     fn shift_ref(&mut self) -> Option<&'a T> {
 675         unsafe {
 676             let s: &mut Slice<T> = transmute(self);
 677             match raw::shift_ptr(s) {
 678                 Some(p) => Some(&*p),
 679                 None => None
 680             }
 681         }
 682     }
 683
 684     fn pop_ref(&mut self) -> Option<&'a T> {
 685         unsafe {
 686             let s: &mut Slice<T> = transmute(self);
 687             match raw::pop_ptr(s) {
 688                 Some(p) => Some(&*p),
 689                 None => None
 690             }
 691         }
 692     }
 693 }
 694
 695 /// Extension methods for vectors contain `Eq` elements.
 696 pub trait ImmutableEqVector<T:Eq> {
 697     /// Find the first index containing a matching value
 698     fn position_elem(&self, t: &T) -> Option<uint>;
 699
 700     /// Find the last index containing a matching value
 701     fn rposition_elem(&self, t: &T) -> Option<uint>;
 702
 703     /// Return true if a vector contains an element with the given value
 704     fn contains(&self, x: &T) -> bool;
 705
 706     /// Returns true if `needle` is a prefix of the vector.
 707     fn starts_with(&self, needle: &[T]) -> bool;
 708
 709     /// Returns true if `needle` is a suffix of the vector.
 710     fn ends_with(&self, needle: &[T]) -> bool;
 711 }
 712
 713 impl<'a,T:Eq> ImmutableEqVector<T> for &'a [T] {
 714     #[inline]
 715     fn position_elem(&self, x: &T) -> Option<uint> {
 716         self.iter().position(|y| *x == *y)
 717     }
 718
 719     #[inline]
 720     fn rposition_elem(&self, t: &T) -> Option<uint> {
 721         self.iter().rposition(|x| *x == *t)
 722     }
 723
 724     #[inline]
 725     fn contains(&self, x: &T) -> bool {
 726         self.iter().any(|elt| *x == *elt)
 727     }
 728
 729     #[inline]
 730     fn starts_with(&self, needle: &[T]) -> bool {
 731         let n = needle.len();
 732         self.len() >= n && needle == self.slice_to(n)
 733     }
 734
 735     #[inline]
 736     fn ends_with(&self, needle: &[T]) -> bool {
 737         let (m, n) = (self.len(), needle.len());
 738         m >= n && needle == self.slice_from(m - n)
 739     }
 740 }
 741
 742 /// Extension methods for vectors containing `TotalOrd` elements.
 743 pub trait ImmutableTotalOrdVector<T: TotalOrd> {
 744     /**
 745      * Binary search a sorted vector for a given element.
 746      *
 747      * Returns the index of the element or None if not found.
 748      */
 749     fn bsearch_elem(&self, x: &T) -> Option<uint>;
 750 }
 751
 752 impl<'a, T: TotalOrd> ImmutableTotalOrdVector<T> for &'a [T] {
 753     fn bsearch_elem(&self, x: &T) -> Option<uint> {
 754         self.bsearch(|p| p.cmp(x))
 755     }
 756 }
 757
 758 /// Extension methods for vectors such that their elements are
 759 /// mutable.
 760 pub trait MutableVector<'a, T> {
 761     /// Work with `self` as a mut slice.
 762     /// Primarily intended for getting a &mut [T] from a [T, ..N].
 763     fn as_mut_slice(self) -> &'a mut [T];
 764
 765     /// Return a slice that points into another slice.
 766     fn mut_slice(self, start: uint, end: uint) -> &'a mut [T];
 767
 768     /**
 769      * Returns a slice of self from `start` to the end of the vec.
 770      *
 771      * Fails when `start` points outside the bounds of self.
 772      */
 773     fn mut_slice_from(self, start: uint) -> &'a mut [T];
 774
 775     /**
 776      * Returns a slice of self from the start of the vec to `end`.
 777      *
 778      * Fails when `end` points outside the bounds of self.
 779      */
 780     fn mut_slice_to(self, end: uint) -> &'a mut [T];
 781
 782     /// Returns an iterator that allows modifying each value
 783     fn mut_iter(self) -> MutItems<'a, T>;
 784
 785     /// Returns a mutable pointer to the last item in the vector.
 786     fn mut_last(self) -> Option<&'a mut T>;
 787
 788     /// Returns an iterator over the mutable subslices of the vector
 789     /// which are separated by elements that match `pred`.  The
 790     /// matched element is not contained in the subslices.
 791     fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T>;
 792
 793     /**
 794      * Returns an iterator over `size` elements of the vector at a time.
 795      * The chunks are mutable and do not overlap. If `size` does not divide the
 796      * length of the vector, then the last chunk will not have length
 797      * `size`.
 798      *
 799      * # Failure
 800      *
 801      * Fails if `size` is 0.
 802      */
 803     fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T>;
 804
 805     /**
 806      * Returns a mutable reference to the first element in this slice
 807      * and adjusts the slice in place so that it no longer contains
 808      * that element. O(1).
 809      *
 810      * Equivalent to:
 811      *
 812      * ```ignore
 813      *     if self.len() == 0 { return None; }
 814      *     let head = &mut self[0];
 815      *     *self = self.mut_slice_from(1);
 816      *     Some(head)
 817      * ```
 818      *
 819      * Returns `None` if slice is empty
 820      */
 821     fn mut_shift_ref(&mut self) -> Option<&'a mut T>;
 822
 823     /**
 824      * Returns a mutable reference to the last element in this slice
 825      * and adjusts the slice in place so that it no longer contains
 826      * that element. O(1).
 827      *
 828      * Equivalent to:
 829      *
 830      * ```ignore
 831      *     if self.len() == 0 { return None; }
 832      *     let tail = &mut self[self.len() - 1];
 833      *     *self = self.mut_slice_to(self.len() - 1);
 834      *     Some(tail)
 835      * ```
 836      *
 837      * Returns `None` if slice is empty.
 838      */
 839     fn mut_pop_ref(&mut self) -> Option<&'a mut T>;
 840
 841     /// Swaps two elements in a vector.
 842     ///
 843     /// Fails if `a` or `b` are out of bounds.
 844     ///
 845     /// # Arguments
 846     ///
 847     /// * a - The index of the first element
 848     /// * b - The index of the second element
 849     ///
 850     /// # Example
 851     ///
 852     /// ```rust
 853     /// let mut v = ["a", "b", "c", "d"];
 854     /// v.swap(1, 3);
 855     /// assert!(v == ["a", "d", "c", "b"]);
 856     /// ```
 857     fn swap(self, a: uint, b: uint);
 858
 859
 860     /// Divides one `&mut` into two at an index.
 861     ///
 862     /// The first will contain all indices from `[0, mid)` (excluding
 863     /// the index `mid` itself) and the second will contain all
 864     /// indices from `[mid, len)` (excluding the index `len` itself).
 865     ///
 866     /// Fails if `mid > len`.
 867     ///
 868     /// # Example
 869     ///
 870     /// ```rust
 871     /// let mut v = [1, 2, 3, 4, 5, 6];
 872     ///
 873     /// // scoped to restrict the lifetime of the borrows
 874     /// {
 875     ///    let (left, right) = v.mut_split_at(0);
 876     ///    assert!(left == &mut []);
 877     ///    assert!(right == &mut [1, 2, 3, 4, 5, 6]);
 878     /// }
 879     ///
 880     /// {
 881     ///     let (left, right) = v.mut_split_at(2);
 882     ///     assert!(left == &mut [1, 2]);
 883     ///     assert!(right == &mut [3, 4, 5, 6]);
 884     /// }
 885     ///
 886     /// {
 887     ///     let (left, right) = v.mut_split_at(6);
 888     ///     assert!(left == &mut [1, 2, 3, 4, 5, 6]);
 889     ///     assert!(right == &mut []);
 890     /// }
 891     /// ```
 892     fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]);
 893
 894     /// Reverse the order of elements in a vector, in place.
 895     ///
 896     /// # Example
 897     ///
 898     /// ```rust
 899     /// let mut v = [1, 2, 3];
 900     /// v.reverse();
 901     /// assert!(v == [3, 2, 1]);
 902     /// ```
 903     fn reverse(self);
 904
 905     /// Returns an unsafe mutable pointer to the element in index
 906     unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T;
 907
 908     /// Return an unsafe mutable pointer to the vector's buffer.
 909     ///
 910     /// The caller must ensure that the vector outlives the pointer this
 911     /// function returns, or else it will end up pointing to garbage.
 912     ///
 913     /// Modifying the vector may cause its buffer to be reallocated, which
 914     /// would also make any pointers to it invalid.
 915     #[inline]
 916     fn as_mut_ptr(self) -> *mut T;
 917
 918     /// Unsafely sets the element in index to the value.
 919     ///
 920     /// This performs no bounds checks, and it is undefined behaviour
 921     /// if `index` is larger than the length of `self`. However, it
 922     /// does run the destructor at `index`. It is equivalent to
 923     /// `self[index] = val`.
 924     ///
 925     /// # Example
 926     ///
 927     /// ```rust
 928     /// let mut v = ~["foo".to_owned(), "bar".to_owned(), "baz".to_owned()];
 929     ///
 930     /// unsafe {
 931     ///     // `"baz".to_owned()` is deallocated.
 932     ///     v.unsafe_set(2, "qux".to_owned());
 933     ///
 934     ///     // Out of bounds: could cause a crash, or overwriting
 935     ///     // other data, or something else.
 936     ///     // v.unsafe_set(10, "oops".to_owned());
 937     /// }
 938     /// ```
 939     unsafe fn unsafe_set(self, index: uint, val: T);
 940
 941     /// Unchecked vector index assignment.  Does not drop the
 942     /// old value and hence is only suitable when the vector
 943     /// is newly allocated.
 944     ///
 945     /// # Example
 946     ///
 947     /// ```rust
 948     /// let mut v = ["foo".to_owned(), "bar".to_owned()];
 949     ///
 950     /// // memory leak! `"bar".to_owned()` is not deallocated.
 951     /// unsafe { v.init_elem(1, "baz".to_owned()); }
 952     /// ```
 953     unsafe fn init_elem(self, i: uint, val: T);
 954
 955     /// Copies raw bytes from `src` to `self`.
 956     ///
 957     /// This does not run destructors on the overwritten elements, and
 958     /// ignores move semantics. `self` and `src` must not
 959     /// overlap. Fails if `self` is shorter than `src`.
 960     unsafe fn copy_memory(self, src: &[T]);
 961 }
 962
 963 impl<'a,T> MutableVector<'a, T> for &'a mut [T] {
 964     #[inline]
 965     fn as_mut_slice(self) -> &'a mut [T] { self }
 966
 967     fn mut_slice(self, start: uint, end: uint) -> &'a mut [T] {
 968         assert!(start <= end);
 969         assert!(end <= self.len());
 970         unsafe {
 971             transmute(Slice {
 972                     data: self.as_mut_ptr().offset(start as int) as *T,
 973                     len: (end - start)
 974                 })
 975         }
 976     }
 977
 978     #[inline]
 979     fn mut_slice_from(self, start: uint) -> &'a mut [T] {
 980         let len = self.len();
 981         self.mut_slice(start, len)
 982     }
 983
 984     #[inline]
 985     fn mut_slice_to(self, end: uint) -> &'a mut [T] {
 986         self.mut_slice(0, end)
 987     }
 988
 989     #[inline]
 990     fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
 991         unsafe {
 992             let len = self.len();
 993             let self2: &'a mut [T] = mem::transmute_copy(&self);
 994             (self.mut_slice(0, mid), self2.mut_slice(mid, len))
 995         }
 996     }
 997
 998     #[inline]
 999     fn mut_iter(self) -> MutItems<'a, T> {
1000         unsafe {
1001             let p = self.as_mut_ptr();
1002             if mem::size_of::<T>() == 0 {
1003                 MutItems{ptr: p,
1004                          end: (p as uint + self.len()) as *mut T,
1005                          marker: marker::ContravariantLifetime::<'a>,
1006                          marker2: marker::NoCopy}
1007             } else {
1008                 MutItems{ptr: p,
1009                          end: p.offset(self.len() as int),
1010                          marker: marker::ContravariantLifetime::<'a>,
1011                          marker2: marker::NoCopy}
1012             }
1013         }
1014     }
1015
1016     #[inline]
1017     fn mut_last(self) -> Option<&'a mut T> {
1018         let len = self.len();
1019         if len == 0 { return None; }
1020         Some(&mut self[len - 1])
1021     }
1022
1023     #[inline]
1024     fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T> {
1025         MutSplits { v: self, pred: pred, finished: false }
1026     }
1027
1028     #[inline]
1029     fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T> {
1030         assert!(chunk_size > 0);
1031         MutChunks { v: self, chunk_size: chunk_size }
1032     }
1033
1034     fn mut_shift_ref(&mut self) -> Option<&'a mut T> {
1035         unsafe {
1036             let s: &mut Slice<T> = transmute(self);
1037             match raw::shift_ptr(s) {
1038                 // FIXME #13933: this `&` -> `&mut` cast is a little
1039                 // dubious
1040                 Some(p) => Some(&mut *(p as *mut _)),
1041                 None => None,
1042             }
1043         }
1044     }
1045
1046     fn mut_pop_ref(&mut self) -> Option<&'a mut T> {
1047         unsafe {
1048             let s: &mut Slice<T> = transmute(self);
1049             match raw::pop_ptr(s) {
1050                 // FIXME #13933: this `&` -> `&mut` cast is a little
1051                 // dubious
1052                 Some(p) => Some(&mut *(p as *mut _)),
1053                 None => None,
1054             }
1055         }
1056     }
1057
1058     fn swap(self, a: uint, b: uint) {
1059         unsafe {
1060             // Can't take two mutable loans from one vector, so instead just cast
1061             // them to their raw pointers to do the swap
1062             let pa: *mut T = &mut self[a];
1063             let pb: *mut T = &mut self[b];
1064             ptr::swap(pa, pb);
1065         }
1066     }
1067
1068     fn reverse(self) {
1069         let mut i: uint = 0;
1070         let ln = self.len();
1071         while i < ln / 2 {
1072             self.swap(i, ln - i - 1);
1073             i += 1;
1074         }
1075     }
1076
1077     #[inline]
1078     unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T {
1079         transmute((self.repr().data as *mut T).offset(index as int))
1080     }
1081
1082     #[inline]
1083     fn as_mut_ptr(self) -> *mut T {
1084         self.repr().data as *mut T
1085     }
1086
1087     #[inline]
1088     unsafe fn unsafe_set(self, index: uint, val: T) {
1089         *self.unsafe_mut_ref(index) = val;
1090     }
1091
1092     #[inline]
1093     unsafe fn init_elem(self, i: uint, val: T) {
1094         mem::overwrite(&mut (*self.as_mut_ptr().offset(i as int)), val);
1095     }
1096
1097     #[inline]
1098     unsafe fn copy_memory(self, src: &[T]) {
1099         let len_src = src.len();
1100         assert!(self.len() >= len_src);
1101         ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), src.as_ptr(), len_src)
1102     }
1103 }
1104
1105 /// Trait for &[T] where T is Cloneable
1106 pub trait MutableCloneableVector<T> {
1107     /// Copies as many elements from `src` as it can into `self` (the
1108     /// shorter of `self.len()` and `src.len()`). Returns the number
1109     /// of elements copied.
1110     ///
1111     /// # Example
1112     ///
1113     /// ```rust
1114     /// use std::slice::MutableCloneableVector;
1115     ///
1116     /// let mut dst = [0, 0, 0];
1117     /// let src = [1, 2];
1118     ///
1119     /// assert!(dst.copy_from(src) == 2);
1120     /// assert!(dst == [1, 2, 0]);
1121     ///
1122     /// let src2 = [3, 4, 5, 6];
1123     /// assert!(dst.copy_from(src2) == 3);
1124     /// assert!(dst == [3, 4, 5]);
1125     /// ```
1126     fn copy_from(self, &[T]) -> uint;
1127 }
1128
1129 impl<'a, T:Clone> MutableCloneableVector<T> for &'a mut [T] {
1130     #[inline]
1131     fn copy_from(self, src: &[T]) -> uint {
1132         for (a, b) in self.mut_iter().zip(src.iter()) {
1133             a.clone_from(b);
1134         }
1135         cmp::min(self.len(), src.len())
1136     }
1137 }
1138
1139 /// Unsafe operations
1140 pub mod raw {
1141     use mem::transmute;
1142     use iter::Iterator;
1143     use ptr::RawPtr;
1144     use raw::Slice;
1145     use option::{None, Option, Some};
1146
1147     /**
1148      * Form a slice from a pointer and length (as a number of units,
1149      * not bytes).
1150      */
1151     #[inline]
1152     pub unsafe fn buf_as_slice<T,U>(p: *T, len: uint, f: |v: &[T]| -> U)
1153                                -> U {
1154         f(transmute(Slice {
1155             data: p,
1156             len: len
1157         }))
1158     }
1159
1160     /**
1161      * Form a slice from a pointer and length (as a number of units,
1162      * not bytes).
1163      */
1164     #[inline]
1165     pub unsafe fn mut_buf_as_slice<T,
1166                                    U>(
1167                                    p: *mut T,
1168                                    len: uint,
1169                                    f: |v: &mut [T]| -> U)
1170                                    -> U {
1171         f(transmute(Slice {
1172             data: p as *T,
1173             len: len
1174         }))
1175     }
1176
1177     /**
1178      * Returns a pointer to first element in slice and adjusts
1179      * slice so it no longer contains that element. Returns None
1180      * if the slice is empty. O(1).
1181      */
1182      #[inline]
1183     pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> Option<*T> {
1184         if slice.len == 0 { return None; }
1185         let head: *T = slice.data;
1186         slice.data = slice.data.offset(1);
1187         slice.len -= 1;
1188         Some(head)
1189     }
1190
1191     /**
1192      * Returns a pointer to last element in slice and adjusts
1193      * slice so it no longer contains that element. Returns None
1194      * if the slice is empty. O(1).
1195      */
1196      #[inline]
1197     pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> Option<*T> {
1198         if slice.len == 0 { return None; }
1199         let tail: *T = slice.data.offset((slice.len - 1) as int);
1200         slice.len -= 1;
1201         Some(tail)
1202     }
1203 }
1204
1205 /// Operations on `[u8]`.
1206 pub mod bytes {
1207     use container::Container;
1208     use ptr;
1209     use slice::MutableVector;
1210
1211     /// A trait for operations on mutable `[u8]`s.
1212     pub trait MutableByteVector {
1213         /// Sets all bytes of the receiver to the given value.
1214         fn set_memory(self, value: u8);
1215     }
1216
1217     impl<'a> MutableByteVector for &'a mut [u8] {
1218         #[inline]
1219         fn set_memory(self, value: u8) {
1220             unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1221         }
1222     }
1223
1224     /// Copies data from `src` to `dst`
1225     ///
1226     /// `src` and `dst` must not overlap. Fails if the length of `dst`
1227     /// is less than the length of `src`.
1228     #[inline]
1229     pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1230         // Bound checks are done at .copy_memory.
1231         unsafe { dst.copy_memory(src) }
1232     }
1233 }
1234
1235 /// Immutable slice iterator
1236 pub struct Items<'a, T> {
1237     ptr: *T,
1238     end: *T,
1239     marker: marker::ContravariantLifetime<'a>
1240 }
1241
1242 /// Mutable slice iterator
1243 pub struct MutItems<'a, T> {
1244     ptr: *mut T,
1245     end: *mut T,
1246     marker: marker::ContravariantLifetime<'a>,
1247     marker2: marker::NoCopy
1248 }
1249
1250 macro_rules! iterator {
1251     (struct $name:ident -> $ptr:ty, $elem:ty) => {
1252         impl<'a, T> Iterator<$elem> for $name<'a, T> {
1253             #[inline]
1254             fn next(&mut self) -> Option<$elem> {
1255                 // could be implemented with slices, but this avoids bounds checks
1256                 unsafe {
1257                     if self.ptr == self.end {
1258                         None
1259                     } else {
1260                         let old = self.ptr;
1261                         self.ptr = if mem::size_of::<T>() == 0 {
1262                             // purposefully don't use 'ptr.offset' because for
1263                             // vectors with 0-size elements this would return the
1264                             // same pointer.
1265                             transmute(self.ptr as uint + 1)
1266                         } else {
1267                             self.ptr.offset(1)
1268                         };
1269
1270                         Some(transmute(old))
1271                     }
1272                 }
1273             }
1274
1275             #[inline]
1276             fn size_hint(&self) -> (uint, Option<uint>) {
1277                 let diff = (self.end as uint) - (self.ptr as uint);
1278                 let size = mem::size_of::<T>();
1279                 let exact = diff / (if size == 0 {1} else {size});
1280                 (exact, Some(exact))
1281             }
1282         }
1283
1284         impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
1285             #[inline]
1286             fn next_back(&mut self) -> Option<$elem> {
1287                 // could be implemented with slices, but this avoids bounds checks
1288                 unsafe {
1289                     if self.end == self.ptr {
1290                         None
1291                     } else {
1292                         self.end = if mem::size_of::<T>() == 0 {
1293                             // See above for why 'ptr.offset' isn't used
1294                             transmute(self.end as uint - 1)
1295                         } else {
1296                             self.end.offset(-1)
1297                         };
1298                         Some(transmute(self.end))
1299                     }
1300                 }
1301             }
1302         }
1303     }
1304 }
1305
1306 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
1307     #[inline]
1308     fn indexable(&self) -> uint {
1309         let (exact, _) = self.size_hint();
1310         exact
1311     }
1312
1313     #[inline]
1314     fn idx(&mut self, index: uint) -> Option<&'a T> {
1315         unsafe {
1316             if index < self.indexable() {
1317                 transmute(self.ptr.offset(index as int))
1318             } else {
1319                 None
1320             }
1321         }
1322     }
1323 }
1324
1325 iterator!{struct Items -> *T, &'a T}
1326
1327 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
1328 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
1329
1330 impl<'a, T> Clone for Items<'a, T> {
1331     fn clone(&self) -> Items<'a, T> { *self }
1332 }
1333
1334 iterator!{struct MutItems -> *mut T, &'a mut T}
1335
1336 /// An iterator over the subslices of the vector which are separated
1337 /// by elements that match `pred`.
1338 pub struct MutSplits<'a, T> {
1339     v: &'a mut [T],
1340     pred: |t: &T|: 'a -> bool,
1341     finished: bool
1342 }
1343
1344 impl<'a, T> Iterator<&'a mut [T]> for MutSplits<'a, T> {
1345     #[inline]
1346     fn next(&mut self) -> Option<&'a mut [T]> {
1347         if self.finished { return None; }
1348
1349         let pred = &mut self.pred;
1350         match self.v.iter().position(|x| (*pred)(x)) {
1351             None => {
1352                 self.finished = true;
1353                 let tmp = mem::replace(&mut self.v, &mut []);
1354                 let len = tmp.len();
1355                 let (head, tail) = tmp.mut_split_at(len);
1356                 self.v = tail;
1357                 Some(head)
1358             }
1359             Some(idx) => {
1360                 let tmp = mem::replace(&mut self.v, &mut []);
1361                 let (head, tail) = tmp.mut_split_at(idx);
1362                 self.v = tail.mut_slice_from(1);
1363                 Some(head)
1364             }
1365         }
1366     }
1367
1368     #[inline]
1369     fn size_hint(&self) -> (uint, Option<uint>) {
1370         if self.finished {
1371             (0, Some(0))
1372         } else {
1373             // if the predicate doesn't match anything, we yield one slice
1374             // if it matches every element, we yield len+1 empty slices.
1375             (1, Some(self.v.len() + 1))
1376         }
1377     }
1378 }
1379
1380 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T> {
1381     #[inline]
1382     fn next_back(&mut self) -> Option<&'a mut [T]> {
1383         if self.finished { return None; }
1384
1385         let pred = &mut self.pred;
1386         match self.v.iter().rposition(|x| (*pred)(x)) {
1387             None => {
1388                 self.finished = true;
1389                 let tmp = mem::replace(&mut self.v, &mut []);
1390                 Some(tmp)
1391             }
1392             Some(idx) => {
1393                 let tmp = mem::replace(&mut self.v, &mut []);
1394                 let (head, tail) = tmp.mut_split_at(idx);
1395                 self.v = head;
1396                 Some(tail.mut_slice_from(1))
1397             }
1398         }
1399     }
1400 }
1401
1402 /// An iterator over a vector in (non-overlapping) mutable chunks (`size`  elements at a time). When
1403 /// the vector len is not evenly divided by the chunk size, the last slice of the iteration will be
1404 /// the remainder.
1405 pub struct MutChunks<'a, T> {
1406     v: &'a mut [T],
1407     chunk_size: uint
1408 }
1409
1410 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
1411     #[inline]
1412     fn next(&mut self) -> Option<&'a mut [T]> {
1413         if self.v.len() == 0 {
1414             None
1415         } else {
1416             let sz = cmp::min(self.v.len(), self.chunk_size);
1417             let tmp = mem::replace(&mut self.v, &mut []);
1418             let (head, tail) = tmp.mut_split_at(sz);
1419             self.v = tail;
1420             Some(head)
1421         }
1422     }
1423
1424     #[inline]
1425     fn size_hint(&self) -> (uint, Option<uint>) {
1426         if self.v.len() == 0 {
1427             (0, Some(0))
1428         } else {
1429             let (n, rem) = div_rem(self.v.len(), self.chunk_size);
1430             let n = if rem > 0 { n + 1 } else { n };
1431             (n, Some(n))
1432         }
1433     }
1434 }
1435
1436 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
1437     #[inline]
1438     fn next_back(&mut self) -> Option<&'a mut [T]> {
1439         if self.v.len() == 0 {
1440             None
1441         } else {
1442             let remainder = self.v.len() % self.chunk_size;
1443             let sz = if remainder != 0 { remainder } else { self.chunk_size };
1444             let tmp = mem::replace(&mut self.v, &mut []);
1445             let tmp_len = tmp.len();
1446             let (head, tail) = tmp.mut_split_at(tmp_len - sz);
1447             self.v = head;
1448             Some(tail)
1449         }
1450     }
1451 }
1452
1453 impl<'a, T> Default for &'a [T] {
1454     fn default() -> &'a [T] { &[] }
1455 }
1456
1457 impl<T> Default for ~[T] {
1458     fn default() -> ~[T] { ~[] }
1459 }