The Tree Trimming Issue

Part I

2013-09-18

How would I traverse a tree structure but handle each node according the sequence of handler dependencies? Or, to put it another way, manipulate one tree of "objects" with another tree of "functions". This is a problem I've found myself thinking about and what follows is just my heavily diagrammed description of it.

An Example Tree Structure

Here's an example of a tree structure - a segment of a file system; directories and files:

The Handlers

Assume that we want to manipulate each of these nodes with certain functions. A function can be assigned to more than one node of the tree. Execution of a function may depend upon another function having been executed previously. So, our functions also form a tree of dependencies which need to execute in a specific order:

Putting Them Together

When we assign each node of our tree with a handler we end up with a view of our file tree that looks like this:

A View of the Problem

Traversing the tree of files might run in the following order:

This is fine, except when we consider that we want to execute our handler functions in the order of their dependencies and not those of the file tree. For example, the blog-index-handler depends upon the markdown-handler:

The copy-index-handler in turn is dependant upon the executing of the blog-index-handler:

The tag-handler nodes are also dependant upon the markdown-handler:

What Needs To Happen

Somehow I need to arrange the order of node processing such that independent handlers process first:

Then the second layer of dependant handlers:

Until the last layer of dependant handlers:

Solutions

It is interesting how just describing a problem in some detail can suddenly make an answer appear. Prior to writing this post my view of the problem was very one-directional, from the point of view of traversing the file/directory tree, rather than the alternative of traversing the handler tree. In a follow up post I may detail how this was solved with some working code.

Tags: patterns