Making Good Software

A blog by Alberto G (Alberto Gutierrez)

Written by Alberto Gutierrez

July 25th, 2010 at 12:11 pm

Java and tree data structures.

with 18 comments

There isn’t any standard java implementation.

In almost every single project I have been involved, at some stage, I have found necessary to use a tree data structure, but I have found myself rewriting the same code to represent it because Java doesn’t provide with standard interfaces and implementations for Trees.

There are some open source tree data structures, but they are not flexible enough.

It is also surprising that there isn’t any major open source project, at least that I’m aware of, that tries to fill this gap. I have found on the Internet a few attempts to implement trees, but even thought they are correct, I don’t think they are as flexible as they should be.

The usual solution, the composite pattern on the objects itself, is far from ideal.

The most common implementation of trees, is using the composite pattern on the objects itself, meaning that no abstractions are created for classes as Tree, or Node. This approach has two main flaws:

  • Low cohesion: Now each object which is member of the tree needs to also have methods for navigation, insertion or other operations which are completely out of the scope of their own nature.
  • High coupling: Each node knows about their parents or about their children, changing one of them usually requires to changes the others as well.

How it should be (IMHO)

In my opinion, these are at least the main characteristics that a flexible Tree library should have.

  1. Ability to branch and sub-branch. Instead hanging nodes directly from other nodes, have the ability to add branches and sub-branches to nodes and hang the child nodes from them.
  2. XPath enabled. So you can call something like Node<Something> node = tree.get (“path/to/node”);
  3. Navigation specified through strategy. Navigator nav = tree.getNavigator (Strategy);
  4. Ability to filter.Navigator nav = tree.getNavigator (Strategy, Filter);
  5. Ability to create sub-trees from nodes. Tree subTree = new Tree (tree.get (“path/to/node”));
  6. Multi-threaded.

Your opinion and collaboration.

The main reason to write this article, is that I’m actually about to start writing this library myself, and I would like to share it with everyone, but before, I would like to hear from you guys. What’s your opinion: Do you think this sort of library would be useful? Would you use it? Do you think there are classes already that I might not know that have this functionality?

I am really looking forward for your comments!

Update

To find more information about the above mentioned Java tree library, including the SVN locations to download the source code check here.