Really Stuck With Recursive Tree Problem

General
1

I have spent ages on this problem and I know it must be staring me in the face but I just can’t figure it out.

I have (heavily) modified old code by @Kem_Tekinay and @Jeremy_Cowgar (see here) that takes a Xojo project file and parses it into the constituent items (such as modules, classes, interfaces, etc).

This code creates a File instance for each class, module, etc. Each File tracks the unique ID of it’s parent (which might be the root of the project, a module, folder, etc). It uses this information to construct the Files name and path.

After modification, my code knows the path in the project for every item. For example, given this project structure:

App
Class1
Module1
- Module2
--- Class2
- Class3
Folder
- SubFolder
-- Class4

I have this information:

App.Path = ""
Class1.Path = ""
Module1.Path = ""
Class2.Path = "Module1>Module2"
Class3.Path = "Module1"
Folder.Path = ""
SubFolder.Path = "Folder"
Class4.Path = "Folder>SubFolder"

I also know the unique ID for each item’s parent.

I’ve been trying for hours to turn this flat structure into a tree. Specifically, I want to use @Björn_Eiríksson TreeView control to represent this hierarchy. I know I need to use some sort of recursion but I just can’t work out how to find nodes that have already been added to the tree view. At this point I’d settle for using a hierarchical listbox.

Any help would be greatly appreciated.

As you might imagine, this is for a tool in development to help other Xojo coders manage their projects.

2

You could loop through your paths I guess and Link your Path to Dictionary where the Path is the Key and the Value is TreeViewNode (or class derrived from that if you want to store additional properties on it)

So if you check in the dictionary for existence of the path then your not adding it again.

But its really hard from your info to know whats good for you though. Like is it guarantied you get the parent node before you get child node in your data, I would think thats important.

3

Depth-First or Breadth-First search algorithm? Wikipedia should provide details.

4

Do you want to just get it into the control, or do you need to use it for some purpose beyond the control? If the latter, you may want to create an actual tree structure with objects, which you can then easily traverse for a range of purposes, to include populating the control.

Similar to Björn’s idea with a dictionary, you could also use an array in which you insert the paths. Only add a path if IndexOf is -1, though assuming the source list doesn’t have duplicates, you can just add without testing. The sort the array (assumes you don’t care about ordering; if you do, maintain that in a related array and use SortWith). If you are using a hierarchical listbox, then initial population is scanning the array for items with no path separator; look at the next item in the list to see if it has the same base path to determine if the node you are adding has a child and should be added with AddExpandableRow. Store the full path to the node in either a hidden column or the row tag. Then, when a row is clicked to expand, first find the clicked node with IndexOf, then just add all of the subsequent items with the matching base path of the clicked node (adding their full paths to the row tag) – these are the children, and due to the sort, they are in order; just go until you hit one with different base path (or the end).
Since this is Xojo projects, I don’t think these arrays will be huge, and once you find a node with IndexOf (which I assume is optimized…), it’s sequential read. You wouldn’t be able to do this part with the Dictionary,

1 Like
5

Modify the File class to include these properties:

  • Children() as File
  • mParent As WeakRef
  • Parent.Get (returns mParent.Value)
  • Parent.Set (sets mParent)

In your example, App, Class1, and Module1 would be siblings. Module2 and Class3 would be children of Module1, and Class2 would be a child of Module2.

Traversing would be as easy as storing each top-level parent in a RowTag. When expanding, it would merely loop through the Children, storing each one in a RowTag as well.

1 Like
6

Having done simple Org charts in the past, my take on the tree view process is a simple one.

‘All’ you need is a list of these:

{stuff about me} , {myUniqueID}, {ParentUniqueID}

So if these were people, and {stuff about me} was just a name, you might have

Sam,1,0
Bill,2,1
Sandra,3,1
Jenny,4,3
Mike,5,4

Level 1 of your tree is ‘anything with no parent/ parent of 0’
eg
Sam

Now you have that, if you want to expand on Sam, and see his children, you want ‘anyone whose parent is 1 (sam’s ID)’

Sam
…Bill
…Sandra

You might want to know in advance which rows CAN be expanded.
Thats ‘rows with an ID which something else is using as the parent’, and that is true of all but Bill in the list above.

Now, say you want to expand Sandra…
Find rows whose parent is 3 (Sandras ID)

Sam
…Bill
…Sandra
…Jenny

SO:
I recommend creating an on-disc or in-memory database

can be a name, and can in fact be many fields, as long as you have a UniqueID and the ID of the parent.

Lets call the fields Stuff,MyID,ParentID, and the table MyList

A sample SQL query to return the children of the first row might be:

select a.Stuff, a.MyId, count(b.Kid) from
Mylist a left outer join Mylist b
on a.MyID = b.ParentID
group by a.stuff,a.MyId
order by a.Stuff;

Which would return

Bill,2,0 (or possibly Null)
Sandra,3,1

To add them to your list, Bill is an unexpandable row
Sandra is expandable

For FILES in an hierarchical listbox control, you might display the filename and icon instead of a person name.
You might store the folderitem object as a rowtag, for easy file access

7

OK. Thanks for all the help guys. It was all useful.

I borrowed a little bit of advice from column A and some from B and have finally figured it. I think a good night’s sleep was actually what was needed because I was able to purge loads of lines of redundant code in doing so.

I actually went down the recursion method route and parse the project into a tree. It’s then trivial to add that to Einhugur’s TreeView control.

3 Likes