TinyButStrong - the PHP Template Engine
Categories > Your tips & tricks >

Adjacency List -> Hierarchy List

The forum is closed. Please use Stack Overflow for submitting new questions. Use tags: tinybutstrong , opentbs

By: Jared Eckersley
Date: 2010-04-15
Time: 21:02

Adjacency List -> Hierarchy List

Hi All,

I just thought I would share this bit of code that creates an Adjacency / Heiarchy list:

First, here is the table structure:
CREATE TABLE IF NOT EXISTS Locations (
  ID int unsigned NOT NULL auto_increment,
  PARENT int NOT NULL DEFAULT 0,
  LABEL varchar(100) NOT NULL,
  PRIMARY KEY  (ID)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

Now, the query and array creation:
$sql = "SELECT ID,PARENT,LABEL from Locations ORDER BY ID ASC";
$res = mysql_query($sql);
$data = array(); // array that ends up holding the tree
$tree = array(); // array that just holds the results from db - indexed by table ID
$pointers = array(); // temporary helper array
$x = array(); // this is an array that I build to pass into MergeBlock() method

Now, the while loop that is modified from the work found here: http://blog.jdbartlett.com/2008/01/php-data-hierarchies-now-with-100-more.html
while ($row = mysql_fetch_row($res)) {
  $tree[$row[0]] = array('id'=>$row[0],'parent'=>$row[1],'label'=>$row[2]);

  if(!isset($pointers[$row[0]]))
    $pointers[$row[0]] = array();

  if(!empty($row[1])) {
    if(!isset($pointers[$row[1]]))
      $pointers[$row[1]] = array();
    $pointers[$row[1]][$row[0]] = &$pointers[$row[0]];
  }
  else $data[$row[0]] = &$pointers[$row[0]];
}

Now, I build up an array that I can use to pass data into the MergeBlock method:
unset($pointers); // we do not need this anymore

foreach ($data as $k1=>$v1) {
  $x[$k1]['loc'] = $tree[$k1]['label'];
  foreach ($data[$k1] as $k2=>$v2) {
    $x[$k1]['sub1'][$k2]['loc'] = $tree[$k2]['label'];
    foreach ($data[$k1][$k2] as $k3=>$v3) {
      $x[$k1]['sub1'][$k2]['sub2'][$k3]['loc'] = $tree[$k3]['label'];
    }
  }

}

unset($data); // we do not need this anymore
unset($tree); // we do not need this anymore

We now have an array that MergeBlock can handle:
include('tbs_class_php5.php');
$tbs  = new clsTinyButStrong;

$tbs->LoadTemplate('test.html');
$tbs->MergeBlock('top','array','x');
$tbs->MergeBlock('sub1','array',"x[%p1%][sub1]");
$tbs->MergeBlock('sub2','array',"x[%p1%][sub1][%p2%][sub2]");

This is the same html:
<html><head><title></title></head>
  <body>
    <ul>
      <li>[top.loc;block=li]
        <ul>
          <li>[sub1.loc;block=li;p1=[top.$]]
            <ul>
              <li>[sub2.loc;block=li;p1=[top.$];p2=[sub1.$]]</li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </body>
</html>

I hope this helps someone else with the problem I had of creating this type of structure.

- Jared
By: Skrol29
Date: 2010-04-15
Time: 21:13

Re: Adjacency List -> Hierarchy List

Thanks Jared :)
By: Jared Eckersley
Date: 2010-04-15
Time: 22:19

Re: Adjacency List -> Hierarchy List

No Problem,

I have reworked your list-boxes using javascript example to reflect this new concept:

