# Array_intersect and set theory

Sometime back a colleague asked me when would one use a function like array_intersect(). At that time other than asking him to read up on set theory I filed the question away. If you think about it when was the last time you thought about set theory while programming:-)

This week a simple problem was presented to me. A table of users has 4322 users and a new list had 1698 users. The new list was the latest list with valid users and the users table had to be synced up to the new list. I realized that this was a classic set theory problem and broke it down in to three parts:

1. If a user in the user table is also in the new list – do nothing
2. If a user in the user table is not in the new list then delete it from the user table
3. If a user in the new list is not in the user table, add it to the user table

Using a Venn diagram this can be shown as follows:

In this we have two sets, A and B where:
A = New list of users (latest list of users)
B = User table (existing users)

The common area where the “users in the new list” are also in the “user table” is called an “intersection” in set theory and can be shown as follows (satisfies item-1 above):

C = A ∩ B

Users in the user table but not in the new list can be shown using set difference like so (satisfies item-2 above):

D = B – C

Users in the new list but not in the user table can be shown again using difference like so (satisfies item-3 above):

E = A – C

If we were to use an example:

New list: A = {‘John’, ‘Mary’, ‘David’, ‘Jack’, ‘Jason’}

User table: B = {‘Dexter’, ‘William’, ‘Jack’, ‘John’, ‘Christine’}

Users in user table and new list: C = A ∩ B = {‘Jack’, ‘John’}.
Users in the user table but not in the new list: D = B – C = {‘Dexter’, ‘William’, ‘Christine’}.
Users in the new list but not in the user table: E = A – C = {‘Mary’, ‘David’, ‘Jason’};

If we use Venn diagrams:

Using PHP we can write this as:

```\$A = array('John', 'Mary', 'David', 'Jack', 'Jason');
\$B = array('Dexter', 'William', 'Jack', 'John', 'Christine');
\$C = array_intersect(\$A, \$B);

\$D = array_diff(\$B, \$C);
\$E = array_diff(\$A, \$C);

//display the results
echo 'New list A: ', print_r(\$A, true);
echo 'User table B: ', print_r(\$B, true);

echo 'Users in user table and new list(Item 1) – do nothing C: ', print_r(\$C, true);
echo 'Users in the user table but not in the new list(Item 2) – delete from user table D: ', print_r(\$D, true);

echo 'Users in the new list but not in the user table(Item 3) – add to user table E: ', print_r(\$E, true);

```

New list A: Array
(
[0] => John
[1] => Mary
[2] => David
[3] => Jack
[4] => Jason
)
User table B: Array
(
[0] => Dexter
[1] => William
[2] => Jack
[3] => John
[4] => Christine
)
Users in user table and new list (Item 1) – do nothing C: Array
(
[0] => John
[3] => Jack
)
Users in the user table but not in the new list (Item 2) – delete from user table D: Array
(
[0] => Dexter
[1] => William
[4] => Christine
)
Users in the new list but not in the user table (Item 3) – add to user table E: Array
(
[1] => Mary
[2] => David
[4] => Jason
)

Once you have your arrays you can iterate over them and perform any operations such as deleting records from the database.

There are other ways to solving this problem but none that are elegant come to mind. How would you solve such a problem? I look forward to your comments.

Happy Programming!

-Jayesh

# Google image charts in the PHP MVC pudding!

The other day I had to implement Google Image charts using a MVC framework. I could not find any information easily so came up with this idea which I wanted to share with you. I am sure that there are others who have also thought about this.

So in essence, I had a controller, where the action would:

1. Get the charting information from the model
2. Prepare the post packet for the call to Google charts api
3. Display the chart image in the view.

In this case my view contains in addition to other markup an image tag to receive the chart image:

```<img src="/myController/myAction/" width="xxx" height="yyy">
```

The source attribute of an image is any URL and the only requirement is that the return data be of type ‘image’. In this case the URL follows the standard Controller/Action format.You can add parameters to this URL in case you wanted to something special in your action.

My action in the controller is something like this:

