bounded generic problem

From:

Eric Smith <eric@brouhaha.com>

Newsgroups:

comp.lang.java.programmer

Date:

08 May 2007 02:08:15 -0700

Message-ID:

<qhsla7y96o.fsf@ruckus.brouhaha.com>

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