Recursive Generic Usage

Question

Edited:" I received a very pertinent answer from 'erickson', but there is a side problem (up-casting?) that was not explicitly covered in my original example and is not solved with his answer. I've extended the example to cover this other problem, and I've included it at the end of this post. Thanks for your help.

I'm currently facing a problem with Java generics that is related to something that has been called the "Curiously Recurring Generic Pattern". I thought I had found the solution after reading the answer from Jon Skeet to this question "java enum definition". Nevertheless, I found myself with different problems when I tried to apply it in my code.

I've come up with a 'small' example where the problem I'm facing appears. I hope it will be clear enough to illustrate my questions.

Description of the example: I want to build a graph where node types can vary. I've defined an abstract class Node, which defines some basic methods, and a concrete class that implements those methods, namely ConcreteNode. I've also created a specialization of ConcreteNode called City.

In a given graph, an important requirement is that all the elements should be made of the same types or subtypes of it, i.e. a graph of ConcreteNode can have only ConcreteNodes or Cities.

These are the definitions of my classes:

abstract class Node<T extends Node<T>>
class ConcreteNode<T extends ConcreteNode<T>> extends Node<T>
class City extends ConcreteNode<City>

These definitions make use the 'Recurring Generic Pattern' also found in the definition of the Enum class:

Class Enum<E extends Enum<E>>

Questions: I'm having problem using these classes. I don't have problems if I have to stay at the City level in the hierarchy, i.e. connecting City to City, but I'm having huge problems when trying to access other classes.

In the following code, my problems can be seen in the signature of the methods of GraphUtil:

1. addNewNeighbors1a uses the raw type Node, but at least it works.
2. addNewNeighbors1b uses the type Node, but it doesn't compile at all (the error is included the code).
3. addNewNeighbors1c uses a more complex parameter for Node, that I expected to work, but it doesn't compile (the error is included the code).
4. addNewNeighbors3 uses complex parameters for Node, but it doesn't compile again, even though the parameters are the same for node and newNode.

In synthesis, my question is how to upcast these generic types that are parametrized on themselves?.

I will be really glad to get help with the best signature for the methods of GraphUtil, assuming that these methods are going to be located in a library that doesn't know anything about City or even ConcreteNode.

Thank you all.

Here's the full code of the example

package test.city;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class TestCity {
    abstract class Node<T extends Node<T>> {
    public abstract void addNeighbor(T n);
    public abstract void addNeighbors(Collection<? extends T> nodes);
    public abstract Collection<T> neighbors();
    }

    class ConcreteNode<T extends ConcreteNode<T>> extends Node<T> {
    protected Collection<T> _neighbors = new ArrayList<T>();

    @Override
    public void addNeighbor(T n) {
        _neighbors.add(n);
    }

    @Override
    public void addNeighbors(Collection<? extends T> nodes) {
        _neighbors.addAll(nodes);
    }

    @Override
    public Collection<T> neighbors() {
        return _neighbors;
    }
    }

    class City extends ConcreteNode<City> {
    protected String _name;

    public City(String name) {
        _name = name;
    }

    @Override
    public String toString() {
        return _name;
    }
    }

    public TestCity() {
    City nyc = new City("NYC");
    nyc.addNeighbor(new City("Boston"));
    nyc.addNeighbor(new City("Wash"));

    GraphUtil.print("Printing cities", nyc.neighbors());

    GraphUtil.printNeighbors1(nyc);
    GraphUtil.printNeighbors2(nyc);
    GraphUtil.printNeighbors3(nyc);
    GraphUtil.printNeighbors4(nyc);
    GraphUtil.addNewNeighbors1a(nyc, new City("Miami"));
    GraphUtil.addNewNeighbors2(nyc, new City("NewOr"));
    GraphUtil.addNewNeighbors3(nyc, new City("Dallas"));
    }

    static class GraphUtil {
    static void printNeighbors1(Node<?> node) {
        print("Nodes", node.neighbors());
    }

    static void printNeighbors2(ConcreteNode<?> node) {
        print("Concrete nodes", node.neighbors());
    }

    static void printNeighbors3(Node<? extends Node<?>> node) {
        print("Nodes2", node.neighbors());
    }

    static void printNeighbors4(ConcreteNode<? extends ConcreteNode<?>> node) {
        print("Concrete nodes2", node.neighbors());
    }

    static void addNewNeighbors1a(Node node, City newNode) {
        node.addNeighbor(newNode);
        print("Add city to node", node.neighbors());
    }

    static void addNewNeighbors1b(Node<?> node, City newNode) {
        // node.addNeighbor( newNode ); <---- DOES NOT COMPILE!!!
        // The method addNeighbor(capture#8-of ?) in the type
        // TestCity.Node<capture#8-of ?>
        // is not applicable for the arguments (TestCity.City)
    }

    static void addNewNeighbors1c(Node<? extends Node<?>> node, City newNode) {
        // node.addNeighbor( newNode ); <---- DOES NOT COMPILE!!!
        // The method addNeighbor(capture#9-of ? extends TestCity.Node<?>)
        // in the type
        // TestCity.Node<capture#9-of ? extends TestCity.Node<?>> is not
        // applicable for the arguments (TestCity.City)

    }

    static void addNewNeighbors2(Node node, ConcreteNode newNode) {
        node.addNeighbor(newNode);
        print("Add concrete node to node", node.neighbors());
    }

    static void addNewNeighbors3(Node<? extends Node<?>> node,
     Node<? extends Node<?>> newNode) {
        // node.addNeighbor( newNode ); <---- DOES NOT COMPILE!!!
        // The method addNeighbor(capture#8-of ? extends TestCity.Node<?>)
        // in the type
        // TestCity.Node<capture#8-of ? extends TestCity.Node<?>> is not
        // applicable for the arguments
        // (TestCity.Node<capture#10-of ? extends TestCity.Node<?>>)
    }

    static void print(String msg, Collection<?> col) {
        System.out.println(msg + ": " + Arrays.toString(col.toArray()));
    }
    }

    public static void main(String[] args) {
    new TestCity();
    }

}

