This is a demonstration of how to meaningfully make sense of a theoretically
infinitely recursing tree stored in a database as a set of records which all
specify who their parent is (the simplest way to store such a structure in a 
flat form, such as a database table).

- Top-level entries have parent = 0;
- Depth is capped at 64 levels, to simplify loop detection.
- Nodes are divided into two groups:
	a) "folders" -- contain 0 or more nodes of any type, in any combination
	b) "leaves" -- may not contain other nodes, but have a URL attached.
- Currently, if a node has a URL, it is assumed to be a leaf, and thus have no 
children, as this does not make sense for the intended implementation.

- The source code is available below, if desired.


[neofw_db_mysql] Warning: Could not USE database test
[neofw_db_mysql] Warning: Problem running query: "SELECT id,name,url,parent FROM tree_urls": No database selected
Error fetching from database: No database selected
Resulting tree:



---
Source:

<?PHP
/*
The contents of this file are hereby released to the public domain. I, Octav
Sandulescu, as the author of this work, waive any and all copyrights to the work
contained in this file. You may copy it, slice it, dice it, or even flush it
down the toilet if you prefer. 

This is intended as EXAMPLE CODE, and comes with NO WARRANTY WHATSOEVER. If it 
works for you, good. If it does not, or if you lose data as a result of using 
this code, I personally disclaim any and all responsibility for your loss: you 
have been warned and are expected to act as an intelligent human being -- so
understand the code before you put it to work.

However, I must note that any additions, corrections, or bug fixes may be freely
submitted at tiadb-fixes@narc.ro. These additions will be incorporated
into this example code on an as-needed basis.

Lastly, on a more personal note, I have attempted to comment the source code as
clearly as possible. Please use the email address tiadb-questions@narc.ro
for any questions regarding the code.
*/

// Background: NeoFW is my personal code library, gathered into a single
//coherent whole.
// I am using NeoFW as a database access/abstraction layer with error handling.
//This is my production-level code, and is copywritten.
// To convert this code to something usable elsewhere, you will need to remove 
//the next few lines up to the comment "NeoFW ends", and will also need to 
//provide alternatives to the functions db_query(), db_error(), and 
//db_fetch_assoc(). For production code, you should also consider error 
//handling.
define('PATH_NEOFW',    dirname(dirname(__FILE__)).'/CM/NeoFW');

include(PATH_NEOFW.'/neo_fw.h.inc');

$config['db']['type'] = 'mysql';
$config['db']['user'] = 'readonly';
$config['db']['db'] = 'test';

$config['err']['log'] = NEOFW_LOG_CONSOLE_RAW;
$config['err']['with_error_location'] = false;

include(PATH_NEOFW.'/neo_fw.inc');
// NeoFW ends.


header('Content-Type: text/plain; charset=iso-8859-1');

echo <<<EOF
This is a demonstration of how to meaningfully make sense of a theoretically
infinitely recursing tree stored in a database as a set of records which all
specify who their parent is (the simplest way to store such a structure in a 
flat form, such as a database table).

- Top-level entries have parent = 0;
- Depth is capped at 64 levels, to simplify loop detection.
- Nodes are divided into two groups:
	a) "folders" -- contain 0 or more nodes of any type, in any combination
	b) "leaves" -- may not contain other nodes, but have a URL attached.
- Currently, if a node has a URL, it is assumed to be a leaf, and thus have no 
children, as this does not make sense for the intended implementation.

- The source code is available below, if desired.



EOF;

// Get our tree out of the database...
$arr = fetch_tree();

// ...and display it indented prettily.
$str = produce($arr);
echo "Resulting tree:\n\n$str";

// Finally, make good on the promise to include the source code.
echo "\n\n---\nSource:\n\n".file_get_contents(__FILE__);


//* Only functions beyond this point.


function fetch_tree()
{
	// Get the flat list, with nodes specifying their parents...
	$arr = fetch_from_db();
	
	// ...enhance the flat list by telling each parent who its children are...
	$arr = parse_parents_to_children($arr);
	
	// ...and produce a tree by selecting the root node and, recursively, all of
	//its children.
	$arr = recursive_select_nodes($arr,array(0));
	
	// Finally, return all of root's children...
	if(!empty($arr[0]['children']))
		return $arr[0]['children'];
	else // ...or, if root has no children, return an empty array.
		return array();
}

