Monday, March 1, 2010

Things I Ponder About

I've been working on a new parser for fitSharp and one of the things I've been kicking around is how to model a tree structure. This is what I'm currently looking at:

public interface Tree<T> { T Value { get; } IEnumerable<Tree<T>> Branches { get; } }
This says that a tree node has a collection of tree nodes that are its branches.

The existing Fit code base takes a different approach, something like this:

public interface Tree<T> { T Value { get; } Tree<T> Child { get; } Tree<T> Sibling { get; } }
This says that a tree node is related to two other nodes, a child and a sibling. (Fit calls them Parts and More). This model actually gives us more information, since we can get a node's sibling, which the first doesn't provide.

But when I started writing implementing classes, I ran into a tangle. I wanted a method to add a branch:

public void AddBranch(Tree<T> newBranch) { ... }
With the first model, this was simple. But with the second model, I need to be able to modify a branch to link in the new branch. So I need to know more about the branches than the basic Tree interface tells me.  The additional information it provides comes with a cost.

Do I really want to pay for the extra benefit of knowing a node's sibling? I don't think so. One thing I find confusing in the Fit code base is that a tree node has two uses. Sometimes it's used as a single node (a table, row or cell) and sometimes as a collection (tables, rows or cells) that can be iterated over using the sibling link. If I mean a collection, I think I should use a collection, like the Branches in the first model.

These are the things I ponder.

No comments:

Post a Comment