```public function myAction(){
//for simplicity I have created an array for demo
\$rows = array(array('Count' => 2, 'Date' => '08/09/2010'),
array('Count' => 2, 'Date' => '08/09/2010'),
array('Count' => 2, 'Date' => '08/09/2010'),
array('Count' => 2, 'Date' => '08/09/2010'),
\$chd = 't:';
\$chxl = '0:|';
\$chxp = '0,';
\$xoff = 35;
foreach(\$rows as \$row){
\$chd .= \$row['Count'] . ',';
\$chxl .= urlencode(\$row['Date']) . '|';
\$chxp .= \$xoff . ',';
\$xoff = \$xoff * 2;
}
\$chd = rtrim(\$chd, ',');
\$chxl = rtrim(\$chxl, '|');
\$chxp = rtrim(\$chxp, ',');

// Add data, chart type, chart size, and scale to params.
\$chart = array(
'cht' => 'bvg',
'chs' => '600x500',
'chxr' => '1,0,7',
'chbh' => '50',
'chds' => '0,7',
'chxp' => \$chxp,
'chxt' => 'x,y',
'chxs' => '2,000000,12',
'chxl' => \$chxl,
'chtt' => 'Movies VS. Date',
'chd' => \$chd);

\$p = '';
foreach(\$chart as \$k => \$v){
\$p .= "&{\$k}={\$v}";
}

\$url = 'https://chart.googleapis.com/chart?chid=' . md5(uniqid(rand(), true));

\$ch = curl_init();
// set URL and other appropriate options
curl_setopt(\$ch, CURLOPT_URL, \$url);
curl_setopt(\$ch, CURLOPT_CONNECTTIMEOUT, 30);
curl_setopt(\$ch, CURLOPT_POST, 1);
curl_setopt(\$ch, CURLOPT_POSTFIELDS, \$p);
curl_setopt(\$ch, CURLOPT_RETURNTRANSFER, 1);
curl_setopt(\$ch, CURLOPT_VERBOSE, 1);
curl_setopt(\$ch, CURLOPT_TIMEOUT, 180);

// grab URL and pass it to the browser
\$response = curl_exec(\$ch);
\$errorNo = curl_errno(\$ch);

if (\$errorNo !== 0) {
\$info = curl_getinfo(\$ch);
curl_close(\$ch);
error_log ("ErrorNo: {\$errorNo} Curl Info: " . print_r(\$info, true));
}

curl_close(\$ch);

echo \$response;
```

So, when the view loads , the src attribute makes the call and an image is returned. Nice and simple.

But then what happens if in this same view I need to select different type of charts?

In that case my view is now something like this:

```<script>
\$('#chart_type_select').change(function(){
var type = \$(this).val();
\$('#chart_draw').attr('src', '/myController/myAction?type=' + type);
})
});
</script>

<select id='chart_type_select'>
<option value =''>Select Chart</option>
<option value ='1'>Chart Type 1</option>
<option value ='2'>Chart Type 2</option>
</select>

<img id="chart_draw" width="xxx" height="yyy">

```

All I do in this case is switch the src attribute of the image tag which now also has a get parameter, ‘type’. You can now acquire this parameter in your action and process a different chart! No page refreshes!

Whenever we do not want page refreshes the usual temptation is of course to use an AJAX call. However if you do that you will run into cross domain issues and using AJAX with large binary payloads is not recommended.

I hope this idea of using an image tag instead of an AJAX call helps you.

Happy programming!

-Jayesh

# Apple push notification, PHP and XML diff

In a recent project I had to send a push notification to my iOS app by differencing two XML files.

The XML file basically contains a list of incidents and looks like this:

```<?xml version="1.0" encoding="UTF-8"?>
<incidents>
<incident>
<description><![CDATA[Server crashed.]]></description>
<id>88</id>
<time>1/4/2012 5:31 PM</time>
</incident>
<incident>
<description><![CDATA[Server stolen.]]></description>
<id>87</id>
<time>1/3/2012 4:30 PM</time>
</incident>
<incident>
<description><![CDATA[Server on fire.]]></description>
<id>86</id>
<time>1/2/2012 3:29 PM</time>
</incident>
<incident>
<description><![CDATA[Server damaged.]]></description>
<id>85</id>
<time>1/2/2012 2:28 PM</time>
</incident>
<incident>
<description><![CDATA[Server misplaced.]]></description>
<id>84</id>
<time>1/1/2012 1:27 PM</time>
</incident>
</incidents>
```

Please note that for the purposes of this post I have pared down the structure and content of the file. Also, the XML file was sent to me from a parent application server and I had no control over its generation.

For the push notification I had to inform the app how many incidents had changed and new ones added. This implied that I had to do an XML diff on the current XML file and the previous one.

I could recurse over the two files but then that would be too cumbersome. It would be coupled with the structure of the xml file and I am against tight coupling. So, I thought of comparing hashes of the old and new incidents.

My strategy was to use three arrays, one which would contain the previous hashes for reference, second which would store the incident hashes from the current XML and the third which would store the counts for changed, new and deleted and un-changed.

Here is the code:

