src/libcore/slice.rs

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