Matching against type hierarchy

Question

Suppose we have a fixed type hierarchy, e.g. as depicted below. It is a well-defined tree, where each node has one parent (except for the root).

Each type has an action associated with it, that should be performed upon successful matching. This does not mean that an action corresponds to a method on said type. It's just arbitrary association.

What are intelligent ways to match objects against a type hierarchy? Each object should be matched against the most specific type possible. The objects are already created.

Answer 1

Use recursive search from the root.

Once no match can be found in children, remember the matched object if its level is deeper than the last match.

Pseudocode:

    class MatchContext {
         public int level;
         public Node result;
    }

    public boolean match(Node object, int level, MatchContext ctx) {
        if (no match)
            return false;
        boolean found = false;
        for (all children in object) {
            if (match(child, level + 1, ctx))
                found = true;
        }
        if (!found && level > ctx.level) {
            ctx.level = level;
            ctx.result = this;
        }
        return found;
    }

Invoke it like this:

    MatchContext ctx;
    if (match(root, 0, ctx))
        myAction(ctx.result);