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