ILIAS Release_3_7_x_branch .rev 46817: classes/class.ilTree.php Source File

Go to the documentation of this file.
00001 <?php
00002 /*
00003         +-----------------------------------------------------------------------------+
00004         | ILIAS open source                                                           |
00005         +-----------------------------------------------------------------------------+
00006         | Copyright (c) 1998-2006 ILIAS open source, University of Cologne            |
00007         |                                                                             |
00008         | This program is free software; you can redistribute it and/or               |
00009         | modify it under the terms of the GNU General Public License                 |
00010         | as published by the Free Software Foundation; either version 2              |
00011         | of the License, or (at your option) any later version.                      |
00012         |                                                                             |
00013         | This program is distributed in the hope that it will be useful,             |
00014         | but WITHOUT ANY WARRANTY; without even the implied warranty of              |
00015         | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               |
00016         | GNU General Public License for more details.                                |
00017         |                                                                             |
00018         | You should have received a copy of the GNU General Public License           |
00019         | along with this program; if not, write to the Free Software                 |
00020         | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. |
00021         +-----------------------------------------------------------------------------+
00022 */
00023 
00024 define("IL_LAST_NODE", -2);
00025 define("IL_FIRST_NODE", -1);
00026 
00041 class ilTree
00042 {
00048         var $ilias;
00049 
00050 
00056         var $log;
00057 
00063         var $root_id;
00064 
00070         var $tree_id;
00071 
00077         var $table_tree;
00078 
00084         var $table_obj_data;
00085 
00091         var $table_obj_reference;
00092 
00098         var $ref_pk;
00099 
00105         var $obj_pk;
00106 
00112         var $tree_pk;
00113 
00138         var $gap;
00139 
00146         function ilTree($a_tree_id, $a_root_id = 0)
00147         {
00148                 global $ilDB,$ilErr,$ilias,$ilLog;
00149 
00150                 // set db & error handler
00151                 (isset($ilDB)) ? $this->ilDB =& $ilDB : $this->ilDB =& $ilias->db;
00152 
00153                 if (!isset($ilErr))
00154                 {
00155                         $ilErr = new ilErrorHandling();
00156                         $ilErr->setErrorHandling(PEAR_ERROR_CALLBACK,array($ilErr,'errorHandler'));
00157                 }
00158                 else
00159                 {
00160                         $this->ilErr =& $ilErr;
00161                 }
00162 
00163                 $this->lang_code = "en";
00164                 
00165                 if (!isset($a_tree_id) or (func_num_args() == 0) )
00166                 {
00167                         $this->ilErr->raiseError(get_class($this)."::Constructor(): No tree_id given!",$this->ilErr->WARNING);
00168                 }
00169 
00170                 if (func_num_args() > 2)
00171                 {
00172                         $this->ilErr->raiseError(get_class($this)."::Constructor(): Wrong parameter count!",$this->ilErr->WARNING);
00173                 }
00174 
00175                 // CREATE LOGGER INSTANCE
00176                 $this->log =& $ilLog;
00177 
00178                 //init variables
00179                 if (empty($a_root_id))
00180                 {
00181                         $a_root_id = ROOT_FOLDER_ID;
00182                 }
00183 
00184                 $this->tree_id            = $a_tree_id;
00185                 $this->root_id            = $a_root_id;
00186                 $this->table_tree     = 'tree';
00187                 $this->table_obj_data = 'object_data';
00188                 $this->table_obj_reference = 'object_reference';
00189                 $this->ref_pk = 'ref_id';
00190                 $this->obj_pk = 'obj_id';
00191                 $this->tree_pk = 'tree';
00192 
00193                 // By default, we create gaps in the tree sequence numbering for 50 nodes 
00194                 $this->gap = 50;
00195         }
00196         
00201         function initLangCode()
00202         {
00203                 global $ilUser;
00204                 
00205                 // lang_code is only required in $this->fetchnodedata
00206                 if (!is_object($ilUser))
00207                 {
00208                         $this->lang_code = "en";
00209                 }
00210                 else
00211                 {
00212                         $this->lang_code = $ilUser->getCurrentLanguage();
00213                 }
00214         }
00215 
00216 
00231         function setTableNames($a_table_tree,$a_table_obj_data,$a_table_obj_reference = "")
00232         {
00233                 if (!isset($a_table_tree) or !isset($a_table_obj_data))
00234                 {
00235                         $this->ilErr->raiseError(get_class($this)."::setTableNames(): Missing parameter! ".
00236                                                                 "tree table: ".$a_table_tree." object data table: ".$a_table_obj_data,$this->ilErr->WARNING);
00237                 }
00238 
00239                 $this->table_tree = $a_table_tree;
00240                 $this->table_obj_data = $a_table_obj_data;
00241                 $this->table_obj_reference = $a_table_obj_reference;
00242 
00243                 return true;
00244         }
00245 
00252         function setReferenceTablePK($a_column_name)
00253         {
00254                 if (!isset($a_column_name))
00255                 {
00256                         $this->ilErr->raiseError(get_class($this)."::setReferenceTablePK(): No column name given!",$this->ilErr->WARNING);
00257                 }
00258 
00259                 $this->ref_pk = $a_column_name;
00260                 return true;
00261         }
00262 
00269         function setObjectTablePK($a_column_name)
00270         {
00271                 if (!isset($a_column_name))
00272                 {
00273                         $this->ilErr->raiseError(get_class($this)."::setObjectTablePK(): No column name given!",$this->ilErr->WARNING);
00274                 }
00275 
00276                 $this->obj_pk = $a_column_name;
00277                 return true;
00278         }
00279 
00286         function setTreeTablePK($a_column_name)
00287         {
00288                 if (!isset($a_column_name))
00289                 {
00290                         $this->ilErr->raiseError(get_class($this)."::setTreeTablePK(): No column name given!",$this->ilErr->WARNING);
00291                 }
00292 
00293                 $this->tree_pk = $a_column_name;
00294                 return true;
00295         }
00296 
00302         function buildJoin()
00303         {
00304                 if ($this->table_obj_reference)
00305                 {
00306                         return "LEFT JOIN ".$this->table_obj_reference." ON ".$this->table_tree.".child=".$this->table_obj_reference.".".$this->ref_pk." ".
00307                                    "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
00308                 }
00309                 else
00310                 {
00311                         return "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_tree.".child=".$this->table_obj_data.".".$this->obj_pk." ";
00312                 }
00313         }
00314 
00323         function getChilds($a_node_id, $a_order = "", $a_direction = "ASC")
00324         {
00325                 global $ilBench;
00326                 
00327                 if (!isset($a_node_id))
00328                 {
00329                         $message = get_class($this)."::getChilds(): No node_id given!";
00330                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00331                 }
00332 
00333                 // init childs
00334                 $childs = array();
00335 
00336                 // number of childs
00337                 $count = 0;
00338 
00339                 // init order_clause
00340                 $order_clause = "";
00341 
00342                 // set order_clause if sort order parameter is given
00343                 if (!empty($a_order))
00344                 {
00345                         $order_clause = "ORDER BY ".$a_order." ".$a_direction;
00346                 }
00347                 else
00348                 {
00349                         $order_clause = "ORDER BY ".$this->table_tree.".lft";
00350                 }
00351 
00352         //666
00353                 $q = "SELECT * FROM ".$this->table_tree." ".
00354                          $this->buildJoin().
00355                          "WHERE parent = ".$this->ilDB->quote($a_node_id)." ".
00356                          "AND ".$this->table_tree.".".$this->tree_pk." = ".$this->ilDB->quote($this->tree_id)." ".
00357                          $order_clause;
00358 
00359                 //$ilBench->start("Tree", "getChilds_Query");
00360                 $r = $this->ilDB->query($q);
00361                 //$ilBench->stop("Tree", "getChilds_Query");
00362 
00363                 $count = $r->numRows();
00364 
00365 
00366                 if ($count > 0)
00367                 {
00368                         //$ilBench->start("Tree", "getChilds_fetchNodeData");
00369                         while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00370                         {
00371                                 $childs[] = $this->fetchNodeData($row);
00372                         }
00373                         //$ilBench->stop("Tree", "getChilds_fetchNodeData");
00374 
00375                         // mark the last child node (important for display)
00376                         $childs[$count - 1]["last"] = true;
00377                         return $childs;
00378                 }
00379                 else
00380                 {
00381                         return $childs;
00382                 }
00383         }
00384 
00394         function getFilteredChilds($a_filter,$a_node,$a_order = "",$a_direction = "ASC")
00395         {
00396                 $childs = $this->getChilds($a_node,$a_order,$a_direction);
00397 
00398                 foreach($childs as $child)
00399                 {
00400                         if(!in_array($child["type"],$a_filter))
00401                         {
00402                                 $filtered[] = $child;
00403                         }
00404                 }
00405                 return $filtered ? $filtered : array();
00406         }
00407 
00408 
00416         function getChildsByType($a_node_id,$a_type)
00417         {
00418                 if (!isset($a_node_id) or !isset($a_type))
00419                 {
00420                         $message = get_class($this)."::getChildsByType(): Missing parameter! node_id:".$a_node_id." type:".$a_type;
00421                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00422                 }
00423 
00424                 // init childs
00425                 $childs = array();
00426 
00427                 $q = "SELECT * FROM ".$this->table_tree." ".
00428                          $this->buildJoin().
00429                          "WHERE parent = '".$a_node_id."' ".
00430                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."' ".
00431                          "AND ".$this->table_obj_data.".type='".$a_type."' ".
00432                          "ORDER BY ".$this->table_tree.".lft";
00433                 $r = $this->ilDB->query($q);
00434 
00435                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00436                 {
00437                         $childs[] = $this->fetchNodeData($row);
00438                 }
00439 
00440 
00441                 return $childs;
00442         }
00443 
00444 
00452         function insertNode($a_node_id, $a_parent_id, $a_pos = IL_LAST_NODE, $a_reset_deletion_date = false)
00453         {
00454 //echo "+$a_node_id+$a_parent_id+";
00455                 // CHECK node_id and parent_id > 0 if in main tree
00456                 if($this->__isMainTree())
00457                 {
00458                         if($a_node_id <= 1 or $a_parent_id <= 0)
00459                         {
00460                                 $message = sprintf('%s::insertNode(): Invalid parameters! $a_node_id: %s $a_parent_id: %s',
00461                                                                    get_class($this),
00462                                                                    $a_node_id,
00463                                                                    $a_parent_id);
00464                                 $this->log->write($message,$this->log->FATAL);
00465                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00466                         }
00467                 }
00468 
00469 
00470                 if (!isset($a_node_id) or !isset($a_parent_id))
00471                 {
00472                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Missing parameter! ".
00473                                 "node_id: ".$a_node_id." parent_id: ".$a_parent_id,$this->ilErr->WARNING);
00474                 }
00475                 if ($this->isInTree($a_node_id))
00476                 {
00477                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Node ".$a_node_id." already in tree ".
00478                                                                          $this->table_tree."!",$this->ilErr->WARNING);
00479                 }
00480 
00481                 //
00482                 switch ($a_pos)
00483                 {
00484                         case IL_FIRST_NODE:
00485 
00486                                 if($this->__isMainTree())
00487                                 {
00488                                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00489                                 }
00490 
00491                                 // get left value of parent
00492                                 $q = "SELECT * FROM ".$this->table_tree." ".
00493                                         "WHERE child = '".$a_parent_id."' ".
00494                                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
00495                                 $res = $this->ilDB->query($q);
00496                                 $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00497 
00498                                 if ($r->parent == NULL)
00499                                 {
00500                                         if($this->__isMainTree())
00501                                         {
00502                                                 ilDBx::_unlockTables();
00503                                         }
00504                                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".$a_parent_id." not found in ".
00505                                                                                          $this->table_tree."!",$this->ilErr->WARNING);
00506                                 }
00507 
00508                                 $left = $r->lft;
00509                                 $lft = $left + 1;
00510                                 $rgt = $left + 2;
00511 
00512                                 // spread tree
00513                                 $q = "UPDATE ".$this->table_tree." SET ".
00514                                         "lft = CASE ".
00515                                         "WHEN lft > ".$left." ".
00516                                         "THEN lft + 2 ".
00517                                         "ELSE lft ".
00518                                         "END, ".
00519                                         "rgt = CASE ".
00520                                         "WHEN rgt > ".$left." ".
00521                                         "THEN rgt + 2 ".
00522                                         "ELSE rgt ".
00523                                         "END ".
00524                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00525                                 $this->ilDB->query($q);
00526                                 break;
00527 
00528                         case IL_LAST_NODE:
00529                                 // Special treatment for trees with gaps
00530                                 if ($this->gap > 0)
00531                                 {
00532                                         if($this->__isMainTree())
00533                                         {
00534                                                 ilDBx::_lockTables(array('tree' => 'WRITE'));
00535                                         }
00536 
00537                                         // get lft and rgt value of parent
00538                                         $q = 'SELECT rgt,lft,parent FROM '.$this->table_tree.' '.
00539                                                 'WHERE child = '.$a_parent_id.' '.
00540                                                 'AND '.$this->tree_pk.' = '.$this->tree_id;
00541                                         $res = $this->ilDB->query($q);
00542                                         $r = $res->fetchRow(DB_FETCHMODE_ASSOC);
00543 
00544                                                                         
00545                                         if ($r['parent'] == NULL)
00546                                         {
00547                                                 if($this->__isMainTree())
00548                                                 {
00549                                                         ilDBx::_unlockTables();
00550                                                 }
00551                                                 $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
00552                                                                                                 $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
00553                                         }
00554                                         $parentRgt = $r['rgt'];
00555                                         $parentLft = $r['lft'];
00556                                         
00557                                         // Get the available space, without taking children into account yet
00558                                         $availableSpace = $parentRgt - $parentLft;
00559                                         if ($availableSpace < 2)
00560                                         {
00561                                                 // If there is not enough space between parent lft and rgt, we don't need
00562                                                 // to look any further, because we must spread the tree.
00563                                                 $lft = $parentRgt;
00564                                         }
00565                                         else
00566                                         {
00567                                                 // If there is space between parent lft and rgt, we need to check
00568                                                 // whether there is space left between the rightmost child of the
00569                                                 // parent and parent rgt.
00570                                                 $q = 'SELECT MAX(rgt) AS max_rgt FROM '.$this->table_tree.' '.
00571                                                         'WHERE parent = '.$a_parent_id.' '.
00572                                                         'AND '.$this->tree_pk.' = '.$this->tree_id;
00573                                                 $res = $this->ilDB->query($q);
00574                                                 $r = $res->fetchRow(DB_FETCHMODE_ASSOC);
00575                                                 if (isset($r['max_rgt']))
00576                                                 {
00577                                                         // If the parent has children, we compute the available space
00578                                                         // between rgt of the rightmost child and parent rgt.
00579                                                         $availableSpace = $parentRgt - $r['max_rgt'];
00580                                                         $lft = $r['max_rgt'] + 1;
00581                                                 }
00582                                                 else
00583                                                 {
00584                                                         // If the parent has no children, we know now, that we can
00585                                                         // add the new node at parent lft + 1 without having to spread
00586                                                         // the tree.
00587                                                         $lft = $parentLft + 1;
00588                                                 }
00589                                         }
00590                                         $rgt = $lft + 1;
00591                                         
00592 
00593                                         // spread tree if there is not enough space to insert the new node
00594                                         if ($availableSpace < 2)
00595                                         {
00596                                                 $this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
00597                                                 $q = "UPDATE ".$this->table_tree." SET ".
00598                                                         "lft = CASE ".
00599                                                         "WHEN lft > ".$parentRgt." ".
00600                                                         "THEN lft + ".(2 + $this->gap * 2).' '.
00601                                                         "ELSE lft ".
00602                                                         "END, ".
00603                                                         "rgt = CASE ".
00604                                                         "WHEN rgt >= ".$parentRgt." ".
00605                                                         "THEN rgt + ".(2 + $this->gap * 2).' '.
00606                                                         "ELSE rgt ".
00607                                                         "END ".
00608                                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00609                                                 $this->ilDB->query($q);
00610                                         }
00611                                         else
00612                                         {
00613                                                 $this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') reusing gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.' for node '.$a_node_id.' '.$lft.'..'.$rgt);
00614                                         }                               
00615                                 }
00616                                 // Treatment for trees without gaps
00617                                 else 
00618                                 {
00619                                         if($this->__isMainTree())
00620                                         {
00621                                                 ilDBx::_lockTables(array('tree' => 'WRITE'));
00622                                         }
00623 
00624                                         // get right value of parent
00625                                         $q = "SELECT * FROM ".$this->table_tree." ".
00626                                                 "WHERE child = '".$a_parent_id."' ".
00627                                                 "AND ".$this->tree_pk." = '".$this->tree_id."'";
00628                                         $res = $this->ilDB->query($q);
00629                                         $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00630 
00631                                         if ($r->parent == NULL)
00632                                         {
00633                                                 if($this->__isMainTree())
00634                                                 {
00635                                                         ilDBx::_unlockTables();
00636                                                 }
00637                                                 $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
00638                                                                                                  $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
00639                                         }
00640 
00641                                         $right = $r->rgt;
00642                                         $lft = $right;
00643                                         $rgt = $right + 1;
00644 
00645                                         // spread tree
00646                                         $q = "UPDATE ".$this->table_tree." SET ".
00647                                                 "lft = CASE ".
00648                                                 "WHEN lft > ".$right." ".
00649                                                 "THEN lft + 2 ".
00650                                                 "ELSE lft ".
00651                                                 "END, ".
00652                                                 "rgt = CASE ".
00653                                                 "WHEN rgt >= ".$right." ".
00654                                                 "THEN rgt + 2 ".
00655                                                 "ELSE rgt ".
00656                                                 "END ".
00657                                                 "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00658                                         $this->ilDB->query($q);
00659                                 }
00660 
00661                                 break;
00662 
00663                         default:
00664 
00665                                 // this code shouldn't be executed
00666                                 if($this->__isMainTree())
00667                                 {
00668                                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00669                                 }
00670 
00671                                 // get right value of preceeding child
00672                                 $q = "SELECT * FROM ".$this->table_tree." ".
00673                                         "WHERE child = '".$a_pos."' ".
00674                                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
00675                                 $res = $this->ilDB->query($q);
00676                                 $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00677 
00678                                 // crosscheck parents of sibling and new node (must be identical)
00679                                 if ($r->parent != $a_parent_id)
00680                                 {
00681                                         if($this->__isMainTree())
00682                                         {
00683                                                 ilDBx::_unlockTables();
00684                                         }
00685                                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Parents mismatch! ".
00686                                                 "new node parent: ".$a_parent_id." sibling parent: ".$r->parent,$this->ilErr->WARNING);
00687                                 }
00688 
00689                                 $right = $r->rgt;
00690                                 $lft = $right + 1;
00691                                 $rgt = $right + 2;
00692 
00693                                 // update lft/rgt values
00694                                 $q = "UPDATE ".$this->table_tree." SET ".
00695                                         "lft = CASE ".
00696                                         "WHEN lft > ".$right." ".
00697                                         "THEN lft + 2 ".
00698                                         "ELSE lft ".
00699                                         "END, ".
00700                                         "rgt = CASE ".
00701                                         "WHEN rgt > ".$right." ".
00702                                         "THEN rgt + 2 ".
00703                                         "ELSE rgt ".
00704                                         "END ".
00705                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00706                                 $this->ilDB->query($q);
00707                                 break;
00708 
00709                 }
00710 
00711                 // get depth
00712                 $depth = $this->getDepth($a_parent_id) + 1;
00713 
00714                 // insert node
00715                 $this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') inserting node:'.$a_node_id.' parent:'.$a_parent_id." ".$lft."..".$rgt." depth:".$depth);
00716                 $q = "INSERT INTO ".$this->table_tree." (".$this->tree_pk.",child,parent,lft,rgt,depth) ".
00717                          "VALUES ".
00718                          "('".$this->tree_id."','".$a_node_id."','".$a_parent_id."','".$lft."','".$rgt."','".$depth."')";
00719 
00720                 $this->ilDB->query($q);
00721 
00722                 // Finally unlock tables
00723                 if($this->__isMainTree())
00724                 {
00725                         ilDBx::_unlockTables();
00726                 }
00727                 
00728                 // reset deletion date
00729                 if ($a_reset_deletion_date)
00730                 {
00731                         ilObject::_resetDeletedDate($a_node_id);
00732                 }
00733         }
00734 
00743         function getSubTree($a_node,$a_with_data = true, $a_type = "")
00744         {
00745                 if (!is_array($a_node))
00746                 {
00747                         $this->ilErr->raiseError(get_class($this)."::getSubTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
00748                 }
00749 
00750                 if($a_node['lft'] < 1 or $a_node['rgt'] < 2)
00751                 {
00752                         $message = sprintf('%s::getSubTree(): Invalid node given! $a_node["lft"]: %s $a_node["rgt"]: %s',
00753                                                                    get_class($this),
00754                                                                    $a_node['lft'],
00755                                                                    $a_node['rgt']);
00756 
00757                         $this->log->write($message,$this->log->FATAL);
00758 
00759                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00760                 }
00761 
00762             $subtree = array();
00763                 
00764                 $type_str = "";
00765                 if ($a_type != "")
00766                 {
00767                         $type_str = "AND ".$this->table_obj_data.".type='".$a_type."' ";
00768                 }
00769 
00770                 $q = "SELECT * FROM ".$this->table_tree." ".
00771                          $this->buildJoin().
00772                          "WHERE ".$this->table_tree.".lft BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00773                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."' ".
00774                          $type_str.
00775                          "ORDER BY ".$this->table_tree.".lft";
00776 
00777                 $r = $this->ilDB->query($q);
00778 
00779                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00780                 {
00781                         if($a_with_data)
00782                         {
00783                                 $subtree[] = $this->fetchNodeData($row);
00784                         }
00785                         else
00786                         {
00787                                 $subtree[] = $row['child_id'];
00788                         }
00789                 }
00790 
00791                 return $subtree ? $subtree : array();
00792         }
00793 
00802         function getSubTreeTypes($a_node,$a_filter = 0)
00803         {
00804                 $a_filter = $a_filter ? $a_filter : array();
00805 
00806                 foreach($this->getSubtree($this->getNodeData($a_node)) as $node)
00807                 {
00808                         if(in_array($node["type"],$a_filter))
00809                         {
00810                                 continue;
00811                         }
00812                         $types["$node[type]"] = $node["type"];
00813                 }
00814                 return $types ? $types : array();
00815         }
00816 
00822         function deleteTree($a_node)
00823         {
00824                 if (!is_array($a_node))
00825                 {
00826                         $this->ilErr->raiseError(get_class($this)."::deleteTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
00827                 }
00828                 if($this->__isMainTree() and $a_node[$this->tree_pk] === 1)
00829                 {
00830                         if($a_node['lft'] <= 1 or $a_node['rgt'] <= 2)
00831                         {
00832                                 $message = sprintf('%s::deleteTree(): Invalid parameters given: $a_node["lft"]: %s, $a_node["rgt"] %s',
00833                                                                    get_class($this),
00834                                                                    $a_node['lft'],
00835                                                                    $a_node['rgt']);
00836 
00837                                 $this->log->write($message,$this->log->FATAL);
00838                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00839                         }
00840                         else if(!$this->__checkDelete($a_node))
00841                         {
00842                                 $message = sprintf('%s::deleteTree(): Check delete failed: $a_node["lft"]: %s, $a_node["rgt"] %s',
00843                                                                    get_class($this),
00844                                                                    $a_node['lft'],
00845                                                                    $a_node['rgt']);
00846                                 $this->log->write($message,$this->log->FATAL);
00847                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00848                         }
00849 
00850                 }
00851                 $diff = $a_node["rgt"] - $a_node["lft"] + 1;
00852 
00853 
00854                 // LOCKED ###########################################################
00855                 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
00856                 if($this->__isMainTree())
00857                 {
00858                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00859                 }
00860 
00861                 $query = "SELECT * FROM ".$this->table_tree." ".
00862                         "WHERE child = '".$a_node['child']."' ".
00863                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00864 
00865                 $res = $this->ilDB->query($query);
00866                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
00867                 {
00868                         $a_node['lft'] = $row->lft;
00869                         $a_node['rgt'] = $row->rgt;
00870                         $diff = $a_node["rgt"] - $a_node["lft"] + 1;
00871                 }
00872 
00873                 // delete subtree
00874                 $q = "DELETE FROM ".$this->table_tree." ".
00875                         "WHERE lft BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00876                         "AND rgt BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00877                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00878                 $this->ilDB->query($q);
00879 
00880                 // We only close the gap, if the resulting gap will be larger then the gap value 
00881                 if ($a_node['rgt'] - $a_node['lft'] >= $this->gap * 2)
00882                 {
00883                         $this->log->write('ilTree.deleteTree('.$a_node['child'].') closing gap at '.$a_node['lft'].'...'.$a_node['rgt']);
00884                         // close gaps
00885                         $q = "UPDATE ".$this->table_tree." SET ".
00886                                  "lft = CASE ".
00887                                  "WHEN lft > '".$a_node["lft"]." '".
00888                                  "THEN lft - '".$diff." '".
00889                                  "ELSE lft ".
00890                                  "END, ".
00891                                  "rgt = CASE ".
00892                                  "WHEN rgt > '".$a_node["lft"]." '".
00893                                  "THEN rgt - '".$diff." '".
00894                                  "ELSE rgt ".
00895                                  "END ".
00896                                  "WHERE ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00897                         $this->ilDB->query($q);
00898                 }
00899                 else
00900                 {
00901                         $this->log->write('ilTree.deleteTree('.$a_node['child'].') leaving gap open '.$a_node['lft'].'...'.$a_node['rgt']);
00902                 }
00903 
00904                 if($this->__isMainTree())
00905                 {
00906                         ilDBx::_unlockTables();
00907                 }
00908                 // LOCKED ###########################################################
00909         }
00910 
00921         function getPathFull($a_endnode_id, $a_startnode_id = 0)
00922         {
00923                 $pathIds =& $this->getPathId($a_endnode_id, $a_startnode_id);
00924                 $dataPath = array();
00925                 foreach ($pathIds as $id) {
00926                         $dataPath[] = $this->getNodeData($id);
00927                 }
00928 
00929                 return $dataPath;
00930         }
00939         function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
00940         {
00941                 // The nested sets algorithm is very easy to implement.
00942                 // Unfortunately it always does a full table space scan to retrieve the path
00943                 // regardless whether indices on lft and rgt are set or not.
00944                 // (At least, this is what happens on MySQL 4.1).
00945                 // This algorithms performs well for small trees which are deeply nested.
00946                 
00947                 
00948                 if (!isset($a_endnode_id))
00949                 {
00950                         $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
00951                 }
00952                 
00953                 $q = "SELECT T2.child ".
00954                         "FROM ".$this->table_tree." AS T1, ".$this->table_tree." AS T2 ".
00955                         "WHERE T1.child = '".$a_endnode_id."' ".
00956                         "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
00957                         "AND T1.".$this->tree_pk." = '".$this->tree_id." '".
00958                         "AND T2.".$this->tree_pk." = '".$this->tree_id." '".
00959                         "ORDER BY T2.depth";
00960 
00961                 $r = $this->ilDB->query($q);
00962                 $takeId = $a_startnode_id == 0;
00963                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00964                 {
00965                         if ($takeId || $row['child'] == $a_startnode_id)
00966                         {
00967                                 $takeId = true;
00968                                 $pathIds[] = $row['child'];
00969                         }
00970                 }
00971                 return $pathIds;
00972 
00973         }
00982         function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
00983         {
00984                 // The adjacency map algorithm is harder to implement than the nested sets algorithm.
00985                 // This algorithms performs an index search for each of the path element.
00986                 // This algorithms performs well for large trees which are not deeply nested.
00987 
00988                 // The $takeId variable is used, to determine if a given id shall be included in the path
00989                 $takeId = $a_startnode_id == 0;
00990                 
00991                 if (!isset($a_endnode_id))
00992                 {
00993                         $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
00994                 }
00995                 
00996                 global $log, $ilDB;
00997                 
00998                 // Determine the depth of the endnode, and fetch its parent field also.
00999                 $q = 'SELECT t.depth,t.parent '.
01000                         'FROM '.$this->table_tree.' AS t '.
01001                         'WHERE child='.$this->ilDB->quote($a_endnode_id).' '.
01002                         'AND '.$this->tree_pk.' = '.$this->tree_id.' '.
01003                         'LIMIT 1';
01004                         //$this->writelog('getIdsUsingAdjacencyMap q='.$q);
01005                 $r = $this->ilDB->query($q);
01006                 
01007                 if ($r->numRows() == 0)
01008                 {
01009                         return array();
01010                 }
01011                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01012                 $nodeDepth = $row['depth'];
01013                 $parentId = $row['parent'];
01014                         //$this->writelog('getIdsUsingAdjacencyMap depth='.$nodeDepth);
01015 
01016                 // Fetch the node ids. For shallow depths we can fill in the id's directly.     
01017                 $pathIds = array();
01018                 if ($nodeDepth == 1)
01019                 {
01020                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01021                                 if ($takeId) $pathIds[] = $a_endnode_id;
01022                 }
01023                 else if ($nodeDepth == 2)
01024                 {
01025                                 $takeId = $takeId || $parentId == $a_startnode_id;
01026                                 if ($takeId) $pathIds[] = $parentId;
01027                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01028                                 if ($takeId) $pathIds[] = $a_endnode_id;
01029                 }
01030                 else if ($nodeDepth == 3)
01031                 {
01032                                 $takeId = $takeId || $this->root_id == $a_startnode_id;
01033                                 if ($takeId) $pathIds[] = $this->root_id;
01034                                 $takeId = $takeId || $parentId == $a_startnode_id;
01035                                 if ($takeId) $pathIds[] = $parentId;
01036                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01037                                 if ($takeId) $pathIds[] = $a_endnode_id;
01038                 }
01039                 else if ($nodeDepth < 10)
01040                 {
01041                         // The following code construct nested self-joins
01042                         // Since we already know the root-id of the tree and
01043                         // we also know the id and parent id of the current node,
01044                         // we only need to perform $nodeDepth - 3 self-joins. 
01045                         // We can further reduce the number of self-joins by 1
01046                         // by taking into account, that each row in table tree
01047                         // contains the id of itself and of its parent.
01048                         $qSelect = 't1.child as c0';
01049                         $qJoin = '';
01050                         for ($i = 1; $i < $nodeDepth - 2; $i++)
01051                         {
01052                                 $qSelect .= ', t'.$i.'.parent as c'.$i;
01053                                 $qJoin .= ' JOIN '.$this->table_tree.' AS t'.$i.' ON '.
01054                                                         't'.$i.'.child=t'.($i - 1).'.parent AND '.
01055                                                         't'.$i.'.'.$this->tree_pk.' = '.$this->tree_id;
01056                         }
01057                         $q = 'SELECT '.$qSelect.' '.
01058                                 'FROM '.$this->table_tree.' AS t0 '.$qJoin.' '.
01059                                 'WHERE t0.'.$this->tree_pk.' = '.$this->tree_id.' '.
01060                                 'AND t0.child='.$parentId.' '.
01061                                 'LIMIT 1';
01062                         $r = $this->ilDB->query($q);
01063                         if ($r->numRows() == 0)
01064                         {
01065                                 return array();
01066                         }
01067                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01068                         
01069                         $takeId = $takeId || $this->root_id == $a_startnode_id;                 
01070                         if ($takeId) $pathIds[] = $this->root_id;
01071                         for ($i = $nodeDepth - 4; $i >=0; $i--)
01072                         {
01073                                 $takeId = $takeId || $row['c'.$i] == $a_startnode_id;
01074                                 if ($takeId) $pathIds[] = $row['c'.$i];
01075                         }
01076                         $takeId = $takeId || $parentId == $a_startnode_id;
01077                         if ($takeId) $pathIds[] = $parentId;
01078                         $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01079                         if ($takeId) $pathIds[] = $a_endnode_id;
01080                 }
01081                 else
01082                 {
01083                         return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
01084                 }
01085                 
01086                 return $pathIds;
01087         }
01088 
01097         function getPathId($a_endnode_id, $a_startnode_id = 0)
01098         {
01099                 $pathIds =& $this->getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id);
01100                 return $pathIds;
01101         }
01102 
01109         function checkTree()
01110         {
01111                 $q = "SELECT lft,rgt FROM ".$this->table_tree." ".
01112                          "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
01113 
01114                 $r = $this->ilDB->query($q);
01115 
01116                 while ($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01117                 {
01118                         $lft[] = $row->lft;
01119                         $rgt[] = $row->rgt;
01120                 }
01121 
01122                 $all = array_merge($lft,$rgt);
01123                 $uni = array_unique($all);
01124 
01125                 if (count($all) != count($uni))
01126                 {
01127                         $message = sprintf('%s::checkTree(): Tree is corrupted!',
01128                                                            get_class($this));
01129 
01130                         $this->log->write($message,$this->log->FATAL);
01131                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01132                 }
01133 
01134                 return true;
01135         }
01136 
01140         function checkTreeChilds($a_no_zero_child = true)
01141         {
01142                 $q = "SELECT * FROM ".$this->table_tree." ".
01143                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01144                          "ORDER BY lft";
01145                 $r1 = $this->ilDB->query($q);
01146                 while ($row = $r1->fetchRow(DB_FETCHMODE_ASSOC))
01147                 {
01148 //echo "tree:".$row[$this->tree_pk].":lft:".$row["lft"].":rgt:".$row["rgt"].":child:".$row["child"].":<br>";
01149                         if (($row["child"] == 0) && $a_no_zero_child)
01150                         {
01151                                 $this->ilErr->raiseError(get_class($this)."::checkTreeChilds(): Tree contains child with ID 0!",$this->ilErr->WARNING);
01152                         }
01153 
01154                         if ($this->table_obj_reference)
01155                         {
01156                                 // get object reference data
01157                                 $q = "SELECT * FROM ".$this->table_obj_reference." WHERE ".$this->ref_pk."='".$row["child"]."'";
01158                                 $r2 = $this->ilDB->query($q);
01159 //echo "num_childs:".$r2->numRows().":<br>";
01160                                 if ($r2->numRows() == 0)
01161                                 {
01162                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No Object-to-Reference entry found for ID ".
01163                                                 $row["child"]."!",$this->ilErr->WARNING);
01164                                 }
01165                                 if ($r2->numRows() > 1)
01166                                 {
01167                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More Object-to-Reference entries found for ID ".
01168                                                 $row["child"]."!",$this->ilErr->WARNING);
01169                                 }
01170 
01171                                 // get object data
01172                                 $obj_ref = $r2->fetchRow(DB_FETCHMODE_ASSOC);
01173 
01174                                 $q = "SELECT * FROM ".$this->table_obj_data." WHERE ".$this->obj_pk."='".$obj_ref[$this->obj_pk]."'";
01175                                 $r3 = $this->ilDB->query($q);
01176                                 if ($r3->numRows() == 0)
01177                                 {
01178                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
01179                                                 $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
01180                                 }
01181                                 if ($r3->numRows() > 1)
01182                                 {
01183                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
01184                                                 $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
01185                                 }
01186 
01187                         }
01188                         else
01189                         {
01190                                 // get only object data
01191                                 $q = "SELECT * FROM ".$this->table_obj_data." WHERE ".$this->obj_pk."='".$row["child"]."'";
01192                                 $r2 = $this->ilDB->query($q);
01193 //echo "num_childs:".$r2->numRows().":<br>";
01194                                 if ($r2->numRows() == 0)
01195                                 {
01196                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
01197                                                 $row["child"]."!",$this->ilErr->WARNING);
01198                                 }
01199                                 if ($r2->numRows() > 1)
01200                                 {
01201                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
01202                                                 $row["child"]."!",$this->ilErr->WARNING);
01203                                 }
01204                         }
01205                 }
01206 
01207                 return true;
01208         }
01209 
01215         function getMaximumDepth()
01216         {
01217                 $q = "SELECT MAX(depth) FROM ".$this->table_tree;
01218                 $r = $this->ilDB->query($q);
01219 
01220                 $row = $r->fetchRow();
01221 
01222                 return $row[0];
01223         }
01224 
01231         function getDepth($a_node_id)
01232         {
01233                 if ($a_node_id)
01234                 {
01235                         $q = "SELECT depth FROM ".$this->table_tree." ".
01236                                  "WHERE child = '".$a_node_id."' ".
01237                                  "AND ".$this->tree_pk." = '".$this->tree_id."'";
01238 
01239                         $res = $this->ilDB->query($q);
01240                         $row = $res->fetchRow(DB_FETCHMODE_OBJECT);
01241 
01242                         return $row->depth;
01243                 }
01244                 else
01245                 {
01246                         return 1;
01247                 }
01248         }
01249 
01250 
01258         function getNodeData($a_node_id)
01259         {
01260                 if (!isset($a_node_id))
01261                 {
01262                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01263                 }
01264                 if($this->__isMainTree())
01265                 {
01266                         if($a_node_id < 1)
01267                         {
01268                                 $message = sprintf('%s::getNodeData(): No valid parameter given! $a_node_id: %s',
01269                                                                    get_class($this),
01270                                                                    $a_node_id);
01271 
01272                                 $this->log->write($message,$this->log->FATAL);
01273                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01274                         }
01275                 }
01276 
01277                 $q = "SELECT * FROM ".$this->table_tree." ".
01278                          $this->buildJoin().
01279                          "WHERE ".$this->table_tree.".child = ".$this->ilDB->quote($a_node_id)." ".
01280                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01281                 $r = $this->ilDB->query($q);
01282                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01283                 $row[$this->tree_pk] = $this->tree_id;
01284 
01285                 return $this->fetchNodeData($row);
01286         }
01287 
01295         function fetchNodeData($a_row)
01296         {
01297                 global $objDefinition, $lng, $ilBench;
01298 
01299                 //$ilBench->start("Tree", "fetchNodeData_getRow");
01300                 $data = $a_row;
01301                 $data["desc"] = $a_row["description"];  // for compability
01302                 //$ilBench->stop("Tree", "fetchNodeData_getRow");
01303 
01304                 // multilingual support systemobjects (sys) & categories (db)
01305                 //$ilBench->start("Tree", "fetchNodeData_readDefinition");
01306                 if (is_object($objDefinition))
01307                 {
01308                         $translation_type = $objDefinition->getTranslationType($data["type"]);
01309                 }
01310                 //$ilBench->stop("Tree", "fetchNodeData_readDefinition");
01311 
01312                 if ($translation_type == "sys")
01313                 {
01314                         //$ilBench->start("Tree", "fetchNodeData_getLangData");
01315                         if ($data["type"] == "rolf" and $data["obj_id"] != ROLE_FOLDER_ID)
01316                         {
01317                                 $data["description"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
01318                                 $data["desc"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
01319                                 $data["title"] = $lng->txt("obj_".$data["type"]."_local");
01320                         }
01321                         else
01322                         {
01323                                 $data["title"] = $lng->txt("obj_".$data["type"]);
01324                                 $data["description"] = $lng->txt("obj_".$data["type"]."_desc");
01325                                 $data["desc"] = $lng->txt("obj_".$data["type"]."_desc");
01326                         }
01327                         //$ilBench->stop("Tree", "fetchNodeData_getLangData");
01328                 }
01329                 elseif ($translation_type == "db")
01330                 {
01331                         //$ilBench->start("Tree", "fetchNodeData_getTranslation");
01332                         $q = "SELECT title,description FROM object_translation ".
01333                                  "WHERE obj_id = ".$data["obj_id"]." ".
01334                                  "AND lang_code = '".$this->lang_code."' ".
01335                                  "AND NOT lang_default = 1";
01336                         $r = $this->ilDB->query($q);
01337 
01338                         $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01339 
01340                         if ($row)
01341                         {
01342                                 $data["title"] = $row->title;
01343                                 $data["description"] = ilUtil::shortenText($row->description,MAXLENGTH_OBJ_DESC,true);
01344                                 $data["desc"] = $row->description;
01345                         }
01346                         //$ilBench->stop("Tree", "fetchNodeData_getTranslation");
01347                 }
01348 
01349                 return $data ? $data : array();
01350         }
01351 
01352 
01360         function isInTree($a_node_id)
01361         {
01362                 if (!isset($a_node_id))
01363                 {
01364                         return false;
01365                         #$this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01366                 }
01367 
01368                 $q = "SELECT * FROM ".$this->table_tree." ".
01369                          "WHERE ".$this->table_tree.".child = ".$this->ilDB->quote($a_node_id)." ".
01370                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01371                 $r = $this->ilDB->query($q);
01372 
01373                 if ($r->numRows() > 0)
01374                 {
01375                         return true;
01376                 }
01377                 else
01378                 {
01379                         return false;
01380                 }
01381 
01382         }
01383 
01390         function getParentNodeData($a_node_id)
01391         {
01392                 if (!isset($a_node_id))
01393                 {
01394                         $this->ilErr->raiseError(get_class($this)."::getParentNodeData(): No node_id given! ",$this->ilErr->WARNING);
01395                 }
01396 
01397                 if ($this->table_obj_reference)
01398                 {
01399                         $leftjoin = "LEFT JOIN ".$this->table_obj_reference." ON v.child=".$this->table_obj_reference.".".$this->ref_pk." ".
01400                                                 "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
01401                 }
01402                 else
01403                 {
01404                         $leftjoin = "LEFT JOIN ".$this->table_obj_data." ON v.child=".$this->table_obj_data.".".$this->obj_pk." ";
01405                 }
01406 
01407                 $q = "SELECT * FROM ".$this->table_tree." s,".$this->table_tree." v ".
01408                          $leftjoin.
01409                          "WHERE s.child = '".$a_node_id."' ".
01410                          "AND s.parent = v.child ".
01411                          "AND s.lft > v.lft ".
01412                          "AND s.rgt < v.rgt ".
01413                          "AND s.".$this->tree_pk." = '".$this->tree_id."' ".
01414                          "AND v.".$this->tree_pk." = '".$this->tree_id."'";
01415                 $r = $this->ilDB->query($q);
01416 
01417                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01418 
01419                 return $this->fetchNodeData($row);
01420         }
01421 
01429         function isGrandChild($a_startnode_id,$a_querynode_id)
01430         {
01431                 if (!isset($a_startnode_id) or !isset($a_querynode_id))
01432                 {
01433                         return false;
01434                         // No raise error, since it is a already a check function
01435                         #$this->ilErr->raiseError(get_class($this)."::isGrandChild(): Missing parameter! startnode: ".$a_startnode_id." querynode: ".
01436                         #                                                $a_querynode_id,$this->ilErr->WARNING);
01437                 }
01438 
01439                 $q = "SELECT * FROM ".$this->table_tree." s,".$this->table_tree." v ".
01440                          "WHERE s.child = '".$a_startnode_id."' ".
01441                          "AND v.child = '".$a_querynode_id."' ".
01442                          "AND s.".$this->tree_pk." = '".$this->tree_id."' ".
01443                          "AND v.".$this->tree_pk." = '".$this->tree_id."' ".
01444                          "AND v.lft BETWEEN s.lft AND s.rgt ".
01445                          "AND v.rgt BETWEEN s.lft AND s.rgt";
01446                 $r = $this->ilDB->query($q);
01447 
01448                 return $r->numRows();
01449         }
01450 
01459         function addTree($a_tree_id,$a_node_id = -1)
01460         {
01461                 // FOR SECURITY addTree() IS NOT ALLOWED ON MAIN TREE
01462                 // IF SOMEONE WILL NEED FEATURES LIKE $tree->addTree(2) ON THE MAIN TREE PLEASE CONTACT ME (smeyer@databay.de)
01463                 if($this->__isMainTree())
01464                 {
01465                         $message = sprintf('%s::addTree(): Operation not allowed on main tree! $a_tree_if: %s $a_node_id: %s',
01466                                                            get_class($this),
01467                                                            $a_tree_id,
01468                                                            $a_node_id);
01469                         $this->log->write($message,$this->log->FATAL);
01470                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01471                 }
01472 
01473                 if (!isset($a_tree_id))
01474                 {
01475                         $this->ilErr->raiseError(get_class($this)."::addTree(): No tree_id given! ",$this->ilErr->WARNING);
01476                 }
01477 
01478                 if ($a_node_id <= 0)
01479                 {
01480                         $a_node_id = $a_tree_id;
01481                 }
01482 
01483                 $q = "INSERT INTO ".$this->table_tree." (".$this->tree_pk.", child, parent, lft, rgt, depth) ".
01484                          "VALUES ".
01485                          "('".$a_tree_id."','".$a_node_id."', 0, 1, 2, 1)";
01486 
01487                 $this->ilDB->query($q);
01488 
01489                 return true;
01490         }
01491 
01499         function getNodeDataByType($a_type)
01500         {
01501                 if (!isset($a_type) or (!is_string($a_type)))
01502                 {
01503                         $this->ilErr->raiseError(get_class($this)."::getNodeDataByType(): Type not given or wrong datatype!",$this->ilErr->WARNING);
01504                 }
01505 
01506                 $data = array();        // node_data
01507                 $row = "";                      // fetched row
01508                 $left = "";                     // tree_left
01509                 $right = "";            // tree_right
01510 
01511                 $q = "SELECT * FROM ".$this->table_tree." ".
01512                          "WHERE ".$this->tree_pk." = '".$this->tree_id."'".
01513                          "AND parent = '0'";
01514                 $r = $this->ilDB->query($q);
01515 
01516                 while ($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01517                 {
01518                         $left = $row->lft;
01519                         $right = $row->rgt;
01520                 }
01521 
01522                 $q = "SELECT * FROM ".$this->table_tree." ".
01523                          $this->buildJoin().
01524                          "WHERE ".$this->table_obj_data.".type = '".$a_type."' ".
01525                          "AND ".$this->table_tree.".lft BETWEEN '".$left."' AND '".$right."' ".
01526                          "AND ".$this->table_tree.".rgt BETWEEN '".$left."' AND '".$right."' ".
01527                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01528                 $r = $this->ilDB->query($q);
01529 
01530                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01531                 {
01532                         $data[] = $this->fetchNodeData($row);
01533                 }
01534 
01535                 return $data;
01536         }
01537 
01545         function removeTree($a_tree_id)
01546         {
01547                 // OPERATION NOT ALLOWED ON MAIN TREE
01548                 if($this->__isMainTree())
01549                 {
01550                         $message = sprintf('%s::removeTree(): Operation not allowed on main tree! $a_tree_if: %s',
01551                                                            get_class($this),
01552                                                            $a_tree_id);
01553                         $this->log->write($message,$this->log->FATAL);
01554                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01555                 }
01556                 if (!$a_tree_id)
01557                 {
01558                         $this->ilErr->raiseError(get_class($this)."::removeTree(): No tree_id given! Action aborted",$this->ilErr->MESSAGE);
01559                 }
01560 
01561                 $q = "DELETE FROM ".$this->table_tree." WHERE ".$this->tree_pk." = '".$a_tree_id."'";
01562                 $this->ilDB->query($q);
01563 
01564                 return true;
01565         }
01566 
01574         function saveSubTree($a_node_id, $a_set_deleted = false)
01575         {
01576                 if (!$a_node_id)
01577                 {
01578                         $message = sprintf('%s::saveSubTree(): No valid parameter given! $a_node_id: %s',
01579                                                            get_class($this),
01580                                                            $a_node_id);
01581                         $this->log->write($message,$this->log->FATAL);
01582                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01583                 }
01584 
01585                 // LOCKED ###############################################
01586                 if($this->__isMainTree())
01587                 {
01588                         ilDBx::_lockTables(array('tree' => 'WRITE',
01589                                 'object_reference' => 'WRITE'));
01590                 }
01591 
01592                 // GET LEFT AND RIGHT VALUE
01593                 $q = "SELECT * FROM ".$this->table_tree." ".
01594                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01595                          "AND child = '".$a_node_id."' ";
01596                 $r = $this->ilDB->query($q);
01597 
01598                 while($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01599                 {
01600                         $lft = $row->lft;
01601                         $rgt = $row->rgt;
01602                 }
01603 
01604                 // GET ALL SUBNODES
01605                 $q = "SELECT * FROM ".$this->table_tree." ".
01606                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01607                          "AND lft BETWEEN '".$lft."' AND '".$rgt."'";
01608                 $r = $this->ilDB->query($q);
01609 
01610                 while($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01611                 {
01612                         $subnodes[$row["child"]] = $this->fetchNodeData($row);
01613                 }
01614 
01615                 // SAVE SUBTREE
01616                 foreach($subnodes as $node)
01617                 {
01618                         $q = "INSERT INTO ".$this->table_tree." ".
01619                                  "VALUES ('".-$a_node_id."','".$node["child"]."','".$node["parent"]."','".
01620                                  $node["lft"]."','".$node["rgt"]."','".$node["depth"]."')";
01621                         $r = $this->ilDB->query($q);
01622                         
01623                         // set node as deleted
01624                         if ($a_set_deleted)
01625                         {
01626                                 ilObject::_setDeletedDate($node["child"]);
01627                         }
01628                 }
01629                 if($this->__isMainTree())
01630                 {
01631                         ilDBX::_unlockTables();
01632                 }
01633 
01634                 // LOCKED ###############################################
01635                 return true;
01636         }
01637 
01641         function isDeleted($a_node_id)
01642         {
01643                 return $this->isSaved($a_node_id);
01644         }
01645 
01649         function isSaved($a_node_id)
01650         {
01651                 $q = "SELECT * FROM ".$this->table_tree." ".
01652                          "WHERE child = '".$a_node_id."'";
01653                 $s = $this->ilDB->query($q);
01654                 $r = $s->fetchRow(DB_FETCHMODE_ASSOC);
01655 
01656                 if ($r[$this->tree_pk] < 0)
01657                 {
01658                         return true;
01659                 }
01660                 else
01661                 {
01662                         return false;
01663                 }
01664         }
01665 
01666 
01680         function saveNode($a_node_id,$a_parent_id)
01681         {
01682                 if($this->__isMainTree())
01683                 {
01684                         if($a_node_id <= 1 or $a_parent_id <= 0)
01685                         {
01686                                 $message = sprintf('%s::saveSubTree(): No valid parameter given! $a_node_id: %s $a_parent_id: %s',
01687                                                                    get_class($this),
01688                                                                    $a_node_id,
01689                                                                    $a_parent_id);
01690 
01691                                 $this->log->write($message,$this->log->FATAL);
01692                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01693                         }
01694                 }
01695                 if ($a_node_id < 1 or !isset($a_parent_id))
01696                 {
01697                         $this->ilErr->raiseError(get_class($this)."::saveNode(): Missing parameter! ".
01698                                                                          "node_id: ".$a_node_id." parent_id: ".$a_parent_id,$this->ilErr->WARNING);
01699                 }
01700 
01701                 // SAVE NODE
01702                 $q = "INSERT INTO ".$this->table_tree." ".
01703                          "VALUES ('".-$a_node_id."','".$a_node_id."','".$a_parent_id."','1','2','1')";
01704                 $r = $this->ilDB->query($q);
01705 
01706                 return true;
01707         }
01708 
01715         function getSavedNodeData($a_parent_id)
01716         {
01717                 if (!isset($a_parent_id))
01718                 {
01719                         $this->ilErr->raiseError(get_class($this)."::getSavedNodeData(): No node_id given!",$this->ilErr->WARNING);
01720                 }
01721 
01722                 $q =    "SELECT * FROM ".$this->table_tree." ".
01723                                 $this->buildJoin().
01724                                 "WHERE ".$this->table_tree.".".$this->tree_pk." < 0 ".
01725                                 "AND ".$this->table_tree.".parent = '".$a_parent_id."' ";
01726                 $r = $this->ilDB->query($q);
01727 
01728                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01729                 {
01730                         $saved[] = $this->fetchNodeData($row);
01731                 }
01732 
01733                 return $saved ? $saved : array();
01734         }
01735 
01742         function getParentId($a_node_id)
01743         {
01744                 if (!isset($a_node_id))
01745                 {
01746                         $this->ilErr->raiseError(get_class($this)."::getParentId(): No node_id given! ",$this->ilErr->WARNING);
01747                 }
01748 
01749                 $q = "SELECT parent FROM ".$this->table_tree." ".
01750                          "WHERE child='".$a_node_id."' ".
01751                          "AND ".$this->tree_pk."='".$this->tree_id."'";
01752                 $r = $this->ilDB->query($q);
01753 
01754                 $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01755 
01756                 return $row->parent;
01757         }
01758 
01765         function getLeftValue($a_node_id)
01766         {
01767                 if (!isset($a_node_id))
01768                 {
01769                         $this->ilErr->raiseError(get_class($this)."::getLeftValued(): No node_id given! ",$this->ilErr->WARNING);
01770                 }
01771 
01772                 $q = "SELECT lft FROM ".$this->table_tree." ".
01773                          "WHERE child='".$a_node_id."' ".
01774                          "AND ".$this->tree_pk."='".$this->tree_id."'";
01775                 $r = $this->ilDB->query($q);
01776 
01777                 $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01778 
01779                 return $row->lft;
01780         }
01781 
01788         function getChildSequenceNumber($a_node, $type = "")
01789         {
01790                 if (!isset($a_node))
01791                 {
01792                         $this->ilErr->raiseError(get_class($this)."::getChildSequenceNumber(): No node_id given! ",$this->ilErr->WARNING);
01793                 }
01794 
01795                 $type_str = ($type != "")
01796                         ? "AND type='$type'"
01797                         : "";
01798 
01799                 $q = "SELECT count(*) AS cnt FROM ".$this->table_tree." ".
01800                         $this->buildJoin().
01801                         "WHERE lft <=".$this->ilDB->quote($a_node["lft"])." ".
01802                         $type_str.
01803                         "AND parent=".$this->ilDB->quote($a_node["parent"])." ".
01804                         "AND ".$this->table_tree.".".$this->tree_pk."=".$this->ilDB->quote($this->tree_id);
01805                 $r = $this->ilDB->query($q);
01806 
01807                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01808 
01809                 return $row["cnt"];
01810         }
01811 
01818         function readRootId()
01819         {
01820                 $query = "SELECT child FROM $this->table_tree ".
01821                         "WHERE parent = '0'".
01822                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
01823                 $row = $this->ilDB->getRow($query,DB_FETCHMODE_OBJECT);
01824 
01825                 $this->root_id = $row->child;
01826                 return $this->root_id;
01827         }
01828 
01834         function getRootId()
01835         {
01836                 return $this->root_id;
01837         }
01838         function setRootId($a_root_id)
01839         {
01840                 $this->root_id = $a_root_id;
01841         }
01842 
01848         function getTreeId()
01849         {
01850                 return $this->tree_id;
01851         }
01852 
01858         function setTreeId($a_tree_id)
01859         {
01860                 $this->tree_id = $a_tree_id;
01861         }
01862 
01870         function fetchSuccessorNode($a_node_id, $a_type = "")
01871         {
01872                 if (!isset($a_node_id))
01873                 {
01874                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01875                 }
01876 
01877                 // get lft value for current node
01878                 $q = "SELECT lft FROM ".$this->table_tree." ".
01879                          "WHERE ".$this->table_tree.".child = '".$a_node_id."' ".
01880                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01881                 $r = $this->ilDB->query($q);
01882                 $curr_node = $r->fetchRow(DB_FETCHMODE_ASSOC);
01883 
01884                 // get data of successor node
01885                 $type_where = ($a_type != "")
01886                         ? "AND ".$this->table_obj_data.".type = '$a_type' "
01887                         : "";
01888                 $q = "SELECT * FROM ".$this->table_tree." ".
01889                          $this->buildJoin().
01890                          "WHERE lft > '".$curr_node["lft"]."' ".
01891                          $type_where.
01892                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'".
01893                          "ORDER BY lft LIMIT 1";
01894                 $r = $this->ilDB->query($q);
01895 
01896                 if ($r->numRows() < 1)
01897                 {
01898                         return false;
01899                 }
01900                 else
01901                 {
01902                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01903                         return $this->fetchNodeData($row);
01904                 }
01905         }
01906 
01914         function fetchPredecessorNode($a_node_id, $a_type = "")
01915         {
01916                 if (!isset($a_node_id))
01917                 {
01918                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01919                 }
01920 
01921                 // get lft value for current node
01922                 $q = "SELECT lft FROM ".$this->table_tree." ".
01923                          "WHERE ".$this->table_tree.".child = '".$a_node_id."' ".
01924                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01925                 $r = $this->ilDB->query($q);
01926                 $curr_node = $r->fetchRow(DB_FETCHMODE_ASSOC);
01927 
01928                 // get data of predecessor node
01929                 $type_where = ($a_type != "")
01930                         ? "AND ".$this->table_obj_data.".type = '$a_type' "
01931                         : "";
01932                 $q = "SELECT * FROM ".$this->table_tree." ".
01933                          $this->buildJoin().
01934                          "WHERE lft < '".$curr_node["lft"]."' ".
01935                          $type_where.
01936                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'".
01937                          "ORDER BY lft DESC LIMIT 1";
01938                 $r = $this->ilDB->query($q);
01939 
01940                 if ($r->numRows() < 1)
01941                 {
01942                         return false;
01943                 }
01944                 else
01945                 {
01946                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01947                         return $this->fetchNodeData($row);
01948                 }
01949         }
01950 
01959         function renumber($node_id = 1, $i = 1)
01960         {
01961                 // LOCKED ###################################
01962                 if($this->__isMainTree())
01963                 {
01964                         ilDBx::_lockTables(array($this->table_tree => 'WRITE',
01965                                                                          $this->table_obj_data => 'WRITE',
01966                                                                          $this->table_obj_reference => 'WRITE',
01967                                                                          'object_translation' => 'WRITE'));
01968                 }
01969                 $return = $this->__renumber($node_id,$i);
01970                 if($this->__isMainTree())
01971                 {
01972                         ilDBx::_unlockTables();
01973                 }
01974                 // LOCKED ###################################
01975                 return $return;
01976         }
01977 
01978         // PRIVATE
01988         function __renumber($node_id = 1, $i = 1)
01989         {
01990                 $q = "UPDATE ".$this->table_tree." SET lft='".$i."' WHERE child='".$node_id."'";
01991                 $this->ilDB->query($q);
01992 
01993                 $childs = $this->getChilds($node_id);
01994 
01995                 foreach ($childs as $child)
01996                 {
01997                         $i = $this->__renumber($child["child"],$i+1);
01998                 }
01999 
02000                 $i++;
02001                 
02002                 // Insert a gap at the end of node, if the node has children
02003                 if (count($childs) > 0)
02004                 {
02005                         $i += $this->gap * 2;
02006                 }
02007                 
02008                 $q = "UPDATE ".$this->table_tree." SET rgt='".$i."' WHERE child='".$node_id."'";
02009                 $this->ilDB->query($q);
02010 
02011                 return $i;
02012         }
02013 
02014 
02024         function checkForParentType($a_ref_id,$a_type)
02025         {
02026                 if(!$this->isInTree($a_ref_id))
02027                 {
02028                         return false;
02029                 }
02030                 $path = array_reverse($this->getPathFull($a_ref_id));
02031 
02032                 foreach($path as $node)
02033                 {
02034                         if($node["type"] == $a_type)
02035                         {
02036                                 return $node["child"];
02037                         }
02038                 }
02039                 return 0;
02040         }
02041 
02051         function _removeEntry($a_tree,$a_child,$a_db_table = "tree")
02052         {
02053                 global $ilDB,$ilLog,$ilErr;
02054 
02055                 if($a_db_table === 'tree')
02056                 {
02057                         if($a_tree == 1 and $a_child == ROOT_FOLDER_ID)
02058                         {
02059                                 $message = sprintf('%s::_removeEntry(): Tried to delete root node! $a_tree: %s $a_child: %s',
02060                                                                    get_class($this),
02061                                                                    $a_tree,
02062                                                                    $a_child);
02063                                 $ilLog->write($message,$ilLog->FATAL);
02064                                 $ilErr->raiseError($message,$ilErr->WARNING);
02065                         }
02066                 }
02067 
02068                 $q = "DELETE from ".$a_db_table." WHERE tree='".$a_tree."' AND child='".$a_child."'";
02069                 $ilDB->query($q);
02070         }
02071 
02072         // PRIVATE METHODS
02079         function __isMainTree()
02080         {
02081                 return $this->table_tree === 'tree';
02082         }
02083 
02092         function __checkDelete($a_node)
02093         {
02094                 // get subtree by lft,rgt
02095                 $query = "SELECT * FROM ".$this->table_tree." ".
02096                         "WHERE lft >= ".$a_node['lft']." ".
02097                         "AND rgt <= ".$a_node['rgt']." ".
02098                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
02099 
02100 
02101                 $res = $this->ilDB->query($query);
02102 
02103                 $counter = (int) $lft_childs = array();
02104                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02105                 {
02106                         $lft_childs[$row->child] = $row->parent;
02107                         ++$counter;
02108                 }
02109 
02110                 // CHECK FOR DUPLICATE CHILD IDS
02111                 if($counter != count($lft_childs))
02112                 {
02113                         $message = sprintf('%s::__checkTree(): Duplicate entries for "child" in maintree! $a_node_id: %s',
02114                                                                    get_class($this),
02115                                                            $a_node['child']);
02116                         $this->log->write($message,$this->log->FATAL);
02117                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02118                 }
02119 
02120                 // GET SUBTREE BY PARENT RELATION
02121                 $parent_childs = array();
02122                 $this->__getSubTreeByParentRelation($a_node['child'],$parent_childs);
02123                 $this->__validateSubtrees($lft_childs,$parent_childs);
02124 
02125                 return true;
02126         }
02127 
02128         function __getSubTreeByParentRelation($a_node_id,&$parent_childs)
02129         {
02130                 // GET PARENT ID
02131                 $query = "SELECT * FROM ".$this->table_tree." ".
02132                         "WHERE child = '".$a_node_id."' ".
02133                         "AND tree = '".$this->tree_id."'";
02134 
02135                 $res = $this->ilDB->query($query);
02136                 $counter = 0;
02137                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02138                 {
02139                         $parent_childs[$a_node_id] = $row->parent;
02140                         ++$counter;
02141                 }
02142                 // MULTIPLE ENTRIES
02143                 if($counter > 1)
02144                 {
02145                         $message = sprintf('%s::__getSubTreeByParentRelation(): Multiple entries in maintree! $a_node_id: %s',
02146                                                            get_class($this),
02147                                                            $a_node_id);
02148                         $this->log->write($message,$this->log->FATAL);
02149                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02150                 }
02151 
02152                 // GET ALL CHILDS
02153                 $query = "SELECT * FROM ".$this->table_tree." ".
02154                         "WHERE parent = '".$a_node_id."'";
02155 
02156                 $res = $this->ilDB->query($query);
02157                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02158                 {
02159                         // RECURSION
02160                         $this->__getSubTreeByParentRelation($row->child,$parent_childs);
02161                 }
02162                 return true;
02163         }
02164 
02165         function __validateSubtrees(&$lft_childs,$parent_childs)
02166         {
02167                 // SORT BY KEY
02168                 ksort($lft_childs);
02169                 ksort($parent_childs);
02170 
02171                 if(count($lft_childs) != count($parent_childs))
02172                 {
02173                         $message = sprintf('%s::__validateSubtrees(): (COUNT) Tree is corrupted! Left/Right subtree does not comply .'.
02174                                                            'with parent relation',
02175                                                            get_class($this));
02176                         $this->log->write($message,$this->log->FATAL);
02177                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02178                 }
02179 
02180                 foreach($lft_childs as $key => $value)
02181                 {
02182                         if($parent_childs[$key] != $value)
02183                         {
02184                                 $message = sprintf('%s::__validateSubtrees(): (COMPARE) Tree is corrupted! Left/Right subtree does not comply '.
02185                                                                    'with parent relation',
02186                                                                    get_class($this));
02187                                 $this->log->write($message,$this->log->FATAL);
02188                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02189                         }
02190                         if($key == ROOT_FOLDER_ID)
02191                         {
02192                                 $message = sprintf('%s::__validateSubtrees(): (ROOT_FOLDER) Tree is corrupted! Tried to delete root folder',
02193                                                                    get_class($this));
02194                                 $this->log->write($message,$this->log->FATAL);
02195                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02196                         }
02197                 }
02198                 return true;
02199         }
02200 
02201 } // END class.tree
02202 ?>