```define('INCIDENT_HASHES_FILENAME', 'incident_hashes.txt');
define('XML_FILE', 'test.xml');

\$incidentsPrev = array(); //will contain previous hashes if any
\$incidentHashes = array(); //will contain new hashes
\$incidentStatus = array(); //will contain final status id => status - 'N' = New 'C' = Changed, 'D' = Deleted 'NC' => No Change

//check if a reference file exists.
//if a file exists but returns corrupt information
//start anew
if(file_exists(INCIDENT_HASHES_FILENAME)){
\$incidentsPrev = unserialize(trim(file_get_contents(INCIDENT_HASHES_FILENAME)));
if(!is_array(\$incidentsPrev)){
\$incidentsPrev = array();
}
}

//debug
echo 'Previous Hashes: ', '<pre>', print_r(\$incidentsPrev, true), '</pre>';

//contents of the new xml file
\$xml = file_get_contents(XML_FILE);
\$xmlIterator = new SimpleXMLIterator(\$xml);

//iterate and get hashes
foreach(\$xmlIterator as \$incident){
//get hash for the incident
\$hash = md5(\$incident->asXML());
\$id = (int)\$incident[0]->id;
\$incidentHashes[\$id] = \$hash;
}

//compare hashes
foreach(\$incidentHashes as \$id => \$hash){
//check if the incident exists in the hash array
if(array_key_exists(\$id, \$incidentsPrev) === true){
if(\$incidentsPrev[\$id] === \$hash){ //no change
\$incidentStatus[\$id] = 'NC';
}else{
\$incidentStatus[\$id] = 'C'; //changed
}
unset(\$incidentsPrev[\$id]); //we are done with this one
}else{
\$incidentStatus[\$id] = 'N';//new one
}
//at this point what \$incidentsPrev contains are incidents
//which are deleted
foreach(\$incidentsPrev as \$k => \$v){ //all deletes
\$incidentStatus[\$k] = 'D';
}
}

//save away the results for next time
file_put_contents(INCIDENT_HASHES_FILENAME, serialize(\$incidentHashes));

//results
\$new = count(array_keys(\$incidentStatus, 'N'));
\$changed = count(array_keys(\$incidentStatus, 'C'));
\$deleted = count(array_keys(\$incidentStatus, 'D'));
\$noChange = count(array_keys(\$incidentStatus, 'NC'));

echo '<p>', 'New: ', \$new, ' Changed: ', \$changed, ' Deleted: ', \$deleted, ' No Change: ', \$noChange, '</p>';

echo 'Current Hashes: ', '<pre>', print_r(\$incidentHashes, true), '</pre>';
echo 'Status: ', '<pre>', print_r(\$incidentStatus, true), '</pre>';
```

First off I check if I have a file with previous hashes. First time around I will not have any previous hashes so all incidents will be labeled as new. This is what my output looks like:

```Previous Hashes: Array
(
)
New: 5 Changed: 0 Deleted: 0 No Change: 0

Current Hashes: Array
(
[88] => e99e791d7413872d2b10b2774ae75e32
[87] => 68e218269cc5a548d86272b4dee27015
[86] => 71cc7681549a1590748ceef9034069b0
[85] => 1d71598d3142a946e9d115276a4baee8
[84] => eb2869de9544a89515604da930522298
)
Status: Array
(
[88] => N
[87] => N
[86] => N
[85] => N
[84] => N
)
</pre>
```

Now I will change one incident, delete another and add a new one. The XML file now looks like this:

```<?xml version="1.0" encoding="UTF-8"?>
<incidents>
<incident>
<description><![CDATA[Rat ate server **NEW**.]]></description>
<id>89</id>
<time>1/5/2012 6:32 PM</time>
</incident>
<incident>
<description><![CDATA[Server crashed.]]></description>
<id>88</id>
<time>1/4/2012 5:31 PM</time>
</incident>
<incident>
<description><![CDATA[Server stolen again. **CHANGED**]]></description>
<id>87</id>
<time>1/3/2012 4:30 PM</time>
</incident>
<incident>
<description><![CDATA[Server on fire.]]></description>
<id>86</id>
<time>1/2/2012 3:29 PM</time>
</incident>
<incident>
<description><![CDATA[Server misplaced.]]></description>
<id>84</id>
<time>1/1/2012 1:27 PM</time>
</incident>
</incidents>
```

Now if I run the program again this is what I get:

```Previous Hashes: Array
(
[88] => e99e791d7413872d2b10b2774ae75e32
[87] => 68e218269cc5a548d86272b4dee27015
[86] => 71cc7681549a1590748ceef9034069b0
[85] => 1d71598d3142a946e9d115276a4baee8
[84] => eb2869de9544a89515604da930522298
)

New: 1 Changed: 1 Deleted: 1 No Change: 3

Current Hashes: Array
(
[89] => 98b372c37454d5e0209109cc3393274a
[88] => e99e791d7413872d2b10b2774ae75e32
[87] => 9f72a06f5f193ec350300754419444dc
[86] => 71cc7681549a1590748ceef9034069b0
[84] => eb2869de9544a89515604da930522298
)

Status: Array
(
[89] => N
[88] => NC
[87] => C
[86] => NC
[85] => D
[84] => NC
)

```

The code is pretty straightforward. Here are the significant steps:

0. Get hold of previous hashes if available.
1. Iterate over the XML and get all the current hashes.
2. Now compare the two.
4. If found and hashes do not match then data has changed, otherwise unchanged.
5. The remaining hashes indicate that those incidents have been removed.

