PHP sitemap using a tree data structure

I was once asked to create a sitemap given a specific table structure.

This was the structure(the table):

The resulting sitemap as I understood it was supposed to look something like this:

The parenthesis after the titles actually hold the value of the id of the node so they weren't in the original design but whatever.

So I implemented this in PHP using a tree data structure where each node held 3 pieces of information:

id - the current node's id as read from the database

parent_id - the current node's parent id as read from the database

title - the title

A real-world implementation would also have to include a link and print out elements but this is good enough for educational purposes.

Each node also holds an array of subnodes.

This is the database information read to create the tree:

CREATE TABLE IF NOT EXISTS `sitepages` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`id_parent` int(11) unsigned NOT NULL,
`title` varchar(100) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=3 ;

INSERT INTO `sitepages` (`id`, `id_parent`, `title`) VALUES
(1, 0, 'Home'),
(2, 1, 'Page 1'),
(3, 0, 'Page 2'),
(4, 1, 'Page 3'),
(5, 3, 'Page 4'),
(6, 1, 'Page 5'),
(7, 4, 'Page 6'),
(8, 7, 'Page 7'),
(9, 5, 'Page 8');

I used to php classes to represent the tree. One to represent a node of the tree and one for the tree itself:

This is for the node:

//a node of a tree that is not binary, each nodes has multiple subnodes 
class Node 
{  
public $id;  
public $id_parent;  
public $childnodes;  
public $title;    

public function __construct($id,$id_parent,$title)  
{   
//in the test script I use mysql_fetch_object which populates the members and then //calls the constuctor with all    
//parameters as null   
//the following checks are here to make sure no members are accidentally overriden
      
if(!isset($this--->id))
  $this->id = $id;

 if(!isset($this->id_parent))  
  $this->id_parent = $id_parent;

 if(!isset($this->title))  
  $this->title = $title;

 if(!isset($this->childnodes))  
  $this->childnodes = array();
}

//check if this node has subnodes or not
public function hasChildren()
{
 if($this->childnodes === null)
  return false;

 if(!isset($this->childnodes))  
  return false;

 if(count($this->childnodes) == 0)
  return false;

 return true;
}
}

This is the tree:

require("node.class.php");  
class Tree 
{  

private $root;   

//construct a tree with only one root node  public function __construct()  
{   
$this->root = new Node(0,0);
}

//recursively traverse the tree looking for the appropiate parent id
//the node to be inserted($node) must have a parent id equal to one of the ids in the nodes of the tree
//if such an id is found in a node the node is included as a subnode of that node
private function addNodeRecursive(&$nextnode,$node)
{
 if($nextnode == null)
  return false;
 
 if($nextnode->id == $node->id_parent)
 {
  array_push($nextnode->childnodes,$node);
  return true;
 }
 else
 {
  if($nextnode->hasChildren())
  {
   foreach ($nextnode->childnodes as $childnode)
   {
    $this->addNodeRecursive($childnode,$node);
   }
   return false;
  }
  else
   return false;
 }
}

//add a node to the tree
//check if it is a valid node start at the root and recursively traverse the tree looking for the appropiate parent id
public function addNode($node)
{
 if(!($node instanceof Node))
  return;

 $nextnode = $this->root;

 $this->addNodeRecursive($nextnode,$node);
}

//print the tree in sitemap style
public function printSiteMap()
{
 foreach($this->root->childnodes as $childnode)
 {
  $this->printTree($childnode,0);
 }
}

//print the tree recursively
//first print the current node's value and then print the cycle through it's subnodes
public function printTree(&$nextnode,$level)
{
 $this->printNodeAccordingToLevel($nextnode,$level);

 if($nextnode->hasChildren())
 {
  foreach($nextnode->childnodes as $childnode)
  {
   $this->printTree($childnode,$level+1);
  }
 }
}

//add the appropiate number of   before each node value so as to obtain a nicely formatted sitemap
//each node value is indented with respect to the node's level
private function printNodeAccordingToLevel($node,$level)
{
 for($i=0;$i<$level;$i++)    echo " ";    echo $node->title."(".$node->id.")";
 
 echo "
";
}

}

And this is a test just to make sure everything works:

