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