Possibilities for something like this are many. For example I could send the status array as a JSON package and inform the user what has changed, new or deleted with icons or change in background color.

Also note that you could use array_intersect_assoc for getting unchanged incidents or array_diff_assoc for new incidents. I will leave the rest to your imagination.

I hope this helps you and I look forward to your comments.

Happy Coding!

Jayesh

# Implementation of a Tree Structure in PHP – II

I received an excellent comment by ‘Chris Rogers’ on my earlier post Implementation of a Tree Structure in PHP. He commented to the fact that the iterator does not work if the child was created prior to the parent. Excellent catch!

To that end I have modified the class, specifically the iterator’s ‘createNode’ method which takes care of this fact. The final code can be found on Github: tree-php

```
/**
* JTreeRecursiveIterator
*
* To use a recursive iterator you have to extend of the RecursiveIteratorIterator
* As an example I have built an unordered list
* For detailed information on please see RecursiveIteratorIterator
* http://us.php.net/manual/en/class.recursiveiteratoriterator.php
*
* @package   JTree
* @version 1.0 2011
*/
class JTreeRecursiveIterator extends RecursiveIteratorIterator {
/**
* @var _jTree the JTree object
*/
private \$_jTree;
/**
* @var _str string with ul/li string
*/
private \$_str;

/**
* JTreeRecursiveIterator::__construct()
*
* @param mixed \$jt - the tree object
* @param mixed \$iterator - the tree iterator
* @param mixed \$mode
* @param integer \$flags
* @return
*/
public function __construct(JTree \$jt, \$iterator, \$mode = RecursiveIteratorIterator::LEAVES_ONLY, \$flags = 0) {

parent::__construct(\$iterator, \$mode, \$flags);
\$this->_jTree = \$jt;
\$this->_str = "<ul>\n";
}

/**
* JTreeRecursiveIterator::endChildren()
* Called when end recursing one level.(See manual)
* @return void
*/
public function endChildren() {
parent::endChildren();
\$this->_str .= "</ul></li>\n";
}

/**
* JTreeRecursiveIterator::callHasChildren()
* Called for each element to test whether it has children. (See Manual)
*
* @return mixed
*/
public function callHasChildren() {
\$ret = parent::callHasChildren();
\$value = \$this->current()->getValue();

if(\$ret === true) {
\$this->_str .= "<li>{\$value}<ul>\n";
} else {
\$this->_str .= "<li>{\$value}</li>\n";
}
return \$ret;
}

/**
* JTreeRecursiveIterator::__destruct()
* On destruction end the list and display.
* @return void
*/
public function __destruct() {
\$this->_str .= "</ul>\n";
echo \$this->_str;
}

}
```

Now if you were to re-arrange the array like so where I have made ‘Fires'(id=5) as a child of Hurricanes(id=9)

```\$categories = array();
\$categories[] = array('id' => 1, 'weather_condition' => 'weather', 'parent_id' => 9999);
\$categories[] = array('id' => 2, 'weather_condition' => 'Earthquakes', 'parent_id' => 1);
\$categories[] = array('id' => 3, 'weather_condition' => 'Major', 'parent_id' => 2);
\$categories[] = array('id' => 4, 'weather_condition' => 'Minor', 'parent_id' => 2);
\$categories[] = array('id' => 5, 'weather_condition' => 'Fires', 'parent_id' => 9);
\$categories[] = array('id' => 6, 'weather_condition' => 'Rain', 'parent_id' => 1);
\$categories[] = array('id' => 7, 'weather_condition' => 'Flooding', 'parent_id' => 6);
\$categories[] = array('id' => 8, 'weather_condition' => 'Washout', 'parent_id' => 6);
\$categories[] = array('id' => 9, 'weather_condition' => 'Hurricanes', 'parent_id' => 1);
```

And run it

```//create a new tree object
\$jt = new JTree();

//iterate building the tree
foreach(\$categories as \$category) {
\$uid = \$jt->createNode(\$category['weather_condition'],\$category['id'], \$category['parent_id']);
}

//update: removed third variable. Use defaults
\$it = new JTreeRecursiveIterator(\$jt, new JTreeIterator(\$jt->getTree()));

//iterate to create the ul list
foreach(\$it as \$k => \$v) {}
```

Note that I have removed addChild. It is included in createNode.

The result being:

• weather
• Earthquakes
• Major
• Minor
• Rain
• Flooding
• Washout
• Hurricanes
• Fires

Many thanks to Chris for pointing this out.

Happy computing!

# Implementation of a Tree Structure in PHP

Further to my post on implementing a doubly linked list I took on the adventure of implementing a tree structure. I have used my linked list as my base where I use a hash table to store my node or child objects. Also the most important difference being that the next node is now a collection of children nodes. Also it goes without saying that not implementing a recursive iterator for the tree would make the tree implementation incomplete.

