Adds asSet() to Bag for #726

[victornoel]

⚠️ Edit: all of this is outdated, see #869 for the latest design ⚠️

Finally had the time to finish my PR for #726.

I made the following design decisions:

• The different Bag interfaces exposes asSet() which is a view on the unique elements of the bag
• They are either a SetIterable or a MutableSet
• I didn't tackle returning sorted o immutable variants because
• implementing it was way too complex
• this is not the primary use case for accessing a Bag as a Set IMHO
• The synchronized, unmodifiable and multi reader variants are implemented though
• Only for ImmutableArrayBag and ImmutableSortedBagImpl, I had to implement it by subclassing AbstractImmutableSet inline: since they are both based on arrays, I only implemented the minimum because I don't think it would have much impact on performance to do more.

One open question is: should the inline subclassing be extracted in a separate class that wraps an array maybe?

[motlin]

The main feedback is that returning mutable views breaks bag invariants.

[victornoel]

@motlin any feedbacks on the best way to tackle the problems discussed above?

[motlin]

@victornoel my recommendation would still be to just use SetIerable for now. That way the interface doesn't promise to return a MutableSet in places where you'd expect to be able to mutate but we can't yet support it. It's a step in the right direction and we can always support mutation in another major version.

[victornoel]

@motlin yes, I will go with that then, thanks

[victornoel]

@motlin one more advice request: if we use SetIterable everywhere, it becomes difficult to take advantage of existing Synchronized and Unmodifiable wrappers for mutable sets, what do you recommend? Writing some for SetIterable itself?

[victornoel]

Okay, so I pushed a final version with:

• read only sets as result of asSet:
  • SetIterable for all various MutableBag
  • corresponding Immutable and Sorted and so on for all the non mutable bags.
• for multireader and synchronized bags, I had to add SynchronizedSetIterable and SynchronizedParallelSetIterable classes

[motlin]

This seems out of place.

[victornoel]

@motlin why is that? Maybe we don't want to test for being in instance of Set and let AbstractCollectionAdapter define equals directly?

[motlin]

Why does this catch exceptions? Can we have hashcode here too?

[victornoel]

@motlin some of the implementations of equals that rely on Collection.containsAll do catch those exception because Collection.containsAll document them and if they are thrown, it's not an error, it means the element are not contained (because of different types or things like that).

I can add hashCode, I didn't because I expected that all subclass should be more relevant to implement it, but if I add it, I'm not sure what is the best default implementation? An hashCode of all elements?

[victornoel]

@motlin concerning hashCode, actually findbugs is complaining about it, so I moved it to the two subclasses that needed it.

[motlin]

Seems out of place

[victornoel]

@motlin what do you mean? Should I move equals and hashCode to AbstractCollectionAdapter maybe? But I wouldn't be able to test for instance of Set though

[motlin]

I see the problem with the types. If the view has no way of supporting mutation, then it's ok.

…

On Sat, Mar 14, 2020 at 2:10 PM Victor Noël ***@***.***> wrote: ***@***.**** commented on this pull request. ------------------------------ In eclipse-collections/src/main/java/org/eclipse/collections/impl/bag/mutable/UnmodifiableBag.java <#797 (comment)> : > @@ -438,4 +439,10 @@ protected Object readResolve() { return this.getMutableBag().selectUnique(); } + + @OverRide + public SetIterable<T> asSet() + { + return this.getMutableBag().asSet(); @motlin <https://github.com/motlin> I can't call asUnmodifiable() because the return type of asSet() here is SetIterable: I am expecting it to be unmodifiable if needed be. I will add a test to ensure it is the case though! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#797 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAB3UISK25LGG5O7AM2UEH3RHPB7RANCNFSM4KV2JJUA> .

[motlin]

Using inner class views makes me nervous, especially in the immutable collections. I was imagining a class like SetFromBagAdapter that's almost like SetAdapter, but implemented by delegating to a Bag. As long as it doesn't delegate to a MutableBag, we can have high confidence that it never allows mutation as well as unsynchronized access.

[victornoel]

@motlin trying back to work on this, you said:

Using inner class views makes me nervous, especially in the immutable collections. I was imagining a class like SetFromBagAdapter that's almost like SetAdapter, but implemented by delegating to a Bag. As long as it doesn't delegate to a MutableBag, we can have high confidence that it never allows mutation as well as unsynchronized access.

How would that work? In order to implement SetFromBagAdapter by delegating to a Bag I would need to be able to access the internal of the bag... or do you mean that it is created by passing to it the underlying datastructure used inside the bag? the array or the map, depending on the implementation?

[victornoel]

@motlin I have pushed some changes that I think all together make sense, here is a rundown of the changes that could raise discussion and rationale for the choices I made:

