As part of a project where I’m building a simulator I wanted a pathfinding algorithm and looked around for an A*-library in Java. I found a few that I didn’t like the look of and decided to just make my own library. Luckily the algorithm is simple enough to basically copy-paste from the pseudocode found on Wikipedia, and it was during the rewrite I decided to really look into generics for the first time.

Below is an example of generics (note that the methods returns “T“, and not an int or string. Basically, if we send a specific object that implements AStarNode to these methods, we get an object of the same type back.

public interface AStarNode {
    public <T extends AStarNode> Collection<T> getNeighbours();
    public <T extends AStarNode> double getDistance(T node);
}

Why are generics cool?

When we use libraries it’s often smart to specify an interface that classes must implement to function with library functions. An example from A* would be that we need to know that a class provides both neighbours (nodes) and a way to calculate the distance between said nodes. Therefore we can write an interface that looks like this:

public interface Node {
    public Collection<Node> getNeighbours();
    public double getDistance(Node node) throws Exception;
}

This will let people our A* library requires these two functions to work. The problem now is that our A* algorithm returns an interface, so now the user has to cast the interface to the class they sent in. It’s a real nuisance.

Consider this:

Collection c1 = new ArrayList();
Collection c2 = new HashSet();

Both c1 and c2 are Collections, but c1 is not a Hashset and c2 is not an Arraylist. Thus when we send an ArrayList into a function that requires and returns a Collection we have to check if we don’t get a HashSet back if we want to use ArrayList-specific functions.

Generics to the rescue!

I made a small A*-library on Github using pseudocode from Wikipedia which illustrates the solution to the above problem. If you’ve used the diamond operator before (ArrayList<String>) you’ve used generics already, but when you handle interfaces you need to change the syntax slightly.

Using generics our interface now looks like this:

public interface AStarNode { 
    public <T extends AStarNode> Collection<T> getNeighbours();
    public <T extends AStarNode> double getDistance(T node) throws Exception;
}

“T extends AStarNode” basically means that we require a class T that implements a specific interface, and that we return the very same class T. Now you no longer need to do the normal class check:

T class = (T) class;

Which makes the library much more comfortable to use. My probably very inefficient A*-algorithm on Github demonstrates the generic approach with interfaces.

https://github.com/Oddsor/AStarMulti/