Create a Multimap

[danieldietrich]

We have to make a decision about the type of container that holds values. Scala uses Set but I would use Traversable like in Guava. This allows us to store the same values in containers in certain multimap implementations. On the other side, using the Set as container is much easier to implement and much shorter API

[danieldietrich]

Hi Ruslan,
yes, that's a tough decision to make. I like the idea to have different value container types. But in order to benefit from it, the values() method should return a Traversable of the correct type. This is only possible, if the Multimap is aware of the type by specifiying an additional generic:

interface MultiMap<K, V, TYPE extends Traversable<V>> {
    TYPE values();
}

We could have factory methods for the default-value container Set:

static <...> Multimap<..., Set<V>> empty();
static <...> Multimap<..., Set<V>> ofEntries(...);
...

Because we need appropriate create and add methods for construction and element addition, we could pre-define known Traversable types that can be used as value-containers. These enum knows all necessary operations.

interface Multimap {

    enum Type {

        INDEXED_SEQ(Vector::new, Vector::append),
        LINEAR_SEQ(...),
        SET(...),
        SORTED_SET(...)

        Type(...) {
            ...
        }
    }

    static Multimap<..., Set<V>> empty(Type type);
    static Multimap<..., Set<V>> ofEntries(Type type, ...);
    ...
}

To have the most flexibility, we could provide also a factory method that allows to create arbitrary value containers:

static <...> Multimap<..., Set<V>> empty(Supplier<TYPE> unit, BiFunction<TYPE, V, TYPE> add);

// maybe we omit all other factory methods for the general case to keep it simple?
// static <...> Multimap<..., Set<V>> ofEntries(...);
...

[ruslansennov]

interface MultiMap<K, V, TYPE extends Traversable<V>>

Yes, I thought about it.
OK, let's make the big Zoo of Multimap's implementations :)

[danieldietrich]

Cool, one Multimap will rule all :-)

[talios]

My original naive implementation was https://gist.github.com/talios/97c27fe577894e96cc46 - which was basically doing the bare minimum of what I was wanting. And when I say naive - I mean incredibly so :)

[ruslansennov]

partly blocked by #1132

[ruslansennov]

Backed by	Container	Multimap
HashMap	HashSet	HashMultimapSet
HashMap	List	HashMultimapSeq
LinkedHashMap	LinkedHashSet	LinkedMultimapSet
LinkedHashMap	List	LinkedMultimapSeq
TreeMap	HashSet	TreeMultimapSet
TreeMap	List	TreeMultimapSeq

MultimapSeq can store duplicate key-value pairs unlike MultimapSet

[danieldietrich]

Why can't we have just HashMultimap, LinkedMultimap and TreeMultimap?

I guess it is because Seq and Set are orthogonal return types and they can't be overridden? Do you have examples where it does not work?

I think the Seq/Set return type problem could be solved if we make use of Kind1<..., ...> for the container type... but I have to see where it clashes.

(Btw Kind has to be properly implemented by all Javaslang classes, I will do that)

[danieldietrich]

Backed by	Container	Multimap
HashMap	(appropritate traversables)	HashMultimap
LinkedHashMap	(appropritate traversables)	LinkedMultimap
TreeMap	(appropritate traversables)	TreeMultimap

If we specifiy the container type at construction type, e.g.

HashMultimap.emptyWithSeq(); // List is chosen
HashMultimap.emptyWithSet(); // HashSet is chosen

or

import javaslang.collection.TreeMultimap.ContainerType.*;

TreeMultimap.empty(SEQ); // List is chosen
TreeMultimap.empty(SET); // TreeSet is chosen

[ruslansennov]

I think the Seq/Set return type problem could be solved if we make use of Kind1<..., ...> for the container type... but I have to see where it clashes.

I will check it

TreeMultimap.empty(SEQ); // List is chosen
TreeMultimap.empty(SET); // TreeSet is chosen

Yes, looks good 👍

P.S. I saw your comment about deadline at 15.03.2016 and I believe Multimap will be ready

[danieldietrich]

Ok - let's try to meet that date. I've s.th. todo with Match, too. If you need longer it should be no problem.

[patrox]

@danieldietrich is there something which I could help you guys with ?

[danieldietrich]

Until release we have two things: Pattern Matching (me on it) + Multimap (Ruslan on it). I think helping out with the features makes not much sense at this state because they are under 'heavy' development, right @ruslansennov?

But... tests, tests, tests! We aim 100% coverage and there is still much missing. A helping hand would be awesome!

[ruslansennov]

they are under 'heavy' development

Multimap mostly done...

[patrox]

ok, then I'll try to add some tests - is there an easy way to check which fragments of code are not covered ?

[ruslansennov]

@patrox just click on codecov badge

[patrox]

thanks @ruslansennov , I've already started to drill down to sub directories to find some blind spots.

[danieldietrich]

great!

[ruslansennov]

Multimap mostly done...

haha...

Why can't we have just HashMultimap, LinkedMultimap and TreeMultimap?

I have no idea how this can be implemented 😞

For example, Multimap.get(key) can't return Traversable<V> because it is unsafe. And we can't use Kind1<T, V> as return type because it not works in Multimap.flatMap(BiFunction)

Current state you can see in my branch 'multimap'

[danieldietrich]

I know that feeling - 99% are straight forward, but the last 1%... I will take a look!

[danieldietrich]

I've created a workspace with your branch and started reading the code. The type signatures of the classes / interfaces look good.

Multimap.get(key) could return T, which is Traversable<V> and safe. Do we return an empty collection instead of an empty Option if the key is not present? Just asking, I don't know because I haven't used multimaps yet.

