[
https://issues.apache.org/jira/browse/GROOVY-11649?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17949224#comment-17949224
]
Paul King edited comment on GROOVY-11649 at 5/5/25 9:52 AM:
------------------------------------------------------------
When working with sorted aggregates (lists, arrays, etc.) many languages
provide methods to calculate an index to insert into the aggregate and maintain
the sort order.
For example, suppose we want to insert the number 1 into the following list:
{code:groovy}
def s = [0, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 8]
{code}
We can insert the 1 anywhere from index 1 to index 8 and the sort order will be
maintained.
In Python, bisect_left(1) returns 1, and bisect_right(1) returns 8.
In C++, lower_bound(1) returns 1, and upper_bound(1) returns 8. Rust provides a
binary_search which will return some number between 1 and 8. Java has
Arrays.binarySearch which returns 5 (and can return a negative number to
indicate that the actual result wasn't found but can then never-the-less be
used to work out where to insert).
The {{partitionPoint}} method is a generalisation of the above mentioned
methods.
So, for our example,
{code:groovy}
def low = s.partitionPoint{ it < 1 } // equiv to bisect_left/lower_bound
assert low == 1
def high = s.partitionPoint{ it <= 1 } // equiv to bisect_right/upper_bound
assert high == 8
assert Arrays.binarySearch(s, 1) in low..high
// anything above all existing values will always be inserted at the end
assert s.partitionPoint{ it <= 20 } == s.size()
assert (Arrays.binarySearch(s, 20) + 1).abs() == s.size()
// low == high when the element isn't found (there is exactly one spot we
should insert)
low = s.partitionPoint{ it < 4 }
high = s.partitionPoint{ it <= 4 }
assert low == high
{code}
But partitionPoint is even more general than it might first appear. It doesn't
require the elements in the aggregate to be sorted, but just partitioned in
some way.
Groovy's sort variants that take a closure allow such partitioning.
As an example, let's sort the numbers in a list into even and odd (using the
mutating variant of sort):
{code:groovy}
def even = { it % 2 == 0 }
def odd = { it % 2 != 0 }
def list = [4, 7, 15, 12, 6, 3, 5]
list.sort(even)
assert list == [7, 15, 3, 5, 4, 12, 6]
{code}
Now supposed we want to add more numbers into this list. We can add them and
re-sort, but {{partitionPoint}} let's us know where to add to retain the sorted
properties:
{code:groovy}
def additions = [1, 6, 8, 7]
additions.each {
def idx = list.partitionPoint(odd)
list.add(idx, it)
}
assert list == [7, 15, 3, 5, 1, 7, 8, 6, 4, 12, 6]
{code}
The partitionPoint method is also useful when processing partitioned data:
{code:groovy}
def idx = list.partitionPoint(odd)
assert list[0..<idx].every(odd)
assert list[idx..-1].every(even)
{code}
Does Java offer some better way to do this? It does offer the {{PriorityQueue}}
and this means there is no need for {{partitionPoint}} to insert into such a
collection, but it is a little cumbersome to use:
{code:groovy}
def evenComparator = { a, b -> (a % 2 == 0) <=> (b % 2 == 0) }
def ordered = new PriorityQueue(evenComparator)
ordered.addAll([4, 7, 15, 12, 6, 3, 5])
ordered.addAll(additions)
println ordered.toList() // [7, 1, 15, 4, 7, 3, 5, 12, 6, 8, 6]
while(!ordered.empty) {
println ordered.poll()
} // 7 1 7 15 3 5 6 6 4 12 8
assert ordered.empty
{code}
The standard iterator ordered doesn't follow the priority. The "poll" method
can be used but the queue will be exhausted of elements after using it.
What about arrays? We can sort non-primitive arrays (and processing can make
use of {{partitionPoint}}):
{code:groovy}
Integer[] array = [4, 7, 15, 12, 6, 3, 5]
array.sort(true, evenComparator)
assert array == [7, 15, 3, 5, 4, 12, 6]
idx = array.partitionPoint(odd)
assert array[0..<idx].every(odd)
assert array[idx..-1].every(even)
{code}
But, we currently don't have sort variants for primitive arrays. Arrays.sort is
available without the comparator, but no variant with comparators exist. This
alone doesn't make partitionPoint less useful, but since arrays are of fixed
size, we also don't have the ability to insert an extra into an array at a
given index. I think this makes {{partitionPoint}} less useful for arrays in
general.
was (Author: paulk):
The {{partitionPoint}} method is handy when you have some kind of partitioned
aggregate and you want to insert into the aggregate while maintaining the
partitions. Often, this will mean you have a sorted list and you want to insert
while maintaining the sort order.
Groovy's sort variants give you lists that could benefit from this method.
Consider this example (we'll use the mutating variant):
{code:groovy}
def even = { it % 2 == 0 }
def odd = { it % 2 != 0 }
def list = [4, 7, 15, 12, 6, 3, 5]
list.sort(even)
assert list == [7, 15, 3, 5, 4, 12, 6]
{code}
Now supposed we want to add more numbers into this list. We can add them and
resort, but {{partitionPoint}} let's us know where to add to retain the sorted
properties:
{code:groovy}
def additions = [1, 6, 8, 7]
additions.each {
def idx = list.partitionPoint(odd)
list.add(idx, it)
}
assert list == [7, 15, 3, 5, 1, 7, 8, 6, 4, 12, 6]
{code}
It is also useful for working with the partitions:
{code:groovy}
def idx = list.partitionPoint(odd)
assert list[0..<idx].every(odd)
assert list[idx..-1].every(even)
{code}
Does Java offer some better way to do this? It does offer the {{PriorityQueue}}
and this means there is no need for {{partitionPoint}} to insert into such a
collection, but it is a little cumbersome to use:
{code:groovy}
def evenComparator = { a, b -> (a % 2 == 0) <=> (b % 2 == 0) }
def ordered = new PriorityQueue(evenComparator)
ordered.addAll([4, 7, 15, 12, 6, 3, 5])
ordered.addAll(additions)
println ordered.toList() // [7, 1, 15, 4, 7, 3, 5, 12, 6, 8, 6]
while(!ordered.empty) {
println ordered.poll()
} // 7 1 7 15 3 5 6 6 4 12 8
assert ordered.empty
{code}
The standard iterator ordered doesn't follow the priority. The "poll" method
can be used but the queue will be exhausted of elements after using it.
What about arrays? We can sort non-primitive arrays (and processing can make
use of {{partitionPoint}}):
{code:groovy}
Integer[] array = [4, 7, 15, 12, 6, 3, 5]
array.sort(true, evenComparator)
assert array == [7, 15, 3, 5, 4, 12, 6]
idx = array.partitionPoint(odd)
assert array[0..<idx].every(odd)
assert array[idx..-1].every(even)
{code}
But, we currently don't have sort variants for primitive arrays. Arrays.sort is
available without the comparator, but no variant with comparators exist. This
alone doesn't make partitionPoint less useful, but since arrays are of fixed
size, we also don't have the ability to insert an extra into an array at a
given index. I think this makes {{partitionPoint}} less useful for arrays in
general.
> 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)
