Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"
>
<html>
<head>
<title>Hierarchical Howto</title>
<meta name="GENERATOR" content="Quanta Plus">
<meta name="AUTHOR" content="R. W. Rodolico">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<h1>
Hierarchical Hash Documentation
</h1>
<p>
An Hierarchical Hash is a hash where a parent node may have one or more "chilren", which in turn may act as parent nodes for additional children. This is most commonly seen with a menu, or it could be seen as clients with one or more sites, with each site containing one or more computers, which are made up of components. This can easily be stored in a hash where the top elements are clients, each of which have child nodes that are sites, each of which have child nodes that are computers, etc...
</p>
<p>
The problem with this is storing it the hierarchy in a database table. The most common way to do this is to have a unique id for each node and a second column that points to the parent node (ie, stores the unique id of the parent, if a parent exists)
</p>
<p>
The class DBHierarchicalHash performs the one way function from database table to Hierarchical Hash. As an exercise in usefulness, the class DBMenu extends DBHierarchicalHash to allow an html menu to be stored in a database table.
</p>
<h3>
class DBHierarchicalHash
</h3>
<p>
class reads a database table and converts it to an Hierarchical hash (aka, parent/child).
</p>
<p>
Table structure is assume to be:
</p>
<pre> create table menu (
id int unsigned not null,
parent_id int unsigned not null default 0,
other columns below
)
</pre>
<p>
where id is a unique identifier and parent_id is points to id in another row (zero indicating it is a top level)
</p>
<p>
NOTE: column names may be changed. Also, while it is assumed id and parent_id are int's, it is quite likely it will work with other column types, including varchar
</p>
<p>
Uses include any parent/child relationship, to an arbitrary depth. See class DBMenu for one example
</p>
<p>
This class was written to be generic. The algorithm used attempts to not take advantage of any special language capabilities, and should be generic. However, various languages can optimize this capability by using capabilities unique to the language in question. For an example, see David North's PERL implementation which utilizes references to allow for a single pass to convert from an array to a Hierarchical structure. Taking advantage of this allows his script to run use no additional memory (this algorithm will double the amount of memory used for the initial array) and does in a single iterative pass what the recursive function copyChildren does.
</p>
<table border="1">
<caption>
Members
</caption>
<thead>
<tr>
<th>
Visibility
</th>
<th>
Variable
</th>
<th>
Description
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
protected
</td>
<td>
$tableName
</td>
<td>
table name that data will be read from
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$keyField
</td>
<td>
name of the primary id field in table
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$parentFieldName
</td>
<td>
name of the field used to point to the parent of the current row
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$rootNodevalue
</td>
<td>
the value (default 0) of the indicator that a row has no parent. THIS MUST NOT EXIST in the id column of the table
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$inputRecords
</td>
<td>
storage for the records read in.
</td>
</tr>
</tbody>
</table>
<table border="1">
<caption>
Functions
</caption>
<thead>
<tr>
<th>
Visibility
</th>
<th>
Name
</th>
<th>
Parameters
</th>
<th>
Description
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
public
</td>
<td>
__construct
</td>
<td>
$tableName
<br>
$keyField = 'id'
<br>
$parentFieldName = 'parent_id'
<br>
$rootNodeValue = 0
</td>
<td>
Constructor: Initializes the data, reads from database, and creates the hash
</td>
</tr>
<tr>
<td>
private
</td>
<td>
findChildren
</td>
<td>
</td>
<td>
Goes through each node and reverses the "who is my parent" to the parent's "who are my children". It does not populate the children; it simply creates an empty array for each child to be processed later.
</td>
</tr>
<tr>
<td>
public
</td>
<td>
toHash
</td>
<td>
</td>
<td>
simply returns inputRecords for processing by calling routine. This is the goal of this class, to create this structure from the database structure defined above
</td>
</tr>
<tr>
<td>
private
</td>
<td>
loadData
</td>
<td>
</td>
<td>
loads data from database. The column defined in $this->keyField will become the index into the hash, and all additional columns will simply be added to the array pointed by it. An additional entry in the table will be created with $this->rootNodeValue as its index, to allow root level items to have a parent.
</td>
</tr>
<tr>
<td>
private
</td>
<td>
copyChildren
</td>
<td>
$currentNode
</td>
<td>
populates the hiearchy created in load <strong>NOTE</strong>: if the current node also has children, it will recursively do those main call is &copyChildren( rootNode )
</td>
</tr>
</tbody>
</table>
<h3>
class DBMenu extends DBHierarchicalHash
</h3>
<p>
simple extension of DBHierarchicalHash allowing a menu structure to be stored in a database.
</p>
<p>
the structure for the database is simple:
</p>
<pre> create table menu (
menu_id int unsigned not null auto_increment,
parent_id int unsigned not null default 0,
caption varchar(20) not null,
url varchar(64),
primary key (menu_id)
)
</pre>
<p>
where caption is the string displayed on the menu, and url is the (possibly null) url to be called when the link is clicked by the user. The resulting line is something like:
<br>
<em><a href="url">caption</a></em>
</p>
<p>
though this can be modified by changing $menuItemString and $menuHeaderString (see below)
</p>
<p>
menu_id is a unique identifier for a single row, and parent_id points to the menu that it is a submenu of (0 indicates a root menu item)
</p>
<p>
<strong>Note</strong>: I tried to avoid any constants in the class, so column names, menu_id data type, root menu indicator are all modifiable
</p>
</pre>
<table border="1">
<caption>
Members
</caption>
<thead>
<tr>
<th>
Visibility
</th>
<th>
Variable
</th>
<th>
Description
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
protected
</td>
<td>
$captionName = 'caption'
</td>
<td>
column name for display string in database
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$urlName = 'url'
</td>
<td>
column name for URL field in database
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$menuItemString = '<li class="menu_item_<level>"><a href="<url>"><caption></a></li>'
</td>
<td>
string which is searched/replaced for a menu item that has a URL (<url> and <caption> are replaced)
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$menuHeaderString = '<li class="menu_header_<level>"><caption></li>'
</td>
<td>
string which is searched/replaced for a menu item that has no URL (<caption> and <level> are replaced)
</td>
</tr>
<tr>
<td>
protected
</td>
<td>
$menuBlockString = '<ul class="menu"><menublock></ul>'
</td>
<td>
string which is placed around <menublock>, ie this goes around a menu/submenu. <level> can be used to determine. which level (zero based) we are in the menu (level = 0 is top menu)
</td>
</tr>
<table border="1">
<caption>
Functions
</caption>
<thead>
<tr>
<th>
Visibility
</th>
<th>
Name
</th>
<th>
Parameters
</th>
<th>
Description
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
public
</td>
<td>
__construct
</td>
<td>
$tableName = 'menu'
<br>
$idFieldName = 'id'
<br>
$parentFieldName = 'parent_id'
</td>
<td>
simply pass fields on to DBHierarchicalHash so it can load and parse the table
</td>
</tr>
<tr>
<td>
public
</td>
<td>
captionColumnName
</td>
<td>
$newValue = ''
</td>
<td>
simple setter/getter for the caption column name in table
</td>
</tr>
<tr>
<td>
public
</td>
<td>
urlColumnName
</td>
<td>
$newValue = ''
</td>
<td>
simple setter/getter for the url column name in table
</td>
</tr>
<tr>
<td>
public
</td>
<td>
menuItemString
</td>
<td>
$newValue = ''
</td>
<td>
simple setter/getter for menuItemString for output
</td>
</tr>
<tr>
<td>
public
</td>
<td>
menuHeaderString
</td>
<td>
$newValue = ''
</td>
<td>
simple setter/getter for menuHeaderString for output
</td>
</tr>
<tr>
<td>
public
</td>
<td>
menuBlockString
</td>
<td>
$newValue = ''
</td>
<td>
simple setter/getter for menu block string for output
</td>
</tr>
<tr>
<td>
</td>
<td>
DBMenu2String
</td>
<td>
</td>
<td>
just an entry point to displayMenu, with root of inputRecords and level 0
</td>
</tr>
<tr>
<td>
private
</td>
<td>
htmlMenu
</td>
<td>
$menu
<br>
$level=0
</td>
<td>
function takes a menu level and creates an HTML Menu items from it. If a node has children, will recursively call itself for each child node
</td>
</tr>
</tbody>
</table>
</body>
</html>