• I extracted the internal classes into their own file as you proposed
  • ImmutableSetAdapter wraps any UnsortedSetIterable and is used by ImmutableHashBag
    • I tried to override what was needed to have best performances
  • ImmutableSetFromArrayBagAdapter wraps the array of a ImmutableArrayBag directly
    • this could also be moved to set package and called ImmutableArraySetAdapter or something like that but I feel like it's better if it stays hidden next to the class using it
  • same for ImmutableSortedSetFromArrayBagAdapter.
  • we can't just have a simple ImmutableSetFromBagAdapter because it would need asSet() to be implemented (and that would lead to risk of strange infinite loops :)
  • I'm not sure how the serialization stuffs work in there, so I may have made mistakes...
• MutableBag.asSet() returns MutableSet
  • they all are unmodifiable for now: we should create a new issue to tackle this later.
  • it is mainly needed to elegantly take advantage of all the MutableSet decorators for synchronized, unmodifiable, multi reader, etc without pain. I tried many times in the previous iterations to do without it, but there always was a problem somewhere so I think it's best to return MutableSet and for now not honour the mutability contract of it.
• MutableSortedBag does not return MutableSortedSet
  • because of MutableSortedMap.keySet contract
  • I added comments there for now but maybe there is something else to be done so that this can go on?
  • this is the only place where it would be needed to change the signatures of interface methods in the future
• MultiReaderBag returns MultiReaderSet
  • I added a MultiReaderSetAdapter that share most of its implementation with MultiReaderUnifiedSet (shared in in AbstractMultiReaderSet).
  • I'm not sure how the serialization stuffs work in there, so I may have made mistakes...

[motlin]

we can't just have a simple ImmutableSetFromBagAdapter because it would need asSet() to be implemented (and that would lead to risk of strange infinite loops :)

Can't it return this?

MutableSet.asSet() returns MutableBag

Something sounds backwards in this sentence

ImmutableSetAdapter wraps any UnsortedSetIterable

This isn't what I meant - I'll have to take a closer look. Why does the wrapper need access to the Bag internals?

[victornoel]

@motlin

Can't it return this?

what I mean is that if you wrap a bag, to implement some of the set method, you need to have access to the underlying datatstructure, for example to implement iterator, and in our situation there are two cases when this happens:

• for ImmutableArrayBag, in this case you need access to the array
  • That's why I introduced ImmutableSetFromArrayBagAdapter and also ImmutableSortedSetFromArrayBagAdapter
• for ImmutableHashBag, in this case you can indeed have an hypothetical ImmutableSetFromBagAdapter that takes the hidden mutable HashBag and then call asSet() on it, but if you pass it this, it will go into infinite loop of course
  • That's why I introduced ImmutableSetAdapter that introduces no risks but allow to achieve the same objective in a more generic way.

MutableSet.asSet() returns MutableBag

Something sounds backwards in this sentence

it was, I will fix my comment :)

[motlin]

I tried to write a set-from-bag adapter to see how feasible it is. It's nearly possible, it would need one new method on Bags for a distinct keys view. Take a look at the iterator() method to see what I mean.

public class SetFromBagAdapter<T>
        extends AbstractImmutableSet<T>
{
    private final Bag<T> bag;

    public SetFromBagAdapter(Bag<T> bag)
    {
        this.bag = bag;
    }

    @Override
    public int size()
    {
        return this.bag.sizeDistinct();
    }

    @Override
    public T getFirst()
    {
        return this.bag.getFirst();
    }

    @Override
    public T getLast()
    {
        return this.bag.getLast();
    }

    @Override
    public void each(Procedure<? super T> procedure)
    {
        this.bag.forEachWithOccurrences((each, parameter) -> procedure.accept(each));
    }

    @Override
    public Iterator<T> iterator()
    {
        // This works but is inefficient. It really creates the map in O(n) time and space.
        Iterator<T> iterator = this.bag.toMapOfItemToCount().keysView().iterator();

        // This doesn't work today, but it could without too much effort.
        return this.bag.distinctView().iterator();
    }
}

[motlin]

The in places like AbstractHashBag, it's pretty easy to implement the distinct view.

    @Override
    public RichIterable<T> distinctView()
    {
        return this.items.keysView();
    }

[victornoel]

@motlin if you look back at the issue #726 that spawned this whole PR, this keyView is the reason it exists :) so yes, a keyView() would be useful, but implementing means doing all that was done here.

[motlin]

I did forget that context but I think this shows we can implement both with just a few lines of code?

[victornoel]

@motlin no, because of all the other implementation of Bag that do not rely on a Map as in your example. For example ImmutableArrayBag is such an example. Let's also not forget that we want to have a O(1) method asSet, if I just want to be able to iterate on the distinct keys, as you said, I can always use toMapOfItemToCount but it's not efficient.

The purpose of this PR is to:

• implement such distinct key method, we decided in Distinct element view of Bag  #726 that it was a Set view of the map
• that it behave in O(1), that's why the name of the method starting with as

Hence this proposal for asSet.

Honestly I've tried many alternative to arrive to this solution, with various iterations that can we witnessed here, I think we did go around all the possibilities and that the design proposed here is the best. Maybe to better understand that, it would make sense for you to play with the code and experience with the alternative you propose to either see why it doesn't work or to show me how it would work.

[victornoel]

Closing this as this will most certainly never be merged and based on very outdated code