We start with the main class, followed by the node class and the iterator. Finally an example on application of the tree to create an unordered ul/li list.

```/**
* JTree
*
* This class implements the Tree structure and is based on linked list using a hash table.
* Using hash table prevents all possible recursive references and
* allows for more efficient garbage collection. A particularly sore point in PHP.
*
* I have used my implementation of Doubly Linked list as my base.
*
* I have heavily relied on the following 2 references for their algorithms.
* Beginning Algorithims by Simon Harris and James Ross. Wrox publishing.
* Data Structures and Algorithms in Java Fourth Edition by Michael T. Goodrich
* and Roberto Tamassia. John Wiley & Sons.
*
* This program is free software: you can redistribute it and/or modify
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.

* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.

* You should have received a copy of the GNU General Public License
* along with this program.  If not, see <http://www.gnu.org/licenses/>.
* @package JTree
* @version 1.0
*/
class JTree {
/**
* @var UID for the header node
*/

/**
* @var size of list
*/
private \$_size;

/**
* @var hash table to store node objects
*/
private \$_list = array();

/**
* JTree::__construct()
*
* @return
*/
public function __construct() {
\$this->_size = 0;
}

/**
* JTree::getList()
*
* Retreives the hash table
*
* @return array
*/
public function getTree() {
return \$this->_list;
}

/**
* JTree::getNode()
* Given a UID get the node object
*
* @param mixed \$uid
* @return JNode/Boolean
*/
public function getNode(\$uid) {
if(empty(\$uid)) {
throw new Exception('A unique id is required.');
}
\$ret = false;
//look for the node in the hash table
if(array_key_exists(\$uid,\$this->_list) === true) {
\$ret = \$this->_list[\$uid];
}
return \$ret;
}

/**
* JTree::setChild()
*
* This is a helper function. Given a UID for a node
* set it as the next UID for the node.
*
* @param mixed \$uid
* @param mixed \$childUid
* @return void
*/
public function setChild(\$uid, \$childUid) {
if(empty(\$uid) || empty(\$childUid)) {
throw new Exception('Both a from and a to UIDs are required.');
}
//get the node object for this node uid
\$node = \$this->getNode(\$uid);

if(\$node !== false) {
\$node->setChild(\$childUid);
}
}

/**
* JTree::setParent()
*
* This is a helper function to set the parent uid
*
* @param mixed \$uid - UID of the object to be processed on
* @param mixed \$prevUid - put this as next in the above object
* @return void
*/
public function setParent(\$uid, \$parentUid) {
if(empty(\$uid) || empty(\$parentUid)) {
throw new Exception('Both a from and a to UIDs are required.');
}
\$node = \$this->getNode(\$uid);

if(\$node !== false) {
\$node->setParent(\$parentUid);
}
}

/**
* JTree::createNode()
*
* Create a node, store in hash table
* return the reference uid
* @param mixed \$value
* @param mixed \$uid
* @return string \$uid
*/
public function createNode(\$value, \$uid = null) {
if(!isset(\$value)) {
throw new Exception('A value is required to create a node');
}

\$node = new JNode(\$value, \$uid);
\$uid = \$node->getUid();
\$this->_list[\$uid] = \$node;
return \$uid;
}

/**
*
* @param mixed \$parentUid
* @param mixed \$childUid
* @return
*/
public function addChild(\$parentUid = null, \$childUid) {
if(empty(\$childUid)) {
throw new Exception('A UID for the child is required.');
}
//if no parent assume it is the head
if(empty(\$parentUid)) {
}
//parent points to child
\$this->setChild(\$parentUid, \$childUid);

//child points to parent
\$this->setParent(\$childUid, \$parentUid);

return \$childUid;
}

/**
*
* @param mixed \$uid
* @return void
*/
if(empty(\$uid)) {
throw new Exception('A unique ID is required.');
}
}

/**
* JTree::getChildren()
*
* This is a helper function to get the child node uids given the node uid
*
* @param mixed \$uid
* @return mixed
*/
public function getChildren(\$uid) {
if(empty(\$uid)) {
throw new Exception('A unique ID is required.');
}

\$node = \$this->getNode(\$uid);

if(\$node !== false) {
return \$node->getChildren();
}
}

/**
* JTree::getParent()
*
* This is a helper function to get the
* parent node uid
*
* @param mixed \$uid
* @return string \$uid
*/
public function getParent(\$uid) {
if(empty(\$uid)) {
throw new Exception('A unique ID is required.');
}
\$ret = false;
\$node = \$this->getNode(\$uid);

if(\$node !== false) {
\$ret = \$node->getParent();
}
return \$ret;
}

/**
* JTree::getValue()
*
* @param mixed \$uid
* @return
*/
public function getValue(\$uid) {
if(empty(\$uid)) {
throw new Exception('A unique ID is required.');
}

\$node = \$this->getNode(\$uid);
return \$node->getValue();
}
}

```

