Author Topic: Building a treeview with recursion  (Read 8214 times)

0 Members and 1 Guest are viewing this topic.

Keith™

  • Villiage Idiot
  • Seagull
  • Posts: 16828
  • Superior Stupidity at its best
Building a treeview with recursion
« on: March 19, 2009, 10:24:51 AM »
I'll admit that recursion has never been one of my strongest points, and I only use it except for the simplest of tasks. But I find myself once again in a situation that I "think" requires more than a case, while or for next loop.

I have a file (many actually) that must be read into an application and displayed on a treeview control, each line represents a single node and each line has a variable number of preceeding tabs that determine the heirarchy of the items in the file. Try as I might, I am not getting my head wrapped around this ... or maybe my last project fried my brain ... take your pick.

The file will look something like this:
Code: [Select]
Top Node1
        Child Node1_1
        Child Node1_2
                Child Node1_2_1
Top Node2
Top Node3
        Child Node3_1
        Child Node3_2
                Child Node3_2_1
                        Child Node3_2_1_1
                                Child Node3_2_1_1_1

... and I need it to look like this:

Proud provider of opinion and arrogance since November 22, 2003 at 09:35:31 am
CadJockey Militia Field Marshal

Find me on https://parler.com @kblackie

Tuoni

  • Gator
  • Posts: 3032
  • I do stuff, and things!
Re: Building a treeview with recursion
« Reply #1 on: March 19, 2009, 11:04:48 AM »
I did something similar with recursion in PHP a couple or three years back... http://www.theswamp.org/~tuoni/FileManagement/ (sorry about the roughness, it was a WIP which never got even close to being finished :( )

I can post the code if you'd like, but like I say it's all in PHP

Keith™

  • Villiage Idiot
  • Seagull
  • Posts: 16828
  • Superior Stupidity at its best
Re: Building a treeview with recursion
« Reply #2 on: March 19, 2009, 11:18:39 AM »
I could translate the php to .net, but I think this is more about concept than actual code. I am having a tough time wrapping my mind around it, not so much coding it.

I guess, what I need to do is understand the requirements a little better.

Currently, I have the entire contents of the file in a single variable that I can split
i.e.
Code: [Select]
Dim objLines As Object = Split(strFilecontents, vbCrLf)

I can also create a global var to hold the index (which line we are reading) then compare the current line to the previous one to determine if it is indeed a child. The best way I can figure to do that is to split the line by tabs

Code: [Select]
Dim curNode As Object = Split(objLines(N),vbTab)
Dim prvNode As Object = Split(objLines(N - 1), vbTab)
If Ubound(curNode) > Ubound(prvNode) Then
IsChild = True
End If

Now if it is a child, call the recursion function with the current node as the parent to add to.

At least that seems to be the concept. If the current node isn't a child, it backs up the line to the previous parent... I think

I'd appreciate any insight
Proud provider of opinion and arrogance since November 22, 2003 at 09:35:31 am
CadJockey Militia Field Marshal

Find me on https://parler.com @kblackie

T.Willey

  • Needs a day job
  • Posts: 5242
Re: Building a treeview with recursion
« Reply #3 on: March 19, 2009, 11:24:11 AM »
Couldn't you count the tabs, and then get the ' Parent ' property of the node just added?  In your example
Top Node1 ( no tab, new main node. )
        Child Node1_1 ( one tab more than previous, so it is owned by previous )
        Child Node1_2 ( same amount of tabs, owned by previous parent )
                Child Node1_2_1 ( one more tab than previous, so it is owned by previous )
