<?php
/**
* $Id: adjacency.class.php,v 1.2 2010/05/15
*
*
* This is a simple class to handle adjacency list model operations within a MySQL database.
* The class manages data trees based on the adjacency list model.
* Please see: http://en.wikipedia.org/wiki/Adjacency_list
*
*
* Please see examples file for operation
*
* LICENSE: Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met: Redistributions of source code must retain the
* above copyright notice, this list of conditions and the following
* disclaimer. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following disclaimer
* in the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
* NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*
* @package Adjacency List Model
* @author Peter Drinnan <hide@address.com[dot]com>
* @copyright 2010 Peter Drinnan
* @license http://www.opensource.org/licenses/bsd-license.php
*
*
*/
class adjacencyTree{
/**
* @var used for mysql operations
*/
public $dbConnectionID;
/**
* @var array $refs holds a data reference to the child nodes
*/
public $dbtablename = '';
/**
* @var array $refs holds a data reference to the child nodes
*/
public $refs = array();
/**
* @var array $list holds a data reference to the parent node(s)
*/
public $list = array();
/**
* @var array $idlist holds a list of ids
*/
public $idlist = array();
/**
* @var int used to set initial list key to parent id
*/
private $initparentid = null;
/**
* @var string $id_field points to the key id of the record
*/
public $id_field = '';
/**
* @var string $parent_id_field points to the key parent_id of the record
*/
public $parent_id_field = '';
/**
* @var string $position_field points to the key position of the record
*/
public $position_field = '';
/**
* @var array $tablefields holds all non key fields of the source data table
*/
private $tablefields = array();
/**
* @var array $deleteids holds a list of ids that can be deleted from a node
*/
private $deleteids = array();
/**
* Constructor
*
*/
public function __construct(){
}//////////////
/**
* set database connection id
* @param string
*/
public function setDBConnectionID($dbconnectionid){
$this->dbConnectionID = $dbconnectionid;
}//////////////////////////
/**
* set var id_field
* @param string
*/
public function setidfield($id_field){
$this->id_field = $id_field;
}/////////////////
/**
* set var parent_id_field
* @param string
*/
public function setparentidfield($parent_id_field){
$this->parent_id_field = $parent_id_field;
}//////////////////
/**
* set var position_field
* @param string
*/
public function setpositionfield($position_field){
$this->position_field = $position_field;
}/////////////
/**
* set var dbtablename
* @param string
*/
public function setdbtable($tablename){
$this->dbtablename = $tablename;
}///////////////////
/**
* Set the field names for the table omitting key fields
*/
private function setFieldNames(){
$sql = "SHOW COLUMNS FROM " . $this->dbtablename;
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$fieldname = $row['Field'];
if( $fieldname != $this->id_field
&&
$fieldname != $this->parent_field
&&
$fieldname != $this->position_field
){
$this->tablefields[] = $fieldname;
}
}
}//////////////////
/**
* trigger for getFullNodesArray resets list and ref before call
* @return multidimensional array
*/
public function getFullNodes(){
$this->resetdrill = false;
$this->list = array(); // reinitialize this list
$this->refs = array(); // reinitialize this list
$this->initparentid = null; // init all
return $this->getFullNodesArray();
}/////////////////
/**
* read all data from the source able and put it into a multidimensional array
* @return multidimensional array
*/
private function getFullNodesArray(){
$this->setFieldNames();
$sql = "SELECT * FROM " . $this->dbtablename . " ORDER BY ".$this->position_field;
$result = mysql_query($sql);
while($data = @mysql_fetch_assoc($result)) {
$thisref = &$this->refs[ $data[$this->id_field] ];
$thisref[$this->parent_id_field] = $data[$this->parent_id_field];
$thisref[$this->position_field] = $data[$this->position_field];
foreach($this->tablefields as $val){
$thisref[$val] = $data[$val];
}
if ($data[$this->parent_id_field] == 0) {
$this->list[ $data[$this->id_field] ] = &$thisref;
} else {
$this->refs[ $data[$this->parent_id_field] ]['children'][ $data[$this->id_field] ] = &$thisref;
}
}
return $this->list;
}////////////////////
/**
* Not used yet but may come in useful later
*/
public function getFullNodesIDs($parent) {
$items = $this->getFullNodesArray($parent);
return $this->getNodeIds($items);
}//////////
/**
* Return all the ids of the children
*@param $parent_id
*@return array
*/
public function getChildNodeIDs($parent) {
$this->list = array(); // reinitialize this list
$this->refs = array(); // reinitialize this list
$this->initparentid = null; // init all
$items = $this->getChildNodesArray($parent);
return $this->getNodeIds($items);
}//////////
/*
* gets the nodes for a sibling , trigger for getChildNodesArray resets list and ref before call
* @return multidimensional array
*/
public function getSiblingNodes($sibling_id) {
$this->list = array(); // reinitialize this list
$this->refs = array(); // reinitialize this list
$this->initparentid = null; // init all
$parent_id = $this->getParentID($sibling_id);
return $this->getChildNodesArray($parent_id);
}//////////////
/*
* trigger for getChildNodesArray resets list and ref before call
* @return multidimensional array
*/
public function getChildNodes($parent) {
$this->list = array(); // reinitialize this list
$this->refs = array(); // reinitialize this list
$this->initparentid = null; // init all
return $this->getChildNodesArray($parent);
}//////////////
/*
* return the parent id of the selected category
*@param $node_id
*@return $parent_id
*/
public function getParentID($node_id) {
$sql = "SELECT " . $this->parent_id_field . " FROM " . $this->dbtablename . " WHERE " . $this->id_field . " = '$node_id' ";
$row = mysql_fetch_row(mysql_query($sql));
return $row[0];
}
/*
* return the immediate parent data of the selected category
*@param $node_id
*@return $array of parent data
*/
public function getParentData($node_id) {
$parent_id = $this->getParentID($node_id);
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->id_field . " = '$parent_id' ";
$row = mysql_fetch_assoc(mysql_query($sql));
return $row;
}
/*
* return an enumerated array of parent ids for the selected child
*@param $node_id
*@return array list of full path parent_ids
*/
public function getParentIDs($node) {
$ajdparent_ids = array(); // initialize the idlist
$has_parent = true;
while($has_parent){
$node = $this->getParentID($node);
if($node > 1){ // over the master id
$ajdparent_ids[] = $node;
}else{
$has_parent = false;
}
}
$ajdparent_ids = array_reverse($ajdparent_ids);
return $ajdparent_ids;
}/////////////
/*
* return an enumerated array of parent data for the selected child
*@param $node_id
*@return array list of full path parents data
*/
public function getParentsData($node) {
$ajdparent_data = array(); // initialize the idlist
$nodedata[$this->id_field] = $node;
$has_parent = true;
while($has_parent){
$nodedata = $this->getParentData($nodedata[$this->id_field]);
if($nodedata[$this->id_field] > 1){ // over the master id
$ajdparent_data[] = $nodedata;
}else{
$has_parent = false;
}
}
return array_reverse($ajdparent_data);
}/////////////
/**
* Get all the position info required to determine where a category is in terms of the beginning or end of a list
* Useful if you want to add move up/down arrows
*@param int node_id
*@return array
*/
public function getPositionData($node_id) {
$cat_count = 0;
$found_position = null;
$parent_id = $this->getParentID($node_id);
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->parent_id_field . " = '$parent_id' ORDER BY ".$this->position_field;
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$this_id = $row[$this->id_field];
if($node_id == $this_id){
$found_position = $cat_count;
}
$cat_count ++;
}
return array("parent_id"=>$parent_id,"numcats"=>($cat_count-1),"position"=>$found_position);
}//////////////
/**
* Moves a node up or down within the parent list
*@params $node_id, $direction
*@return null
*/
public function repositionSibling($node_id,$direction){
$direction = strtolower($direction);
$parent_id = $this->getParentID($node_id);
// first thing is to clean gaps and set positions for the siblings
$positioncount = 0;
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->parent_id_field . " = '$parent_id' ORDER BY ".$this->position_field . " ASC";
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$this_id = $row[$this->id_field];
$sql = "UPDATE " . $this->dbtablename . " SET " . $this->position_field . "='$positioncount' WHERE " . $this->id_field . " = '$this_id'";
mysql_query($sql);
$positioncount ++;
}
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->parent_id_field . " = '$parent_id' ORDER BY ".$this->position_field;
if($direction == "up") $sql .= " ASC";
else $sql .= " DESC";
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$this_id = $row[$this->id_field];
$this_position = $row[$this->position_field];
if( $this_id == $node_id){
// we need to get the previous id and position
$sql = "UPDATE " . $this->dbtablename . " SET " . $this->position_field . "='".$prev_position."' WHERE " . $this->id_field . " = '$this_id'";
mysql_query($sql);
$sql = "UPDATE " . $this->dbtablename . " SET " . $this->position_field . "='".$this_position."' WHERE " . $this->id_field . " = '$prev_id'";
mysql_query($sql);
}
$prev_id = $this_id;
$prev_position = $this_position;
}
}////////////
/**
* Get all the nodes that have the same parent .. pretty basic
*/
public function getSiblings($node_id) {
$this->setFieldNames();
$siblings = array();
$parent_id = $this->getParentID($node_id);
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->parent_id_field . " = '$parent_id' AND " . $this->id_field . " != '$node_id' ORDER BY ".$this->position_field;
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$thisref = array($this->id_field=>$row[$this->id_field]);
$thisref[$this->parent_id_field] = $row[$this->parent_id_field];
$thisref[$this->position_field] = $row[$this->position_field];
foreach($this->tablefields as $val){
$thisref[$val] = $row[$val];
}
$siblings[] = $thisref;
}
return $siblings;
}//////////////
/**
* A more efficient way to get data from child sets
*/
private function getChildNodesArray($parent, $level=0) {
global $originalparentid;
if($this->initparentid == null){
$this->initparentid = "$parent"; // make it a string so it isn't null 0
}
$this->setFieldNames();
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE " . $this->parent_id_field . " = '$parent' ORDER BY ".$this->position_field;
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
$thisref = &$this->refs[ $row[$this->id_field] ];
$thisref[$this->parent_id_field] = $row[$this->parent_id_field];
$thisref[$this->position_field] = $row[$this->position_field];
foreach($this->tablefields as $val){
$thisref[$val] = $row[$val];
}
$this->getChildNodesArray($row[$this->id_field], $level+1);
if ($this->initparentid == $row[$this->parent_id_field]) { // is this a root node relative to the parent
$this->list[ $row[$this->id_field] ] = &$thisref;
} else {
$this->refs[ $row[$this->parent_id_field] ]['children'][ $row[$this->id_field] ] = &$thisref;
}
}
return $this->list;
}//////////
/**
* Get all the data from a single node
*/
public function getNode($id){
$this->setFieldNames();
$sql = "SELECT * FROM " . $this->dbtablename . " WHERE ".$this->id_field."='".$id."'";
return mysql_fetch_assoc(mysql_query($sql));
}////////////////
/**
* make a simple one dimensional array if ids and filed names
*/
public function getNodeIds($items){
global $nodeids;
if (count($items) && is_array($items)) {
foreach ($items as $node_id=>$catvals) {
$nodeids[] = $node_id;
if (count($catvals['children'])) {
$this->getNodeIds($catvals['children']);
}
}
}
return $nodeids;
}////////////////
/**
* Move a node to a new parent. With Adjacency, this single record update will move all child nodes as well
*/
public function reparentNode($id,$new_parent_id){
if($id != $new_parent_id){
$sql = "UPDATE " . $this->dbtablename . " SET " . $this->parent_id_field . "='$new_parent_id' WHERE ".$this->id_field."='$id'";
mysql_query($sql);
}
}//////////////
/**
* Update a node
*@return null
*/
public function updateNode($id,$data){
$fnames = array();
foreach($data as $key=>$val){
if($key != $this->id_field) $fnames[] = " $key = '$val' ";
}
$sql = "UPDATE " . $this->dbtablename . " SET ";
$sql .= implode(",",$fnames);
$sql .= " WHERE " . $this->id_field . " = '$id'";
mysql_query($sql);
}////////////////
/**
* Add a node
*@return id of new node
*/
public function addNode($parent_id,$data){
$fnames = array();
$fvals = array();
foreach($data as $key=>$val){
$fnames[] = $key;
$fvals[] = $val;
}
$sql = "INSERT INTO " . $this->dbtablename;
$sql .= " (" . $this->parent_id_field . ",";
$sql .= implode(",",$fnames);
$sql .= ") VALUES ('".$parent_id."','";
$sql .= implode("','",$fvals);
$sql .= "')";
mysql_query($sql);
return mysql_insert_id($this->dbConnectionID);
}////////////////
/**
* Add a node next to a sibling
*@params $sibling_id, $data
*@return id of new node
*/
public function addSiblingNode($sibling_id,$data){
$parent_id = $this->getParentID($sibling_id);
return $this->addNode($parent_id,$data);
}////////////////
/**
* Get all ids for child notes that are to be be deleted
*@return array
*/
public function getIndentedNodeIds($items) {
global $group_indent, $indentedarray;
$this->setFieldNames();
if(!is_array($indentedarray)) $indentedarray = array();
if (count($items) && is_array($items)) {
$group_indent ++;
foreach ($items as $node_id=>$catvals) {
$indentedarray[$node_id] = $catvals;
$indentedarray[$node_id]['indent'] = $group_indent;
if (count($catvals['children'])) {
$this->getIndentedNodeIds($catvals['children']);
}
}
$group_indent --;
}
return $indentedarray;
}////////////////////
/**
* Get all ids for child notes that are to be be deleted
*@return array
*/
private function getdeleteids($items,$subloop = false){
if($subloop == false){
$this->deleteids = array();
}
if (count($items) && is_array($items)) {
foreach ($items as $node_id=>$catvals) {
$this->deleteids[] = $node_id;
if (count($catvals['children'])) {
$this->getdeleteids($catvals['children'],true);
}
}
}
return $this->deleteids;
}//////////////////
/**
* DELETE CATEGORY AND all child nodes
*/
public function deleteNode($id){
global $opcmf;
$deleteitems = $this->getChildNodes($id);
$deleteids = $this->getdeleteids($deleteitems);
$deleteids[] = $id;
$sql = "DELETE FROM " . $this->dbtablename . " WHERE " . $this->id_field . "='";
$sql .= implode("' OR " . $this->id_field . "='",$deleteids);
$sql .= "';";
mysql_query($sql);
}//////////////
}
?>