Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursive tree-like class in java?

 
Ben Ethridge
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, all.
I've looked around here at javaranch, at the FAQ's and the code barn, and also at the Sun Java API, but I can't yet find a tree-like array class in regular java. I'm thinking many programmmers must have had the need for one, so if Sun hasn't written one, surely someone else has.
When I say tree-like class, I mean a structure similar to a directory tree structure or an XML tree structure, in which there is a recursive one-to-many parent-child relationship, with methods that allow one to walk up and down the tree.
Anyone know of such a beast?
Respectfully,
Ben Ethridge
 
Joe Ess
Bartender
Posts: 9300
10
Linux Mac OS X Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's two that I know of in the Java API:
Look at the javax.swing.tree and org.w3c.dom packages.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's pretty simple to roll your own. A node in the tree needs to be able to navigate to its children, and (maybe) to its parent.

Then just add functionality from there. There are many interesting types of trees: b-trees, balanced, self-balancing, ternary search trees ... probably a whole CS class worth. Do you have some fun requirements to meet here?
 
Ben Ethridge
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Define "fun". I could do it myself, but I'm too lazy. :-)
Seriously, this would be a recursive array of Objects, i.e would hold an objects (any type), but not primitives. Similar to TreeSet or Vector. Let's call it a "TreeArray", unless someone can think of a more appropriate name.
Each "parent" element would hold an Object containing the value of the parent, plus an array of TreeArray objects. (Thus the recursion.)
Methods would allow the caller to "walk" the TreeArray, and yes, this is very similar to what's available in DOM. However, I don't want it to be exclusively about DOM or Swing. I want it to be about simple old Object, same as, say, TreeSet or ArrayList in the 1.4 API.
In fact, I'm a little amazed this isn't in the 1.4 API. This kind of class has probably been reinvented a thousand times. If no one has one I can use, and none of you want to write it for fun, profit and/or glory :-)...
...I guess I'll just have to "cowboy-up", write it myself, and post it for you all. Who knows? Maybe it'll even make it to the code barn. Yeehaw!
Respectfully,
Ben
 
Wayne L Johnson
Ranch Hand
Posts: 399
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about javax.swing.tree.DefaultMutableTreeNode? This class has a single parent, multiple children, and holds onto an optional "user object". This is the default class used by JTree and it can be a parent node (holding on to a bunch of children) or a leaf node (holding on to a user object). There are methods to add children, remove children, walk the tree structure, etc.
Unless I misunderstand your question, I think this would be just what you are looking for ...
 
Ben Ethridge
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that's exactly what I need. Thanks, Wayne.
Joe, please pardon my ignorance of the swing.tree package. I thought it was only for GUI development.
Respectfully,
Ben
 
Maulin Vasavada
Ranch Hand
Posts: 1873
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Charles
Here is a very minor issue though. I hesitate to use swing package classes if not needed because I faced one problem on one instance of webserver.
The issue was- somehow the AWT's .so file was missing or something (not the awt.so but some other JNI impl files) and then it took us 4 day to debug that on the server to figure out what is missing. My code was a servlet using AWT's java.awt.List as that class is the only, as far as I know, provides simple way of inserting dynamic String objects and return array of String in "one shot" via getItems()...
Just a thought. (Still I end up using java.awt.List in servlets due to the functionality mentioned above )
Regards
Maulin
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'll just throw in the Visitor Pattern for fun. If you build your own nodes, you can build the mechanism to "walk" the tree right in to it, so clients never have to iterate children and all that repetitive drudge.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic