0

Say you have a set of objects that are arranged into a hierarchy. That is, there is an all encompassing object, then that object refers to several objects of the same kind but at a lower level, and each of those objects refer to several objects of the same kind but of a lower level, and so on for a variable number of steps. For example sake, lets consider these objects to be governments, so the highest level would be global, then global would have countries, and tribes, and countries would have towns, and towns would have houses, and businesses ect. All these governments extend the gov abstract class, so they all share the same kind.

I need to iterate through all the objects in the whole hierarchy, but because I don't know the complete structure at run-time, I have to do it in a generalized fashion.I only know for certain that there is a Global government, and then I have to check what sub-governments it has to proceed.

One way I'v found to do it is to give the super class a function called getSubGovs() which returns a list of all it's sub governments plus what each of those sub governments return from getSubGovs(). I hope that makes sense. It's a nice way to recurs through the problem.

What I'm looking for is a way to do this without having to add a function to the super class, for the case where I'm dealing with an API and cannot modify the super class. What would be an elegant way to do that?

Kammeot
  • 469
  • 7
  • 18
  • Do you want to perform a common operation on all objects in your structure? If so, what type of operation? If not, why do you want to iterate over it? – Bohemian Aug 22 '13 at 02:42

2 Answers2

0

I'm not 100% certain about what you want to achieve, but I believe what you would want here is polymorphism, namely inheritance and virtual functions (I dunno which language you are using but C++, for example, supports this).

Basically, you would make Global government the base class, and all your other classes the derived classes which would inherit Global government (or each other). Through inheritance you can establish the hierarchy you want (for example, by making classes lower in the hierarchy inherit from classes higher up in the hierarchy).

This page covers inheritance: http://en.wikipedia.org/wiki/Inheritance_(object-oriented_programming)

Now for the iterative part: first, you declare functions/methods virtual (using the keyword virtual) in the base class (e.g. global government). The derived classes will overwrite this function and customize it however they want. Note that you do not need the virtual keyword in the derived classes.

Here is the cool part: while you are iterating through the mix of sub and super classes, you use the base class pointer for all. Even when you call the functions of derived classes from a base class pointer, because you declared the functions you need virtual, the C++ determines which version of the function to call based upon the type of the object pointed to by the pointer. This determination is made at runtime, therefore you don't even need to worry about which object in the hierarchy the pointer is pointing to.

This page covers virtual functions: http://en.wikipedia.org/wiki/Virtual_inheritance.

Hope this is the sort of thing you wanted.

EDIT:

According to this page:

How do you find all subclasses of a given class in Java?

There is no elegant method, you will have to look at every class on the classpath.

Community
  • 1
  • 1
Joohwan
  • 2,374
  • 1
  • 19
  • 30
  • Well, I'm using Java, which shares a lot of similarities with C++. I did use inheritance for my version of the solution, which is pretty elegant, but not always available. I think I maybe didn't phrase the question well. The problem is more hypothetical than anything and I'm interested in a logic algorithm that can look at a hierarchy from the outside (with only access to the function getImmediateSubGov() which returns only the governments directly below the associated object and not, for instance, the subgovs of it's subgovs.) This is for the case where I'm given an API which I can't change. – Kammeot Aug 22 '13 at 01:25
0

This kind of structure is called a tree

Normally, every tree node has the same type, which has a getChildren() method or similar - in your case getSubGovs(). It sounds like each class has its own way of getting the children, so a straightforward abstraction is not possible.

The standard software pattern to apply that can navigate the tree in a generalised way is the visitor pattern, but because you can't modify the classes, you may need the facade pattern too.

Bohemian
  • 412,405
  • 93
  • 575
  • 722