The output of running this code is the following (no surprises at all):

Printing cities: [Boston, Wash]
Nodes: [Boston, Wash]
Concrete nodes: [Boston, Wash]
Nodes2: [Boston, Wash]
Concrete nodes2: [Boston, Wash]
Add city to node: [Boston, Wash, Miami]
Add concrete node to node: [Boston, Wash, Miami, NewOr]

Second part of the problem

There is a related problem that I had not included in the original example because I thought the solution was also going to apply.

I've now added the following method to GraphUtil:

static <T extends Node<T>> T getSomeNeighbor(T node) {
    return node.neighbors().iterator().next();
}

And from my main class I'm trying the following:

City someCity = GraphUtil.getSomeNeighbor(nyc); 
someCity.addNeighbor(new City("London")); // OK

ConcreteNode someCN1 = GraphUtil.getSomeNeighbor(nyc); 
someCN1.addNeighbor(new City("Paris")); // OK, but raw

ConcreteNode<?> someCN2 = GraphUtil.getSomeNeighbor(nyc); 
someCN2.addNeighbor(new City("Berlin")); // Does not compile

ConcreteNode<?> nc = new City("");
nc.addNeighbor(new City("Bern")); // Does not compile

The first case works, because I know the concrete type that is returned, and it is coherent with the type provided in the parameter.

In the second and third cases I'm assuming I don't know the type City. The second case works, but I'm using the raw type ConcreteNode.

In the third case, there is a compilation error in the second line: "The method addNeighbor(capture#3-of ?) in the type TestCity.ConcreteNode is not applicable for the arguments (TestCity.City)."

In the example I'm using 'new City("-")' as a parameter because I don't know how to up-cast them. In the fourth case I tried to up-cast City to ConcreteNode, but it failed. The current compiler error is the following: "The method addNeighbor(capture#4-of ?) in the type TestCity.ConcreteNode is not applicable for the arguments (TestCity.City)"

Questions:

1. How can I fix cases 2 and 3 without knowing the type City?
2. How can up-cast City to ConcreteNode (or to Node)?

Thanks for your help.

Answer 1

One, your wildcards in the static methods allow for any sort of node addition, which your compiler knows isn't allowed. Suppose you were doing graphs of proteins (like, for example, I do) and you had a Protein extends Node<Protein> class with instances. Your wildcard methods, were they to work, would allow me to add said proteins.

As for fixing the problem, try defining your add methods along these lines:

public <U extends T> void add(U other)

T is defined by the class parameter, and the method allows adding any subclass of T, as defined by the local parameter U. That should take care of your problem in one direction, though you are restricted to only adding subclasses to superclasses.

Answer 2

To your second part, again the wildcards are a problem. ConcreteNode could presumably be of some type which City does not extend - e.g., ConcreteNode<Suburb> is not extended by City - despite the fact that you know what it is, the compiler doesn't.

Answer 3

For part 1, I would make the method signiture

static <T extends Node<T>> void addNewNeighbors(Node<? super T> node, T newNode)
{
  node.addNeighbor(newNode);
}

That way, node does not have to specifically be the same type as newNode.

For part 2, I would do something similar.

ConcreteNode<? super City> nc = new City("");
nc.addNeighbor(new City("Bern"));