Where to put the code that searches objects in a complex hierarchy?

Question

Given the following hierarchy of objects: a keyed collection of ClassA objects, where each ClassA object contains a keyed collection of ClassB objects and each ClassB object contains a keyed collection of ClassC objects.

No suppose we start out with the root collection of ClassA objects (called a_objs) and we want to look for a ClassC object with a specific key. The (pseudo) code would look something like this:

a = a_objs.get(a_key);
if (a) {
 b = a.get(b_key);
 if (b) {
 c = b.get(c_key);
 }
}
if (c) {
 // do the actual work with object c
}

The code that tries to find the requested ClassC object looks relatively simple, but can be bigger or more complex depending on the depth of the hierarchy or the kind of search that is necessary (e.g. find first ClassC object that has a certain property). Also with regards to unit testing it would be useful to be able to write separate tests for the code that searches the ClassC object and for the code that does the actions on the ClassC object.

As such I think it would be best to move the search for a ClassC object to a dedicated function:

c = findC(a_objs, <params depending on specific search operation>)
if (c) {
 // do the actual work with object c
}

My question is now: where should I put this findC() function?

I don't want to put it in the file that contains the calling code, because it will be called from multiple different files. I also don't feel like it fits in the files for any of the objects in the hierarchy (ClassA, ClassB, ClassC) because they should only need to know about the piece of the hierarchy they directly maintain (ClassA maintains a collection of ClassB objects, but doesn't need to know that ClassB contains a collection of ClassC objects).

Should I create a dedicated Manager-like object for the hierarchy and its search operations? Should it reside in some generic Utility file somewhere?

Edit: The languague I am working in is C.

Edit: Another example of a search action would be to look for the next ClassC object in the hierarchy, given a specific ClassC object (specific <a_key, b_key, c_key>).

• Robert Harvey: Well, your pedantic peers will not like Manager or Utility. Call them whatever you want, but yes, the idea is to put the function in some central location where it can be shared.
• Caleth: If your language supports free functions, you can make it a free function, probably in the same namespace as C, or maybe in a subnamespace like Queries
• Greg Burghardt: Without knowing more about what this search utility needs to do, this almost sounds like a textbook case for the visitor pattern.

Answer 1

Based on what you've said (and not knowing the language), I'd probably do something like

1. Create an interface ISearchable, containing a single method: Optional<T> satisfies<T>(<predicate function parameter>, boolean recursive)
2. Your hierarchy would then all extend this interface. Each one would search itself (if it's of type T) or (if recursive is set) call the function on each of its children until it finds one, returning a failure state (empty Optional) (if it doesn't satisfy the condition itself OR is not of type T) AND (recursive is not set OR the type does not contain any ISearchable collections).

Effectively, that means that the caller only has to know that it has an ISearchable, then the each level only has to know about itself and its children. This extends to arbitrary hierarchy depth and can adapt to any search (you only need to filter on ClassC...for now). And returns sane values when it fails. And it means you're not locked to a keyed collection either, since each extending entity decides how to iterate over its children. Heck, it may only have one child. Or none at all.

You could even make it always recursive and spare the parameter.

Answer 2

A first option is to look how similar problems are solved in popular designs. The first that comes to my mind is the document object model (dom) that is used to manipulate html documents an their elements. The dom interface exposes several get methods to access to one or several elements of the hierarchy.

The question for your design is if classA shouldn't better expose such a method to access class C elements. Because forcing to go successively through hierarchical levels creates a hidden coupling with assumptions on classes internals at several levels. This is not fully in line with the principle of least knowledge. There may be valid reasons to do so, however.

Another approach would be to use the query object pattern. This would suit your needs and even allow to provide for search criteria in a very elegant way.