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 a07690bc669f324155a3f1d2c56f444fb7e17f04..07b45640a522505aff10968073d9a84d420fc5e0 100644 (file)
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -2664,13 +2664,17 @@ pub fn is_sorted_by_key<F, K>(&self, f: F) -> bool
         self.iter().is_sorted_by_key(f)
     }
 
-    /// Returns index of partition point according to the given predicate,
-    /// such that all those that return true precede the index and
-    /// such that all those that return false succeed the index.
+    /// Returns the index of the partition point according to the given predicate
+    // (the index of the first element of the second partition).
     ///
-    /// The slice must be partitioned
-    /// so that all elements where the predicate returns true
-    /// precede the elements where the predicate returns false.
+    /// 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
     ///
@@ -2684,7 +2688,7 @@ pub fn is_sorted_by_key<F, K>(&self, f: F) -> bool
     /// assert!(v[..i].iter().all(|&x| x < 5));
     /// assert!(v[i..].iter().all(|&x| !(x < 5)));
     /// ```
-    #[unstable(feature = "partition_point", reason = "new API", issue = "99999")]
+    #[unstable(feature = "partition_point", reason = "new API", issue = "73831")]
     pub fn partition_point<P>(&self, mut pred: P) -> usize
     where
         P: FnMut(&T) -> bool,
@@ -2694,6 +2698,15 @@ pub fn partition_point<P>(&self, mut pred: P) -> usize
 
         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;
@@ -2701,7 +2714,8 @@ pub fn partition_point<P>(&self, mut pred: P) -> usize
                 right = mid;
             }
         }
-        return left;
+
+        left
     }
 }