Update tracking issue number

[rust.git] / src / libcore / slice / mod.rs

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 4efb1db7a1a68b1cb3c7da985ac9719c91804043..07b45640a522505aff10968073d9a84d420fc5e0 100644 (file)
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -2663,6 +2663,60 @@ pub fn is_sorted_by_key<F, K>(&self, f: F) -> bool
     {
         self.iter().is_sorted_by_key(f)
     }
+
+    /// Returns the index of the partition point according to the given predicate
+    // (the index of the first element of the second partition).
+    ///
+    /// The slice is assumed to be partitioned according to the given predicate.
+    /// This means that all elements for which the predicate returns true are at the start of the slice
+    /// and all elements for which the predicate returns false are at the end.
+    /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0
+    /// (all odd numbers are at the start, all even at the end).
+    ///
+    /// If this slice is not partitioned, the returned result is unspecified and meaningless,
+    /// as this method performs a kind of binary search.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(partition_point)]
+    ///
+    /// let v = [1, 2, 3, 3, 5, 6, 7];
+    /// let i = v.partition_point(|&x| x < 5);
+    ///
+    /// assert_eq!(i, 4);
+    /// assert!(v[..i].iter().all(|&x| x < 5));
+    /// assert!(v[i..].iter().all(|&x| !(x < 5)));
+    /// ```
+    #[unstable(feature = "partition_point", reason = "new API", issue = "73831")]
+    pub fn partition_point<P>(&self, mut pred: P) -> usize
+    where
+        P: FnMut(&T) -> bool,
+    {
+        let mut left = 0;
+        let mut right = self.len();
+
+        while left != right {
+            let mid = left + (right - left) / 2;
+            // SAFETY:
+            // When left < right, left <= mid < right.
+            // Therefore left always increases and right always decreases,
+            // and eigher of them is selected.
+            // In both cases left <= right is satisfied.
+            // Therefore if left < right in a step,
+            // left <= right is satisfied in the next step.
+            // Therefore as long as left != right, 0 <= left < right <= len is satisfied
+            // and if this case 0 <= mid < len is satisfied too.
+            let value = unsafe { self.get_unchecked(mid) };
+            if pred(value) {
+                left = mid + 1;
+            } else {
+                right = mid;
+            }
+        }
+
+        left
+    }
 }
 
 #[lang = "slice_u8"]
@@ -3043,16 +3097,12 @@ impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
 
     #[inline]
     fn get(self, slice: &[T]) -> Option<&[T]> {
-        if *self.end() == usize::max_value() {
-            None
-        } else {
-            (*self.start()..self.end() + 1).get(slice)
-        }
+        if *self.end() == usize::MAX { None } else { (*self.start()..self.end() + 1).get(slice) }
     }
 
     #[inline]
     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
-        if *self.end() == usize::max_value() {
+        if *self.end() == usize::MAX {
             None
         } else {
             (*self.start()..self.end() + 1).get_mut(slice)
@@ -3071,7 +3121,7 @@ unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 
     #[inline]
     fn index(self, slice: &[T]) -> &[T] {
-        if *self.end() == usize::max_value() {
+        if *self.end() == usize::MAX {
             slice_index_overflow_fail();
         }
         (*self.start()..self.end() + 1).index(slice)
@@ -3079,7 +3129,7 @@ fn index(self, slice: &[T]) -> &[T] {
 
     #[inline]
     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
-        if *self.end() == usize::max_value() {
+        if *self.end() == usize::MAX {
             slice_index_overflow_fail();
         }
         (*self.start()..self.end() + 1).index_mut(slice)