generics-question about sets and collections

[Piet Souris]

Just when you thought you knew it all...

var s = new HashSet<String>();
System.out.println(s instanceof Collection<String>);
System.out.println(s instanceof Set<String>);

prints true in both cases.

Why is this an error?

var t = new HashMap<String, HashSet<String>>();
System.out.println(t instanceof HashMap<String, Set<String>>);

I have this method:

public static <T> Set<Set<T>> getFullConnectedSubLists(Map<T, Collection<T>> map) {...}

meant to be called for Lists and Sets. How do I get that to work?

edit:
found the solution. I must use

public static <T, S extends Collection<T>> Set<Set<T>> getFullConnectedSubLists(Map<T,S> map) {...}

Never too old to learn.

[Tim Holloway]

Gnarly!

I've never been one to shy at stacking complex expressions, but I generally like to simplify the grammar on stuff like that, both for readability and to make it harder to fat-finger intermediate types.

For example:

class StringHashSet extends HashSet<String> {}
class StringHashMap extends HashMap<String, StringHashSet>{}

var t = new StringHashMap();

Use private classes, if you prefer, and of course add methods if they make life easier.

[Rob Spoor]

Piet Souris wrote:edit:
found the solution. I must use

public static <T, S extends Collection<T>> Set<Set<T>> getFullConnectedSubLists(Map<T,S> map) {...}

Never too old to learn.

There's another way that also makes the map's value type not-Collection-but-compatible-with:

public static <T> Set<Set<T>> getFullConnectedSubLists(Map<T, ? extends Collection<T>> map) {...}

[Tim Holloway]

Just to add. If the point is to obtain a Set of all the StringHashSets (as defined above), then it's a lot simpler to just invoke the StringHashMap.entrySet() method.

Actually, I mis-named StringHashMap. It would be better named String[Hash]SetHashMap. Or more abstractly, StringSetMap.

[Piet Souris]

Thanks for the responses, guys!

@Rob,

problem with "? extends Collection<T>"is that I need to do a map.get(t) somewhere, and there I need to specify some type.

It is about Advent Of Code 2024, day 23. I used a HashMap<String, HashSet<String>> hardcoded, and I had in mind to generalize this someday.
I had in my opening post this (I already changed the "Collection<T>"to the thing with S extends...):

public static <T, S extends Collection<T>> Set<Set<T>> getFullConnectedSubsets2(Map<T, S> map) {
    var result = new HashSet<Set<T>>();
    for (var s: map.keySet()) {
        var set = new HashSet<T>();
        set.add(s);
        gFCSHelper2(map, result, set, map.get(s));
    }
    return result;
}

private static <T, S extends Collection<T>> void gFCSHelper2(
        Map<T, S> map, 
        Set<Set<T>> result, 
        Set<T> sofar, 
        S candidates
    ) 
{
    if (candidates.isEmpty()) {
        result.add(new HashSet<>(sofar));
        return;
    }
    for (var c: candidates) {
        sofar.add(c);
        var temp = map.get(c);
        temp.removeAll(sofar);
        var cand = new HashSet<>(candidates);
        cand.retainAll(temp);
        gFCSHelper2(map, result, sofar, (S) cand);
        sofar.remove(c);
    }
}

And what I do not fully understand is that in the first method I can use "map.get(s)", while I need  to do a cast to (S) in the helper method. Well, maybe Tim is right that I make all this far too complicated and there are much easier solutions.

If anyone wants an explanation of what is happening here, let me know.

[Tim Holloway]

I can't say anything more for certain. The getFullConnectedSubLists() method doesn't seem to be part of standard Java. so I'm not clear on what it is actually trying to do.

I mentioned 2 advantages of creating custom classes for that kind of stuff, but a third — and possibly most important — is that by not explicitly specifying the inner constructs all in one big statement you also have the ability to change what you're working with without massive code changes, possibly splattered all over the application.

To put it another way, all that templating and super-templating is well and good if your end goal is to create new templates of your own, but for an actual application, it' s cleaner, safer, and more flexible to define those extra layers.

[Mike Simmons]

Piet Souris wrote:And what I do not fully understand is that in the first method I can use "map.get(s)", while I need  to do a cast to (S) in the helper method.

I haven't fully analyzed what this is trying to do, but it looks to me like the issue is that in your second helper method, you need to create a new S instance - and you are choosing to do this by creating a new HashSet, and casting it to S.  This will produce problems if you try to call the code from a context where S needs to be, say, a List - since the HashSet is not a List.  Probably you will get a class cast exception when you run it, at some point when you try to access an S instance and it turns out to be an inappropriate type.

If your second helper method does need the ability to create an S instance, then I suggest passing in a Supplier < S > into the method.  You may need to add this to the first helper as well.  If you want this code to work for an arbitrary S that extends Collection, it has to be able to create a new S - so force the client code to provide that, by passing a Supplier < S >.  This can be something as simple as "HashSet::new" or "ArrayList::new"".

[Rob Spoor]

Piet Souris wrote:Thanks for the responses, guys!

@Rob,

problem with "? extends Collection<T>"is that I need to do a map.get(t) somewhere, and there I need to specify some type.

I think that you can just use Collection<T> for that.

Untested:

public static <T> Set<Set<T>> getFullConnectedSubsets2(Map<T, ? extends Collection<T>> map) {
    var result = new HashSet<Set<T>>();
    for (var s: map.keySet()) {
        var set = new HashSet<T>();
        set.add(s);
        gFCSHelper2(map, result, set, map.get(s)); // map.get(s) is (assignable to) Collection<T>
    }
    return result;
}

private static <T> void gFCSHelper2(
        Map<T, ? extends Collection<T>> map, 
        Set<Set<T>> result, 
        Set<T> sofar, 
        Collection<T> candidates
    ) 
{
    if (candidates.isEmpty()) {
        result.add(new HashSet<>(sofar));
        return;
    }
    for (var c: candidates) {
        sofar.add(c);
        var temp = map.get(c);
        temp.removeAll(sofar);
        var cand = new HashSet<>(candidates);
        cand.retainAll(temp);
        gFCSHelper2(map, result, sofar, cand); // no cast needed, cand is HashSet<T> which is assignable to Collection<T>
        sofar.remove(c);
    }
}

[Mike Simmons]

Yeah, that looks like it works.  Because the final return type does not contain any reference to S, there's no real need to capture S all along the way - and there's no need for a Supplier < S > since a HashSet is all that we need for what we're actually returning, a Set < Set < T > >.  

[Piet Souris]

Thanks again!

@Rob
yes, your method works. I tested my and your code with a HashMap of Sets and a HashMap of ArrayLists.There was a small mistake in my code, in your code, line 25 should be:

var temp = new HashSet<>(map.get(c));

The intention of the code is, as the name of the method suggests, to get the full collection of full connected subsets of a graph. In day 23b the question was to get the largest full connected subset.

The idea of the code is: say we have the map (undirected graph)
1 => 2, 3, 4
2 => 1, 4, 6, 8
...
then I start with the set 'sofar' with 1. The possible candidates are of course 2, 3, 4, called 'candidates'. I then add the first candidate, 2, to sofar, and next, my new candidates are then 1, 4, 6, 8, I remove from these my sofar, keeping 4, 6 and 7, and then my new candidates for the next recursion is the intersection of the old candidates and the new one.That gives only 4, et cetera. Using HashSets for the inbetween results ensures that the solutions are unique, even when the inputmap has Lists instead of Sets. The map I had to deal with had a size of 520 and the code took 0,4 seconds. Good enough, I read on the internet that getting full connected subsets (cliques?) has a pretty nasty runtime.