Most efficient way to search multi-tree data structure

Question

I am wondering if there is a more efficient way to search through a multi-tree than what I have been doing. I recently built a multi-tree data structure for a project that is illustrated below.

The cave would hold the parties in an array list. The different parties would hold different creatures. Different creatures would hold different items.

I needed a way to search the whole tree to match an object to an attribute it had such as index. This is a snippet of my program that searches through every ArrayList to see if either a party, creature, treasure, or artifact matches an int I call index.

Edit(Explaining my code) The classes Party, Creature, Treasure, and Artifact all have attributes such as index, name, type, etc. The multi-tree has the Cave set as the root note. Cave has an ArrayList that can contain a number of Party objects. Each Party has an ArrayList that can contain a a number of Creature objects. Each creature has two array lists one to hold Artifact objects and one for Treasure objects.

Below I am searching to see which party, creature, artifact, or treasure holds the specific index that I am searching for. I do this by iterating over parties, with each party I look in the creatures, and with each creature I look in the artifacts and treasures. That is why I have so many for loops inside of for loops :(.

case 0 :
            int index =                 Integer.parseInt( stat );
            for ( Party p : SorcerersCave.theCave.parties ) {
                if ( index == p.getIndex()) {
                    generateInterface.theGame.printOutput( "\t" + p );
                    break;
                } else {
                    for ( Creature c : p.members ){
                        if ( index == c.getIndex() ){
                            generateInterface.theGame.printOutput( "\t" + c );
                            break;
                        } else {
                            for ( Treasure t : c.inventory ){
                                if ( index == t.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + t );
                                    break;
                                }
                            }
                            for ( Artifact a : c.artifacts ){
                                if ( index == a.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + a );
                                    break;
                                }
                            }
                        }
                    }
                }
            }

I feel this code is too complicated and is difficult to follow. The code works but its an ugly stain on my otherwise really good looking code. I've been looking around to find a better way to do this, or even a way to improve it.

Note* Project requirements forbid us from placing every object in the same ArrayList.

Answer 1

Your classes could implement a common interface SearchableByIndex that would look like this and which would be implemented by every class in the tree:

public interface SearchableByIndex {
    public SearchableByIndex searchByIndex(int index);
    public int getIndex();
}

Then Cave, Party and Creature require this code:

public SearchableByIndex searchByIndex(int index) {
    if (getIndex() == index) {
        return this;
    } else {
        for (Party party : parties) {    // or Creature creature : members etc.
            SearchableByIndex found = party.searchByIndex(index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

The Treasure and Artifact's version:

public SearchableByIndex searchByIndex(int index) {
    return (getIndex() == index) ? this : null;
}

And instead of your nested looping you have there, you'd have

case 0:
    int index = Integer.parseInt(stat);
    SearchableByIndex foundItem = SorcerersCave.theCave.searchByIndex(index);
    if (foundItem != null) {
        generateInterface.theGame.printOutput("\t" + foundItem);
    } else {
        // print out that the item was not found
    }
    break;

While the searchByIndex() method on every class may seem repetitive, it's the OOP way to do it. This way, every class would take care of searching all its contents. In your case, all classes would have the code very similar (the only change will be the line with the for loop), but you can consider this to be an accident - any class could contain any data it wants and no other classes should care about how it stores its data.

In future, if one of your classes would hold more searchable data (Treasure, Artifact and Hostage?), or you'd like to change the structure of its data (consider HashMap, if you can!), you would just have to change the searchByIndex() method in the particular class.

Also, only the class containing the data should know how it contains it. The way you now have it, some other class that invokes the searching knows exactly how data is stored in every class - this should not be. If one class changes, it breaks internal code of other classes. For example, the Cave class should state in its documentation that it holds e.g. different Party instances and that it can give out some of them if you search for it by searchForIndex().

Answer 2

Project requirements forbid us from placing every object in the same ArrayList.

(And presumably, a HashMap or TreeMap is forbidden too ...)

Without some kind of secondary data structure for mapping index values to the objects they refer to, you have no choice but to do a tree traversal. So on average, your "find an object" code will be O(N) if there are N objects ... with a rather large constant of proportionality.

(Presumably, whoever placed that constraint on the problem didn't care about performance. You should take the same attitude ... especially given the context set out in your comments.)

You could improve the code in a couple ways that will make it more readable and (most likely) more efficient.

1. Use "break to label" so that the inner loops exit to the end of the outer loop when they get a hit. (Assuming that's what you want.)

2. Use temporary variables to avoid evaluating multiple method calls each time you lookup an element in the container hierarchy. UPDATE: it looks like you've just rewritten the code to do that ...

---

... project requirements dictate that each object needs to be instantiate in a multi-tree data structure as shown in the diagram I posted.

But do they expressly forbid a secondary data structure? Or have you just assumed that you are not allowed to do that?

Answer 3

I would use the for-each loop instead:

int index = Integer.parseInt(stat);
for(Party party : parties){
    if( index == party.members.get( c ).getIndex() ){
        generateInterface.theGame.printOutput( "\t" + party.summary );
        break;
    } else {
        for(Creature creature : party.Creatures){
            // etc etc.....
        }
    }
}

That would make the code a little easier to read. It does have the disadvantage that you do not have a counter built into the loop.

EDIT: This article may clarify: https://blogs.oracle.com/CoreJavaTechTips/entry/using_enhanced_for_loops_with

Answer 4

This is a pretty odd constraint set, but in the spirit of tree traversal without needing to modify the original data structure at all, why not write the naive recursive traversal function as a set of overloaded methods? It might look like this:

public Object search(int index, Cave c) {
  if (c.id == index) return c;

  for (Party p : c.parties) {
    Object result = search(index, p);
    if (result != null) 
      return result;
  }

  return null;
}

public Object search(int index, Party p) {
  ...
}

And so on.