From 4f7a3fba59269a2b37b78655a10778ba5af796bd Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
Date: Thu, 23 Jul 2020 12:59:18 +0200
Subject: Replace superslice with API on path to stabilization

---
 crates/stdx/src/lib.rs | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

(limited to 'crates/stdx')

diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index 988853ed2..ea0e6b949 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -158,6 +158,36 @@ impl<'a> Iterator for LinesWithEnds<'a> {
     }
 }
 
+// https://github.com/rust-lang/rust/issues/73831
+pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
+where
+    P: FnMut(&T) -> bool,
+{
+    let mut left = 0;
+    let mut right = slice.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 either 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 { slice.get_unchecked(mid) };
+        if pred(value) {
+            left = mid + 1;
+        } else {
+            right = mid;
+        }
+    }
+
+    left
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
-- 
cgit v1.2.3