Efficient Inheritance Relationship Checking

I’m working on a team making an RPG, and the lead designer needed a way to quickly check whether some class A (on the data level, not the code level) is derived from another class B. Here is the solution. This is actually a solution for mapping any partially ordering relation into pairs of real numbers.

Static Forward-Reverse Order

This is the best way if you know your entire hierarchy at compile time. Assign each class two numbers as follows: The base of the hierarchy gets the pair <0,0>. From there, do a leftmost preorder depth-first traversal and assign the first element of the tuple increasing natural numbers. For example:

                <0,0>
                /    \
             <1,>   <3,>
             /
           <2,>

Now start at the top again, and do the same thing for the right element of the tuple, starting at zero, and doing a rightmost traversal. So this hierarchy becomes:

                <0,0>
                /    \
             <1,2>  <3,1>
             /
           <2,3>

And now, a class with the tuple <a,b> is derived from <c,d> iff a ≥ c and b ≥ d. If a<c and b<d, then <a,b> is a parent of <c,d> If neither of these cases hold, then the two classes are siblings.

Interval Arithmetic

That’s all well and good, but it fails in the presence of dynamic hierarchies. What if someone loads a module at runtime that defines a new class? Then you have to recompute everything, which may not be practical (though it may; it depends on your design). Our next solution relies on the structure of intervals of a line. We’ll use the intervals in the naturals less than 232.

Again, classes are assigned duples of numbers. This time, they represent an interval. If class A’s interval is contained within class B’s, then A is derived from B. Here’s the algorithm:

Factor your hierarchy into a binary tree using “dummy” classes. It’s probably best to turn it into a linked node tree (where every node is a child of a dummy node) so it can be extended anywhere. Start at the root of the hierarchy again, and assign it the tuple <0,231-1>, that is, the interval containing the entire line. Proceeding downward, for each node in the tree, assign its left child the lower half of the node’s interval, and the right child the upper half. Then you’re done. <a,b> is derived from <c,d> iff a ≥ c and b ≤ d.

Infinite Precision

That falls down when you have more than 32 levels of inheritance, which, admittedly, is more than any reasonable designer would use. However, because the tree has been factored into a binary tree, those 32 levels can come from a completely flat hierarchy. So we’d like to use infinite precision numbers, without using a slow infinite precision library.

Larry Wall points out that strings make really good infinite precision numbers. But you can’t do the trick above starting at <0,∞>, since you can’t represent infinity. However, if you store the tuples in the form <a,~b> (where ~ is the compliment operator), then you can! The top node again gets <0,0>, since 0 is the compliment of infinity. Then each level in the tree has an associated bit position (increasing with level) that is incremented to its children. The left child gets incremented in the left tuple element, the right child gets incremented in the right tuple position. And then the familiar relation <a,b> is derived from <c,d> iff a ≥ b and c ≥ d holds, where > represents a stringwise comparison. For example:

                <0,0>
               /     \
             <.1,0>  <0,.1>
             /    \       \
        <.11,0> <.1,.01>  <0,.11>

(Note the point in front of the numbers. That just means that they start with the highest order bit and get lower as you move to the right).

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s