require("tree.class.php");  
$tree = new Tree();  
if(!($conn = mysql_connect("localhost","root",""))) 
{  
echo "Could not connect";  
exit; 
}  
if(!mysql_selectdb("sitemap")) 
{  
echo "No such database";  
exit; 
}  
if($result = mysql_query("SELECT id,id_parent,title FROM sitepages")) 
{  
while ($page = mysql_fetch_object($result,'Node'))   
$tree->addNode($page);
}

$tree->printSiteMap();

Prefix tree(trie) implementation in F#

Update: all the code can be downloaded from here

This is my implementation of a a prefix tree data structure in F#.
This structure is described in more detail in a previous post of mine.
I just describe the F# related stuff in the comments.
I'm sure this is not the best implementation. I am aware this is not the most functional implementation ever.
I am open to all constructive criticism of course.

	open System.Collections.Generic;
	//the trie node type which is stores a char, a bool to mark the end of the node and a list of all it's subnodes
	type TrieNode = TrieNode of (char * bool * TrieNode list) with
	//just a getter the char stored
	member this.Char = match this with TrieNode(c,weh,subnodes) -> c
	//get the first node that is a subnode of the current node and stores the char passed as parameter (c)
	//this returns a list which can be either empty or have one element this is probably not the best option since there will never be
	//more than one element in the list but I am new to F#
	member this.GetChild(c:char) = match this with TrieNode(c,weh,subnodes) -> match List.tryFind (fun (this:TrieNode) -> this.Char = c) subnodes with
	| Some value -> [value]
	| None -> []
	//just return true if a word ends here
	member this.AWordEndsHere = match this with TrieNode(_,weh,_) -> weh
	//just a getter for the the subnodes
	member this.Subnodes = match this with TrieNode(_,_,subnodes) -> subnodes
	//type members cannot be recursive so I implemented this in a module
	//a more functional approach was to implement all methods here I guess ... anyways ...
	module TrieFunctions =
	//this inserts a word passed as a char list
	let rec insertWord (wordChars:char list) = function
	| TrieNode(c, weh, subnodes) as node ->
	if(wordChars.Length > 0) then
	//get the first char in the word and see if there are any child nodes storing that char
	let child = node.GetChild(wordChars.Head)
	if child = [] then
	//if there aren't insert this node and make a new node to pass to the insertion function
	let newnode = TrieNode(wordChars.Head,false,[])
	TrieNode(c,weh,(insertWord wordChars.Tail newnode)::subnodes )
	else
	//otherwise the node that has to be passed to the insertion function is the child node as all other nodes will be
	//added after it and the first char in the word will be added
	TrieNode(wordChars.Head,false,(insertWord wordChars.Tail child.Head)::subnodes )
	else
	//there are no more characters in the word so we must add a node with no subnodes and mark it as a valid end of a word
	TrieNode(c,true,[])
	//turn a string into a char list - ofSeq turns any sequence into a list of it's composing elements
	//and a string is made up of chars
	let stringToCharList(s:string) = List.ofSeq s
	//print the trie - use an accumulator(acc)
	let rec print acc = function
	//if there are no subnodes
	| TrieNode(c, weh, []) ->
	//add the current char node to the accumulator, print if it the end of a word and return unit
	let str = acc + c.ToString()
	if weh then printfn "%s" str
	()
	| TrieNode(c, weh, subnodes) ->
	//add the current char node to the accumulator, print if it the end of a word
	let str = acc + (if c.Equals(' ') then "" else c.ToString())
	if weh then printfn "%s" str
	//iterate through the list of subnodes and call print function for each of them
	List.iter (fun (node : TrieNode) -> print str node) subnodes
	//unlike in C# in F# the type has a default constructor containing the maximum number of parameters
	type Trie(inner : TrieNode) =
	member this.InsertWord(wordChars:char list) = Trie(TrieFunctions.insertWord wordChars inner)
	member this.InsertWord(str:string) = Trie(TrieFunctions.insertWord (TrieFunctions.stringToCharList str) inner)
	member this.Root() = inner
	//and an empty constructor must be declared if you want to have it
	new() = Trie(TrieNode(' ',false,List.empty))
	let trie = Trie()
	.InsertWord("abc")
	.InsertWord("abcd")
	.InsertWord("abcd")
	.InsertWord("abcde")
	.InsertWord("abcdef")
	.InsertWord("ab123cd")
	.InsertWord("abc123d")
	.InsertWord("abc132d")
	TrieFunctions.print "" (trie.Root())

view raw PrefixTreeF# hosted with ❤ by GitHub