Java - store objects in a hierarchy that follows their class inheritance

Question

I need to store lots of objects that belong to different classes:

ClassA {...}
ClassA1 extends ClassA {...}
ClassA2 extends ClassA {...}
ClassA2a extends ClassA2 {...}
ClassB {...}

Now I need to find a way to store all these objects in a way that allows me to efficiently get all objects that belong to a particular class and its ~~inherited~~ child classes. For example, this imaginary code

getObjects(ClassA2)

would return a list of all stored objects that belong to ClassA2 or ClassA2a.

I believe a tree collection of some sort would be suitable, but I can't think of any way to implement it. Any ideas?

(Background: I am creating a simple java game, in which there's number of sprites that I need to manage, while some of those sprites share similar properties. When I check for events like collisions, I need to get all objects that extend EnemySprite and compare their coordinates with the player's sprite.)

All objects of type ChildClass2 (extends Class1). I'll try to write it more clearly. — Brikowski, May 11 '16 at 21:48
The question is clearer now. Did I get right what you intended in my answer? — Mifeet, May 11 '16 at 22:30
Just completely rewrote the description of classes and their inheritance, it should be clearer now. :) — Brikowski, May 11 '16 at 22:30
Why don't you just store each type of `Sprite` in their own `List`? That's essentially what a `Map` would do anyway. Also, how many objects are we talking? Have you experienced speed issues? — 4castle, May 11 '16 at 22:55

score 5 · Answer 1 · edited May 23 '17 at 12:31

There are several ways how to approach this. One would be, e.g., to generate strings like ParentClass1:ChildClass2:ChildClass1: for every object and use them as a key to a TreeMap or Trie which you would then traverse.

Here is a simpler solution, though. The following class contains a map from class to all objects implementing it. The only trick is adding an object to all buckets where it belongs:

public class HierarchyMap {
    private final Map<Class<?>, List<Object>> map = new HashMap<>();

    public void add(Object o) {
        Class<?> clazz = o.getClass();
        while (clazz != Object.class) {
            List<Object> list = map.computeIfAbsent(clazz, c -> new ArrayList<>());
            list.add(o);
            clazz = clazz.getSuperclass();
        }
    }

    public List<Object> getByClass(Class<?> clazz) {
        return map.get(clazz);
    }
}

Usage:

public class A { public String toString() { return "A"; } }
public class B extends  A{ public String toString() { return "B"; } }
public class C extends  B { public String toString() { return "C"; } }
// ...
HierarchyMap hierarchyMap = new HierarchyMap();
hierarchyMap.add(new A());
hierarchyMap.add(new B());
hierarchyMap.add(new C());
System.out.println(hierarchyMap.getByClass(B.class)); 
// prints [B, C]

I would update the map while iterating instead of constructing a throwaway list. Also, if you want a lighter map and faster writes (albeit with slower reads), you can map an object only by its own class and traverse the hierarchy in `getByClass()`. — shmosel, May 11 '16 at 22:22
I totally agree with the first point. The second depends on the usage pattern so it's up to @Brikowski to decide. — Mifeet, May 11 '16 at 22:24
As for my specific problem, I have decided to use an easier method, but your algorithm answers my question very well. Thank you! — Brikowski, May 11 '16 at 23:48

score 4 · Accepted Answer · edited May 23 '17 at 11:44

Mifeet seems to have literally answered your question, but I suspect you shouldn't be trying to do what you're proposing to do. Why not just have a master list of all objects that might collide, then filter it as needed using instanceof?

This is conceptually a lot easier than what you're proposing to do, and the efficiency impact probably isn't that big. (In general, you will probably hear or have heard the mantra: Don't try to optimize too early.)

To be honest, I'm not sure you realize that filtering for EnemySprite will get you all object instances of its subclasses as well.

public class CollisionChecker(){

   private List colliders;

   public CollisionChecker(){    
       colliders = new ArrayList<Object>();    
   }

   public void addCollider(Object o){
       colliders.add(o);
   }

   public List<EnemySprite> getEnemySprites(){
       List<EnemySprite> enemies = new ArrayList<EnemySprite>();
       for (Object o : colliders)
           if (o instanceof EnemySprite)
               enemies.add((EnemySprite)o);
       return enemies;        
   }     
}

You're absolutely right! I had no idea that instanceof() works for subclasses, so I'll use something similar to your answer - going through a single list of all objects and narrowing the results is just more than sufficient for my needs. Thanks! — Brikowski, May 11 '16 at 23:35
For a more generalized solution, [see this answer](http://stackoverflow.com/a/37174482/5743988) — 4castle, May 11 '16 at 23:49

4castle · Answer 3 · 2016-05-11T23:53:36.860

1

If you're storing the objects in a List<Object>, call Class#isInstance() on each element, adding them to another List if isInstance() returns true.

List<Object> objects = new ArrayList<>();

public <T> List<T> getObjects(Class<T> desiredClass) {
    List<T> desiredObjects = new ArrayList<>();
    for (Object o : objects)
        if (desiredClass.isInstance(o))
            desiredObjects.add((T)o);
    return desiredObjects;
}

getObjects(EnemySprite.class); // call it like this

edited May 11 '16 at 23:53

answered May 11 '16 at 22:45

4castle

32,613
11
69
106

*...that allows me to **efficiently** get all objects...* – shmosel May 11 '16 at 22:46
@shmosel It depends on how many objects we're talking. 1000s? Yes – 4castle May 11 '16 at 22:53
If it's a minimal number of objects, I don't think OP would have mentioned efficiency as a concern. – shmosel May 11 '16 at 22:55
Alternatively, you can just use `o.getClass() == desiredClass`, but that won't allow a check for inheritance (though it would be faster). – 4castle May 11 '16 at 23:06
I didn't actually know that instanceof() would work for subclasses, so I didn't realize your answer is right until now. But thanks! – Brikowski May 11 '16 at 23:40
Great! Keep this implementation in mind if you would like it to be reusable for other classes. It uses generics (notice the `T`) in order to generalize the operation for any class that you might want to search for. – 4castle May 11 '16 at 23:46

score 0 · Answer 4 · answered May 11 '16 at 22:40

If you just want collision detection, then I would add them to a static collection in the ancestor class. This would be the most efficient solution.

If you want to all descendants for a class you should check out the reflection APIs. Yes, they're said to be slow, but I have doubts that it matters enough for things that aren't computed for every frame. And for things that you need in every frame tree traversal would inefficient anyway. (@Miffet's suggestion of string comparison would probably be even slower than regular reflection.)

Java - store objects in a hierarchy that follows their class inheritance

4 Answers4