src/libcore/slice.rs

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