aboutsummaryrefslogtreecommitdiff
path: root/crates/stdx/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/stdx/src')
-rw-r--r--crates/stdx/src/lib.rs30
1 files changed, 30 insertions, 0 deletions
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> {
158 } 158 }
159} 159}
160 160
161// https://github.com/rust-lang/rust/issues/73831
162pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
163where
164 P: FnMut(&T) -> bool,
165{
166 let mut left = 0;
167 let mut right = slice.len();
168
169 while left != right {
170 let mid = left + (right - left) / 2;
171 // SAFETY:
172 // When left < right, left <= mid < right.
173 // Therefore left always increases and right always decreases,
174 // and either of them is selected.
175 // In both cases left <= right is satisfied.
176 // Therefore if left < right in a step,
177 // left <= right is satisfied in the next step.
178 // Therefore as long as left != right, 0 <= left < right <= len is satisfied
179 // and if this case 0 <= mid < len is satisfied too.
180 let value = unsafe { slice.get_unchecked(mid) };
181 if pred(value) {
182 left = mid + 1;
183 } else {
184 right = mid;
185 }
186 }
187
188 left
189}
190
161#[cfg(test)] 191#[cfg(test)]
162mod tests { 192mod tests {
163 use super::*; 193 use super::*;