9 Replies Latest reply: Aug 9, 2009 11:32 AM by YoungWinston

# N-Ary tree lengths

What is the best way of calculating the length of a specific node?

I'm working on code folding, and am storing each line of text as a node of a tree structure. When the user clicks on a line in the editor, I need to know which node is currently selected so I know what to edit.
I figured that if each node holds its own length(based on how many children and grand-children and so on it has) that I can find where the line of code is within the tree.

However I'm trying to find either the most efficient way of calculating this length, or another way altogether.

I was working on the length as 1(itself) plus each child, which they in turn calculate this. Which to m seems horrible in efficient if done for ever line select in the editor.
Any help?
• ###### 1. Re: N-Ary tree lengths
agehoops wrote:
What is the best way of calculating the length of a specific node?
FYI, tree nodes have a height, not a length.
I'm working on code folding, and am storing each line of text as a node of a tree structure. When the user clicks on a line in the editor, I need to know which node is currently selected so I know what to edit.
I figured that if each node holds its own length(based on how many children and grand-children and so on it has) that I can find where the line of code is within the tree.

However I'm trying to find either the most efficient way of calculating this length, or another way altogether.

I was working on the length as 1(itself) plus each child, which they in turn calculate this. Which to m seems horrible in efficient if done for ever line select in the editor.
Any help?
Err, help with what exactly?
• ###### 2. Re: N-Ary tree lengths
agehoops wrote:
What is the best way of calculating the length of a specific node?
Wrong question, I suspect.
I'm working on code folding, and am storing each line of text as a node of a tree structure. When the user clicks on a line in the editor, I need to know which node is currently selected so I know what to edit.
I figured that if each node holds its own length(based on how many children and grand-children and so on it has) that I can find where the line of code is within the tree.
Now we're getting somewhere.
At the risk of sounding like a schoolteacher, I think you're falling into the trap of thinking about a solution based on an implementation, rather than coming up with a design based on a problem and then implementing it.

"I need to store source code (lines of text) in a way that allows groups of lines to be folded; groups can themselves contain other groups that can be folded. What is the best way of holding the source code for folding purposes?"

Assuming that the above statement is close to the problem, we can probably agree that a Tree structure of some sort is appropriate; however, we aren't constrained by your implementation decision to "stor[e] each line of text as a node of a tree structure".
You may have other reasons for that decision, but it seems much more likely to me that a node should include a set (or range) of lines, rather than a single one. The nice thing about this decision is that there's nothing to stop you having a "set" of 1 line.
However I'm trying to find either the most efficient way of calculating this length, or another way altogether.
Again, this will depend on implementation. One possibility is to include a pointer to a "parent" node, but there are many others.

HIH

Winston
• ###### 3. Re: N-Ary tree lengths
Sorry I should have explained a bit further. The code being edited is xml, and will only ever be XML

I've been looking around and have found the java Document which i can parse the XML file into which creates my tree for me automatically which (i'm guessing) makes life a lot easier?

How do I link this with my GUI though? If I have a text area or similar component and I click on a line, how do I link this line to a node within the document?
• ###### 4. Re: N-Ary tree lengths
Then why not use a JTree?
[http://java.sun.com/docs/books/tutorial/uiswing/components/tree.html]
• ###### 5. Re: N-Ary tree lengths
Doesn't have the flexibility I'm after otherwise I would for sheer simplicity
• ###### 6. Re: N-Ary tree lengths
agehoops wrote:
Doesn't have the flexibility I'm after otherwise I would for sheer simplicity
Sounds like DOM (or some variant) is what you want. I suspect you'll need to decorate the supplied components to implement your "folding" requirements though.

Winston
• ###### 7. Re: N-Ary tree lengths
Well I'm looking at the DOM using the XML parser built in to generate my DOM of the XML, but how do I link it with the text component? I know I have to do the graphics side myself in terms of drawing the fold points and such but how do i know where in the dom I currently am when I click somewhere in the text
• ###### 8. Re: N-Ary tree lengths
agehoops wrote:
Well I'm looking at the DOM using the XML parser built in to generate my DOM of the XML, but how do I link it with the text component? I know I have to do the graphics side myself in terms of drawing the fold points and such but how do i know where in the dom I currently am when I click somewhere in the text
Aha, a further requirement. So, we're not really dealing with lines of text, what we have is a block of text that you want to interpret in two different ways (a DOM and a character offset) with translation between the two. I suspect you're going to need some collection (maybe this should be your tree) that keeps track of DOM changes by character offset. I'm not familiar enough with the DOM API to know if it provides such a facility, but I doubt it. I think you might be down to building a similar structure with character offset (or line.char) ranges.

Winston

PS: If you do find such a beast already written by someone, do let us know. I'm currently working on a Line/Character holder for source code parsing myself, and I do hate reinventing the wheel :-).
• ###### 9. Re: N-Ary tree lengths
agehoops wrote:
Well I'm looking at the DOM using the XML parser...
You might also want to look at SAX.

Winston