[
https://issues.apache.org/jira/browse/GROOVY-11649?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17949489#comment-17949489
]
ASF GitHub Bot commented on GROOVY-11649:
-----------------------------------------
dongwq commented on PR #2210:
URL: https://github.com/apache/groovy/pull/2210#issuecomment-2851517853
what about the usage, my q: why rust vec.partition_point is useful if there
is binary_search already?
and copilot give below:
Let me help you understand the difference between `partition_point` and
`binary_search` in Rust's Vec implementation. I'll use semantic code search to
find relevant implementations and examples in the Rust codebase.
Let me explain why `partition_point` is useful even though `binary_search`
exists:
1. Different Return Types and Use Cases:
- `binary_search` returns a `Result<usize, usize>`:
- `Ok(index)` if the element is found
- `Err(index)` where the element should be inserted to maintain
sorting
- `partition_point` returns a single `usize` that represents the first
position where the predicate returns false
2. Finding Ranges:
One of the most important use cases for `partition_point` is finding
ranges of equal elements in a sorted collection. For example, if you have
multiple equal elements:
```rust
let s = [0, 1, 1, 1, 1, 2, 3, 5, 8];
// To find the range of all 1s:
let low = s.partition_point(|x| x < &1); // Returns 1
let high = s.partition_point(|x| x <= &1); // Returns 5
// Now s[low..high] contains all the 1s
assert_eq!(&s[low..high], &[1, 1, 1, 1]);
```
3. More Flexible Predicates:
- `partition_point` works with any predicate that divides the slice into
true/false regions
- `binary_search` is specifically for finding exact matches or insertion
points
4. Cleaner Code for Insertion:
- When you want to insert an element while maintaining sort order,
`partition_point` gives you the position directly
- With `binary_search` you need to handle both `Ok` and `Err` cases,
even though you only care about the position
5. Implementation Detail:
- Interestingly, `binary_search` is actually implemented in terms of
`partition_point` internally in Rust, showing how fundamental the partition
operation is
Here's a practical example showing the difference:
```rust
let vec = vec![1, 2, 2, 2, 3, 4];
// Using binary_search to find a 2:
match vec.binary_search(&2) {
Ok(idx) => println!("Found a 2 at {}", idx), // Will find *some* 2, but
which one?
Err(_) => println!("Not found")
}
// Using partition_point to find ALL 2s:
let start = vec.partition_point(|x| x < &2);
let end = vec.partition_point(|x| x <= &2);
println!("All 2s are in positions {}..{}", start, end); // Gives you the
exact range
```
So while both functions are useful, `partition_point` is particularly
valuable when you need to:
1. Find ranges of equal elements
2. Work with more flexible predicates
3. Get clean insertion points
4. Need a simpler API that doesn't require match statements
> Create partitionPoint extension method variants
> -----------------------------------------------
>
> Key: GROOVY-11649
> URL: https://issues.apache.org/jira/browse/GROOVY-11649
> Project: Groovy
> Issue Type: New Feature
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
> Fix For: 5.x
>
>
> See: https://github.com/apache/groovy/pull/2210
> * rust:
> https://doc.rust-lang.org/std/primitive.slice.html#method.partition_point
> * c++: https://en.cppreference.com/w/cpp/algorithm/ranges/partition_point
> * python: https://docs.python.org/3/library/bisect.html#module-bisect
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