Top Node2 ( no tab, new main node. )
Top Node3 ( no tab, new main node. )
        Child Node3_1 ( one tab more than previous, so it is owned by previous )
        Child Node3_2 ( same amount of tabs, owned by previous parent )
                Child Node3_2_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_1 ( one tab more than previous, so it is owned by previous )
                                Child Node3_2_1_1_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_2 ( one tab less than previous, so it is owned by previous parent's parent )

There is also a ' PrevNode ' property that may be of help also.
Tim

I don't want to ' end-up ', I want to ' become '. - Me

Please think about donating if this post helped you.

Tuoni

  • Gator
  • Posts: 3032
  • I do stuff, and things!
Re: Building a treeview with recursion
« Reply #4 on: March 19, 2009, 11:27:12 AM »
I could translate the php to .net, but I think this is more about concept than actual code. I am having a tough time wrapping my mind around it, not so much coding it.
Well that was kinda my thought.

So... here goes.  Please excuse dodgy code, like I say it was a WIP which never got finished

index.php
Code: [Select]
<?php

require "settings.inc.php";
require 
"filefunctions.inc.php";

$ParentArray = array();

if (!isset(
$_GET['CurrentFolder']) && !isset($_SESSION['CurrentFolder'])){
$_SESSION['CurrentFolder'] = $UserBaseDir;
} elseif (isset(
$_GET['id'])) {

$i 0;

$FolderId $_GET['id'];
$oldParentArray $_SESSION['parentArray'];
unset($_SESSION['parentArray']);
while ($oldParentArray[$i][3] != $FolderId && $i count($oldParentArray)){ $i++; }
$_SESSION['CurrentFolder'] = $oldParentArray[$i][1];
unset($oldParentArray);
}

if(isset(
$_GET['Reset']))
{
$_SESSION['CurrentFolder'] = $UserBaseDir;
header('location:./index.php');
}

$Folder $_SESSION['CurrentFolder'];

$found false;

$dir opendir($Folder);  //Open the resulting folder for inspection

while(false !== ($file readdir($dir))) //While there are still files in there...
{
    
$type filetype($Folder $file); //Get the file type (file/dir)
    
if($type == "dir" && $file != "." && $file != ".."//While it's a dir and isn't "." or ".."...
    
{
        
$found true//There are sub-directories, let's display one
        
$headhurts=TraverseToCurrent($Folder.$file."/");
    }
}
if(
$found == false)
{
    
$headhurts=TraverseToCurrent($Folder);
}

sort($ParentArray); //Make it alphabetical

$_SESSION['parentArray'] = $ParentArray//Assign ParentArray to a session so we can access it

printTree();
ListDirContents();


?>

settings.inc.php
Code: [Select]
<?php

session_start
(); //Sessions hold the current folder for updating columns, leave this value alone :)

// *** Edittable stuff starts ***

//Where are the files stored? (With trailing /)
$FilesDirectory "./files/";

// Do you want to show "." and ".." directories on file pane? (does not affect sub folders)
$listDirectories false// "true" or "false" with no quote marks

$ChMod="0777"//Permissions directories are created with

$username "tuoni"//Temp hard-value for username

// *** Edittable stuff stops ***

// *** Session setup stuff for current base directory ***

if (!isset($_SESSION['UserBaseDir']))
{
    
$_SESSION['UserBaseDir'] = $FilesDirectory.$username."/";
}
if (!isset(
$_SESSION['BaseDir']))
{
    
$_SESSION['BaseDir'] = $FilesDirectory;
}

$UserBaseDir $_SESSION['UserBaseDir'];
$BaseDir $_SESSION['BaseDir'];

if(
is_dir($UserBaseDir) == false)
{
    
mkdir($UserBaseDir$ChMod);

    
$indexFile fopen($UserBaseDir.'/index.html''w');
    
fwrite($indexFile"w00t w00t");
    
fclose($indexFile);
}

?>

fileFunctions.inc.php (where the recursion actually happens)
Code: [Select]
<?php

/*****************************************************************************************************************
* This is a set of functions which handle traversing to a folder given in $_GET['id'] and
* then print them out to the page.  It is designed to be included in another file as finished
* functions, rather than to be used on their own.  It requires that session values are set,
* so try not to use these functions unless you can understand what they do :)
*
* Author: Ed Geraghty
* Version: 2007-10-14
*****************************************************************************************************************/

//This is the function which does the physical traversing through the directory structure
Function traverseToCurrent($GivenFolder){

global $PushPopArray//Present the array in a way the recursive fn can use it
global $BaseDir;
global $ParentArray;

$found false;

$filepath=explode("/"$GivenFolder); //Split the string into an array
$poppedentity=array_pop($filepath); //Take off the last two elements
$poppedentity2=array_pop($filepath);

$subfilepath=implode("/",$filepath); //Put the string back together

$subfilepath.="/"//Add a trailing /

$dir opendir($subfilepath);  //Open the resulting folder for inspection

while(false !== ($file readdir($dir))) //While there are still files in there...
{
$type filetype($subfilepath $file); //Get the file type (file/dir)
if($type == "dir" && $file != "." && $file != ".." && $subfilepath != $BaseDir//While it's a dir and isn't "." or ".."... or the user's base dir
{
for($i 0$i < (count($ParentArray)); $i++) //Quick loop through the array to check this file isn't already listed
{
if (count($ParentArray) != 0//If there are entities in the array
{
if($ParentArray[$i][0] == $subfilepath && $ParentArray[$i][1] == $subfilepath.$file."/"//If it is already there
{
$found true//We found it, don't add it again
break; //Break out of the loop
//If
//If
//For
if (!$found || count($ParentArray) == 0//If we haven't found it or the array isn't populated
{
if (count($ParentArray) == 0//If the array isn't populated
{
$i 0//Set the index to the first record
//If
$ParentArray[$i][0] = $subfilepath//Set [0] to the parent folder
$ParentArray[$i][1] = $subfilepath.$file."/"//Set [1] to the current folder
$ParentArray[$i][2] = $file//Set [2] to what we want the folder name to appear as
$ParentArray[$i][3] = $i//Set [3] to a folder id - was originally folder name
//If
traverseToCurrent($subfilepath); //Otherwise recurse
//If
//While
//Function

//All recursion and no play mAkES ed a dull boy
//allRecRUSIon and no play makes ed a dull boy
//All recursion and No play mkaes Ed a dull hboy

//This function prints the directory tree out as a div to the page
Function printTree()
{

global $ParentArray;
global $UserBaseDir;

$PushPopArray = array();
$LevelsDeep=1;

array_push($PushPopArray$UserBaseDir);
$LevelsDeep++;

print "<div id='foldertree'>";

print "<li><a href='index.php?Reset=True'>Home</a></li>";

while (count($ParentArray) > 0)
{
$PreviousFolder array_pop($PushPopArray);
$LevelsDeep--;
$found false;
for ($i=0$i count($ParentArray); $i++)
{
if($PreviousFolder == $ParentArray[$i][0]) //If they share the same parent
{
$aHrefString=ltrim($ParentArray[$i][1],$UserBaseDir);
print "<li>";
for ($foo=0$foo < ($LevelsDeep); $foo++)
{
print "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
}
print "<a href='index.php?id=".$ParentArray[$i][3]."'>".$ParentArray[$i][2]."</a></li>";
array_push($PushPopArray,$PreviousFolder);
$LevelsDeep++;
array_push($PushPopArray,$ParentArray[$i][1]);
$LevelsDeep++;

array_splice($ParentArray$i1);
$found true;
break;
//If
//For
If ($found != true//If its not been found
{
array_push($PushPopArray,$PreviousFolder);
$tempvar array_pop($PushPopArray);
if($tempvar==$UserBaseDir)
{
$aHrefString=ltrim($ParentArray[0][1],$UserBaseDir);
array_push($PushPopArray,$PreviousFolder);
print "<li><a href='index.php?CurrentFolder=".$aHrefString."'>".$ParentArray[0][2]."</a></li>";
array_splice($ParentArray01);
}
//If
//While

print "</div>";
}

//Lists the contents of a directory in a div
Function ListDirContents()
{
$filesInDirectory = array();
$ListMeDirectory $_SESSION['CurrentFolder'];
$foo 0;

echo "<div id='foldercontents'>";
if(is_dir($ListMeDirectory)) //If directory exists, show its contents
{
echo "<table>
<tr>
<td width='25px'></td>
<td width='100%'><b><u>Name</u></b></td>
<td width='100px'><b><u>Type</u></b></td>
<td width='100px'><b><u>Size</u></b></td>
</tr>"
;
$dir opendir($ListMeDirectory);
while(false !== ($file readdir($dir)))
{
$type filetype($ListMeDirectory ."/"$file);
if($file != "." && $file != "..")
{
if ($type == "file")
{
echo "<tr>
<td><input type='checkbox' name='file|
$foo' />
<td><a href='index.php?action=showfile&id=
$foo'>" $file "</a></td>";
$filesInDirectory[$foo] = $file;
$foo++;
} elseif ($type == "dir") {
$folderId getIdForFolder($file);
echo "<tr>
<td><input type='checkbox' name='folder|
$folderId' />
<td><a href='index.php?id=
$folderId'>" $file "</a></td>";
}
echo "<td>" $type "</td>";
echo "<td>";
if($type == "file"){ echo filesize($ListMeDirectory ."/".$file); }
echo "</td></tr>";
//If
//While
closedir($dir);
echo "</table>";
echo "</div>";

$_SESSION['fileArray'] = $filesInDirectory;
//If
//Fn

//Retrieves the folder ID for a given foldername
Function getIdForFolder($folderName)
{
$ParentArray $_SESSION['parentArray'];
$i 0;

while ($ParentArray[$i][2] != $folderName){ $i++; }

return $ParentArray[$i][3];
}

?>

It was originally intended to be a file management script to use with the lilly pad here, it reads structure in a directory based on the user's login name...

It got abandoned when I found better, OSS, completed solutions.

Keith™

  • Villiage Idiot
  • Seagull
  • Posts: 16828
  • Superior Stupidity at its best
Re: Building a treeview with recursion
« Reply #5 on: March 19, 2009, 11:31:34 AM »
Couldn't you count the tabs, and then get the ' Parent ' property of the node just added?  In your example
Top Node1 ( no tab, new main node. )
        Child Node1_1 ( one tab more than previous, so it is owned by previous )
        Child Node1_2 ( same amount of tabs, owned by previous parent )
                Child Node1_2_1 ( one more tab than previous, so it is owned by previous )
Top Node2 ( no tab, new main node. )
Top Node3 ( no tab, new main node. )
        Child Node3_1 ( one tab more than previous, so it is owned by previous )
        Child Node3_2 ( same amount of tabs, owned by previous parent )
                Child Node3_2_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_1 ( one tab more than previous, so it is owned by previous )
                                Child Node3_2_1_1_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_2 ( one tab less than previous, so it is owned by previous parent's parent )

There is also a ' PrevNode ' property that may be of help also.

Essentially that is what I am trying to do, except if a node has less tabs than the previous child, it may not necessarily be a top level node. In that case it may be node.parent.parent.parent.parent adinfinitum ... and I don't see how coding that would be very efficient or easy to accomplish.

Tuoni, I'll look at that code in depth and see if I can garner what I need from it.

Thanks
Proud provider of opinion and arrogance since November 22, 2003 at 09:35:31 am
CadJockey Militia Field Marshal

Find me on https://parler.com @kblackie

Tuoni

  • Gator
  • Posts: 3032
  • I do stuff, and things!
Re: Building a treeview with recursion
« Reply #6 on: March 19, 2009, 11:40:49 AM »
Tuoni, I'll look at that code in depth and see if I can garner what I need from it.
I hope it helps :)  Most of it is setting up sessions and variables to be honest.

Basically the way it works is with a stack, there are almost definitely better ways of doing it, but hopefully this will help you get your head around at least some of the logic.  Though as you'll probably work out from the comments, I ended up frying my own mind :)

T.Willey

  • Needs a day job
  • Posts: 5242
Re: Building a treeview with recursion
« Reply #7 on: March 19, 2009, 11:45:41 AM »
Couldn't you count the tabs, and then get the ' Parent ' property of the node just added?  In your example
Top Node1 ( no tab, new main node. )
        Child Node1_1 ( one tab more than previous, so it is owned by previous )
        Child Node1_2 ( same amount of tabs, owned by previous parent )
                Child Node1_2_1 ( one more tab than previous, so it is owned by previous )
Top Node2 ( no tab, new main node. )
Top Node3 ( no tab, new main node. )
        Child Node3_1 ( one tab more than previous, so it is owned by previous )
        Child Node3_2 ( same amount of tabs, owned by previous parent )
                Child Node3_2_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_1 ( one tab more than previous, so it is owned by previous )
                                Child Node3_2_1_1_1 ( one tab more than previous, so it is owned by previous )
                        Child Node3_2_1_2 ( one tab less than previous, so it is owned by previous parent's parent )

There is also a ' PrevNode ' property that may be of help also.

Essentially that is what I am trying to do, except if a node has less tabs than the previous child, it may not necessarily be a top level node. In that case it may be node.parent.parent.parent.parent adinfinitum ... and I don't see how coding that would be very efficient or easy to accomplish.

You would just need to setup a repeat for the amount of tabs less than.  I showed that on the one extra node I added ( the last node ).  You would repeat 1 ( since there is one less tab ) on the previous nodes parent.  That should work for what you are trying to do.
Tim

I don't want to ' end-up ', I want to ' become '. - Me

Please think about donating if this post helped you.

Glenn R

  • Water Moccasin
  • Posts: 1932
  • What idiot child of married cousins wrote this?!
Re: Building a treeview with recursion
« Reply #8 on: March 19, 2009, 12:18:27 PM »
Got a sample text file to help people think with?
Me

Keith™

  • Villiage Idiot
  • Seagull
  • Posts: 16828
  • Superior Stupidity at its best
Re: Building a treeview with recursion
« Reply #9 on: March 19, 2009, 01:52:32 PM »
Attached is a sample ...
Proud provider of opinion and arrogance since November 22, 2003 at 09:35:31 am
CadJockey Militia Field Marshal

Find me on https://parler.com @kblackie

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9524
Re: Building a treeview with recursion
« Reply #10 on: March 19, 2009, 02:43:52 PM »
I think a recursive procedure would be extremely expensive in this instance; use a loop.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

Keith™

  • Villiage Idiot
  • Seagull
  • Posts: 16828
  • Superior Stupidity at its best
Re: Building a treeview with recursion
« Reply #11 on: March 19, 2009, 02:47:26 PM »
yeah I tried that too ... I just can't seem to loop my mind around it hahahahaha .. sometimes I crack me up

seriously ... I can't seem to get it ironed out ... and I am losing my hair fast enough as it is ...
Proud provider of opinion and arrogance since November 22, 2003 at 09:35:31 am
CadJockey Militia Field Marshal

Find me on https://parler.com @kblackie

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9524
Re: Building a treeview with recursion
« Reply #12 on: March 19, 2009, 02:58:05 PM »
A recursive procedure is nothing more then an expensive loop. Sometimes its simpler to build so that is the trade off with using a recursive procedure (spend time coding or waste some time on execution).

I have some drafting to do so I can think a bit.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9524
Re: Building a treeview with recursion
« Reply #13 on: March 19, 2009, 03:24:55 PM »
so-far i cant think of anything better then parsing that string and counting tabs like T.Willey suggested. I mean that sounds like the most straight forward and efficient way.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

T.Willey

  • Needs a day job
  • Posts: 5242
Re: Building a treeview with recursion
« Reply #14 on: March 19, 2009, 03:38:18 PM »
Here is proof of concept.  Real simple, but works here.

Code: [Select]
void MainFormLoad(object sender, EventArgs e)
{
TreeNode PrevNode = new TreeNode();
TreeNode CurNode;
int OldTabCnt = -1;
using ( StreamReader sr = new StreamReader( @"C:\MyCustom\material list.txt" ) ) {
while ( sr.Peek() != -1 ) {
string tempStr = sr.ReadLine();
if ( string.IsNullOrEmpty( tempStr ) )
continue;
int CurTabCnt = tempStr.LastIndexOf( '\t' );
string[] tempAr = tempStr.Split( '\t' );
CurNode = new TreeNode( tempAr[ tempAr.Length - 1 ] );
if ( CurTabCnt == -1 ) {
Tview.Nodes.Add( CurNode );
}
else if ( CurTabCnt == OldTabCnt ) {
PrevNode.Parent.Nodes.Add( CurNode );
}
else if ( CurTabCnt > OldTabCnt ) {
PrevNode.Nodes.Add( CurNode );
}
else if ( CurTabCnt < OldTabCnt ) {
for ( int i = 0; i <= OldTabCnt - CurTabCnt; ++i ) {
PrevNode = PrevNode.Parent;
}
PrevNode.Nodes.Add( CurNode );
}
OldTabCnt = CurTabCnt;
PrevNode = CurNode;
}
}
}
Tim

I don't want to ' end-up ', I want to ' become '. - Me

Please think about donating if this post helped you.