• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Tree Structure + Depth First Traversal?

 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Posted up on Servlets forum but my question could not be answered. Maybe it was too vague.

Anyway,
How can I create a Tree that can be depth-first traversed?


It's gonna be for an HTML page. Method next() does Depth First Traversal.

each item will need some slighly complex, varied HTML representation, e.g. href, title, link text, className, optionalImageIcon, et c.

I need to know current, hasNext(), and also..

How do I build up this tree?
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What are you looking for? Trees are basic structures, and how next() work are implementation details. Are you looking for all the code to cut and paste? a prebuilt library? some Interface definitions to get you started?
 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ideally, you would write and test the code for me, I would copy-paste it, and it would work perfectly.

I'll take what I can get, though.

I need to know how to:
pick a tree structure that fulfills the need
define elements
add elements to the tree
do depth first traversal on the tree, while knowing the level.

The last step is crucial. I need to display nested lists on the navbar.


I would consider prebuilt lib code, but it probably won't do what I want it to. Most Java -> UI code doesn't.

So I think I should just roll up my sleeves and ask for advice
[ October 10, 2007: Message edited by: Garrett Smith ]
 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I want to figure out how to do this.

It's super easy in HTML -- just declare the tree as a list of lists.

In JavaScript, I'd probably write a Tree class that does what I want.

In Java, I need to create a depth-first traversable Tree that can print out a hierarchical structure (as html in my case).

How do I do this?
[ October 11, 2007: Message edited by: Garrett Smith ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A Java tree usually has a Node object something like:

You walk a tree, and in this case generate HTML, by doing something like:

Are you comfortable with that kind of recursion?

Look at the HTML you want to produce from this. I think every node puts out a LI tag. If the node has any children, it also puts out a UL tag around the children.

Along the way you need to detect when node is current page and make it text, not a link. Also note the next link generated and duplicate it in the NEXT link.

Many folks have a strong objection to generating HTML in Java. Once you get this going, we can ask them for alternatives.
[ October 11, 2007: Message edited by: Stan James ]
 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stan James:
A Java tree usually has a Node object something like:

You walk a tree, and in this case generate HTML, by doing something like:

Are you comfortable with that kind of recursion?

I have used this algorithm a few times.

every node puts out a LI tag. If the node has any children, it also puts out a UL tag around the children.

Yes.

Along the way you need to detect when node is current page and make it text, not a link.

Yes.

Also note the next link generated and duplicate it in the NEXT link.

I'll probably need something like:


Many folks have a strong objection to generating HTML in Java. Once you get this going, we can ask them for alternatives.

Putting the HTML in the Java code is messy.

I was thinking that it should be really easy to parse the OL as a fragment using an XML parser, and then walk the list tree. Apparently, that is a bad idea.

So back to putting the algorithm into Java code...



There must be a more standard way to do it.

I can check the current page by checking the requestURI.
[ October 11, 2007: Message edited by: Garrett Smith ]
 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now I am copy-pasting HTML into objects, escaping quote marks.
This is madness.

Parsing the list and the iterating the collection on the server would be less error-prone and would keep my HTML out of the objects.

This HTML parser looks like it might be able to do that. I haven't worked with streams in years, though.

http://htmlparser.sourceforge.net/javadoc/org/htmlparser/Parser.html
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Garrett Smith:
Ideally, you would write and test the code for me, I would copy-paste it, and it would work perfectly.


Hey, I'm a professional programmer, I expect to get paid for it to work perfectly.

Looks like you are getting help and making progress.
Java is actually fairly easy to do the node/tree stuff
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And now for something completely different ...

I recently made a tree with nested ULs that does dynamic open and close. I'd be tempted to reuse that and do all this in JavaScript. Of course users with script turned off would be out of luck.

Here's a little bit of how this works:

options is an array of objects with name and key fields. It comes from the server in JSON syntax like this:

You can generate JSON from your tree of Nodes with a one line call to the StringTree JSON library.
 
Garrett Smith
Ranch Hand
Posts: 401
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Pat Farrell:


Hey, I'm a professional programmer, I expect to get paid for it to work perfectly.

Sorry, bad joke.
Originally posted by Pat Farrell:

Looks like you are getting help and making progress.
Java is actually fairly easy to do the node/tree stuff


It isn't that hard to hard-code, but will be hard to maintain. I'm not putting markup in my HTML. I've been down that road.

Same thing with the JSON approach. Hard to maintain and requires inefficient client-side HTML transforms.

I'm considering the htmlparser. Parser.parse gives a NodeList.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The Quiotix HTML parser builds a DOM from HTML and provides a nifty Visitor interface to walk the DOM. You can modify nodes and use another Visitor to regenerate HTML that is more correct and beautiful than the original in many cases. I found Visitor much more fun than navigating the DOM myself. I've done this kind of thing in a pre-publish step that generated static HTML, but would find it very strange in dynamic server side processing.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic