Query a tree

[and1000]

Hi all,
I feel a bit stupid to ask this question, but I've been working with
this for a while, and I seem to be stuck in a very stupid way of
thinking. I would be very heappy if anybody could point me to a way out
of it. The problem is this: I have a tree structure containing game
data. It's organised as follows: The top of the tree is a scenario
object, and a scenario can contain many teams. Each team contains
several players, and each player contains several objects. Objects in
turn can contain other objects. I thought my problem was one of
traversal at first, but I'm starting to think that what I really want
to do is query the tree. For example, I need to know

- which player owns object with a certain id?
- which team does a certain object belong to?

When traversing the tree, I therefore need information from different
levels, both object level and f.ex team level. I have hard-coded it for
now, because I needed to test other parts of the program. I'll include
it anyway, to show what I mean (I know it's crap, you don't need to
tell me that):

private ITraversable getObject(IObjectModel m, int objectID, String
classname){
List scenarios = m.getContainedElements();
for(Iterator i = scenarios.iterator(); i.hasNext(){
IScenario sc = (IScenario)i.next();
List teams = sc.getContainedElements();
for (Iterator y = teams.iterator(); y.hasNext(){
ITeam t = (ITeam)y.next();
List players = t.getContainedElements();
for(Iterator j = players.iterator(); j.hasNext(){
IPlayer p = (IPlayer)j.next();
if(p.contains(objectID)){
try {
if(Class.forName(classname).isInstance(p)){
return p;
}
else if(Class.forName(classname).isInstance(t)){
return t;
}
} catch (ClassNotFoundException e) {
e.printStackTrace();
}
}
}
}
}
return null;
}

Then the usage of the method is as follows:
IPlayer owner = (IPlayer)getObject(objectmodel, objectid,
IPlayer.class.getName());

The contains(objectid)-method traverses the tree downwards. The problem
with recursively traversing the tree is that I need to "stop" at
different levels depending on what kind of object I'm asking for (team,
player etc). No objects have references to their parents, only
children. I cannot use id as a comparison value either (e.g return the
first object with this id), because though id's are unique within each
level in the tree, different objects in different levels can have the
same id (e.g a player and a team can both have id 1).

Any help will be greatly appreciated.

Regards

 

[jan V]

- which player owns object with a certain id?

scenario.getPlayerOwningObject(objectID)

forall teams of scenario
Player player = team.getPlayer(n)
if (player.owns(objectID)) {
return player;
}

.... no problems so far?

- which team does a certain object belong to?

scenario.getTeamWithPlayer(player)

forall teams of scenario
Player player = team.getPlayer(n)
if (player.equals(soughtPlayer)) {
return team;
}

Note that I'm approaching things totally from an OO approach, not a tree
traversal approach. I think you're getting your knickers in a twist by
imposing a "tree view" on your core objects. Forget about the tree, and just
use pure objects... your scenario objects refer to many teams... every team
refers to many players, and so on... your tree ALREADY exists in the object
graph, so ditch that explicit tree. Implement partial querying logic in your
Scenario, Team and Player classes, then use delegation to let a top-level
query drill down as far as necessary. Do NOT implement "raw" query logic
which knows about the whole tree structure... you're breaking the
encapsulation principle doing this.

 

[Roedy Green]

- which player owns object with a certain id?
- which team does a certain object belong to?

You can get this information by chasing up and down the tree, or if
you need it quickly, you can get it by auxiliary indexes.

Sorts of index you might have:

person index: given person id, find his person node in the tree.

collection of objects currently visible on screen.

Grid. What objects appear in a given grid square. Useful to find
nearby objects.


If you assign your objects reasonably dense ordinal numbers, you can
use java.util.BitSet to rapidly look up boolean facts about them.

 

[and1000]

Thanks jan, your advice really cleared my thoughts! You are of course
right that I was stuck in the tree view just because I happened to have
a tree. Implementing proper methods for each class makes much more
sense.

Again, thanks a lot!

 

[and1000]

Thanks, I appreciate your advice. However, speed is not very crucial in
this case, the most important thing is that the code is readable for
others and extendable for later versions.

The grid idea is interesting though, I might actually need something
like that to find nearby objects. Will check that out!

Thanks!

 

[Roedy Green]

However, speed is not very crucial in
this case,

that is quite unusual for a game.

 

[jan V]

Thanks jan, your advice really cleared my thoughts! You are of course

right that I was stuck in the tree view just because I happened to have
a tree. Implementing proper methods for each class makes much more
sense.

Again, thanks a lot!

My pleasure. You fell in a common OO beginners trap: you strayed from the OO
metaphor. Properly assigning sensible functionality to crisply-defined
classes is half the battle in OO.

 

[and1000]

that is quite unusual for a game.
--

Yes, well, it is quite an unusual game. ;-) Most of the speed crucial
material is done by a simulator engine, and the stuff done by the java
server is of such a small size that it won't be able to slow down the
system in any noticeable way.