The table structure:
CREATE TABLE IF NOT EXISTS Locations (
  ID int unsigned NOT NULL auto_increment,
  PARENT int NOT NULL DEFAULT 0,
  LABEL varchar(100) NOT NULL,
  PRIMARY KEY  (ID)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

The data:
INSERT INTO Locations VALUES (1,0, 'Europe');
INSERT INTO Locations VALUES (2,0, 'Asia');
INSERT INTO Locations VALUES (3,0, 'America');
INSERT INTO Locations VALUES (4,0, 'Africa');
INSERT INTO Locations VALUES (5,0, 'Oceania');
INSERT INTO Locations VALUES (6, 1, 'France');
INSERT INTO Locations VALUES (7, 1, 'United Kindom');
INSERT INTO Locations VALUES (8, 2, 'China');
INSERT INTO Locations VALUES (9, 2, 'Japan');
INSERT INTO Locations VALUES (10, 3, 'USA');
INSERT INTO Locations VALUES (11, 3, 'Argentina');
INSERT INTO Locations VALUES (12, 4, 'Cameroon');
INSERT INTO Locations VALUES (13, 4, 'Tunisia');
INSERT INTO Locations VALUES (14, 5, 'Australia');
INSERT INTO Locations VALUES (15, 5, 'New Zealand');
INSERT INTO Locations VALUES (16, 6, 'Paris');
INSERT INTO Locations VALUES (17, 6, 'Toulouse');
INSERT INTO Locations VALUES (18, 7, 'London');
INSERT INTO Locations VALUES (19, 7, 'Docklands');
INSERT INTO Locations VALUES (20, 8, 'Beijing');
INSERT INTO Locations VALUES (21, 8, 'Shanghai');
INSERT INTO Locations VALUES (22, 9, 'Tokyo');
INSERT INTO Locations VALUES (23, 9, 'Yokohama');
INSERT INTO Locations VALUES (24, 10, 'Washington');
INSERT INTO Locations VALUES (25, 10, 'New York');
INSERT INTO Locations VALUES (26, 11, 'Buenos Aires');
INSERT INTO Locations VALUES (27, 11, 'Santa Fe');
INSERT INTO Locations VALUES (28, 12, 'Yaoundé');
INSERT INTO Locations VALUES (29, 13, 'Garoua');
INSERT INTO Locations VALUES (30, 14, 'T?nis');
INSERT INTO Locations VALUES (31, 15, 'Syndey');
INSERT INTO Locations VALUES (32, 16, 'Auckland');

The PHP:
$sql = "SELECT ID,PARENT,LABEL from Locations ORDER BY ID ASC";
$res = mysql_query($sql);
$data = array();
$tree = array();
$x = array();
$pointers = array();

while ($row = mysql_fetch_row($res)) {
  $tree[$row[0]] = array('id'=>$row[0],'parent'=>$row[1],'label'=>$row[2]);

  if(!isset($pointers[$row[0]]))
    $pointers[$row[0]] = array();

  if(!empty($row[1])) {
    if(!isset($pointers[$row[1]]))
      $pointers[$row[1]] = array();
    $pointers[$row[1]][$row[0]] = &$pointers[$row[0]];
  }
  else $data[$row[0]] = &$pointers[$row[0]];
}

unset($pointers);

foreach ($data as $k1=>$v1) {
  $x[$k1]['loc'] = $tree[$k1]['label'];
  foreach ($data[$k1] as $k2=>$v2) {
    $x[$k1]['sub1'][$k2]['loc'] = $tree[$k2]['label'];
    foreach ($data[$k1][$k2] as $k3=>$v3) {
      $x[$k1]['sub1'][$k2]['sub2'][$k3]['loc'] = $tree[$k3]['label'];
    }
  }

}

unset($data);
unset($tree);

include('gemini/template/tbs_class_php5.php');
$tbs  = new clsTinyButStrong;

$tbs->LoadTemplate('x.html');
$tbs->MergeBlock('top1,top2','array','x');
$tbs->MergeBlock('sub1','array',"x[%p1%][sub1]");
$tbs->MergeBlock('sub2','array',"x[%p1%][sub1][%p2%][sub2]");


The HTML:
<html>
<head>
<title>TEST</title>
<script language="JavaScript" type="text/JavaScript">

var lst_continent = new Array();

[top1;block=begin]lst_continent[[top1.$]] = {id: [top1.$], name: '[top1.loc;htmlconv=js]', lst_country: new Array()};
[sub1;block=begin;p1=[top1.$]]lst_continent[[top1.$]].lst_country[[sub1.$]] = {id: [sub1.$], name: '[sub1.loc;htmlconv=js]', lst_town: new Array()};
[sub2;block=begin;p1=[top1.$];p2=[sub1.$]]lst_continent[[top1.$]].lst_country[[sub1.$]].lst_town[[sub2.$]] = {id: [sub2.$], name: '[sub2.loc;htmlconv=js]' };
[sub2;block=end]
[sub1;block=end]
[top1;block=end]



function f_Change_Continent() {
  var sel_continent = document.forms.frm_selection.elements.sel_continent;
  var sel_country   = document.forms.frm_selection.elements.sel_country;
  var sel_town      = document.forms.frm_selection.elements.sel_town;
  f_Init_List(sel_country,lst_continent[sel_continent.value].lst_country);
  f_Init_List(sel_town,false);
}
function f_Change_Country() {
  var sel_continent = document.forms.frm_selection.elements.sel_continent;
  var sel_country   = document.forms.frm_selection.elements.sel_country;
  var sel_town      = document.forms.frm_selection.elements.sel_town;
  f_Init_List(sel_town,lst_continent[sel_continent.value].lst_country[sel_country.value].lst_town);
}
function f_Change_Town() {
  window.alert('Item selected: '+document.forms.frm_selection.elements.sel_town.value);
}

function f_Init_List(lst,items) {
  var i = 0;
  lst.value = 0;
  // Erase all items but the first
  for (i=lst.options.length-1;i>0;i--) {
    lst.options[i] = null;
  }
  // Insert new items
  if (items!==false) {
    for (i in items) {
      lst.options[lst.options.length] = new Option(items[i].name,items[i].id);
    }
  }

}

</script>
</head>
<body>

<form action="" method="post" name="frm_selection" id="frm_selection">
  Continent:
  <select name="sel_continent" id="sel_continent" onChange="f_Change_Continent()">
    <option value="0">&lt;select a contient&gt;</option>
    <option value="[top2.$;block=option]" selected>[top2.loc]</option>
  </select>
  Country:
  <select name="sel_country" id="sel_country" onChange="f_Change_Country()">
    <option value="0" selected>&lt;select a country&gt;</option>
  </select>
  Town:
  <select name="sel_town" id="sel_town" onChange="f_Change_Town()">
    <option value="0" selected>&lt;select a town&gt;</option>
  </select>
</form>

</body>
</html>

This allows you to go from 3 tables and 3 queries down to 1 table and 1 query.

- Jared
By: Jared Eckersley
Date: 2010-04-16
Time: 02:54

Re: Adjacency List -> Hierarchy List

Just noticed that I had an error in the sql inserts - here are the fixed inserts:

INSERT INTO Locations VALUES (1,0, 'Europe');
INSERT INTO Locations VALUES (2,0, 'Asia');
INSERT INTO Locations VALUES (3,0, 'America');
INSERT INTO Locations VALUES (4,0, 'Africa');
INSERT INTO Locations VALUES (5,0, 'Oceania');

INSERT INTO Locations VALUES (6, 1, 'France');
INSERT INTO Locations VALUES (7, 1, 'United Kindom');
INSERT INTO Locations VALUES (8, 2, 'China');
INSERT INTO Locations VALUES (9, 2, 'Japan');
INSERT INTO Locations VALUES (10, 3, 'USA');
INSERT INTO Locations VALUES (11, 3, 'Argentina');
INSERT INTO Locations VALUES (12, 4, 'Cameroon');
INSERT INTO Locations VALUES (13, 4, 'Tunisia');
INSERT INTO Locations VALUES (14, 5, 'Australia');
INSERT INTO Locations VALUES (15, 5, 'New Zealand');

INSERT INTO Locations VALUES (16, 6, 'Paris');
INSERT INTO Locations VALUES (17, 6, 'Toulouse');
INSERT INTO Locations VALUES (18, 7, 'London');
INSERT INTO Locations VALUES (19, 7, 'Docklands');
INSERT INTO Locations VALUES (20, 8, 'Beijing');
INSERT INTO Locations VALUES (21, 8, 'Shanghai');
INSERT INTO Locations VALUES (22, 9, 'Tokyo');
INSERT INTO Locations VALUES (23, 9, 'Yokohama');
INSERT INTO Locations VALUES (24, 10, 'Washington');
INSERT INTO Locations VALUES (25, 10, 'New York');
INSERT INTO Locations VALUES (26, 11, 'Buenos Aires');
INSERT INTO Locations VALUES (27, 11, 'Santa Fe');
INSERT INTO Locations VALUES (28, 12, 'Yaoundé');
INSERT INTO Locations VALUES (29, 12, 'Garoua');
INSERT INTO Locations VALUES (30, 13, 'T?nis');
INSERT INTO Locations VALUES (31, 14, 'Syndey');
INSERT INTO Locations VALUES (32, 15, 'Auckland');
By: Jared Eckersley
Date: 2010-04-16
Time: 03:19

Re: Adjacency List -> Hierarchy List

I keep responding to myself - I don't normally talk to myself :)

Here is a modified version of this method that removes code that is not needed:

$sql = "SELECT ID,PARENT,LABEL from Locations ORDER BY Locations.ID ASC";
$res = mysql_query($sql);
$data = array();
$pointers = array();

while ($row = mysql_fetch_row($res)) {

  if(!isset($pointers[$row[0]])) {
    $pointers[$row[0]] = array();
    $pointers[$row[0]]['loc'] = $row[2];
  }

  if(!empty($row[1])) {
    if(!isset($pointers[$row[1]])) {
      $pointers[$row[1]] = array();
      $pointers[$row[0]]['loc'] = $row[2];
    }

    $pointers[$row[1]]['sub'][$row[0]] =  &$pointers[$row[0]];

  } else {
    $data[$row[0]] = &$pointers[$row[0]]; // This is our top level

  }

}

unset($pointers);

include('gemini/template/tbs_class_php5.php');
$tbs  = new clsTinyButStrong;

$tbs->LoadTemplate('x.html');
$tbs->MergeBlock('top1,top2','array','data');
$tbs->MergeBlock('sub1','array',"data[%p1%][sub]");
$tbs->MergeBlock('sub2','array',"data[%p1%][sub][%p2%][sub]");

$tbs->Show();
By: TomH
Date: 2010-04-17
Time: 17:13

Re: Adjacency List -> Hierarchy List

Jared,

I can't quite get my head around what you're doing here, but...  I would be interested in your comments comparing the pros and cons of your method to the method found here (under "Menu Tree")
http://tomhenry.us/tbs3/

Thanks for any insights you can contribute,
TomH
By: Jared Eckersley
Date: 2010-04-18
Time: 02:32

Re: Adjacency List -> Hierarchy List

Hi Tom,

Let me start with a code fix:

$pointers[$row[0]]['loc'] = $row[2];

Should read:

$pointers[$row[1]]['loc'] = $row[2];

Also, let me start by saying that I can not take credit for this solution. This is based on the work done by JD Bartlett.

All I have done is adapt this to work with TBS.

So here is the break down of what the solution does:

  if(!isset($pointers[$row[0]])) {
    $pointers[$row[0]] = array();
    $pointers[$row[0]]['loc'] = $row[2];
  }

This just makes sure that the array element is set. The reason that this is important is that a parent item could be added to the DB after a child element - or for what ever reason - you change the sort order of the sql.
The array indice 'loc' is just a means to be able to use the label in the template.

These are the interesting lines:
    $pointers[$row[1]]['sub'][$row[0]] =  &$pointers[$row[0]];

  } else {
    $data[$row[0]] = &$pointers[$row[0]]; // This is our top level

  }

The line that sets the $data var is pointing to the top level indice of $pointer. Because this is being passed by reference, the value is not a constant. As $pointer grows in the line above, $data is also growing. The line above that is setting $pointer is doing the same thing. The child level of pointer is being set to the reference of the parent level.

I hope I was able to explain this well enough.

Since you have a test suit setup, maybe you could run some comparisons and let us know the results.

- Jared