Tree that sorts classes hierarchicly

Question

I need a tree-structure that sorts all added classes hierarchically. I have to get all classes that inherit one certain class. That one particular read access needs to be very fast.

Example:

I add the following classes.

public static class Event
{

}

public static class PlayerEvent extends Event
{

}

public static class PlayerMoveEvent extends PlayerEvent
{

}

public static class WorldEvent extends Event
{

}

It should sort the classes like this:

http://i.imgur.com/J6DyZvL.png

Answer 1

Have a Node class that represents a node in your tree. It stores the class that it represents and its direct children.

class Node {
    Set<Node> children;
    Class class;
}

Then you can construct the tree, and get your root node.

List<Class> classList = ...l
Map<Class,Node> classMap = ... a map from all your classes to nodes made from them;
Node rootNode = null;

for(Class c : classList){
    Node parentNode = classMap.get(c.getSuperclass());
    if(parentNode != null)
        parentNode.children.add(classMap.get(c));
    else
        rootNode = classMap.get(c);
}

Answer 2

Use a Map <Class, List <Class>>, where the key is the parent class, and the List contains all the children.

Answer 3

Andres answer is best for O(1) lookup. You always have to iterate if you are using a hierarchial data structure . If you want to store the hierarchial data structure so that you can have O(1) retrieval , you need to have memory to snapshot it. Java stores references , so it wont be as much memory as you are thinking of, but it still would not be insignificant. If you want to save on memory you can use disk sapce by writing the values of the child classes to a file . Every time you add a child class, you append a row to the list of child classes.