The node class. Note the collection of children.

```/**
* JNode
*
* This is a simple class to construct a node
* Please note that each node object will be
* eventually stored in a hash table where the
* hash will be a UID.
*
* Note that in comparison to thee Doubly Linked List implementation
* the children are now stored in an array
*
* @package JTree
* @version 2011
*/
class JNode {
/**
* @var _value for the value field
*/
private \$_value;
/**
* @var _parent uid of the parent node
*/
private \$_parent;
/**
* @var _children collection of uids for the child nodes
*/
private \$_children = array();
/**
* @var _uid for this node
*/
private \$_uid;

/**
* JNode::__construct()
*
* @param mixed \$value
* @param mixed \$uid
* @return void
*/
public function __construct(\$value = null,\$uid = null) {
if(!isset(\$value)) {
throw new Exception('A value is required to create a node');
}
\$this->setValue(\$value);
\$this->setUid(\$uid);
}

/**
* JNode::setUid()
*
* @param mixed \$uid
* @return
*/
public function setUid(\$uid = null) {
//if uid not supplied...generate
if(empty(\$uid)) {
\$this->_uid = uniqid();
} else {
\$this->_uid = \$uid;
}
}

/**
* JNode::getUid()
*
* @return string uid
*/
public function getUid() {
return \$this->_uid;
}

/**
* JNode::setValue()
*
* @param mixed \$value
* @return void
*/
public function setValue(\$value) {
\$this->_value = \$value;
}

/**
* JNode::getValue()
*
* @return mixed
*/
public function getValue() {
return \$this->_value;
}

/**
* JNode::getParent()
*
* gets the uid of the parent node
*
* @return string uid
*/
public function getParent() {
return \$this->_parent;
}

/**
* JNode::setParent()
*
* @param mixed \$parent
* @return void
*/
public function setParent(\$parent) {
\$this->_parent = \$parent;
}

/**
* JNode::getChildren()
*
* @return mixed
*/
public function getChildren() {
return \$this->_children;
}

/**
* JNode::setChild()
*
* A child node's uid is added to the childrens array
*
* @param mixed \$child
* @return void
*/
public function setChild(\$child) {
if(!empty(\$child)) {
\$this->_children[] = \$child;
}
}

/**
* JNode::anyChildren()
*
* Checks if there are any children
* returns ture if it does, false otherwise
*
* @return bool
*/
public function anyChildren() {
\$ret = false;

if(count(\$this->_children) > 0) {
\$ret = true;
}
return \$ret;
}

/**
* JNode::childrenCount()
*
* returns the number of children
*
* @return bool/int
*/
public function childrenCount() {
\$ret = false;
if(is_array(\$this->_children)){
\$ret = count(\$this->_children);
}
return \$ret;
}
}
```

The tree recursive iterator.

```
/**
* JTreeIterator
*
* The Tree structure would be incomplete if I did not include a
* is pretty standard.
* I have extended the arrayIterator because I am using an array for my hash table.
* Note that I have not implemented the next and rewind methods as I do not need to
* special with these. So the parent(ArrayIterator) methods will be called by default.
*
* @package
* @version 2011
*/
class JTreeIterator extends ArrayIterator implements RecursiveIterator {
/**
* @var _list this is the hash table
*/
private \$_list = array();
/**
* @var _next this is for the children
*/
private \$_next = array();
/**
* @var _position the iterator position
*/
private \$_position;

/**
* JTreeIterator::__construct()
*
* @param mixed \$list - the hash table
* @param mixed \$tree -
* @return JTreeIterator
*/
public function __construct(array \$list, array \$tree = null) {
\$this->_list = \$list;

if(is_null(\$tree)) {
reset(\$this->_list);
\$next = current(\$this->_list);
\$this->_next = \$next->getChildren();
} else {
\$this->_next = \$tree;
}

parent::__construct(\$this->_next);
}

/**
* JTreeIterator::current()
*
* @return
*/
public function current() {
//get the object uid from the hash table
//then get the object
\$current = parent::current();
\$nObj = \$this->_list[\$current];
return \$nObj;
}

/**
* JTreeIterator::key()
*
* @return
*/
public function key() {
\$key = parent::key();
\$key = \$this->_next[\$key];
return \$key;
}

/**
* JTreeIterator::hasChildren()
*
* @return mixed
*/
public function hasChildren() {
\$next = \$this->_list[\$this->key()];
\$next = \$next->anyChildren();
return \$next;
}

/**
* JTreeIterator::getChildren()
*
* @return JTreeIterator
*/
public function getChildren() {
\$childObj = \$this->_list[\$this->key()];
\$children = \$childObj->getChildren();
return new JTreeIterator(\$this->_list, \$children);
}
}
```

As an example assume that you wanted to create a unordered list based on an array of values
similar to something you would get from a database which typically stores hierarchical data using the ‘The Adjacency List Model’. Further assume the following collection:

