]> git.proxmox.com Git - rustc.git/blob - src/libcollections/slice.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / slice.rs
1 // Copyright 2012-2015 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 //! A dynamically-sized view into a contiguous sequence, `[T]`.
12 //!
13 //! Slices are a view into a block of memory represented as a pointer and a
14 //! length.
15 //!
16 //! ```
17 //! // slicing a Vec
18 //! let vec = vec![1, 2, 3];
19 //! let int_slice = &vec[..];
20 //! // coercing an array to a slice
21 //! let str_slice: &[&str] = &["one", "two", "three"];
22 //! ```
23 //!
24 //! Slices are either mutable or shared. The shared slice type is `&[T]`,
25 //! while the mutable slice type is `&mut [T]`, where `T` represents the element
26 //! type. For example, you can mutate the block of memory that a mutable slice
27 //! points to:
28 //!
29 //! ```
30 //! let x = &mut [1, 2, 3];
31 //! x[1] = 7;
32 //! assert_eq!(x, &[1, 7, 3]);
33 //! ```
34 //!
35 //! Here are some of the things this module contains:
36 //!
37 //! ## Structs
38 //!
39 //! There are several structs that are useful for slices, such as `Iter`, which
40 //! represents iteration over a slice.
41 //!
42 //! ## Trait Implementations
43 //!
44 //! There are several implementations of common traits for slices. Some examples
45 //! include:
46 //!
47 //! * `Clone`
48 //! * `Eq`, `Ord` - for slices whose element type are `Eq` or `Ord`.
49 //! * `Hash` - for slices whose element type is `Hash`
50 //!
51 //! ## Iteration
52 //!
53 //! The slices implement `IntoIterator`. The iterator yields references to the
54 //! slice elements.
55 //!
56 //! ```
57 //! let numbers = &[0, 1, 2];
58 //! for n in numbers {
59 //! println!("{} is a number!", n);
60 //! }
61 //! ```
62 //!
63 //! The mutable slice yields mutable references to the elements:
64 //!
65 //! ```
66 //! let mut scores = [7, 8, 9];
67 //! for score in &mut scores[..] {
68 //! *score += 1;
69 //! }
70 //! ```
71 //!
72 //! This iterator yields mutable references to the slice's elements, so while
73 //! the element type of the slice is `i32`, the element type of the iterator is
74 //! `&mut i32`.
75 //!
76 //! * `.iter()` and `.iter_mut()` are the explicit methods to return the default
77 //! iterators.
78 //! * Further methods that return iterators are `.split()`, `.splitn()`,
79 //! `.chunks()`, `.windows()` and more.
80 //!
81 //! *[See also the slice primitive type](../../std/primitive.slice.html).*
82 #![stable(feature = "rust1", since = "1.0.0")]
83
84 // Many of the usings in this module are only used in the test configuration.
85 // It's cleaner to just turn off the unused_imports warning than to fix them.
86 #![cfg_attr(test, allow(unused_imports, dead_code))]
87
88 use alloc::boxed::Box;
89 use core::cmp::Ordering::{self, Greater, Less};
90 use core::cmp;
91 use core::mem::size_of;
92 use core::mem;
93 use core::ptr;
94 use core::slice as core_slice;
95
96 use borrow::{Borrow, BorrowMut, ToOwned};
97 use vec::Vec;
98
99 #[stable(feature = "rust1", since = "1.0.0")]
100 pub use core::slice::{Chunks, Windows};
101 #[stable(feature = "rust1", since = "1.0.0")]
102 pub use core::slice::{Iter, IterMut};
103 #[stable(feature = "rust1", since = "1.0.0")]
104 pub use core::slice::{SplitMut, ChunksMut, Split};
105 #[stable(feature = "rust1", since = "1.0.0")]
106 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
107 #[stable(feature = "rust1", since = "1.0.0")]
108 pub use core::slice::{from_raw_parts, from_raw_parts_mut};
109
110 ////////////////////////////////////////////////////////////////////////////////
111 // Basic slice extension methods
112 ////////////////////////////////////////////////////////////////////////////////
113
114 // HACK(japaric) needed for the implementation of `vec!` macro during testing
115 // NB see the hack module in this file for more details
116 #[cfg(test)]
117 pub use self::hack::into_vec;
118
119 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
120 // NB see the hack module in this file for more details
121 #[cfg(test)]
122 pub use self::hack::to_vec;
123
124 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
125 // functions are actually methods that are in `impl [T]` but not in
126 // `core::slice::SliceExt` - we need to supply these functions for the
127 // `test_permutations` test
128 mod hack {
129 use alloc::boxed::Box;
130 use core::mem;
131
132 #[cfg(test)]
133 use string::ToString;
134 use vec::Vec;
135
136 pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> {
137 unsafe {
138 let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len());
139 mem::forget(b);
140 xs
141 }
142 }
143
144 #[inline]
145 pub fn to_vec<T>(s: &[T]) -> Vec<T>
146 where T: Clone
147 {
148 let mut vector = Vec::with_capacity(s.len());
149 vector.extend_from_slice(s);
150 vector
151 }
152 }
153
154 /// Allocating extension methods for slices.
155 #[lang = "slice"]
156 #[cfg(not(test))]
157 impl<T> [T] {
158 /// Returns the number of elements in the slice.
159 ///
160 /// # Example
161 ///
162 /// ```
163 /// let a = [1, 2, 3];
164 /// assert_eq!(a.len(), 3);
165 /// ```
166 #[stable(feature = "rust1", since = "1.0.0")]
167 #[inline]
168 pub fn len(&self) -> usize {
169 core_slice::SliceExt::len(self)
170 }
171
172 /// Returns true if the slice has a length of 0
173 ///
174 /// # Example
175 ///
176 /// ```
177 /// let a = [1, 2, 3];
178 /// assert!(!a.is_empty());
179 /// ```
180 #[stable(feature = "rust1", since = "1.0.0")]
181 #[inline]
182 pub fn is_empty(&self) -> bool {
183 core_slice::SliceExt::is_empty(self)
184 }
185
186 /// Returns the first element of a slice, or `None` if it is empty.
187 ///
188 /// # Examples
189 ///
190 /// ```
191 /// let v = [10, 40, 30];
192 /// assert_eq!(Some(&10), v.first());
193 ///
194 /// let w: &[i32] = &[];
195 /// assert_eq!(None, w.first());
196 /// ```
197 #[stable(feature = "rust1", since = "1.0.0")]
198 #[inline]
199 pub fn first(&self) -> Option<&T> {
200 core_slice::SliceExt::first(self)
201 }
202
203 /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
204 #[stable(feature = "rust1", since = "1.0.0")]
205 #[inline]
206 pub fn first_mut(&mut self) -> Option<&mut T> {
207 core_slice::SliceExt::first_mut(self)
208 }
209
210 /// Returns the first and all the rest of the elements of a slice.
211 #[stable(feature = "slice_splits", since = "1.5.0")]
212 #[inline]
213 pub fn split_first(&self) -> Option<(&T, &[T])> {
214 core_slice::SliceExt::split_first(self)
215 }
216
217 /// Returns the first and all the rest of the elements of a slice.
218 #[stable(feature = "slice_splits", since = "1.5.0")]
219 #[inline]
220 pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
221 core_slice::SliceExt::split_first_mut(self)
222 }
223
224 /// Returns the last and all the rest of the elements of a slice.
225 #[stable(feature = "slice_splits", since = "1.5.0")]
226 #[inline]
227 pub fn split_last(&self) -> Option<(&T, &[T])> {
228 core_slice::SliceExt::split_last(self)
229
230 }
231
232 /// Returns the last and all the rest of the elements of a slice.
233 #[stable(feature = "slice_splits", since = "1.5.0")]
234 #[inline]
235 pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
236 core_slice::SliceExt::split_last_mut(self)
237 }
238
239 /// Returns the last element of a slice, or `None` if it is empty.
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// let v = [10, 40, 30];
245 /// assert_eq!(Some(&30), v.last());
246 ///
247 /// let w: &[i32] = &[];
248 /// assert_eq!(None, w.last());
249 /// ```
250 #[stable(feature = "rust1", since = "1.0.0")]
251 #[inline]
252 pub fn last(&self) -> Option<&T> {
253 core_slice::SliceExt::last(self)
254 }
255
256 /// Returns a mutable pointer to the last item in the slice.
257 #[stable(feature = "rust1", since = "1.0.0")]
258 #[inline]
259 pub fn last_mut(&mut self) -> Option<&mut T> {
260 core_slice::SliceExt::last_mut(self)
261 }
262
263 /// Returns the element of a slice at the given index, or `None` if the
264 /// index is out of bounds.
265 ///
266 /// # Examples
267 ///
268 /// ```
269 /// let v = [10, 40, 30];
270 /// assert_eq!(Some(&40), v.get(1));
271 /// assert_eq!(None, v.get(3));
272 /// ```
273 #[stable(feature = "rust1", since = "1.0.0")]
274 #[inline]
275 pub fn get(&self, index: usize) -> Option<&T> {
276 core_slice::SliceExt::get(self, index)
277 }
278
279 /// Returns a mutable reference to the element at the given index,
280 /// or `None` if the index is out of bounds
281 #[stable(feature = "rust1", since = "1.0.0")]
282 #[inline]
283 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
284 core_slice::SliceExt::get_mut(self, index)
285 }
286
287 /// Returns a pointer to the element at the given index, without doing
288 /// bounds checking.
289 #[stable(feature = "rust1", since = "1.0.0")]
290 #[inline]
291 pub unsafe fn get_unchecked(&self, index: usize) -> &T {
292 core_slice::SliceExt::get_unchecked(self, index)
293 }
294
295 /// Returns an unsafe mutable pointer to the element in index
296 #[stable(feature = "rust1", since = "1.0.0")]
297 #[inline]
298 pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
299 core_slice::SliceExt::get_unchecked_mut(self, index)
300 }
301
302 /// Returns an raw pointer to the slice's buffer
303 ///
304 /// The caller must ensure that the slice outlives the pointer this
305 /// function returns, or else it will end up pointing to garbage.
306 ///
307 /// Modifying the slice may cause its buffer to be reallocated, which
308 /// would also make any pointers to it invalid.
309 #[stable(feature = "rust1", since = "1.0.0")]
310 #[inline]
311 pub fn as_ptr(&self) -> *const T {
312 core_slice::SliceExt::as_ptr(self)
313 }
314
315 /// Returns an unsafe mutable pointer to the slice's buffer.
316 ///
317 /// The caller must ensure that the slice outlives the pointer this
318 /// function returns, or else it will end up pointing to garbage.
319 ///
320 /// Modifying the slice may cause its buffer to be reallocated, which
321 /// would also make any pointers to it invalid.
322 #[stable(feature = "rust1", since = "1.0.0")]
323 #[inline]
324 pub fn as_mut_ptr(&mut self) -> *mut T {
325 core_slice::SliceExt::as_mut_ptr(self)
326 }
327
328 /// Swaps two elements in a slice.
329 ///
330 /// # Arguments
331 ///
332 /// * a - The index of the first element
333 /// * b - The index of the second element
334 ///
335 /// # Panics
336 ///
337 /// Panics if `a` or `b` are out of bounds.
338 ///
339 /// # Example
340 ///
341 /// ```rust
342 /// let mut v = ["a", "b", "c", "d"];
343 /// v.swap(1, 3);
344 /// assert!(v == ["a", "d", "c", "b"]);
345 /// ```
346 #[stable(feature = "rust1", since = "1.0.0")]
347 #[inline]
348 pub fn swap(&mut self, a: usize, b: usize) {
349 core_slice::SliceExt::swap(self, a, b)
350 }
351
352 /// Reverse the order of elements in a slice, in place.
353 ///
354 /// # Example
355 ///
356 /// ```rust
357 /// let mut v = [1, 2, 3];
358 /// v.reverse();
359 /// assert!(v == [3, 2, 1]);
360 /// ```
361 #[stable(feature = "rust1", since = "1.0.0")]
362 #[inline]
363 pub fn reverse(&mut self) {
364 core_slice::SliceExt::reverse(self)
365 }
366
367 /// Returns an iterator over the slice.
368 #[stable(feature = "rust1", since = "1.0.0")]
369 #[inline]
370 pub fn iter(&self) -> Iter<T> {
371 core_slice::SliceExt::iter(self)
372 }
373
374 /// Returns an iterator that allows modifying each value
375 #[stable(feature = "rust1", since = "1.0.0")]
376 #[inline]
377 pub fn iter_mut(&mut self) -> IterMut<T> {
378 core_slice::SliceExt::iter_mut(self)
379 }
380
381 /// Returns an iterator over all contiguous windows of length
382 /// `size`. The windows overlap. If the slice is shorter than
383 /// `size`, the iterator returns no values.
384 ///
385 /// # Panics
386 ///
387 /// Panics if `size` is 0.
388 ///
389 /// # Example
390 ///
391 /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
392 /// `[3,4]`):
393 ///
394 /// ```rust
395 /// let v = &[1, 2, 3, 4];
396 /// for win in v.windows(2) {
397 /// println!("{:?}", win);
398 /// }
399 /// ```
400 #[stable(feature = "rust1", since = "1.0.0")]
401 #[inline]
402 pub fn windows(&self, size: usize) -> Windows<T> {
403 core_slice::SliceExt::windows(self, size)
404 }
405
406 /// Returns an iterator over `size` elements of the slice at a
407 /// time. The chunks are slices and do not overlap. If `size` does not divide the
408 /// length of the slice, then the last chunk will not have length
409 /// `size`.
410 ///
411 /// # Panics
412 ///
413 /// Panics if `size` is 0.
414 ///
415 /// # Example
416 ///
417 /// Print the slice two elements at a time (i.e. `[1,2]`,
418 /// `[3,4]`, `[5]`):
419 ///
420 /// ```rust
421 /// let v = &[1, 2, 3, 4, 5];
422 /// for win in v.chunks(2) {
423 /// println!("{:?}", win);
424 /// }
425 /// ```
426 #[stable(feature = "rust1", since = "1.0.0")]
427 #[inline]
428 pub fn chunks(&self, size: usize) -> Chunks<T> {
429 core_slice::SliceExt::chunks(self, size)
430 }
431
432 /// Returns an iterator over `chunk_size` elements of the slice at a time.
433 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
434 /// not divide the length of the slice, then the last chunk will not
435 /// have length `chunk_size`.
436 ///
437 /// # Panics
438 ///
439 /// Panics if `chunk_size` is 0.
440 #[stable(feature = "rust1", since = "1.0.0")]
441 #[inline]
442 pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
443 core_slice::SliceExt::chunks_mut(self, chunk_size)
444 }
445
446 /// Divides one slice into two at an index.
447 ///
448 /// The first will contain all indices from `[0, mid)` (excluding
449 /// the index `mid` itself) and the second will contain all
450 /// indices from `[mid, len)` (excluding the index `len` itself).
451 ///
452 /// # Panics
453 ///
454 /// Panics if `mid > len`.
455 ///
456 /// # Examples
457 ///
458 /// ```
459 /// let v = [10, 40, 30, 20, 50];
460 /// let (v1, v2) = v.split_at(2);
461 /// assert_eq!([10, 40], v1);
462 /// assert_eq!([30, 20, 50], v2);
463 /// ```
464 #[stable(feature = "rust1", since = "1.0.0")]
465 #[inline]
466 pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
467 core_slice::SliceExt::split_at(self, mid)
468 }
469
470 /// Divides one `&mut` into two at an index.
471 ///
472 /// The first will contain all indices from `[0, mid)` (excluding
473 /// the index `mid` itself) and the second will contain all
474 /// indices from `[mid, len)` (excluding the index `len` itself).
475 ///
476 /// # Panics
477 ///
478 /// Panics if `mid > len`.
479 ///
480 /// # Example
481 ///
482 /// ```rust
483 /// let mut v = [1, 2, 3, 4, 5, 6];
484 ///
485 /// // scoped to restrict the lifetime of the borrows
486 /// {
487 /// let (left, right) = v.split_at_mut(0);
488 /// assert!(left == []);
489 /// assert!(right == [1, 2, 3, 4, 5, 6]);
490 /// }
491 ///
492 /// {
493 /// let (left, right) = v.split_at_mut(2);
494 /// assert!(left == [1, 2]);
495 /// assert!(right == [3, 4, 5, 6]);
496 /// }
497 ///
498 /// {
499 /// let (left, right) = v.split_at_mut(6);
500 /// assert!(left == [1, 2, 3, 4, 5, 6]);
501 /// assert!(right == []);
502 /// }
503 /// ```
504 #[stable(feature = "rust1", since = "1.0.0")]
505 #[inline]
506 pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
507 core_slice::SliceExt::split_at_mut(self, mid)
508 }
509
510 /// Returns an iterator over subslices separated by elements that match
511 /// `pred`. The matched element is not contained in the subslices.
512 ///
513 /// # Examples
514 ///
515 /// Print the slice split by numbers divisible by 3 (i.e. `[10, 40]`,
516 /// `[20]`, `[50]`):
517 ///
518 /// ```
519 /// let v = [10, 40, 30, 20, 60, 50];
520 /// for group in v.split(|num| *num % 3 == 0) {
521 /// println!("{:?}", group);
522 /// }
523 /// ```
524 #[stable(feature = "rust1", since = "1.0.0")]
525 #[inline]
526 pub fn split<F>(&self, pred: F) -> Split<T, F>
527 where F: FnMut(&T) -> bool
528 {
529 core_slice::SliceExt::split(self, pred)
530 }
531
532 /// Returns an iterator over mutable subslices separated by elements that
533 /// match `pred`. The matched element is not contained in the subslices.
534 #[stable(feature = "rust1", since = "1.0.0")]
535 #[inline]
536 pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
537 where F: FnMut(&T) -> bool
538 {
539 core_slice::SliceExt::split_mut(self, pred)
540 }
541
542 /// Returns an iterator over subslices separated by elements that match
543 /// `pred`, limited to returning at most `n` items. The matched element is
544 /// not contained in the subslices.
545 ///
546 /// The last element returned, if any, will contain the remainder of the
547 /// slice.
548 ///
549 /// # Examples
550 ///
551 /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
552 /// `[20, 60, 50]`):
553 ///
554 /// ```
555 /// let v = [10, 40, 30, 20, 60, 50];
556 /// for group in v.splitn(2, |num| *num % 3 == 0) {
557 /// println!("{:?}", group);
558 /// }
559 /// ```
560 #[stable(feature = "rust1", since = "1.0.0")]
561 #[inline]
562 pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
563 where F: FnMut(&T) -> bool
564 {
565 core_slice::SliceExt::splitn(self, n, pred)
566 }
567
568 /// Returns an iterator over subslices separated by elements that match
569 /// `pred`, limited to returning at most `n` items. The matched element is
570 /// not contained in the subslices.
571 ///
572 /// The last element returned, if any, will contain the remainder of the
573 /// slice.
574 #[stable(feature = "rust1", since = "1.0.0")]
575 #[inline]
576 pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
577 where F: FnMut(&T) -> bool
578 {
579 core_slice::SliceExt::splitn_mut(self, n, pred)
580 }
581
582 /// Returns an iterator over subslices separated by elements that match
583 /// `pred` limited to returning at most `n` items. This starts at the end of
584 /// the slice and works backwards. The matched element is not contained in
585 /// the subslices.
586 ///
587 /// The last element returned, if any, will contain the remainder of the
588 /// slice.
589 ///
590 /// # Examples
591 ///
592 /// Print the slice split once, starting from the end, by numbers divisible
593 /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
594 ///
595 /// ```
596 /// let v = [10, 40, 30, 20, 60, 50];
597 /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
598 /// println!("{:?}", group);
599 /// }
600 /// ```
601 #[stable(feature = "rust1", since = "1.0.0")]
602 #[inline]
603 pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
604 where F: FnMut(&T) -> bool
605 {
606 core_slice::SliceExt::rsplitn(self, n, pred)
607 }
608
609 /// Returns an iterator over subslices separated by elements that match
610 /// `pred` limited to returning at most `n` items. This starts at the end of
611 /// the slice and works backwards. The matched element is not contained in
612 /// the subslices.
613 ///
614 /// The last element returned, if any, will contain the remainder of the
615 /// slice.
616 #[stable(feature = "rust1", since = "1.0.0")]
617 #[inline]
618 pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
619 where F: FnMut(&T) -> bool
620 {
621 core_slice::SliceExt::rsplitn_mut(self, n, pred)
622 }
623
624 /// Returns true if the slice contains an element with the given value.
625 ///
626 /// # Examples
627 ///
628 /// ```
629 /// let v = [10, 40, 30];
630 /// assert!(v.contains(&30));
631 /// assert!(!v.contains(&50));
632 /// ```
633 #[stable(feature = "rust1", since = "1.0.0")]
634 pub fn contains(&self, x: &T) -> bool
635 where T: PartialEq
636 {
637 core_slice::SliceExt::contains(self, x)
638 }
639
640 /// Returns true if `needle` is a prefix of the slice.
641 ///
642 /// # Examples
643 ///
644 /// ```
645 /// let v = [10, 40, 30];
646 /// assert!(v.starts_with(&[10]));
647 /// assert!(v.starts_with(&[10, 40]));
648 /// assert!(!v.starts_with(&[50]));
649 /// assert!(!v.starts_with(&[10, 50]));
650 /// ```
651 #[stable(feature = "rust1", since = "1.0.0")]
652 pub fn starts_with(&self, needle: &[T]) -> bool
653 where T: PartialEq
654 {
655 core_slice::SliceExt::starts_with(self, needle)
656 }
657
658 /// Returns true if `needle` is a suffix of the slice.
659 ///
660 /// # Examples
661 ///
662 /// ```
663 /// let v = [10, 40, 30];
664 /// assert!(v.ends_with(&[30]));
665 /// assert!(v.ends_with(&[40, 30]));
666 /// assert!(!v.ends_with(&[50]));
667 /// assert!(!v.ends_with(&[50, 30]));
668 /// ```
669 #[stable(feature = "rust1", since = "1.0.0")]
670 pub fn ends_with(&self, needle: &[T]) -> bool
671 where T: PartialEq
672 {
673 core_slice::SliceExt::ends_with(self, needle)
674 }
675
676 /// Binary search a sorted slice for a given element.
677 ///
678 /// If the value is found then `Ok` is returned, containing the
679 /// index of the matching element; if the value is not found then
680 /// `Err` is returned, containing the index where a matching
681 /// element could be inserted while maintaining sorted order.
682 ///
683 /// # Example
684 ///
685 /// Looks up a series of four elements. The first is found, with a
686 /// uniquely determined position; the second and third are not
687 /// found; the fourth could match any position in `[1,4]`.
688 ///
689 /// ```rust
690 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
691 ///
692 /// assert_eq!(s.binary_search(&13), Ok(9));
693 /// assert_eq!(s.binary_search(&4), Err(7));
694 /// assert_eq!(s.binary_search(&100), Err(13));
695 /// let r = s.binary_search(&1);
696 /// assert!(match r { Ok(1...4) => true, _ => false, });
697 /// ```
698 #[stable(feature = "rust1", since = "1.0.0")]
699 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
700 where T: Ord
701 {
702 core_slice::SliceExt::binary_search(self, x)
703 }
704
705 /// Binary search a sorted slice with a comparator function.
706 ///
707 /// The comparator function should implement an order consistent
708 /// with the sort order of the underlying slice, returning an
709 /// order code that indicates whether its argument is `Less`,
710 /// `Equal` or `Greater` the desired target.
711 ///
712 /// If a matching value is found then returns `Ok`, containing
713 /// the index for the matched element; if no match is found then
714 /// `Err` is returned, containing the index where a matching
715 /// element could be inserted while maintaining sorted order.
716 ///
717 /// # Example
718 ///
719 /// Looks up a series of four elements. The first is found, with a
720 /// uniquely determined position; the second and third are not
721 /// found; the fourth could match any position in `[1,4]`.
722 ///
723 /// ```rust
724 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
725 ///
726 /// let seek = 13;
727 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
728 /// let seek = 4;
729 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
730 /// let seek = 100;
731 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
732 /// let seek = 1;
733 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
734 /// assert!(match r { Ok(1...4) => true, _ => false, });
735 /// ```
736 #[stable(feature = "rust1", since = "1.0.0")]
737 #[inline]
738 pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>
739 where F: FnMut(&T) -> Ordering
740 {
741 core_slice::SliceExt::binary_search_by(self, f)
742 }
743
744 /// Sorts the slice, in place.
745 ///
746 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
747 ///
748 /// This is a stable sort.
749 ///
750 /// # Examples
751 ///
752 /// ```rust
753 /// let mut v = [-5, 4, 1, -3, 2];
754 ///
755 /// v.sort();
756 /// assert!(v == [-5, -3, 1, 2, 4]);
757 /// ```
758 #[stable(feature = "rust1", since = "1.0.0")]
759 #[inline]
760 pub fn sort(&mut self)
761 where T: Ord
762 {
763 self.sort_by(|a, b| a.cmp(b))
764 }
765
766 /// Sorts the slice, in place, using `key` to extract a key by which to
767 /// order the sort by.
768 ///
769 /// This sort is `O(n log n)` worst-case and stable, but allocates
770 /// approximately `2 * n`, where `n` is the length of `self`.
771 ///
772 /// This is a stable sort.
773 ///
774 /// # Examples
775 ///
776 /// ```rust
777 /// let mut v = [-5i32, 4, 1, -3, 2];
778 ///
779 /// v.sort_by_key(|k| k.abs());
780 /// assert!(v == [1, 2, -3, 4, -5]);
781 /// ```
782 #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
783 #[inline]
784 pub fn sort_by_key<B, F>(&mut self, mut f: F)
785 where F: FnMut(&T) -> B, B: Ord
786 {
787 self.sort_by(|a, b| f(a).cmp(&f(b)))
788 }
789
790 /// Sorts the slice, in place, using `compare` to compare
791 /// elements.
792 ///
793 /// This sort is `O(n log n)` worst-case and stable, but allocates
794 /// approximately `2 * n`, where `n` is the length of `self`.
795 ///
796 /// # Examples
797 ///
798 /// ```rust
799 /// let mut v = [5, 4, 1, 3, 2];
800 /// v.sort_by(|a, b| a.cmp(b));
801 /// assert!(v == [1, 2, 3, 4, 5]);
802 ///
803 /// // reverse sorting
804 /// v.sort_by(|a, b| b.cmp(a));
805 /// assert!(v == [5, 4, 3, 2, 1]);
806 /// ```
807 #[stable(feature = "rust1", since = "1.0.0")]
808 #[inline]
809 pub fn sort_by<F>(&mut self, compare: F)
810 where F: FnMut(&T, &T) -> Ordering
811 {
812 merge_sort(self, compare)
813 }
814
815 /// Copies the elements from `src` into `self`.
816 ///
817 /// The length of this slice must be the same as the slice passed in.
818 ///
819 /// # Panics
820 ///
821 /// This function will panic if the two slices have different lengths.
822 ///
823 /// # Example
824 ///
825 /// ```rust
826 /// let mut dst = [0, 0, 0];
827 /// let src = [1, 2, 3];
828 ///
829 /// dst.clone_from_slice(&src);
830 /// assert!(dst == [1, 2, 3]);
831 /// ```
832 #[stable(feature = "clone_from_slice", since = "1.7.0")]
833 pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
834 core_slice::SliceExt::clone_from_slice(self, src)
835 }
836
837 /// Copies all elements from `src` into `self`, using a memcpy.
838 ///
839 /// The length of `src` must be the same as `self`.
840 ///
841 /// # Panics
842 ///
843 /// This function will panic if the two slices have different lengths.
844 ///
845 /// # Example
846 ///
847 /// ```rust
848 /// let mut dst = [0, 0, 0];
849 /// let src = [1, 2, 3];
850 ///
851 /// dst.copy_from_slice(&src);
852 /// assert_eq!(src, dst);
853 /// ```
854 #[stable(feature = "copy_from_slice", since = "1.9.0")]
855 pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
856 core_slice::SliceExt::copy_from_slice(self, src)
857 }
858
859
860 /// Copies `self` into a new `Vec`.
861 #[stable(feature = "rust1", since = "1.0.0")]
862 #[inline]
863 pub fn to_vec(&self) -> Vec<T>
864 where T: Clone
865 {
866 // NB see hack module in this file
867 hack::to_vec(self)
868 }
869
870 /// Converts `self` into a vector without clones or allocation.
871 #[stable(feature = "rust1", since = "1.0.0")]
872 #[inline]
873 pub fn into_vec(self: Box<Self>) -> Vec<T> {
874 // NB see hack module in this file
875 hack::into_vec(self)
876 }
877 }
878
879 ////////////////////////////////////////////////////////////////////////////////
880 // Extension traits for slices over specific kinds of data
881 ////////////////////////////////////////////////////////////////////////////////
882 #[unstable(feature = "slice_concat_ext",
883 reason = "trait should not have to exist",
884 issue = "27747")]
885 /// An extension trait for concatenating slices
886 pub trait SliceConcatExt<T: ?Sized> {
887 #[unstable(feature = "slice_concat_ext",
888 reason = "trait should not have to exist",
889 issue = "27747")]
890 /// The resulting type after concatenation
891 type Output;
892
893 /// Flattens a slice of `T` into a single value `Self::Output`.
894 ///
895 /// # Examples
896 ///
897 /// ```
898 /// assert_eq!(["hello", "world"].concat(), "helloworld");
899 /// ```
900 #[stable(feature = "rust1", since = "1.0.0")]
901 fn concat(&self) -> Self::Output;
902
903 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
904 /// given separator between each.
905 ///
906 /// # Examples
907 ///
908 /// ```
909 /// assert_eq!(["hello", "world"].join(" "), "hello world");
910 /// ```
911 #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
912 fn join(&self, sep: &T) -> Self::Output;
913
914 #[stable(feature = "rust1", since = "1.0.0")]
915 #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
916 fn connect(&self, sep: &T) -> Self::Output;
917 }
918
919 #[unstable(feature = "slice_concat_ext",
920 reason = "trait should not have to exist",
921 issue = "27747")]
922 impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
923 type Output = Vec<T>;
924
925 fn concat(&self) -> Vec<T> {
926 let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
927 let mut result = Vec::with_capacity(size);
928 for v in self {
929 result.extend_from_slice(v.borrow())
930 }
931 result
932 }
933
934 fn join(&self, sep: &T) -> Vec<T> {
935 let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
936 let mut result = Vec::with_capacity(size + self.len());
937 let mut first = true;
938 for v in self {
939 if first {
940 first = false
941 } else {
942 result.push(sep.clone())
943 }
944 result.extend_from_slice(v.borrow())
945 }
946 result
947 }
948
949 fn connect(&self, sep: &T) -> Vec<T> {
950 self.join(sep)
951 }
952 }
953
954 ////////////////////////////////////////////////////////////////////////////////
955 // Standard trait implementations for slices
956 ////////////////////////////////////////////////////////////////////////////////
957
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<T> Borrow<[T]> for Vec<T> {
960 fn borrow(&self) -> &[T] {
961 &self[..]
962 }
963 }
964
965 #[stable(feature = "rust1", since = "1.0.0")]
966 impl<T> BorrowMut<[T]> for Vec<T> {
967 fn borrow_mut(&mut self) -> &mut [T] {
968 &mut self[..]
969 }
970 }
971
972 #[stable(feature = "rust1", since = "1.0.0")]
973 impl<T: Clone> ToOwned for [T] {
974 type Owned = Vec<T>;
975 #[cfg(not(test))]
976 fn to_owned(&self) -> Vec<T> {
977 self.to_vec()
978 }
979
980 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec`, which is required for this method
981 // definition, is not available. Since we don't require this method for testing purposes, I'll
982 // just stub it
983 // NB see the slice::hack module in slice.rs for more information
984 #[cfg(test)]
985 fn to_owned(&self) -> Vec<T> {
986 panic!("not available with cfg(test)")
987 }
988 }
989
990 ////////////////////////////////////////////////////////////////////////////////
991 // Sorting
992 ////////////////////////////////////////////////////////////////////////////////
993
994 fn insertion_sort<T, F>(v: &mut [T], mut compare: F)
995 where F: FnMut(&T, &T) -> Ordering
996 {
997 let len = v.len() as isize;
998 let buf_v = v.as_mut_ptr();
999
1000 // 1 <= i < len;
1001 for i in 1..len {
1002 // j satisfies: 0 <= j <= i;
1003 let mut j = i;
1004 unsafe {
1005 // `i` is in bounds.
1006 let read_ptr = buf_v.offset(i) as *const T;
1007
1008 // find where to insert, we need to do strict <,
1009 // rather than <=, to maintain stability.
1010
1011 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1012 while j > 0 && compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1013 j -= 1;
1014 }
1015
1016 // shift everything to the right, to make space to
1017 // insert this value.
1018
1019 // j + 1 could be `len` (for the last `i`), but in
1020 // that case, `i == j` so we don't copy. The
1021 // `.offset(j)` is always in bounds.
1022
1023 if i != j {
1024 let tmp = ptr::read(read_ptr);
1025 ptr::copy(&*buf_v.offset(j), buf_v.offset(j + 1), (i - j) as usize);
1026 ptr::copy_nonoverlapping(&tmp, buf_v.offset(j), 1);
1027 mem::forget(tmp);
1028 }
1029 }
1030 }
1031 }
1032
1033 fn merge_sort<T, F>(v: &mut [T], mut compare: F)
1034 where F: FnMut(&T, &T) -> Ordering
1035 {
1036 // warning: this wildly uses unsafe.
1037 const BASE_INSERTION: usize = 32;
1038 const LARGE_INSERTION: usize = 16;
1039
1040 // FIXME #12092: smaller insertion runs seems to make sorting
1041 // vectors of large elements a little faster on some platforms,
1042 // but hasn't been tested/tuned extensively
1043 let insertion = if size_of::<T>() <= 16 {
1044 BASE_INSERTION
1045 } else {
1046 LARGE_INSERTION
1047 };
1048
1049 let len = v.len();
1050
1051 // short vectors get sorted in-place via insertion sort to avoid allocations
1052 if len <= insertion {
1053 insertion_sort(v, compare);
1054 return;
1055 }
1056
1057 // allocate some memory to use as scratch memory, we keep the
1058 // length 0 so we can keep shallow copies of the contents of `v`
1059 // without risking the dtors running on an object twice if
1060 // `compare` panics.
1061 let mut working_space = Vec::with_capacity(2 * len);
1062 // these both are buffers of length `len`.
1063 let mut buf_dat = working_space.as_mut_ptr();
1064 let mut buf_tmp = unsafe { buf_dat.offset(len as isize) };
1065
1066 // length `len`.
1067 let buf_v = v.as_ptr();
1068
1069 // step 1. sort short runs with insertion sort. This takes the
1070 // values from `v` and sorts them into `buf_dat`, leaving that
1071 // with sorted runs of length INSERTION.
1072
1073 // We could hardcode the sorting comparisons here, and we could
1074 // manipulate/step the pointers themselves, rather than repeatedly
1075 // .offset-ing.
1076 for start in (0..len).step_by(insertion) {
1077 // start <= i < len;
1078 for i in start..cmp::min(start + insertion, len) {
1079 // j satisfies: start <= j <= i;
1080 let mut j = i as isize;
1081 unsafe {
1082 // `i` is in bounds.
1083 let read_ptr = buf_v.offset(i as isize);
1084
1085 // find where to insert, we need to do strict <,
1086 // rather than <=, to maintain stability.
1087
1088 // start <= j - 1 < len, so .offset(j - 1) is in
1089 // bounds.
1090 while j > start as isize && compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1091 j -= 1;
1092 }
1093
1094 // shift everything to the right, to make space to
1095 // insert this value.
1096
1097 // j + 1 could be `len` (for the last `i`), but in
1098 // that case, `i == j` so we don't copy. The
1099 // `.offset(j)` is always in bounds.
1100 ptr::copy(&*buf_dat.offset(j), buf_dat.offset(j + 1), i - j as usize);
1101 ptr::copy_nonoverlapping(read_ptr, buf_dat.offset(j), 1);
1102 }
1103 }
1104 }
1105
1106 // step 2. merge the sorted runs.
1107 let mut width = insertion;
1108 while width < len {
1109 // merge the sorted runs of length `width` in `buf_dat` two at
1110 // a time, placing the result in `buf_tmp`.
1111
1112 // 0 <= start <= len.
1113 for start in (0..len).step_by(2 * width) {
1114 // manipulate pointers directly for speed (rather than
1115 // using a `for` loop with `range` and `.offset` inside
1116 // that loop).
1117 unsafe {
1118 // the end of the first run & start of the
1119 // second. Offset of `len` is defined, since this is
1120 // precisely one byte past the end of the object.
1121 let right_start = buf_dat.offset(cmp::min(start + width, len) as isize);
1122 // end of the second. Similar reasoning to the above re safety.
1123 let right_end_idx = cmp::min(start + 2 * width, len);
1124 let right_end = buf_dat.offset(right_end_idx as isize);
1125
1126 // the pointers to the elements under consideration
1127 // from the two runs.
1128
1129 // both of these are in bounds.
1130 let mut left = buf_dat.offset(start as isize);
1131 let mut right = right_start;
1132
1133 // where we're putting the results, it is a run of
1134 // length `2*width`, so we step it once for each step
1135 // of either `left` or `right`. `buf_tmp` has length
1136 // `len`, so these are in bounds.
1137 let mut out = buf_tmp.offset(start as isize);
1138 let out_end = buf_tmp.offset(right_end_idx as isize);
1139
1140 // If left[last] <= right[0], they are already in order:
1141 // fast-forward the left side (the right side is handled
1142 // in the loop).
1143 // If `right` is not empty then left is not empty, and
1144 // the offsets are in bounds.
1145 if right != right_end && compare(&*right.offset(-1), &*right) != Greater {
1146 let elems = (right_start as usize - left as usize) / mem::size_of::<T>();
1147 ptr::copy_nonoverlapping(&*left, out, elems);
1148 out = out.offset(elems as isize);
1149 left = right_start;
1150 }
1151
1152 while out < out_end {
1153 // Either the left or the right run are exhausted,
1154 // so just copy the remainder from the other run
1155 // and move on; this gives a huge speed-up (order
1156 // of 25%) for mostly sorted vectors (the best
1157 // case).
1158 if left == right_start {
1159 // the number remaining in this run.
1160 let elems = (right_end as usize - right as usize) / mem::size_of::<T>();
1161 ptr::copy_nonoverlapping(&*right, out, elems);
1162 break;
1163 } else if right == right_end {
1164 let elems = (right_start as usize - left as usize) / mem::size_of::<T>();
1165 ptr::copy_nonoverlapping(&*left, out, elems);
1166 break;
1167 }
1168
1169 // check which side is smaller, and that's the
1170 // next element for the new run.
1171
1172 // `left < right_start` and `right < right_end`,
1173 // so these are valid.
1174 let to_copy = if compare(&*left, &*right) == Greater {
1175 step(&mut right)
1176 } else {
1177 step(&mut left)
1178 };
1179 ptr::copy_nonoverlapping(&*to_copy, out, 1);
1180 step(&mut out);
1181 }
1182 }
1183 }
1184
1185 mem::swap(&mut buf_dat, &mut buf_tmp);
1186
1187 width *= 2;
1188 }
1189
1190 // write the result to `v` in one go, so that there are never two copies
1191 // of the same object in `v`.
1192 unsafe {
1193 ptr::copy_nonoverlapping(&*buf_dat, v.as_mut_ptr(), len);
1194 }
1195
1196 // increment the pointer, returning the old pointer.
1197 #[inline(always)]
1198 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1199 let old = *ptr;
1200 *ptr = ptr.offset(1);
1201 old
1202 }
1203 }