Generics trouble implementing Map.entrySet()

Question

I'm trying to extend AbstractMap to create a MapTreeNode class (a tree node where children are accessed by key rather than by index).

I already have a method for getting a set of the children which works fine:

public class MapTreeNode<K,V> implements Map.Entry<K,V> {
    private Map<K,MapTreeNode<K,V>> children = new HashMap<K,MapTreeNode<K,V>>();
    private Set<MapTreeNode<K,V>> child_set = null;

    public Set<MapTreeNode<K,V>> children() {
        if (child_set == null)
            child_set = new ChildSet();

        return child_set;
    }

    ...

    private final class ChildSet extends AbstractSet<MapTreeNode<K,V>> {
        @Override
        public Iterator<MapTreeNode<K,V>> iterator() {
            return children.values().iterator();
        }

        @Override
        public int size() {
            return MapTreeNode.this.childCount();
        }
        ...
    }

}

I'd like to create a map view of a node (Map<K,V>) and reuse child_set but I'm not sure it's possible with Java's generics:

public Map<K,V> asMap() {
    return new AbstractMap<K,V>() {
        @Override
        public Set<Map.Entry<K,V>> entrySet() {
            return child_set; // line 166
        }
    };
}

this of course gives

MapTreeNode:166: incompatible types
found   : java.util.Set<MapTreeNode<K,V>>
required: java.util.Set<java.util.MapEntry<K,V>>

Is there a way I can reuse my ChildSet class for this?

Related: [Is `List` a subclass of `List`? Why aren't Java's generics implicitly polymorphic?](http://stackoverflow.com/questions/2745265/is-listdog-a-subclass-of-listanimal-why-arent-javas-generics-implicitly-p). — Paul Bellora, Jul 15 '13 at 21:18

score 3 · Accepted Answer · answered Jul 17 '13 at 09:30

The problem is with entrySet()'s return type. It is Set<Map.Entry<K,V>>. And as you know, Foo<A> is not compatible with Foo<B> for different A and B no matter how they're related.

I would argue that this was a design mistake in the API. The return type of entrySet() should really be Set<? extends Map.Entry<K,V>>. Here is why: If you read the documentation for entrySet(), it says that things can be read from the Set, things can be removed from the Set (which causes changes to the underlying map), but things cannot be added to the Set. This exactly fits the role of a Producer -- you do not add things to it. Per the PECS rule, an extends-wildcard collection type should be used.

score 1 · Answer 2 · answered Jul 15 '13 at 20:25

1

Unless you need something specific from a MapTreeNode method, treat it as a Map.Entry, meaning declare child_set as

private Set<Map.Entry<K,V>> child_set = null;

Since MapTreeNode extends Map.Entry, you should be fine.

answered Jul 15 '13 at 20:25

JoshDM

4,939
7
43
72

I was trying to avoid having to cast everything to `MapTreeNode` throughout the rest of the `MapTreeNode` class, but maybe that's the only workable option. – Brad Mace Jul 15 '13 at 20:27
The trick is, if `MapTreeNode` is only being used to replace internal functionality of Map.Entry, then transform your entries to `MapTreeNode` when the data is added to the Map, and leave `MapTreeNode` invisible to to outside world. If you need a brand new method only `MapTreeNode` can provide, then we can work something else out. – JoshDM Jul 15 '13 at 20:37
`MapTreeNode` is acting as an alternative to [`DefaultMutableTreeNode`](http://docs.oracle.com/javase/6/docs/api/javax/swing/tree/DefaultMutableTreeNode.html), so there's a lot of other functionality I trimmed out to avoid posting a wall of code. – Brad Mace Jul 15 '13 at 20:39
Always post the wall of code, Brad! Tough enough throwing what you had into my compiler and filling in the blanks... – JoshDM Jul 15 '13 at 20:39
Wouldn't be practical to post it all, the important point is that it needs to be a public class, and I need to know that objects are `MapTreeNode`s, not just `Map.Entry`s. So the question boils down to "Can I return a `Set` as a `Set` without changing the return type of `entrySet()`?" – Brad Mace Jul 15 '13 at 20:49
Not if you need them to be explicitly `MapTreeNode` Objects without casting, no. I believe you'd need to roll your own method, `mapTreeNodeSet()` or even write and extend your own `AbstractTreeNodeMap`. – JoshDM Jul 15 '13 at 21:24

score 1 · Answer 3 · answered Jul 17 '13 at 16:20

Here's the best I've been able to do so far at avoiding code duplication:

private abstract class AbstractChildSet<T extends Map.Entry<K,V>> extends AbstractSet<T> {
    @Override
    public boolean remove(Object o) {
        if (o == null || !(o instanceof Map.Entry)) {
            return false;
        }

        MapTreeNode<K,V> node;
        if (o instanceof MapTreeNode)
            node = (MapTreeNode<K,V>) o;
        else
            node = MapTreeNode.this.child(((Map.Entry<K,V>) o).getKey());

        if (node == null || !isParentOf(node))
            return false;

        node.removeFromParent();
        return true;
    }

    @Override
    public int size() {
        return MapTreeNode.this.childCount();
    }

    @Override
    public void clear() {
        MapTreeNode.this.removeAllChildren();
    }
}

private final class ChildSet extends AbstractChildSet<MapTreeNode<K,V>> {
    @Override       
    public boolean add(MapTreeNode<K,V> node) {
        if (MapTreeNode.this.containsKey(node.getKey()))
            return false;

        MapTreeNode.this.addChild(node);
        return true;
    }

    @Override
    public Iterator<MapTreeNode<K,V>> iterator() {
        return children.values().iterator();
    }
}

private final class EntrySet extends AbstractChildSet<Map.Entry<K,V>> {
    @Override
    public boolean add(Map.Entry<K,V> entry) {
        if (MapTreeNode.this.containsKey(entry.getKey()))
            return false;

        MapTreeNode new_child = new HashMapTreeNode(MapTreeNode.this, entry.getKey(), entry.getValue());

        MapTreeNode.this.addChild(new_child);
        return true;
    }

    @Override
    public Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
}

score 0 · Answer 4 · answered Jul 15 '13 at 20:55

What I understood that you have implemented new class to get children which are of type Entry. To build a map again I would iterate over the set of entries and rebuild the map.

Not sure I helped here as like others I am unable to fully read what else this class contains.

score -1 · Answer 5 · answered Jul 15 '13 at 23:07

-1

Why don't you simply cast it like this:

public Map<K,V> asMap() {
    return (Map<K,V>) this;
}

answered Jul 15 '13 at 23:07

Syed Muhammad Humayun

439
4
15

Some of the methods in `Map` don't line up that neatly with the needs of a tree node, so `MapTreeNode` doesn't implement the `Map` interface directly. Also I've run in to this issue in a few other places so I'm looking for a general-purpose way to work around this issue. – Brad Mace Jul 16 '13 at 03:19
`MapTreeNode` does not implement `Map` – newacct Jul 16 '13 at 23:53

Generics trouble implementing Map.entrySet()

5 Answers5