Bag (Multiset) Collection

[-]

>
> 1. Batch tasks processing, especially in concurrent environments, when
> tasks could have different priorities. Sometimes tasks that are stored in a
> queue are processed in batches. Using today's stdlib of Java,
> acquiring such a batch of tasks from collection would be a O(n * log n)
> complexity, because each heapification is log n and called after each task
> is popped. Using TreeMultiset, this could be achieved in log (n). This also
> applies to messaging.
>
This is a good point. There's no way for users to attach tree node metadata
that are maintained when a BST is rebalanced, so having a rank operation
for a Tree Multiset is quite helpful. Unfortunately, not even google guava
supports this operation, but this is technically easy to implement.

I think this is the main advantage of a Multiset over regular Map<T,
Collection<T>> implementations. However, given Java's TreeMap doesn't even
support getting element by rank (its RBTree nodes don't record size), we
might have to start with adding size to RBTree nodes first.

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240420/8a617205/attachment-0001.htm>