```\$categories = array();
\$categories[] = array('id' => 1, 'weather_condition' => 'weather', 'parent_id' => 0);
\$categories[] = array('id' => 2, 'weather_condition' => 'Earthquakes', 'parent_id' => 1);
\$categories[] = array('id' => 3, 'weather_condition' => 'Major', 'parent_id' => 2);
\$categories[] = array('id' => 4, 'weather_condition' => 'Minor', 'parent_id' => 2);
\$categories[] = array('id' => 5, 'weather_condition' => 'Fires', 'parent_id' => 1);
\$categories[] = array('id' => 6, 'weather_condition' => 'Rain', 'parent_id' => 1);
\$categories[] = array('id' => 7, 'weather_condition' => 'Flooding', 'parent_id' => 6);
\$categories[] = array('id' => 8, 'weather_condition' => 'Washout', 'parent_id' => 6);
\$categories[] = array('id' => 9, 'weather_condition' => 'Hurricanes', 'parent_id' => 1);
```

To use our iterator we need to extend our iterator off RecursiveIteratorIterator . Customize it to build our ul/li string.

```/**
* JTreeRecursiveIterator
*
* To use a recursive iterator you have to extend of the RecursiveIteratorIterator
* As an example I have built an unordered list
* For detailed information on please see RecursiveIteratorIterator
* http://us.php.net/manual/en/class.recursiveiteratoriterator.php
*
* @package   JTree
* @version 1.0 2011
*/
class JTreeRecursiveIterator extends RecursiveIteratorIterator {
/**
* @var _jTree the JTree object
*/
private \$_jTree;
/**
* @var _str string with ul/li string
*/
private \$_str;

/**
* JTreeRecursiveIterator::__construct()
*
* @param mixed \$jt - the tree object
* @param mixed \$iterator - the tree iterator
* @param mixed \$mode
* @param integer \$flags
* @return
*/
public function __construct(JTree \$jt, \$iterator, \$mode = LEAVES_ONLY, \$flags = 0) {

parent::__construct(\$iterator, \$mode, \$flags);
\$this->_jTree = \$jt;
\$this->_str = "<ul>\n";
}

/**
* JTreeRecursiveIterator::endChildren()
* Called when end recursing one level.(See manual)
* @return void
*/
public function endChildren() {
parent::endChildren();
\$this->_str .= "</ul></li>\n";
}

/**
* JTreeRecursiveIterator::callHasChildren()
* Called for each element to test whether it has children. (See Manual)
*
* @return mixed
*/
public function callHasChildren() {
\$ret = parent::callHasChildren();
\$value = \$this->current()->getValue();

if(\$ret === true) {
\$this->_str .= "<li>{\$value}<ul>\n";
} else {
\$this->_str .= "<li>{\$value}</li>\n";
}
return \$ret;
}

/**
* JTreeRecursiveIterator::__destruct()
* On destruction end the list and display.
* @return void
*/
public function __destruct() {
\$this->_str .= "</ul>\n";
echo \$this->_str;
}

}
```

Now that our code is done we can use it.

```
//create a new tree object
\$jt = new JTree();

//iterate building the tree
foreach(\$categories as \$category) {
\$uid = \$jt->createNode(\$category['weather_condition'],\$category['id']);
\$parentId = null;

if(!empty(\$category['parent_id'])) {
\$parentId = \$category['parent_id'];
}

}

\$it = new JTreeRecursiveIterator(\$jt, new JTreeIterator(\$jt->getTree()), true);

//iterate to create the ul list
foreach(\$it as \$k => \$v) {}

```

And the output is…

```<ul>
<li>weather
<ul>
<li>Earthquakes
<ul>
<li>Major</li>
<li>Minor</li>
</ul>
</li>
<li>Fires</li>
<li>Rain
<ul>
<li>Flooding</li>
<li>Washout</li>
</ul>
</li>
<li>Hurricanes</li>
</ul>
</li>
</ul>

```

and it looks something like this:

• weather
• Earthquakes
• Major
• Minor
• Fires
• Rain
• Flooding
• Washout
• Hurricanes

Enjoy 🙂
P.S. Based on Chris’s comments I wrote the second part to this post: Implementation of a Tree Structure in PHP – II

# Doubly Linked List in PHP

One of the weaknesses of PHP is the lack of Abstract Data Structures. 5.3 brought in a few but nothing very significant. Users of 5.2+ have none. Creating data structures in PHP is also not very simple because PHP’s garbage collection mechanism does not like recursive references. PHP bug 33595 confirms this very eloquently. This also teaches us an important lesson. Never take garbage collection for granted. Always clean up after yourself.

It all boils down to how objects in PHP are referenced. We have object identifiers and not pointers or object hashes. I did get some implementations on the web but all seemed to have forgotten about the GC issue. A large list with thousands of nodes resulted in memory errors.

