bounded generic problem

[Eric Smith]

I've written a class SPF to implement Dijkstra's Shortest Path First
algorithm using bounded generics to allow the user to supply his own
objects for vertices and edges of the graph, where those objects
must implement interfaces SPFVertex and SPFEdge. I have it working,
but I've got one place where the compiler complains about not finding
the right method profile. If I insert an explicit cast, then it
compiles with a warning about the cast, but executes correctly.

Here are the interfaces and the class stripped down to the bare
minimum that will exhibit the problem:

interface SPFEdge
{
public long getCost ();
}

interface SPFVertex<E extends SPFEdge>
extends Iterable<E>
{
public SPFVertex traverse (E edge);
}

public class SPF<V extends SPFVertex<E>,
E extends SPFEdge>
{
private class State
{
V vertex;
public State (V vertex)
{
this.vertex = vertex;
}
}

public void traverseEdge (State state, E edge)
{
State newState = new State (
state.vertex.traverse (edge)
);
}
}


The compiler complains that it can't find the constructor for State:

% javac *.java
SPF.java:15: cannot find symbol
symbol : constructor State(SPFVertex)
location: class SPF<V,E>.State
State newState = new State (
^
1 error

The problem seems to be that the SPFVertex traverse() method
returns an SPFVirtex, which should be a V in class SPF, but for
some reason the compiler doesn't think it matches.

If I put in an explicit cast to V:

State newState = new State (
(V) (state.vertex.traverse (edge))
);

then the compiler gives the warning:

% javac -Xlint:unchecked *.java
SPF.java:17: warning: [unchecked] unchecked cast
found : SPFVertex<E>
required: V
(V) (state.vertex.traverse (edge))
^
1 warning

I tried changing the return type of traverse to SPFVertex<E>, but
that didn't eliminate the error.

Can anyone explain why the result of the traverse() method is
not being matched with V in class SPF?

I wrote SPF as part of refactoring several puzzle solver programs
I've written, where the puzzles are solved by computing the shortest
path on the phase space of the puzzle. My SPF class is specifically
designed so that it is not necessary for all of the vertices and edges
of the graph to preexist; they can be generated on the fly as needed.

I plan to make the SPF class and several demos (including a few
puzzle solvers) available as Free Software.

Thanks!
Eric Smith

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Eric Smith schreef:

I've written a class SPF to implement Dijkstra's Shortest Path First
algorithm using bounded generics to allow the user to supply his own
objects for vertices and edges of the graph, where those objects
must implement interfaces SPFVertex and SPFEdge. I have it working,
but I've got one place where the compiler complains about not finding
the right method profile. If I insert an explicit cast, then it
compiles with a warning about the cast, but executes correctly.

Here are the interfaces and the class stripped down to the bare
minimum that will exhibit the problem:

interface SPFEdge
{
public long getCost ();
}

interface SPFVertex<E extends SPFEdge>
extends Iterable<E>
{
public SPFVertex traverse (E edge);

}

public class SPF<V extends SPFVertex<E>,
E extends SPFEdge>
{
private class State
{
V vertex;
public State (V vertex)
{
this.vertex = vertex;
}
}

public void traverseEdge (State state, E edge)
{
State newState = new State (
state.vertex.traverse (edge)
);
}
}


The compiler complains that it can't find the constructor for State:

% javac *.java
SPF.java:15: cannot find symbol
symbol : constructor State(SPFVertex)
location: class SPF<V,E>.State
State newState = new State (
^
1 error

You will get a warning about the traverse line as well.

The problem seems to be that the SPFVertex traverse() method
returns an SPFVirtex, which should be a V in class SPF, but for
some reason the compiler doesn't think it matches.

Well, of course it doesn’t: traverse returns an SPFVertex<E>, but State
expects a subclass of it. It’s as if you would pass a Number to a
method which expects a Double. Not the same thing!

If I put in an explicit cast to V:

State newState = new State (
(V) (state.vertex.traverse (edge))
);

then the compiler gives the warning:

% javac -Xlint:unchecked *.java
SPF.java:17: warning: [unchecked] unchecked cast
found : SPFVertex<E>
required: V
(V) (state.vertex.traverse (edge))
^
1 warning

I tried changing the return type of traverse to SPFVertex<E>, but
that didn't eliminate the error.

You should do that anyway. Once you use generics, use them consistently!

Can anyone explain why the result of the traverse() method is
not being matched with V in class SPF?

I hope I did.

Now about a solution: I don’t see one at first. Do you really need
State to have a V? I.e., couldn’t you change State such that it stores
an SPFVertex<E>?

You could make Edges vertex-aware instead. But I didn’t get a nice
design out of that as well.

HTH, H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGQEbYe+7xMGD3itQRAlGwAJ44lu4e74sy6598/QB+IW9nG/+JpQCeIv3G
U0hUeXi5BVI5tkfLmyQxU94=
=l2Yj
-----END PGP SIGNATURE-----

 

[Piotr Kobzda]

Now about a solution: I don’t see one at first. Do you really need
State to have a V? I.e., couldn’t you change State such that it stores
an SPFVertex<E>?

You could make Edges vertex-aware instead. But I didn’t get a nice
design out of that as well.

Or make a vertices other vertices-aware. I.e. declare vertex as:

interface SPFVertex<V extends SPFVertex<V, E>,
E extends SPFEdge>
extends Iterable<E> {
public V traverse(E edge);
}

and SPF as:

public class SPF<V extends SPFVertex<V, E>,
E extends SPFEdge> { ...


piotr

 

[Eric Smith]

My class definition started with:

public class SPF<V extends SPFVertex<E>,
E extends SPFEdge>

Well, of course it doesn¢t: traverse returns an SPFVertex<E>, but State
expects a subclass of it.

OK, now I understand. Thanks!

Do you really need
State to have a V? I.e., couldn¢t you change State such that it stores
an SPFVertex<E>?

Yes, changing it to an SPFVertex<E> solved the problem. In fact, I

You could make Edges vertex-aware instead. But I didn¢t get a nice
design out of that as well.

I thought about that. I never did come up with a very good way to
make the edge object contain any smarts. All the logic wound up
in the vertex object, so the edge is really just a container for
the cost. Of course, the user may have more use for his edge object
unrelated to SPF. In my example code and puzzle solver code, it
is useful for the edge class (which implements SPFEdge) to have
references to the vertices. In particular, the constructors for the
edges automatically add the edge to one or both vertices (depending
on whether it is the edge subclass for a directed or undirected edge).

Only after I picked E and V to be my type parameters for edges and
vertices did I read the recommendation that E should be used for
elements and V for values. Now that I've done away with V, I
suppose I can claim that E does mean an element, which happens to be
an edge.

Thanks for the help!
Eric