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