To decouple my implementation from object identifiers I decided to use hash table to store my node objects. Let me explain.

In a traditional implementation I would have something like the following. A rudimentary node class with few methods shown. Also note that \$_previous and \$_next are object identifiers. :

```class JNode
{
private \$_value;
private \$_previous;
private \$_next;

public function __construct(\$value)
{
\$this->setValue(\$value);
}

public function setPrevious(JNode \$previous)
{
\$this->_previous = \$previous;
}

public function setNext(JNode \$next)
{
\$this->_next = \$next;
}
```

You could use it like this:

```\$head = new MyNode('HEAD');

\$node1 = new MyNode('NODE-1');

...
...
```

Rather than using object identifiers why not do it this way. I have modified the class to use UIDs. Also note that in the constructor I have setting up a new UID for the object. Now \$_next and \$_previous will be UIDs and not object identifiers.:

```public function __construct(\$value)
{
\$this->setValue(\$value);
\$this->setUid();
}

public function setUid(\$uid = null)
{
//if uid not supplied...generate
if(empty(\$uid)) {
\$this->_uid = uniqid();
} else {
\$this->_uid = \$uid;
}
}

public function getUid()
{
return \$this->_uid;
}

public function setValue(\$value)
{
if(empty(\$value)) {
throw new Exception('A value is required.');
}
\$this->_value = \$value;
}

public function setPrevious(\$previous)
{
if(empty(\$previous)) {
throw new Exception('A unique ID is required.');
}
\$this->_previous = \$previous;
}

public function setNext(\$next)
{
if(empty(\$next)) {
throw new Exception('A unique ID is required.');
}
\$this->_next = \$next;
}
```

The use would be according to these line:

```//my hashtable
//uid => object
\$myHashTable = array();

\$node1 = new MyNode('NODE-1');
\$node1Uid = \$node1->getUid();
\$myHashTable[\$node1Uid ] = \$node1;

...
...
```

Now rather than using the object identifier as reference to the object we use a UID to refer to the object identifier which refers to the actual object. This way there are no circular or recursive references. Also GC becomes very straightforward. Every list has an iterator. Writing one in this case also becomes very simple. Now that you have seen the concept here is the final implementation.

The final implementation can be found on Github: doubly-linked-list-php: Implementation of a doubly linked list for legacy PHP sites (5.2.X)

Please note that this is a minimum implementation. You could add many more methods such as inserting at an index, getting the size of the list, indexOf. My main intent is to show how to use UIDs as object references. Also note that in the main class I have helper classes to create, add and delete nodes.

In the following example I have included memory use statements to make sure that I clean up properly.

```//instantiate the list

//First node goes after the head.
\$firstNode = \$ll->createNode('First Node');

//10 more nodes
for(\$i = 0; \$i < 5; \$i++) {
\$node = \$ll->createNode('Node-' . \$i);
\$firstNode = \$node;
}

//and this is how we iterate...iterate

foreach(\$it as \$k => \$v) {
echo '<pre>', \$k, ': ', print_r(\$v, true), '</pre>';
}

unset(\$ll, \$it);

echo 'Peak: ' . number_format(memory_get_peak_usage(), 0, '.', ',') .  " bytes<br>";

echo 'End: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes<br>";

```

The output would be something like this:

```Initial: 126,360 bytes

4d7f677322b38: JNode Object
(
[_value:private] => First Node
[_previous:private] => 4d7f677322b06
[_next:private] => 4d7f677322b69
[_uid:private] => 4d7f677322b38
)

4d7f677322b69: JNode Object
(
[_value:private] => Node-0
[_previous:private] => 4d7f677322b38
[_next:private] => 4d7f677322b95
[_uid:private] => 4d7f677322b69
)

4d7f677322b95: JNode Object
(
[_value:private] => Node-1
[_previous:private] => 4d7f677322b69
[_next:private] => 4d7f677322bbf
[_uid:private] => 4d7f677322b95
)

4d7f677322bbf: JNode Object
(
[_value:private] => Node-2
[_previous:private] => 4d7f677322b95
[_next:private] => 4d7f677322be8
[_uid:private] => 4d7f677322bbf
)

4d7f677322be8: JNode Object
(
[_value:private] => Node-3
[_previous:private] => 4d7f677322bbf
[_next:private] => 4d7f677322c12
[_uid:private] => 4d7f677322be8
)

4d7f677322c12: JNode Object
(
[_value:private] => Node-4
[_previous:private] => 4d7f677322be8
[_next:private] => 4d7f677322b1b
[_uid:private] => 4d7f677322c12
)

Peak: 175,952 bytes
End: 135,080 bytes
```

Notice that the cleanup was not bad. If I had to create 1000 nodes then this is what the memory utilization looks like:

Initial: 126,376 bytes
Peak: 803,464 bytes
End: 192,440 bytes

That’s pretty decent in terms of GC but there is still room for improvement.