I would remove the MutlimapImpl.Factory interface to save the factory instance variable (also removed). The methods of the Factory interface can be protected abstract in MultimapImpl and be overridden by subclasses.

[danieldietrich]

And we can't use Kind1<T, V> as return type

I've thought about it. We should not use Kind1 or Kind2 in the Multimaps at all. It introduces problems. (It should be only used as marker interface which can be further used in javaslang-algebra.)

[ruslansennov]

Do we return an empty collection instead of an empty Option if the key is not present?

empty Option

I would remove the MutlimapImpl.Factory interface to save the factory instance variable (also removed). The methods of the Factory interface can be protected abstract in MultimapImpl and be overridden by subclasses.

Of course, it is just stub...

[danieldietrich]

Then Option<T> get(K key); should work fine. If needed it can be Option<? extends T>. Then we can build Multimap hierarchies greater than one level (same as we've done with Traversable -> Set -> SortedSet -> TreeSet for example).

For example, Multimap.get(key) can't return Traversable because it is unsafe.

I still not fully understand it. Is it not good to return Option<T> with T extends Traversable<V>?

[danieldietrich]

Btw - I'm pretty impressed! The code looks great :-) Nice implementation.

[ruslansennov]

Is it not good to return Option with T extends Traversable?

It is good! And it works fine everywhere except Multimap.flatMap()/biMap()/etc because it must return T2 extends Traversable<V2>. And must be same type of Traversable, like T.
I tried to use Kind1, but it doesn't work

[danieldietrich]

Ok, now I understand. I check that...

[danieldietrich]

It is not possible because of the lack of higher-kinded types / type constructors in Java.

We have two (practicable) options:

1) Create specific implementations for all possible value container types.

--> I'm no friend of that. I think multimaps are rarely used compared to other collections. If they count more than all other collections summed up it would not be good for the readability of the collection library.

2) We just use Traversable<V> instead of ? extends Traversable<V>.

--> We may add check methods for characteristics, such as

• Traversable.isDistinct() // Set, Map
• Traversable.isOrdered() // SortedSet, SortedMap
• Traversable.isSequential() or isInsertionOrder() // Seq, Iterator, Tree?, LinkedHashSet?, LinkedHashMap?

These in conjunction with conversion methods toList, toSet etc. will provide us with all the flexibility to handle values.

What do you think? 2) or 2)? ;-)

Update: internally the multimap of course still uses a specific Traversable impl. I think we still need the factory instance you implemented. I will look into that tomorrow. Need sleep! The last days were a little bit exhausting...

[ruslansennov]

[ruslansennov]

Now Multimap has only 2 generics and it is good (branch updated)

[danieldietrich]

Fine, looks good!

I'm looking forward to the code review. I've seen some minor things:

• in Multimap.forEach we need generics: default void forEach(BiConsumer<? super K,? super V> action)
• we should consider to rename MultimapImpl to AbstractMultimap. Then it is the same as AbstractMap.
• I'm still not convinced about the additional Lazy fields in our collections. It eats memory. I don't care about the performance of the size method. It is not needed, e.g. to iterate collections. But to get sure what is the best practice here we should take a look at other (immutable) Multimap implementations.
• It would be great to get rid of the additional factory field:
  • the Factory methods that return Map and Multimap can move as protected abstract methods into AbstractMultimap
  • String containerName() is the same as emptyContainer().stringPrefix() I think (should be)
  • I would replace the rest of the Factory (i.e. emptyContainer(), addToContainer(..) and removeFromContainer(...)) by something like this:

    enum Container {

        SET(HashSet::empty, (Set<Object> set, Object elem) -> set.add(elem), (Set<Object> set, Object elem) -> set.remove(elem)),
        SORTED_SET(TreeSet::empty, ...),
        SEQ(List::empty, ...);

        final Supplier<Traversable<?>> emptySupplier;
        final BiFunction<Traversable<?>, Object, Traversable<?>> add;
        final BiFunction<Traversable<?>, Object, Traversable<?>> remove;

        <T> Container(Supplier<Traversable<?>> emptySupplier,
                      BiFunction<? extends Traversable<?>, Object, Traversable<?>> add,
                      BiFunction<? extends Traversable<T>, T, Traversable<T>> remove) {
            this.emptySupplier = emptySupplier;
            this.add = add;
            this.remove = remove;
        }

        @SuppressWarnings("unchecked")
        <T> Traversable<T> empty() {
            return (Traversable<T>) emptySupplier.get();
        }

        @SuppressWarnings("unchecked")
        <T> Traversable<T> add(Traversable<T> container, T elem) {
            return (Traversable<T>) add.apply(container, elem);
        }

        @SuppressWarnings("unchecked")
        <T> Traversable<T> remove(Traversable<T> container, T elem) {
            return (Traversable<T>) remove.apply(container, elem);
        }
    }

I'm in a hurry and can't get the generics right. But should be possible somehow...

[danieldietrich]

Hey @ruslansennov,

I want to prepare closed shop for 2.0.0 final. Is it ok to take the Multimap to 2.1.0 which should be short after 2.0.0 (e.g. 1 month?). Then we have time to test. Once we are final with 2.0.0 I don't want to modify existing interface methods if possible. (However, I will take a last look at the Xxx.match() methods).

The next days I will concentrate on the web-page and the documentation.

Is that ok for you?

[ruslansennov]

Fine, let's move it to 2.x.x

[danieldietrich]

Ok, will do it.

[danieldietrich]

Done by Ruslan in #1240