function fetch_from_db()
{
	$arr = array();
	
	// 0 is our "root" element -- i.e. parent of all parents. It makes life 
	//simpler, and can be (and is, later) removed easily.
	$arr[0] = array();
	$arr[0]['name'] = 'Root (you should never see this)';
	
	$q = 'SELECT id,name,url,parent FROM tree_urls';
	
	$resu = db_query($q);
	
	if($resu === false)
	{
		echo 'Error fetching from database: '.db_error()."\n";
		return $arr; // empty array will make for empty results.
	}
	
	echo "From the DB:\n\n";
	printf("%3s  %-30s %-70s %-3s\n",'id','name','url','parent');
	
	// Loop through the resultset and build a "flat" array out of it.
	while($row = db_fetch_assoc($resu))
	{
		printf("%3u: %-30s %-70s %-3u\n",$row['id'],$row['name'],$row['url'],$row['parent']);

		// Null or empty URL means this is a parent. We test this with isset() 
		//later, so get it out of our way.
		if(empty($row['url']))
			unset($row['url']);
		
		// We will later need to refer quickly to a node by its id, so we use
		//its id as the array key.
		$arr[$row['id']] = $row;
	}
	echo "---\n";
	
	return $arr;
}

function parse_parents_to_children($arr)
{
	// This is the only time we explicitly walk *all* the array nodes in 
	//sequence. We do this to make the below recursive select possible.
	foreach($arr as $id=>$row)
	{
		// If this is a child...
		if(isset($row['parent']))
		{
			// ...tell its parent about it...
			$arr[$row['parent']]['childnodes'][] = $id;
			
			// ...and remove the (now useless) parent info.
			unset($arr[$id]['parent']);
		}
	}
	
	return $arr;
}

function recursive_select_nodes($arr,$nodes,$internal_depth = 0)
{
	$selected = array();

	// Error checking, or "Put that thing away, you don't know where it's been!"
	if($internal_depth > 64)
	{
		echo "Error: recursing deeper than 64 levels indicates probable loop formed.\n";
		return $selected;
	}
	
	// Walk through the array of nodes we were told to select...
	foreach($nodes as $id)
	{
		// ...and if the node exists (I said we would need to refer quickly to a
		//node by its id, didn't I?)...
		if(isset($arr[$id]))
		{
			// ...then check if it's a parent,...
			if(isset($arr[$id]['childnodes']))
			{
				// ...select its children via recursion...
				$arr[$id]['children'] = recursive_select_nodes($arr,
					$arr[$id]['childnodes'],$internal_depth + 1);
				
				// ...and erase the now useless list of child nodes.
				unset($arr[$id]['childnodes']);
			}
			
			// Finally, add it to our selected list...
			$selected[] = $arr[$id];
		}
	}
	
	// ...and return the selected nodes.
	return $selected;
}

function produce($in_arr,$level = 0)
{
	if($level > 64)
	{
		echo "Error: recursing deeper than 64 levels indicates probable loop formed.\n";
		echo "WARNING: This should've been caught earlier!\n";
		// Remember, recursive_select_nodes() has at least one level more than 
		//we do: the root node.
		return '';
	}
	
	$out = '';
	
	foreach($in_arr as $elem)
	{
		// Print the element's name to the right depth
		if($level >= 0)
			$out .= str_repeat("\t",$level).$elem['name'];
			
		// Leaves are assumed to have no children...
		if(!empty($elem['url']))
		{
			// ...so we just print them out as is.
			$out .= '|'.$elem['url']."\n";
		}
		// Folders have no URLs...
		else
		{
			// ...so we can print the newline immediately...
			$out .= "\n";
			
			// ...And recurse deeper if needed.
			if(!empty($elem['children']))
				$out .= produce($elem['children'],$level + 1);
		}
	}
	
	return $out;
}
?>