HOOPS Exchange Hierarchy Traversal: Part 2
By Brad Flubacher • This is part two of the two-part article describing a generalized algorithm for traversing the object hierarchy implemented in HOOPS Exchange. If you haven’t started with part 1 or you’d like a quick review you can find it here.
In part 1, we systematically developed a single function called getChildren which returns a collection of child objects owned by a parent. The function’s input parameters allow the caller to specify the type of child objects desired from the parent object. Recall that the function is implemented using unordered hashes to lookup a getter function object. The key values for the hashes are the object type of the parent and the object type of the desired child objects.
The function body declared some type aliases that make the implementation easier to understand and maintain. Recall the following statements:
using Getter = std::function<ts3d::EntityArray(A3DEntity*)>;
using ChildTypeToGetter = std::unordered_map<A3DEEntityType, Getter>;
using ParentTypeToChildTypeToGetter =
std::unordered_map<A3DEEntityType, ChildTypeToGetter>;The type ParentTypeToChildTypeToGetter is the operative standard container here. The function body goes on to declare a static instance of this container populated with all Exchange object types that might contain children objects. For the purposes of the article, we only showed a few object types and getter functions for illustrative purposes. A complete declaration of this container can be found in ExchangeToolkit.h (link).
In this article, we’ll continue to build the functionality we described as the goal in part 1, that is, a generalized algorithm for obtaining a collection of descendant children of a specified type, given a parent object. The algorithm we’ll create is going to be based on the contents of the ParentTypeToChildTypeToGetter instance containing the complete Exchange data hierarchy.
Finding the immediate children of a specified type is quite simple. This was the behavior we implemented in getChildren of Part 1. However, the goal we set out to achieve is to include the traversal of intermediate objects that may exist in the object hierarchy. For example, you might use this functionality to obtain all A3DTopoEdge objects of a provided A3DTopoFace object. To do this, the algorithm must be smart enough to “know” it must start with the list of A3DTopoLoop objects owned by the face, then it must get the A3DTopoCoEdge objects from each loop, then finally it will arrive at the desired child type from each co-edge.
To achieve this goal, I’d like to begin by introducing new type aliases that will be useful to us:
using TypePath = std::vector<A3DEEntityType>;
using TypePathArray = std::vector<TypePath>;
using TypeSet = std::set<A3DEEntityType>; A TypePath is an ordered collection of A3DEEntityType values. For the case of finding all edges used by a particular face, the TypePath we’d like to use would be:
TypePath tp = { kA3DTypeTopoLoop, kA3DTypeTopoCoEdge, kA3DTypeTopoEdge };This specific instance of a TypePath would allow us to make repeated calls to the getChildren function, ultimately allowing us to arrive at the collection of edges by traversing through the intermediate object types (loops and co-edges).
A naïve approach to implementing desired functionality might be to declare all possible TypePath instances a priori. This is a bad idea for more reasons than I care to write about, so I think I’ll just move on.
Since all possible TypePath combinations exist in the (complete) instance of the ParentTypeToChildTypeToGetter hash, we can instead use this as our data model to extract the needed TypePath instances given a parent and descendant object type.
To do this, we begin by implementing a function that returns a TypeSet of possible parent object types, given a child object type. For example, this function should return the set { kA3DTypeAsmModelFile, kA3DTypeAsmProductOccurrence } when kA3DTypeAsmProductOccurrence is provided as the argument.
TypeSet getPossibleParents(A3DEEntityType const &child_type) {
TypeSet possible_parents;
for(auto const &owning_type_entry : _getterMapByParentType) {
auto const &owning_type = owning_type_entry.first;
for(auto const &child_type_entry : owning_type_entry.second) {
if(child_type_entry.first == child_type) {
possible_parents.insert(owning_type);
break;
}
}
}
return possible_parents;This function is implemented to loop over the entire hash. Recall _getterMapByParentType was declared inside Part 1’s final implementation of getChildren. For simplicity’s sake, we’re assuming we have access to it here. In the actual implementation found in ExchangeToolkit.h, it’s declared as a static instance.
Using this as a utility, we’re now in a good position to write a function that returns all possible type paths that start with the owning object type, traversing through arbitrary types of intermediate objects, and ending with the desired child type specified by the caller. To do this, we’ll simply call this function repeatedly, traversing backward through the hierarchy.
TypePathArray getPossibleTypePaths(A3DEEntityType const &parent_type,
A3DEEntityType const &child_type) {
TypePathArray type_paths;
auto const possible_parents = getPossibleParents(child_type);
if(std::end(possible_parents) != possible_parents.find(parent_type)) {
// child entity type is an immediate child of parent entity type
TypePath type_path;
type_path.push_back(parent_type);
type_path.push_back(child_type);
type_paths.push_back(type_path);
} else {
// child entity type is not an immediate child of parent entity type
// so we must iterate over the list of all possible parent types
// and for each of those parent types, examine up the ownership chain
for(auto const intermediate_parent_type : possible_parents) {
if(intermediate_parent_type != child_type) {
auto const intermediate_type_paths =
getPossibleTypePaths(parent_type, intermediate_parent_type);
for(auto const &intermediate_type_path : intermediate_type_paths) {
type_paths.push_back(intermediate_type_path);
type_paths.back().push_back(child_type);
}
}
}
}
return type_paths;
At this point, we’ve created some rather straightforward functionality for decomposing the hierarchical data contained within the parent-child-getter hash maps. With this new functionality, we now can easily obtain possible paths through the Exchange object hierarchy, beginning with any arbitrary object type, leading to any arbitrary child type, taking intermediate objects into account.
A quick aside- I subscribe fully to the practice of coding first and optimizing later. It’s worth noting that within each of these functions, using a simple caching mechanism will have a positive impact on the performance. I’m leaving such optimizations out for the sake of clarity. Also, there are corner cases not considered, but again for the sake of clarity I’m glossing over them here and I will continue to do so in some code snippets yet to come. The purpose of this article is to convey understanding, rather than provide a production-ready implementation.
Now that I’ve got that out of the way, I’ll next present a possible implementation for a function that returns a set of objects matching the desired type from an owner, taking intermediate objects into account. It might look something like this
ts3d::EntitySet getChildrenUsingTypePath(A3DEntity *owner,
TypePath const &type_path) {
ts3d::EntitySet result;
if(type_path.size() < 2) {
return result;
}
auto const owner_type = type_path.front();
assert(owner_type == ts3d::getEntityType(owner));
auto const immediate_child_type = type_path[1];
auto const immediate_children =
_getterMapByParentType[owner_type][immediate_child_type](owner);
if(type_path.size() == 2) {
result.insert(immediate_children.begin(), immediate_children.end());
return result;
}
TypePath const intermediate_type_path(type_path.begin()+1, type_path.end());
for(auto const immediate_child : immediate_children) {
auto const children =
getChildrenUsingTypePath(immediate_child, intermediate_type_path);
result.insert(children.begin(), children.end());
}
return result;
}
This recursive function can be used to obtain all the children of an owning A3DEntity object by following the TypePath provided. It does this by first getting the immediate children that match the next entry in the type path. Next, it creates an intermediate type path by making a copy of the input path, dropping the first entry. Recursion occurs by looping over the immediate children, using each child and the intermediate type path as the arguments.
Finally, we’re ready to write the function we set as our goal from the very beginning of Part 1 of this article. Albeit somewhat anticlimactic, here it is:
ts3d::EntitySet getChildren(A3DEntity *owner, A3DEEntityType const child_type) {
ts3d::EntitySet result;
auto const owner_type = ts3d::getEntityType(owner);
auto const possible_type_paths = getPossibleTypePaths(owner_type, child_type);
for(auto const &possible_type_path : possible_type_paths) {
auto const children = getChildrenUsingTypePath( owner, possible_type_path);
result.insert(children.begin(), children.end());
}
return result;
}
This function and its implementation serve as a kind of entry point into the real work done by all the functions we laid out before it. The only notes worth making here, are that by obtaining all possible type paths, we must loop over the collection and invoke getChildrenUsingTypePath for each of them.
I’ll conclude by summarizing what we’ve achieved, and how we went about getting to this goal. I’d be doing you a disservice if I didn’t point out some of the shortcomings of this abridged implementation, so I’d also like to take a moment to point some of them out.
Our goal was to write a function to obtain a set of Exchange objects of a specified type, providing an arbitrary parent object and the desired object’s type. Internally, the implementation of this function traverses the Exchange object hierarchy in an intelligent way, starting with the owning object provided, and ending with every possible occurrence of the desired type of child object.
We accomplished this by first creating a data type (ParentTypeToChildTypeToGetter) to store key-value pairs. It is comprised of owner type, child types, and function objects serving as the “getter” corresponding to the owner/child type pair. We created and populated a single static instance of this data type (_getterMapByParentType), allowing us to create additional functionality for inspecting its contents.
Next, we turned our attention to some functionality that used this data map to construct possible pathways (by object type) through the Exchange data hierarchies (getPossibleTypePaths). We wrapped things up by using the type path information with the map of getter functions to perform the hierarchy traversal to obtain the desired child objects. Simple, right?
And now the caveats, notable exceptions, and omissions. As I mentioned earlier, my goal was to convey information and ideas more so than production ready code. As such, please don’t expect to copy/paste various bits of code from this article and begin using them without running into trouble.
The first major omission as noted in Part 1, is the fact that we only populated the hash map with a few object types and getters. It’s by no means complete. A far more complete instantiation of the hash can be found in ExchangeToolkit.h. Furthermore, some getter implementations aren’t as straightforward as I’ve presented them to be in this article. Specifically, I’m referring to getters related to A3DAsmProductOccurrence, which must take prototypes into account.
Another detail I purposefully glossed over in this article is the fact that Exchange contains some recursive containers. The code I’ve presented here cleverly avoids them but could be easily augmented to handle these cases with relative ease. I skipped this in favor of code that’s more easily understood. Three examples of such containers are: A3DAsmProductOccurrence, A3DRiSet, and A3DMkpAnnotationSet. To handle these recursive containers correctly, you must identify occurrences of them within the function getChildrenUsingTypePath and handle them separately.
This leads me to what I think is the final omission, which is the fact that Exchange contains an object hierarchy, which I’ve avoided entirely here. For example, A3DRiRepresentationItem is a “base class” for many different concrete representation item types. For our function to handle this correctly, we would have to perform a bit of a dance around base types, derived types, and correctly traverse whichever levels of the “class hierarchy” we might encounter.
Rest assured; the benefits outweigh the costs of skipping over some of these details. By reading this far, you can now step through the implementations of related functions appearing in ExchangeToolkit.h with a nearly complete understanding of what it’s doing and why. Better still, you’re now better equipped to find problems that might exist or even to extend its behavior becoming a contributor as well as a consumer!
I sincerely hope you’ve enjoyed reading this article. If you did, please let us know by leaving a comment below. Your feedback is valuable!