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