Bag (Multiset) Collection

[Holo The Sage Wolf]

Let me prefix this by saying that I'm a mathematician, so maybe the lingo I
use is a bit different. A multi set has no structure apart from "counting
duplication", just like a set has no structure at all, ordered set **is not
a set** and ordered multi set **is not a multi set**.

With the clarification you gave I understand what you mean and retract my
first question (although I believe that "sortedX" or "priorityX" are the
naming Java has for what you called "orderedX").

> THe whole point of the bag is to store duplicate elements without
preserving order, which allows things like ordered collections.

No, the whole point of the bag is to store elements. The difference between
a bag and a list is that a bag has less, anything you can do with a bag you
can do with a list.

The benefit of having a bag is to have a more restrictive interface for the
times you don't need the extra structure, as well as the possible
performant implementation that doesn't need to respect a stricted contract.

CopyOnWriteArratList is more than just a bag.


> then that just adds one more use case to potential Bag interface

Indeed, I gave concurrent bag as an example of a possible implementation of
a bag interface, but you didn't answer my main question, just how common is
a use if a bag to change the std for it?

To me it sounds like you are interested only on the sorted/navigable
variations, so an alternative solution will be to improve PriorityQueue to
have a "subQueue" methods (and friends) as well as extending it to a
Navigable variation.




On Sun, 21 Apr 2024, 00:01 ІП-24 Олександр Ротань, <rotan.olexandr at gmail.com>
wrote:

> Concurrent Bag is something like CopyOnWriteArrayList or Vector, don't we
> have it already? (I know vectors aren't optimized). THe whole point of the
> bag is to store duplicate elements without preserving order, which allows
> things like ordered collections. There could be mutable collections for
> concurrency optimized with read-write locks though, if that is what you are
> referring to as "concurrent bag", and I am missing the point why this
> can't be a part of list interface, then that just adds one more use case to
> potential Bag interface.
>
> PS: Ordered means it preserves order based on comparator, what you are
> referring to as ordered essentially means sequential, or am I missing a
> point?
>
> сб, 20 апр. 2024 г. в 23:52, Holo The Sage Wolf <holo3146 at gmail.com>:
>
>> By "ordered collection" you mean "unordered collection"?
>>
>> How common is it to actually use a multiset in general? Of course there
>> are use cases, and there are areas in which it is used a lot, but I don't
>> believe it is common enough to be part of the std with the one exception of
>> concurrent bag.
>>
>> On Sat, 20 Apr 2024, 23:25 ІП-24 Олександр Ротань, <
>> rotan.olexandr at gmail.com> wrote:
>>
>>> In this letter I would like to express some of my thoughts regarding the
>>> potential Multiset interface.
>>>
>>> I, personally, have encountered a few situations where such an interface
>>> could come in handy, mostly when I needed an ordered collection that
>>> permits duplicates. That time I used guava`s TreeMultiset, but I think Java
>>> itself should have such a collection in its std library. While it is not a
>>> very common problem, there are still a bunch of use cases where such things
>>> could come in handy.
>>>
>>> I am willing to take on development of such thing, but there are a few
>>> concerns about Multiset:
>>>
>>> 1. Is there any other use for this besides ordered collection that
>>> permits duplicates? I can't remember anything else from the top of my head.
>>>
>>> 2. Guava's TreeMultiset class hierarchy pretty much imitates TreeSet
>>> class hierarchy, while not being directly connected. I think introducing
>>> any other ordered collection will require some refactoring of existing
>>> collection interfaces (for example extract SortedCollection from SortedSet,
>>> Navigable Collection from NavigableSet etc.). From the perspective of clean
>>> code, this would be the right decision, but I feel like this will be a very
>>> complex task to accomplish.
>>>
>>> 3. Maybe there should be few versions of Tree collection (for example,
>>> for regular tasks red-black tree and B-Tree for large amounts of data). I
>>> have some expirience implementing both, but is it really needed in standard
>>> library?
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240421/5d872439/attachment-0001.htm>