ILIAS Release_3_6_x_branch .rev 46809: 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-2001 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 
00038 class ilTree
00039 {
00045         var $ilias;
00046 
00047 
00053         var $log;
00054 
00060         var $root_id;
00061 
00067         var $tree_id;
00068 
00074         var $table_tree;
00075 
00081         var $table_obj_data;
00082 
00088         var $table_obj_reference;
00089 
00095         var $ref_pk;
00096 
00102         var $obj_pk;
00103 
00109         var $tree_pk;
00110 
00135         var $gap;
00136 
00143         function ilTree($a_tree_id, $a_root_id = 0)
00144         {
00145                 global $ilDB,$ilErr,$ilUser,$ilias,$ilLog;
00146 
00147                 // set db & error handler
00148                 (isset($ilDB)) ? $this->ilDB =& $ilDB : $this->ilDB =& $ilias->db;
00149 
00150                 if (!isset($ilErr))
00151                 {
00152                         $ilErr = new ilErrorHandling();
00153                         $ilErr->setErrorHandling(PEAR_ERROR_CALLBACK,array($ilErr,'errorHandler'));
00154                 }
00155                 else
00156                 {
00157                         $this->ilErr =& $ilErr;
00158                 }
00159 
00160                 // lang_code is only required in $this->fetchnodedata
00161                 if (!is_object($ilUser))
00162                 {
00163                         $this->lang_code = "en";
00164                 }
00165                 else
00166                 {
00167                         $this->lang_code = $ilUser->getCurrentLanguage();
00168                 }
00169 
00170                 if (!isset($a_tree_id) or (func_num_args() == 0) )
00171                 {
00172                         $this->ilErr->raiseError(get_class($this)."::Constructor(): No tree_id given!",$this->ilErr->WARNING);
00173                 }
00174 
00175                 if (func_num_args() > 2)
00176                 {
00177                         $this->ilErr->raiseError(get_class($this)."::Constructor(): Wrong parameter count!",$this->ilErr->WARNING);
00178                 }
00179 
00180                 // CREATE LOGGER INSTANCE
00181                 $this->log =& $ilLog;
00182 
00183                 //init variables
00184                 if (empty($a_root_id))
00185                 {
00186                         $a_root_id = ROOT_FOLDER_ID;
00187                 }
00188 
00189                 $this->tree_id            = $a_tree_id;
00190                 $this->root_id            = $a_root_id;
00191                 $this->table_tree     = 'tree';
00192                 $this->table_obj_data = 'object_data';
00193                 $this->table_obj_reference = 'object_reference';
00194                 $this->ref_pk = 'ref_id';
00195                 $this->obj_pk = 'obj_id';
00196                 $this->tree_pk = 'tree';
00197 
00198                 // By default, we create gaps in the tree sequence numbering for 50 nodes 
00199                 $this->gap = 50;
00200         }
00201 
00216         function setTableNames($a_table_tree,$a_table_obj_data,$a_table_obj_reference = "")
00217         {
00218                 if (!isset($a_table_tree) or !isset($a_table_obj_data))
00219                 {
00220                         $this->ilErr->raiseError(get_class($this)."::setTableNames(): Missing parameter! ".
00221                                                                 "tree table: ".$a_table_tree." object data table: ".$a_table_obj_data,$this->ilErr->WARNING);
00222                 }
00223 
00224                 $this->table_tree = $a_table_tree;
00225                 $this->table_obj_data = $a_table_obj_data;
00226                 $this->table_obj_reference = $a_table_obj_reference;
00227 
00228                 return true;
00229         }
00230 
00237         function setReferenceTablePK($a_column_name)
00238         {
00239                 if (!isset($a_column_name))
00240                 {
00241                         $this->ilErr->raiseError(get_class($this)."::setReferenceTablePK(): No column name given!",$this->ilErr->WARNING);
00242                 }
00243 
00244                 $this->ref_pk = $a_column_name;
00245                 return true;
00246         }
00247 
00254         function setObjectTablePK($a_column_name)
00255         {
00256                 if (!isset($a_column_name))
00257                 {
00258                         $this->ilErr->raiseError(get_class($this)."::setObjectTablePK(): No column name given!",$this->ilErr->WARNING);
00259                 }
00260 
00261                 $this->obj_pk = $a_column_name;
00262                 return true;
00263         }
00264 
00271         function setTreeTablePK($a_column_name)
00272         {
00273                 if (!isset($a_column_name))
00274                 {
00275                         $this->ilErr->raiseError(get_class($this)."::setTreeTablePK(): No column name given!",$this->ilErr->WARNING);
00276                 }
00277 
00278                 $this->tree_pk = $a_column_name;
00279                 return true;
00280         }
00281 
00287         function buildJoin()
00288         {
00289                 if ($this->table_obj_reference)
00290                 {
00291                         return "LEFT JOIN ".$this->table_obj_reference." ON ".$this->table_tree.".child=".$this->table_obj_reference.".".$this->ref_pk." ".
00292                                    "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
00293                 }
00294                 else
00295                 {
00296                         return "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_tree.".child=".$this->table_obj_data.".".$this->obj_pk." ";
00297                 }
00298         }
00299 
00308         function getChilds($a_node_id, $a_order = "", $a_direction = "ASC")
00309         {
00310                 global $ilBench;
00311                 
00312                 if (!isset($a_node_id))
00313                 {
00314                         $message = get_class($this)."::getChilds(): No node_id given!";
00315                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00316                 }
00317 
00318                 // init childs
00319                 $childs = array();
00320 
00321                 // number of childs
00322                 $count = 0;
00323 
00324                 // init order_clause
00325                 $order_clause = "";
00326 
00327                 // set order_clause if sort order parameter is given
00328                 if (!empty($a_order))
00329                 {
00330                         $order_clause = "ORDER BY ".$a_order." ".$a_direction;
00331                 }
00332                 else
00333                 {
00334                         $order_clause = "ORDER BY ".$this->table_tree.".lft";
00335                 }
00336 
00337         //666
00338                 $q = "SELECT * FROM ".$this->table_tree." ".
00339                          $this->buildJoin().
00340                          "WHERE parent = ".$this->ilDB->quote($a_node_id)." ".
00341                          "AND ".$this->table_tree.".".$this->tree_pk." = ".$this->ilDB->quote($this->tree_id)." ".
00342                          $order_clause;
00343 
00344                 //$ilBench->start("Tree", "getChilds_Query");
00345                 $r = $this->ilDB->query($q);
00346                 //$ilBench->stop("Tree", "getChilds_Query");
00347 
00348                 $count = $r->numRows();
00349 
00350 
00351                 if ($count > 0)
00352                 {
00353                         //$ilBench->start("Tree", "getChilds_fetchNodeData");
00354                         while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00355                         {
00356                                 $childs[] = $this->fetchNodeData($row);
00357                         }
00358                         //$ilBench->stop("Tree", "getChilds_fetchNodeData");
00359 
00360                         // mark the last child node (important for display)
00361                         $childs[$count - 1]["last"] = true;
00362                         return $childs;
00363                 }
00364                 else
00365                 {
00366                         return $childs;
00367                 }
00368         }
00369 
00379         function getFilteredChilds($a_filter,$a_node,$a_order = "",$a_direction = "ASC")
00380         {
00381                 $childs = $this->getChilds($a_node,$a_order,$a_direction);
00382 
00383                 foreach($childs as $child)
00384                 {
00385                         if(!in_array($child["type"],$a_filter))
00386                         {
00387                                 $filtered[] = $child;
00388                         }
00389                 }
00390                 return $filtered ? $filtered : array();
00391         }
00392 
00393 
00401         function getChildsByType($a_node_id,$a_type)
00402         {
00403                 if (!isset($a_node_id) or !isset($a_type))
00404                 {
00405                         $message = get_class($this)."::getChildsByType(): Missing parameter! node_id:".$a_node_id." type:".$a_type;
00406                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00407                 }
00408 
00409                 // init childs
00410                 $childs = array();
00411 
00412                 $q = "SELECT * FROM ".$this->table_tree." ".
00413                          $this->buildJoin().
00414                          "WHERE parent = '".$a_node_id."' ".
00415                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."' ".
00416                          "AND ".$this->table_obj_data.".type='".$a_type."' ".
00417                          "ORDER BY ".$this->table_tree.".lft";
00418                 $r = $this->ilDB->query($q);
00419 
00420                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00421                 {
00422                         $childs[] = $this->fetchNodeData($row);
00423                 }
00424 
00425 
00426                 return $childs;
00427         }
00428 
00429 
00437         function insertNode($a_node_id, $a_parent_id, $a_pos = IL_LAST_NODE, $a_reset_deletion_date = false)
00438         {
00439 //echo "+$a_node_id+$a_parent_id+";
00440                 // CHECK node_id and parent_id > 0 if in main tree
00441                 if($this->__isMainTree())
00442                 {
00443                         if($a_node_id <= 1 or $a_parent_id <= 0)
00444                         {
00445                                 $message = sprintf('%s::insertNode(): Invalid parameters! $a_node_id: %s $a_parent_id: %s',
00446                                                                    get_class($this),
00447                                                                    $a_node_id,
00448                                                                    $a_parent_id);
00449                                 $this->log->write($message,$this->log->FATAL);
00450                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00451                         }
00452                 }
00453 
00454 
00455                 if (!isset($a_node_id) or !isset($a_parent_id))
00456                 {
00457                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Missing parameter! ".
00458                                 "node_id: ".$a_node_id." parent_id: ".$a_parent_id,$this->ilErr->WARNING);
00459                 }
00460                 if ($this->isInTree($a_node_id))
00461                 {
00462                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Node ".$a_node_id." already in tree ".
00463                                                                          $this->table_tree."!",$this->ilErr->WARNING);
00464                 }
00465 
00466                 //
00467                 switch ($a_pos)
00468                 {
00469                         case IL_FIRST_NODE:
00470 
00471                                 if($this->__isMainTree())
00472                                 {
00473                                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00474                                 }
00475 
00476                                 // get left value of parent
00477                                 $q = "SELECT * FROM ".$this->table_tree." ".
00478                                         "WHERE child = '".$a_parent_id."' ".
00479                                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
00480                                 $res = $this->ilDB->query($q);
00481                                 $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00482 
00483                                 if ($r->parent == NULL)
00484                                 {
00485                                         if($this->__isMainTree())
00486                                         {
00487                                                 ilDBx::_unlockTables();
00488                                         }
00489                                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".$a_parent_id." not found in ".
00490                                                                                          $this->table_tree."!",$this->ilErr->WARNING);
00491                                 }
00492 
00493                                 $left = $r->lft;
00494                                 $lft = $left + 1;
00495                                 $rgt = $left + 2;
00496 
00497                                 // spread tree
00498                                 $q = "UPDATE ".$this->table_tree." SET ".
00499                                         "lft = CASE ".
00500                                         "WHEN lft > ".$left." ".
00501                                         "THEN lft + 2 ".
00502                                         "ELSE lft ".
00503                                         "END, ".
00504                                         "rgt = CASE ".
00505                                         "WHEN rgt > ".$left." ".
00506                                         "THEN rgt + 2 ".
00507                                         "ELSE rgt ".
00508                                         "END ".
00509                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00510                                 $this->ilDB->query($q);
00511                                 break;
00512 
00513                         case IL_LAST_NODE:
00514                                 // Special treatment for trees with gaps
00515                                 if ($this->gap > 0)
00516                                 {
00517                                         if($this->__isMainTree())
00518                                         {
00519                                                 ilDBx::_lockTables(array('tree' => 'WRITE'));
00520                                         }
00521 
00522                                         // get lft and rgt value of parent
00523                                         $q = 'SELECT rgt,lft,parent FROM '.$this->table_tree.' '.
00524                                                 'WHERE child = '.$a_parent_id.' '.
00525                                                 'AND '.$this->tree_pk.' = '.$this->tree_id;
00526                                         $res = $this->ilDB->query($q);
00527                                         $r = $res->fetchRow(DB_FETCHMODE_ASSOC);
00528 
00529                                                                         
00530                                         if ($r['parent'] == NULL)
00531                                         {
00532                                                 if($this->__isMainTree())
00533                                                 {
00534                                                         ilDBx::_unlockTables();
00535                                                 }
00536                                                 $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
00537                                                                                                 $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
00538                                         }
00539                                         $parentRgt = $r['rgt'];
00540                                         $parentLft = $r['lft'];
00541                                         
00542                                         // Get the available space, without taking children into account yet
00543                                         $availableSpace = $parentRgt - $parentLft;
00544                                         if ($availableSpace < 2)
00545                                         {
00546                                                 // If there is not enough space between parent lft and rgt, we don't need
00547                                                 // to look any further, because we must spread the tree.
00548                                                 $lft = $parentRgt;
00549                                         }
00550                                         else
00551                                         {
00552                                                 // If there is space between parent lft and rgt, we need to check
00553                                                 // whether there is space left between the rightmost child of the
00554                                                 // parent and parent rgt.
00555                                                 $q = 'SELECT MAX(rgt) AS max_rgt FROM '.$this->table_tree.' '.
00556                                                         'WHERE parent = '.$a_parent_id.' '.
00557                                                         'AND '.$this->tree_pk.' = '.$this->tree_id;
00558                                                 $res = $this->ilDB->query($q);
00559                                                 $r = $res->fetchRow(DB_FETCHMODE_ASSOC);
00560                                                 if (isset($r['max_rgt']))
00561                                                 {
00562                                                         // If the parent has children, we compute the available space
00563                                                         // between rgt of the rightmost child and parent rgt.
00564                                                         $availableSpace = $parentRgt - $r['max_rgt'];
00565                                                         $lft = $r['max_rgt'] + 1;
00566                                                 }
00567                                                 else
00568                                                 {
00569                                                         // If the parent has no children, we know now, that we can
00570                                                         // add the new node at parent lft + 1 without having to spread
00571                                                         // the tree.
00572                                                         $lft = $parentLft + 1;
00573                                                 }
00574                                         }
00575                                         $rgt = $lft + 1;
00576                                         
00577 
00578                                         // spread tree if there is not enough space to insert the new node
00579                                         if ($availableSpace < 2)
00580                                         {
00581                                                 $this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
00582                                                 $q = "UPDATE ".$this->table_tree." SET ".
00583                                                         "lft = CASE ".
00584                                                         "WHEN lft > ".$parentRgt." ".
00585                                                         "THEN lft + ".(2 + $this->gap * 2).' '.
00586                                                         "ELSE lft ".
00587                                                         "END, ".
00588                                                         "rgt = CASE ".
00589                                                         "WHEN rgt >= ".$parentRgt." ".
00590                                                         "THEN rgt + ".(2 + $this->gap * 2).' '.
00591                                                         "ELSE rgt ".
00592                                                         "END ".
00593                                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00594                                                 $this->ilDB->query($q);
00595                                         }
00596                                         else
00597                                         {
00598                                                 $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);
00599                                         }                               
00600                                 }
00601                                 // Treatment for trees without gaps
00602                                 else 
00603                                 {
00604                                         if($this->__isMainTree())
00605                                         {
00606                                                 ilDBx::_lockTables(array('tree' => 'WRITE'));
00607                                         }
00608 
00609                                         // get right value of parent
00610                                         $q = "SELECT * FROM ".$this->table_tree." ".
00611                                                 "WHERE child = '".$a_parent_id."' ".
00612                                                 "AND ".$this->tree_pk." = '".$this->tree_id."'";
00613                                         $res = $this->ilDB->query($q);
00614                                         $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00615 
00616                                         if ($r->parent == NULL)
00617                                         {
00618                                                 if($this->__isMainTree())
00619                                                 {
00620                                                         ilDBx::_unlockTables();
00621                                                 }
00622                                                 $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
00623                                                                                                  $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
00624                                         }
00625 
00626                                         $right = $r->rgt;
00627                                         $lft = $right;
00628                                         $rgt = $right + 1;
00629 
00630                                         // spread tree
00631                                         $q = "UPDATE ".$this->table_tree." SET ".
00632                                                 "lft = CASE ".
00633                                                 "WHEN lft > ".$right." ".
00634                                                 "THEN lft + 2 ".
00635                                                 "ELSE lft ".
00636                                                 "END, ".
00637                                                 "rgt = CASE ".
00638                                                 "WHEN rgt >= ".$right." ".
00639                                                 "THEN rgt + 2 ".
00640                                                 "ELSE rgt ".
00641                                                 "END ".
00642                                                 "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00643                                         $this->ilDB->query($q);
00644                                 }
00645                                 break;
00646 
00647                         default:
00648 
00649                                 if($this->__isMainTree())
00650                                 {
00651                                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00652                                 }
00653 
00654                                 // get right value of preceeding child
00655                                 $q = "SELECT * FROM ".$this->table_tree." ".
00656                                         "WHERE child = '".$a_pos."' ".
00657                                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
00658                                 $res = $this->ilDB->query($q);
00659                                 $r = $res->fetchRow(DB_FETCHMODE_OBJECT);
00660 
00661                                 // crosscheck parents of sibling and new node (must be identical)
00662                                 if ($r->parent != $a_parent_id)
00663                                 {
00664                                         if($this->__isMainTree())
00665                                         {
00666                                                 ilDBx::_unlockTables();
00667                                         }
00668                                         $this->ilErr->raiseError(get_class($this)."::insertNode(): Parents mismatch! ".
00669                                                 "new node parent: ".$a_parent_id." sibling parent: ".$r->parent,$this->ilErr->WARNING);
00670                                 }
00671 
00672                                 $right = $r->rgt;
00673                                 $lft = $right + 1;
00674                                 $rgt = $right + 2;
00675 
00676                                 // update lft/rgt values
00677                                 $q = "UPDATE ".$this->table_tree." SET ".
00678                                         "lft = CASE ".
00679                                         "WHEN lft > ".$right." ".
00680                                         "THEN lft + 2 ".
00681                                         "ELSE lft ".
00682                                         "END, ".
00683                                         "rgt = CASE ".
00684                                         "WHEN rgt > ".$right." ".
00685                                         "THEN rgt + 2 ".
00686                                         "ELSE rgt ".
00687                                         "END ".
00688                                         "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
00689                                 $this->ilDB->query($q);
00690                                 break;
00691 
00692                 }
00693 
00694                 // get depth
00695                 $depth = $this->getDepth($a_parent_id) + 1;
00696 
00697                 // insert node
00698                 $this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') inserting node:'.$a_node_id.' parent:'.$a_parent_id." ".$lft."..".$rgt." depth:".$depth);
00699                 $q = "INSERT INTO ".$this->table_tree." (".$this->tree_pk.",child,parent,lft,rgt,depth) ".
00700                          "VALUES ".
00701                          "('".$this->tree_id."','".$a_node_id."','".$a_parent_id."','".$lft."','".$rgt."','".$depth."')";
00702 
00703                 $this->ilDB->query($q);
00704 
00705                 // Finally unlock tables
00706                 if($this->__isMainTree())
00707                 {
00708                         ilDBx::_unlockTables();
00709                 }
00710                 
00711                 // reset deletion date
00712                 if ($a_reset_deletion_date)
00713                 {
00714                         ilObject::_resetDeletedDate($a_node_id);
00715                 }
00716         }
00717 
00725         function getSubTree($a_node)
00726         {
00727                 if (!is_array($a_node))
00728                 {
00729                         $this->ilErr->raiseError(get_class($this)."::getSubTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
00730                 }
00731 
00732                 if($a_node['lft'] < 1 or $a_node['rgt'] < 2)
00733                 {
00734                         $message = sprintf('%s::getSubTree(): Invalid node given! $a_node["lft"]: %s $a_node["rgt"]: %s',
00735                                                                    get_class($this),
00736                                                                    $a_node['lft'],
00737                                                                    $a_node['rgt']);
00738 
00739                         $this->log->write($message,$this->log->FATAL);
00740 
00741                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00742                 }
00743 
00744             $subtree = array();
00745 
00746                 $q = "SELECT * FROM ".$this->table_tree." ".
00747                          $this->buildJoin().
00748                          "WHERE ".$this->table_tree.".lft BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00749                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."' ".
00750                          "ORDER BY ".$this->table_tree.".lft";
00751 
00752                 $r = $this->ilDB->query($q);
00753 
00754                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00755                 {
00756                         $subtree[] = $this->fetchNodeData($row);
00757                 }
00758 
00759                 return $subtree ? $subtree : array();
00760         }
00761 
00770         function getSubTreeTypes($a_node,$a_filter = 0)
00771         {
00772                 $a_filter = $a_filter ? $a_filter : array();
00773 
00774                 foreach($this->getSubtree($this->getNodeData($a_node)) as $node)
00775                 {
00776                         if(in_array($node["type"],$a_filter))
00777                         {
00778                                 continue;
00779                         }
00780                         $types["$node[type]"] = $node["type"];
00781                 }
00782                 return $types ? $types : array();
00783         }
00784 
00790         function deleteTree($a_node)
00791         {
00792                 if (!is_array($a_node))
00793                 {
00794                         $this->ilErr->raiseError(get_class($this)."::deleteTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
00795                 }
00796                 if($this->__isMainTree() and $a_node[$this->tree_pk] === 1)
00797                 {
00798                         if($a_node['lft'] <= 1 or $a_node['rgt'] <= 2)
00799                         {
00800                                 $message = sprintf('%s::deleteTree(): Invalid parameters given: $a_node["lft"]: %s, $a_node["rgt"] %s',
00801                                                                    get_class($this),
00802                                                                    $a_node['lft'],
00803                                                                    $a_node['rgt']);
00804 
00805                                 $this->log->write($message,$this->log->FATAL);
00806                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00807                         }
00808                         else if(!$this->__checkDelete($a_node))
00809                         {
00810                                 $message = sprintf('%s::deleteTree(): Check delete failed: $a_node["lft"]: %s, $a_node["rgt"] %s',
00811                                                                    get_class($this),
00812                                                                    $a_node['lft'],
00813                                                                    $a_node['rgt']);
00814                                 $this->log->write($message,$this->log->FATAL);
00815                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
00816                         }
00817 
00818                 }
00819                 $diff = $a_node["rgt"] - $a_node["lft"] + 1;
00820 
00821 
00822                 // LOCKED ###########################################################
00823                 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
00824                 if($this->__isMainTree())
00825                 {
00826                         ilDBx::_lockTables(array('tree' => 'WRITE'));
00827                 }
00828 
00829                 $query = "SELECT * FROM ".$this->table_tree." ".
00830                         "WHERE child = '".$a_node['child']."' ".
00831                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00832 
00833                 $res = $this->ilDB->query($query);
00834                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
00835                 {
00836                         $a_node['lft'] = $row->lft;
00837                         $a_node['rgt'] = $row->rgt;
00838                         $diff = $a_node["rgt"] - $a_node["lft"] + 1;
00839                 }
00840 
00841                 // delete subtree
00842                 $q = "DELETE FROM ".$this->table_tree." ".
00843                         "WHERE lft BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00844                         "AND rgt BETWEEN '".$a_node["lft"]."' AND '".$a_node["rgt"]."' ".
00845                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00846                 $this->ilDB->query($q);
00847 
00848                 // We only close the gap, if the resulting gap will be larger then the gap value 
00849                 if ($a_node['rgt'] - $a_node['lft'] >= $this->gap * 2)
00850                 {
00851                         $this->log->write('ilTree.deleteTree('.$a_node['child'].') closing gap at '.$a_node['lft'].'...'.$a_node['rgt']);
00852                         // close gaps
00853                         $q = "UPDATE ".$this->table_tree." SET ".
00854                                  "lft = CASE ".
00855                                  "WHEN lft > '".$a_node["lft"]." '".
00856                                  "THEN lft - '".$diff." '".
00857                                  "ELSE lft ".
00858                                  "END, ".
00859                                  "rgt = CASE ".
00860                                  "WHEN rgt > '".$a_node["lft"]." '".
00861                                  "THEN rgt - '".$diff." '".
00862                                  "ELSE rgt ".
00863                                  "END ".
00864                                  "WHERE ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
00865                         $this->ilDB->query($q);
00866                 }
00867                 else
00868                 {
00869                         $this->log->write('ilTree.deleteTree('.$a_node['child'].') leaving gap open '.$a_node['lft'].'...'.$a_node['rgt']);
00870                 }
00871 
00872                 if($this->__isMainTree())
00873                 {
00874                         ilDBx::_unlockTables();
00875                 }
00876                 // LOCKED ###########################################################
00877         }
00878 
00889         function getPathFull($a_endnode_id, $a_startnode_id = 0)
00890         {
00891                 $pathIds =& $this->getPathId($a_endnode_id, $a_startnode_id);
00892                 $dataPath = array();
00893                 foreach ($pathIds as $id) {
00894                         $dataPath[] = $this->getNodeData($id);
00895                 }
00896 
00897                 return $dataPath;
00898         }
00907         function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
00908         {
00909                 // The nested sets algorithm is very easy to implement.
00910                 // Unfortunately it always does a full table space scan to retrieve the path
00911                 // regardless whether indices on lft and rgt are set or not.
00912                 // (At least, this is what happens on MySQL 4.1).
00913                 // This algorithms performs well for small trees which are deeply nested.
00914                 
00915                 
00916                 if (!isset($a_endnode_id))
00917                 {
00918                         $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
00919                 }
00920                 
00921                 $q = "SELECT T2.child ".
00922                         "FROM ".$this->table_tree." AS T1, ".$this->table_tree." AS T2 ".
00923                         "WHERE T1.child = '".$a_endnode_id."' ".
00924                         "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
00925                         "AND T1.".$this->tree_pk." = '".$this->tree_id." '".
00926                         "AND T2.".$this->tree_pk." = '".$this->tree_id." '".
00927                         "ORDER BY T2.depth";
00928 
00929                 $r = $this->ilDB->query($q);
00930                 $takeId = $a_startnode_id == 0;
00931                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
00932                 {
00933                         if ($takeId || $row['child'] == $a_startnode_id)
00934                         {
00935                                 $takeId = true;
00936                                 $pathIds[] = $row['child'];
00937                         }
00938                 }
00939                 return $pathIds;
00940 
00941         }
00950         function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
00951         {
00952                 // The adjacency map algorithm is harder to implement than the nested sets algorithm.
00953                 // This algorithms performs an index search for each of the path element.
00954                 // This algorithms performs well for large trees which are not deeply nested.
00955 
00956                 // The $takeId variable is used, to determine if a given id shall be included in the path
00957                 $takeId = $a_startnode_id == 0;
00958                 
00959                 if (!isset($a_endnode_id))
00960                 {
00961                         $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
00962                 }
00963                 
00964                 global $log, $ilDB;
00965                 
00966                 // Determine the depth of the endnode, and fetch its parent field also.
00967                 $q = 'SELECT t.depth,t.parent '.
00968                         'FROM '.$this->table_tree.' AS t '.
00969                         'WHERE child='.$this->ilDB->quote($a_endnode_id).' '.
00970                         'AND '.$this->tree_pk.' = '.$this->tree_id.' '.
00971                         'LIMIT 1';
00972                         //$this->writelog('getIdsUsingAdjacencyMap q='.$q);
00973                 $r = $this->ilDB->query($q);
00974                 
00975                 if ($r->numRows() == 0)
00976                 {
00977                         return array();
00978                 }
00979                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
00980                 $nodeDepth = $row['depth'];
00981                 $parentId = $row['parent'];
00982                         //$this->writelog('getIdsUsingAdjacencyMap depth='.$nodeDepth);
00983 
00984                 // Fetch the node ids. For shallow depths we can fill in the id's directly.     
00985                 $pathIds = array();
00986                 if ($nodeDepth == 1)
00987                 {
00988                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
00989                                 if ($takeId) $pathIds[] = $a_endnode_id;
00990                 }
00991                 else if ($nodeDepth == 2)
00992                 {
00993                                 $takeId = $takeId || $parentId == $a_startnode_id;
00994                                 if ($takeId) $pathIds[] = $parentId;
00995                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
00996                                 if ($takeId) $pathIds[] = $a_endnode_id;
00997                 }
00998                 else if ($nodeDepth == 3)
00999                 {
01000                                 $takeId = $takeId || $this->root_id == $a_startnode_id;
01001                                 if ($takeId) $pathIds[] = $this->root_id;
01002                                 $takeId = $takeId || $parentId == $a_startnode_id;
01003                                 if ($takeId) $pathIds[] = $parentId;
01004                                 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01005                                 if ($takeId) $pathIds[] = $a_endnode_id;
01006                 }
01007                 else if ($nodeDepth < 10)
01008                 {
01009                         // The following code construct nested self-joins
01010                         // Since we already know the root-id of the tree and
01011                         // we also know the id and parent id of the current node,
01012                         // we only need to perform $nodeDepth - 3 self-joins. 
01013                         // We can further reduce the number of self-joins by 1
01014                         // by taking into account, that each row in table tree
01015                         // contains the id of itself and of its parent.
01016                         $qSelect = 't1.child as c0';
01017                         $qJoin = '';
01018                         for ($i = 1; $i < $nodeDepth - 2; $i++)
01019                         {
01020                                 $qSelect .= ', t'.$i.'.parent as c'.$i;
01021                                 $qJoin .= ' JOIN '.$this->table_tree.' AS t'.$i.' ON '.
01022                                                         't'.$i.'.child=t'.($i - 1).'.parent AND '.
01023                                                         't'.$i.'.'.$this->tree_pk.' = '.$this->tree_id;
01024                         }
01025                         $q = 'SELECT '.$qSelect.' '.
01026                                 'FROM '.$this->table_tree.' AS t0 '.$qJoin.' '.
01027                                 'WHERE t0.'.$this->tree_pk.' = '.$this->tree_id.' '.
01028                                 'AND t0.child='.$parentId.' '.
01029                                 'LIMIT 1';
01030                         $r = $this->ilDB->query($q);
01031                         if ($r->numRows() == 0)
01032                         {
01033                                 return array();
01034                         }
01035                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01036                         
01037                         $takeId = $takeId || $this->root_id == $a_startnode_id;                 
01038                         if ($takeId) $pathIds[] = $this->root_id;
01039                         for ($i = $nodeDepth - 4; $i >=0; $i--)
01040                         {
01041                                 $takeId = $takeId || $row['c'.$i] == $a_startnode_id;
01042                                 if ($takeId) $pathIds[] = $row['c'.$i];
01043                         }
01044                         $takeId = $takeId || $parentId == $a_startnode_id;
01045                         if ($takeId) $pathIds[] = $parentId;
01046                         $takeId = $takeId || $a_endnode_id == $a_startnode_id;
01047                         if ($takeId) $pathIds[] = $a_endnode_id;
01048                 }
01049                 else
01050                 {
01051                         return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
01052                 }
01053                 
01054                 return $pathIds;
01055         }
01056 
01065         function getPathId($a_endnode_id, $a_startnode_id = 0)
01066         {
01067                 $pathIds =& $this->getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id);
01068                 return $pathIds;
01069         }
01070 
01077         function checkTree()
01078         {
01079                 $q = "SELECT lft,rgt FROM ".$this->table_tree." ".
01080                          "WHERE ".$this->tree_pk." = '".$this->tree_id."'";
01081 
01082                 $r = $this->ilDB->query($q);
01083 
01084                 while ($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01085                 {
01086                         $lft[] = $row->lft;
01087                         $rgt[] = $row->rgt;
01088                 }
01089 
01090                 $all = array_merge($lft,$rgt);
01091                 $uni = array_unique($all);
01092 
01093                 if (count($all) != count($uni))
01094                 {
01095                         $message = sprintf('%s::checkTree(): Tree is corrupted!',
01096                                                            get_class($this));
01097 
01098                         $this->log->write($message,$this->log->FATAL);
01099                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01100                 }
01101 
01102                 return true;
01103         }
01104 
01108         function checkTreeChilds($a_no_zero_child = true)
01109         {
01110                 $q = "SELECT * FROM ".$this->table_tree." ".
01111                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01112                          "ORDER BY lft";
01113                 $r1 = $this->ilDB->query($q);
01114                 while ($row = $r1->fetchRow(DB_FETCHMODE_ASSOC))
01115                 {
01116 //echo "tree:".$row[$this->tree_pk].":lft:".$row["lft"].":rgt:".$row["rgt"].":child:".$row["child"].":<br>";
01117                         if (($row["child"] == 0) && $a_no_zero_child)
01118                         {
01119                                 $this->ilErr->raiseError(get_class($this)."::checkTreeChilds(): Tree contains child with ID 0!",$this->ilErr->WARNING);
01120                         }
01121 
01122                         if ($this->table_obj_reference)
01123                         {
01124                                 // get object reference data
01125                                 $q = "SELECT * FROM ".$this->table_obj_reference." WHERE ".$this->ref_pk."='".$row["child"]."'";
01126                                 $r2 = $this->ilDB->query($q);
01127 //echo "num_childs:".$r2->numRows().":<br>";
01128                                 if ($r2->numRows() == 0)
01129                                 {
01130                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No Object-to-Reference entry found for ID ".
01131                                                 $row["child"]."!",$this->ilErr->WARNING);
01132                                 }
01133                                 if ($r2->numRows() > 1)
01134                                 {
01135                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More Object-to-Reference entries found for ID ".
01136                                                 $row["child"]."!",$this->ilErr->WARNING);
01137                                 }
01138 
01139                                 // get object data
01140                                 $obj_ref = $r2->fetchRow(DB_FETCHMODE_ASSOC);
01141 
01142                                 $q = "SELECT * FROM ".$this->table_obj_data." WHERE ".$this->obj_pk."='".$obj_ref[$this->obj_pk]."'";
01143                                 $r3 = $this->ilDB->query($q);
01144                                 if ($r3->numRows() == 0)
01145                                 {
01146                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
01147                                                 $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
01148                                 }
01149                                 if ($r3->numRows() > 1)
01150                                 {
01151                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
01152                                                 $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
01153                                 }
01154 
01155                         }
01156                         else
01157                         {
01158                                 // get only object data
01159                                 $q = "SELECT * FROM ".$this->table_obj_data." WHERE ".$this->obj_pk."='".$row["child"]."'";
01160                                 $r2 = $this->ilDB->query($q);
01161 //echo "num_childs:".$r2->numRows().":<br>";
01162                                 if ($r2->numRows() == 0)
01163                                 {
01164                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
01165                                                 $row["child"]."!",$this->ilErr->WARNING);
01166                                 }
01167                                 if ($r2->numRows() > 1)
01168                                 {
01169                                         $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
01170                                                 $row["child"]."!",$this->ilErr->WARNING);
01171                                 }
01172                         }
01173                 }
01174 
01175                 return true;
01176         }
01177 
01183         function getMaximumDepth()
01184         {
01185                 $q = "SELECT MAX(depth) FROM ".$this->table_tree;
01186                 $r = $this->ilDB->query($q);
01187 
01188                 $row = $r->fetchRow();
01189 
01190                 return $row[0];
01191         }
01192 
01199         function getDepth($a_node_id)
01200         {
01201                 if ($a_node_id)
01202                 {
01203                         $q = "SELECT depth FROM ".$this->table_tree." ".
01204                                  "WHERE child = '".$a_node_id."' ".
01205                                  "AND ".$this->tree_pk." = '".$this->tree_id."'";
01206 
01207                         $res = $this->ilDB->query($q);
01208                         $row = $res->fetchRow(DB_FETCHMODE_OBJECT);
01209 
01210                         return $row->depth;
01211                 }
01212                 else
01213                 {
01214                         return 1;
01215                 }
01216         }
01217 
01218 
01226         function getNodeData($a_node_id)
01227         {
01228                 if (!isset($a_node_id))
01229                 {
01230                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01231                 }
01232                 if($this->__isMainTree())
01233                 {
01234                         if($a_node_id < 1)
01235                         {
01236                                 $message = sprintf('%s::getNodeData(): No valid parameter given! $a_node_id: %s',
01237                                                                    get_class($this),
01238                                                                    $a_node_id);
01239 
01240                                 $this->log->write($message,$this->log->FATAL);
01241                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01242                         }
01243                 }
01244 
01245                 $q = "SELECT * FROM ".$this->table_tree." ".
01246                          $this->buildJoin().
01247                          "WHERE ".$this->table_tree.".child = ".$this->ilDB->quote($a_node_id)." ".
01248                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01249                 $r = $this->ilDB->query($q);
01250                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01251                 $row[$this->tree_pk] = $this->tree_id;
01252 
01253                 return $this->fetchNodeData($row);
01254         }
01255 
01263         function fetchNodeData($a_row)
01264         {
01265                 global $objDefinition, $lng, $ilBench;
01266 
01267                 //$ilBench->start("Tree", "fetchNodeData_getRow");
01268                 $data = $a_row;
01269                 $data["desc"] = $a_row["description"];  // for compability
01270                 //$ilBench->stop("Tree", "fetchNodeData_getRow");
01271 
01272                 // multilingual support systemobjects (sys) & categories (db)
01273                 //$ilBench->start("Tree", "fetchNodeData_readDefinition");
01274                 if (is_object($objDefinition))
01275                 {
01276                         $translation_type = $objDefinition->getTranslationType($data["type"]);
01277                 }
01278                 //$ilBench->stop("Tree", "fetchNodeData_readDefinition");
01279 
01280                 if ($translation_type == "sys")
01281                 {
01282                         //$ilBench->start("Tree", "fetchNodeData_getLangData");
01283                         if ($data["type"] == "rolf" and $data["obj_id"] != ROLE_FOLDER_ID)
01284                         {
01285                                 $data["description"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
01286                                 $data["desc"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
01287                                 $data["title"] = $lng->txt("obj_".$data["type"]."_local");
01288                         }
01289                         else
01290                         {
01291                                 $data["title"] = $lng->txt("obj_".$data["type"]);
01292                                 $data["description"] = $lng->txt("obj_".$data["type"]."_desc");
01293                                 $data["desc"] = $lng->txt("obj_".$data["type"]."_desc");
01294                         }
01295                         //$ilBench->stop("Tree", "fetchNodeData_getLangData");
01296                 }
01297                 elseif ($translation_type == "db")
01298                 {
01299                         //$ilBench->start("Tree", "fetchNodeData_getTranslation");
01300                         $q = "SELECT title,description FROM object_translation ".
01301                                  "WHERE obj_id = ".$data["obj_id"]." ".
01302                                  "AND lang_code = '".$this->lang_code."' ".
01303                                  "AND NOT lang_default = 1";
01304                         $r = $this->ilDB->query($q);
01305 
01306                         $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01307 
01308                         if ($row)
01309                         {
01310                                 $data["title"] = $row->title;
01311                                 $data["description"] = ilUtil::shortenText($row->description,MAXLENGTH_OBJ_DESC,true);
01312                                 $data["desc"] = $row->description;
01313                         }
01314                         //$ilBench->stop("Tree", "fetchNodeData_getTranslation");
01315                 }
01316 
01317                 return $data ? $data : array();
01318         }
01319 
01320 
01328         function isInTree($a_node_id)
01329         {
01330                 if (!isset($a_node_id))
01331                 {
01332                         return false;
01333                         #$this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01334                 }
01335 
01336                 $q = "SELECT * FROM ".$this->table_tree." ".
01337                          "WHERE ".$this->table_tree.".child = ".$this->ilDB->quote($a_node_id)." ".
01338                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01339                 $r = $this->ilDB->query($q);
01340 
01341                 if ($r->numRows() > 0)
01342                 {
01343                         return true;
01344                 }
01345                 else
01346                 {
01347                         return false;
01348                 }
01349 
01350         }
01351 
01358         function getParentNodeData($a_node_id)
01359         {
01360                 if (!isset($a_node_id))
01361                 {
01362                         $this->ilErr->raiseError(get_class($this)."::getParentNodeData(): No node_id given! ",$this->ilErr->WARNING);
01363                 }
01364 
01365                 if ($this->table_obj_reference)
01366                 {
01367                         $leftjoin = "LEFT JOIN ".$this->table_obj_reference." ON v.child=".$this->table_obj_reference.".".$this->ref_pk." ".
01368                                                 "LEFT JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
01369                 }
01370                 else
01371                 {
01372                         $leftjoin = "LEFT JOIN ".$this->table_obj_data." ON v.child=".$this->table_obj_data.".".$this->obj_pk." ";
01373                 }
01374 
01375                 $q = "SELECT * FROM ".$this->table_tree." s,".$this->table_tree." v ".
01376                          $leftjoin.
01377                          "WHERE s.child = '".$a_node_id."' ".
01378                          "AND s.parent = v.child ".
01379                          "AND s.lft > v.lft ".
01380                          "AND s.rgt < v.rgt ".
01381                          "AND s.".$this->tree_pk." = '".$this->tree_id."' ".
01382                          "AND v.".$this->tree_pk." = '".$this->tree_id."'";
01383                 $r = $this->ilDB->query($q);
01384 
01385                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01386 
01387                 return $this->fetchNodeData($row);
01388         }
01389 
01397         function isGrandChild($a_startnode_id,$a_querynode_id)
01398         {
01399                 if (!isset($a_startnode_id) or !isset($a_querynode_id))
01400                 {
01401                         return false;
01402                         // No raise error, since it is a already a check function
01403                         #$this->ilErr->raiseError(get_class($this)."::isGrandChild(): Missing parameter! startnode: ".$a_startnode_id." querynode: ".
01404                         #                                                $a_querynode_id,$this->ilErr->WARNING);
01405                 }
01406 
01407                 $q = "SELECT * FROM ".$this->table_tree." s,".$this->table_tree." v ".
01408                          "WHERE s.child = '".$a_startnode_id."' ".
01409                          "AND v.child = '".$a_querynode_id."' ".
01410                          "AND s.".$this->tree_pk." = '".$this->tree_id."' ".
01411                          "AND v.".$this->tree_pk." = '".$this->tree_id."' ".
01412                          "AND v.lft BETWEEN s.lft AND s.rgt ".
01413                          "AND v.rgt BETWEEN s.lft AND s.rgt";
01414                 $r = $this->ilDB->query($q);
01415 
01416                 return $r->numRows();
01417         }
01418 
01427         function addTree($a_tree_id,$a_node_id = -1)
01428         {
01429                 // FOR SECURITY addTree() IS NOT ALLOWED ON MAIN TREE
01430                 // IF SOMEONE WILL NEED FEATURES LIKE $tree->addTree(2) ON THE MAIN TREE PLEASE CONTACT ME (smeyer@databay.de)
01431                 if($this->__isMainTree())
01432                 {
01433                         $message = sprintf('%s::addTree(): Operation not allowed on main tree! $a_tree_if: %s $a_node_id: %s',
01434                                                            get_class($this),
01435                                                            $a_tree_id,
01436                                                            $a_node_id);
01437                         $this->log->write($message,$this->log->FATAL);
01438                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01439                 }
01440 
01441                 if (!isset($a_tree_id))
01442                 {
01443                         $this->ilErr->raiseError(get_class($this)."::addTree(): No tree_id given! ",$this->ilErr->WARNING);
01444                 }
01445 
01446                 if ($a_node_id <= 0)
01447                 {
01448                         $a_node_id = $a_tree_id;
01449                 }
01450 
01451                 $q = "INSERT INTO ".$this->table_tree." (".$this->tree_pk.", child, parent, lft, rgt, depth) ".
01452                          "VALUES ".
01453                          "('".$a_tree_id."','".$a_node_id."', 0, 1, 2, 1)";
01454 
01455                 $this->ilDB->query($q);
01456 
01457                 return true;
01458         }
01459 
01467         function getNodeDataByType($a_type)
01468         {
01469                 if (!isset($a_type) or (!is_string($a_type)))
01470                 {
01471                         $this->ilErr->raiseError(get_class($this)."::getNodeDataByType(): Type not given or wrong datatype!",$this->ilErr->WARNING);
01472                 }
01473 
01474                 $data = array();        // node_data
01475                 $row = "";                      // fetched row
01476                 $left = "";                     // tree_left
01477                 $right = "";            // tree_right
01478 
01479                 $q = "SELECT * FROM ".$this->table_tree." ".
01480                          "WHERE ".$this->tree_pk." = '".$this->tree_id."'".
01481                          "AND parent = '0'";
01482                 $r = $this->ilDB->query($q);
01483 
01484                 while ($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01485                 {
01486                         $left = $row->lft;
01487                         $right = $row->rgt;
01488                 }
01489 
01490                 $q = "SELECT * FROM ".$this->table_tree." ".
01491                          $this->buildJoin().
01492                          "WHERE ".$this->table_obj_data.".type = '".$a_type."' ".
01493                          "AND ".$this->table_tree.".lft BETWEEN '".$left."' AND '".$right."' ".
01494                          "AND ".$this->table_tree.".rgt BETWEEN '".$left."' AND '".$right."' ".
01495                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01496                 $r = $this->ilDB->query($q);
01497 
01498                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01499                 {
01500                         $data[] = $this->fetchNodeData($row);
01501                 }
01502 
01503                 return $data;
01504         }
01505 
01513         function removeTree($a_tree_id)
01514         {
01515                 // OPERATION NOT ALLOWED ON MAIN TREE
01516                 if($this->__isMainTree())
01517                 {
01518                         $message = sprintf('%s::removeTree(): Operation not allowed on main tree! $a_tree_if: %s',
01519                                                            get_class($this),
01520                                                            $a_tree_id);
01521                         $this->log->write($message,$this->log->FATAL);
01522                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01523                 }
01524                 if (!$a_tree_id)
01525                 {
01526                         $this->ilErr->raiseError(get_class($this)."::removeTree(): No tree_id given! Action aborted",$this->ilErr->MESSAGE);
01527                 }
01528 
01529                 $q = "DELETE FROM ".$this->table_tree." WHERE ".$this->tree_pk." = '".$a_tree_id."'";
01530                 $this->ilDB->query($q);
01531 
01532                 return true;
01533         }
01534 
01542         function saveSubTree($a_node_id, $a_set_deleted = false)
01543         {
01544                 if (!$a_node_id)
01545                 {
01546                         $message = sprintf('%s::saveSubTree(): No valid parameter given! $a_node_id: %s',
01547                                                            get_class($this),
01548                                                            $a_node_id);
01549                         $this->log->write($message,$this->log->FATAL);
01550                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01551                 }
01552 
01553                 // LOCKED ###############################################
01554                 if($this->__isMainTree())
01555                 {
01556                         ilDBx::_lockTables(array('tree' => 'WRITE',
01557                                 'object_reference' => 'WRITE'));
01558                 }
01559 
01560                 // GET LEFT AND RIGHT VALUE
01561                 $q = "SELECT * FROM ".$this->table_tree." ".
01562                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01563                          "AND child = '".$a_node_id."' ";
01564                 $r = $this->ilDB->query($q);
01565 
01566                 while($row = $r->fetchRow(DB_FETCHMODE_OBJECT))
01567                 {
01568                         $lft = $row->lft;
01569                         $rgt = $row->rgt;
01570                 }
01571 
01572                 // GET ALL SUBNODES
01573                 $q = "SELECT * FROM ".$this->table_tree." ".
01574                          "WHERE ".$this->tree_pk." = '".$this->tree_id."' ".
01575                          "AND lft BETWEEN '".$lft."' AND '".$rgt."'";
01576                 $r = $this->ilDB->query($q);
01577 
01578                 while($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01579                 {
01580                         $subnodes[$row["child"]] = $this->fetchNodeData($row);
01581                 }
01582 
01583                 // SAVE SUBTREE
01584                 foreach($subnodes as $node)
01585                 {
01586                         $q = "INSERT INTO ".$this->table_tree." ".
01587                                  "VALUES ('".-$a_node_id."','".$node["child"]."','".$node["parent"]."','".
01588                                  $node["lft"]."','".$node["rgt"]."','".$node["depth"]."')";
01589                         $r = $this->ilDB->query($q);
01590                         
01591                         // set node as deleted
01592                         if ($a_set_deleted)
01593                         {
01594                                 ilObject::_setDeletedDate($node["child"]);
01595                         }
01596                 }
01597                 if($this->__isMainTree())
01598                 {
01599                         ilDBX::_unlockTables();
01600                 }
01601 
01602                 // LOCKED ###############################################
01603                 return true;
01604         }
01605 
01609         function isDeleted($a_node_id)
01610         {
01611                 return $this->isSaved($a_node_id);
01612         }
01613 
01617         function isSaved($a_node_id)
01618         {
01619                 $q = "SELECT * FROM ".$this->table_tree." ".
01620                          "WHERE child = '".$a_node_id."'";
01621                 $s = $this->ilDB->query($q);
01622                 $r = $s->fetchRow(DB_FETCHMODE_ASSOC);
01623 
01624                 if ($r[$this->tree_pk] < 0)
01625                 {
01626                         return true;
01627                 }
01628                 else
01629                 {
01630                         return false;
01631                 }
01632         }
01633 
01634 
01648         function saveNode($a_node_id,$a_parent_id)
01649         {
01650                 if($this->__isMainTree())
01651                 {
01652                         if($a_node_id <= 1 or $a_parent_id <= 0)
01653                         {
01654                                 $message = sprintf('%s::saveSubTree(): No valid parameter given! $a_node_id: %s $a_parent_id: %s',
01655                                                                    get_class($this),
01656                                                                    $a_node_id,
01657                                                                    $a_parent_id);
01658 
01659                                 $this->log->write($message,$this->log->FATAL);
01660                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
01661                         }
01662                 }
01663                 if ($a_node_id < 1 or !isset($a_parent_id))
01664                 {
01665                         $this->ilErr->raiseError(get_class($this)."::saveNode(): Missing parameter! ".
01666                                                                          "node_id: ".$a_node_id." parent_id: ".$a_parent_id,$this->ilErr->WARNING);
01667                 }
01668 
01669                 // SAVE NODE
01670                 $q = "INSERT INTO ".$this->table_tree." ".
01671                          "VALUES ('".-$a_node_id."','".$a_node_id."','".$a_parent_id."','1','2','1')";
01672                 $r = $this->ilDB->query($q);
01673 
01674                 return true;
01675         }
01676 
01683         function getSavedNodeData($a_parent_id)
01684         {
01685                 if (!isset($a_parent_id))
01686                 {
01687                         $this->ilErr->raiseError(get_class($this)."::getSavedNodeData(): No node_id given!",$this->ilErr->WARNING);
01688                 }
01689 
01690                 $q =    "SELECT * FROM ".$this->table_tree." ".
01691                                 $this->buildJoin().
01692                                 "WHERE ".$this->table_tree.".".$this->tree_pk." < 0 ".
01693                                 "AND ".$this->table_tree.".parent = '".$a_parent_id."' ";
01694                 $r = $this->ilDB->query($q);
01695 
01696                 while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
01697                 {
01698                         $saved[] = $this->fetchNodeData($row);
01699                 }
01700 
01701                 return $saved ? $saved : array();
01702         }
01703 
01710         function getParentId($a_node_id)
01711         {
01712                 if (!isset($a_node_id))
01713                 {
01714                         $this->ilErr->raiseError(get_class($this)."::getParentId(): No node_id given! ",$this->ilErr->WARNING);
01715                 }
01716 
01717                 $q = "SELECT parent FROM ".$this->table_tree." ".
01718                          "WHERE child='".$a_node_id."' ".
01719                          "AND ".$this->tree_pk."='".$this->tree_id."'";
01720                 $r = $this->ilDB->query($q);
01721 
01722                 $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01723 
01724                 return $row->parent;
01725         }
01726 
01733         function getLeftValue($a_node_id)
01734         {
01735                 if (!isset($a_node_id))
01736                 {
01737                         $this->ilErr->raiseError(get_class($this)."::getLeftValued(): No node_id given! ",$this->ilErr->WARNING);
01738                 }
01739 
01740                 $q = "SELECT lft FROM ".$this->table_tree." ".
01741                          "WHERE child='".$a_node_id."' ".
01742                          "AND ".$this->tree_pk."='".$this->tree_id."'";
01743                 $r = $this->ilDB->query($q);
01744 
01745                 $row = $r->fetchRow(DB_FETCHMODE_OBJECT);
01746 
01747                 return $row->lft;
01748         }
01749 
01756         function getChildSequenceNumber($a_node, $type = "")
01757         {
01758                 if (!isset($a_node))
01759                 {
01760                         $this->ilErr->raiseError(get_class($this)."::getChildSequenceNumber(): No node_id given! ",$this->ilErr->WARNING);
01761                 }
01762 
01763                 $type_str = ($type != "")
01764                         ? "AND type='$type'"
01765                         : "";
01766 
01767                 $q = "SELECT count(*) AS cnt FROM ".$this->table_tree." ".
01768                         $this->buildJoin().
01769                         "WHERE lft <=".$this->ilDB->quote($a_node["lft"])." ".
01770                         $type_str.
01771                         "AND parent=".$this->ilDB->quote($a_node["parent"])." ".
01772                         "AND ".$this->table_tree.".".$this->tree_pk."=".$this->ilDB->quote($this->tree_id);
01773                 $r = $this->ilDB->query($q);
01774 
01775                 $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01776 
01777                 return $row["cnt"];
01778         }
01779 
01786         function readRootId()
01787         {
01788                 $query = "SELECT child FROM $this->table_tree ".
01789                         "WHERE parent = '0'".
01790                         "AND ".$this->tree_pk." = '".$this->tree_id."'";
01791                 $row = $this->ilDB->getRow($query,DB_FETCHMODE_OBJECT);
01792 
01793                 $this->root_id = $row->child;
01794                 return $this->root_id;
01795         }
01796 
01802         function getRootId()
01803         {
01804                 return $this->root_id;
01805         }
01806         function setRootId($a_root_id)
01807         {
01808                 $this->root_id = $a_root_id;
01809         }
01810 
01816         function getTreeId()
01817         {
01818                 return $this->tree_id;
01819         }
01820 
01826         function setTreeId($a_tree_id)
01827         {
01828                 $this->tree_id = $a_tree_id;
01829         }
01830 
01838         function fetchSuccessorNode($a_node_id, $a_type = "")
01839         {
01840                 if (!isset($a_node_id))
01841                 {
01842                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01843                 }
01844 
01845                 // get lft value for current node
01846                 $q = "SELECT lft FROM ".$this->table_tree." ".
01847                          "WHERE ".$this->table_tree.".child = '".$a_node_id."' ".
01848                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01849                 $r = $this->ilDB->query($q);
01850                 $curr_node = $r->fetchRow(DB_FETCHMODE_ASSOC);
01851 
01852                 // get data of successor node
01853                 $type_where = ($a_type != "")
01854                         ? "AND ".$this->table_obj_data.".type = '$a_type' "
01855                         : "";
01856                 $q = "SELECT * FROM ".$this->table_tree." ".
01857                          $this->buildJoin().
01858                          "WHERE lft > '".$curr_node["lft"]."' ".
01859                          $type_where.
01860                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'".
01861                          "ORDER BY lft LIMIT 1";
01862                 $r = $this->ilDB->query($q);
01863 
01864                 if ($r->numRows() < 1)
01865                 {
01866                         return false;
01867                 }
01868                 else
01869                 {
01870                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01871                         return $this->fetchNodeData($row);
01872                 }
01873         }
01874 
01882         function fetchPredecessorNode($a_node_id, $a_type = "")
01883         {
01884                 if (!isset($a_node_id))
01885                 {
01886                         $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
01887                 }
01888 
01889                 // get lft value for current node
01890                 $q = "SELECT lft FROM ".$this->table_tree." ".
01891                          "WHERE ".$this->table_tree.".child = '".$a_node_id."' ".
01892                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'";
01893                 $r = $this->ilDB->query($q);
01894                 $curr_node = $r->fetchRow(DB_FETCHMODE_ASSOC);
01895 
01896                 // get data of predecessor node
01897                 $type_where = ($a_type != "")
01898                         ? "AND ".$this->table_obj_data.".type = '$a_type' "
01899                         : "";
01900                 $q = "SELECT * FROM ".$this->table_tree." ".
01901                          $this->buildJoin().
01902                          "WHERE lft < '".$curr_node["lft"]."' ".
01903                          $type_where.
01904                          "AND ".$this->table_tree.".".$this->tree_pk." = '".$this->tree_id."'".
01905                          "ORDER BY lft DESC LIMIT 1";
01906                 $r = $this->ilDB->query($q);
01907 
01908                 if ($r->numRows() < 1)
01909                 {
01910                         return false;
01911                 }
01912                 else
01913                 {
01914                         $row = $r->fetchRow(DB_FETCHMODE_ASSOC);
01915                         return $this->fetchNodeData($row);
01916                 }
01917         }
01918 
01927         function renumber($node_id = 1, $i = 1)
01928         {
01929                 // LOCKED ###################################
01930                 if($this->__isMainTree())
01931                 {
01932                         ilDBx::_lockTables(array($this->table_tree => 'WRITE',
01933                                                                          $this->table_obj_data => 'WRITE',
01934                                                                          $this->table_obj_reference => 'WRITE',
01935                                                                          'object_translation' => 'WRITE'));
01936                 }
01937                 $return = $this->__renumber($node_id,$i);
01938                 if($this->__isMainTree())
01939                 {
01940                         ilDBx::_unlockTables();
01941                 }
01942                 // LOCKED ###################################
01943                 return $return;
01944         }
01945 
01946         // PRIVATE
01956         function __renumber($node_id = 1, $i = 1)
01957         {
01958                 $q = "UPDATE ".$this->table_tree." SET lft='".$i."' WHERE child='".$node_id."'";
01959                 $this->ilDB->query($q);
01960 
01961                 $childs = $this->getChilds($node_id);
01962 
01963                 foreach ($childs as $child)
01964                 {
01965                         $i = $this->__renumber($child["child"],$i+1);
01966                 }
01967 
01968                 $i++;
01969                 
01970                 // Insert a gap at the end of node, if the node has children
01971                 if (count($childs) > 0)
01972                 {
01973                         $i += $this->gap * 2;
01974                 }
01975                 
01976                 $q = "UPDATE ".$this->table_tree." SET rgt='".$i."' WHERE child='".$node_id."'";
01977                 $this->ilDB->query($q);
01978 
01979                 return $i;
01980         }
01981 
01982 
01992         function checkForParentType($a_ref_id,$a_type)
01993         {
01994                 if(!$this->isInTree($a_ref_id))
01995                 {
01996                         return false;
01997                 }
01998                 $path = array_reverse($this->getPathFull($a_ref_id));
01999 
02000                 foreach($path as $node)
02001                 {
02002                         if($node["type"] == $a_type)
02003                         {
02004                                 return $node["child"];
02005                         }
02006                 }
02007                 return 0;
02008         }
02009 
02019         function _removeEntry($a_tree,$a_child,$a_db_table = "tree")
02020         {
02021                 global $ilDB,$ilLog,$ilErr;
02022 
02023                 if($a_db_table === 'tree')
02024                 {
02025                         if($a_tree == 1 and $a_child == ROOT_FOLDER_ID)
02026                         {
02027                                 $message = sprintf('%s::_removeEntry(): Tried to delete root node! $a_tree: %s $a_child: %s',
02028                                                                    get_class($this),
02029                                                                    $a_tree,
02030                                                                    $a_child);
02031                                 $ilLog->write($message,$ilLog->FATAL);
02032                                 $ilErr->raiseError($message,$ilErr->WARNING);
02033                         }
02034                 }
02035 
02036                 $q = "DELETE from ".$a_db_table." WHERE tree='".$a_tree."' AND child='".$a_child."'";
02037                 $ilDB->query($q);
02038         }
02039 
02040         // PRIVATE METHODS
02047         function __isMainTree()
02048         {
02049                 return $this->table_tree === 'tree';
02050         }
02051 
02060         function __checkDelete($a_node)
02061         {
02062                 // get subtree by lft,rgt
02063                 $query = "SELECT * FROM ".$this->table_tree." ".
02064                         "WHERE lft >= ".$a_node['lft']." ".
02065                         "AND rgt <= ".$a_node['rgt']." ".
02066                         "AND ".$this->tree_pk." = '".$a_node[$this->tree_pk]."'";
02067 
02068 
02069                 $res = $this->ilDB->query($query);
02070 
02071                 $counter = (int) $lft_childs = array();
02072                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02073                 {
02074                         $lft_childs[$row->child] = $row->parent;
02075                         ++$counter;
02076                 }
02077 
02078                 // CHECK FOR DUPLICATE CHILD IDS
02079                 if($counter != count($lft_childs))
02080                 {
02081                         $message = sprintf('%s::__checkTree(): Duplicate entries for "child" in maintree! $a_node_id: %s',
02082                                                                    get_class($this),
02083                                                            $a_node['child']);
02084                         $this->log->write($message,$this->log->FATAL);
02085                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02086                 }
02087 
02088                 // GET SUBTREE BY PARENT RELATION
02089                 $parent_childs = array();
02090                 $this->__getSubTreeByParentRelation($a_node['child'],$parent_childs);
02091                 $this->__validateSubtrees($lft_childs,$parent_childs);
02092 
02093                 return true;
02094         }
02095 
02096         function __getSubTreeByParentRelation($a_node_id,&$parent_childs)
02097         {
02098                 // GET PARENT ID
02099                 $query = "SELECT * FROM ".$this->table_tree." ".
02100                         "WHERE child = '".$a_node_id."' ".
02101                         "AND tree = '".$this->tree_id."'";
02102 
02103                 $res = $this->ilDB->query($query);
02104                 $counter = 0;
02105                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02106                 {
02107                         $parent_childs[$a_node_id] = $row->parent;
02108                         ++$counter;
02109                 }
02110                 // MULTIPLE ENTRIES
02111                 if($counter > 1)
02112                 {
02113                         $message = sprintf('%s::__getSubTreeByParentRelation(): Multiple entries in maintree! $a_node_id: %s',
02114                                                            get_class($this),
02115                                                            $a_node_id);
02116                         $this->log->write($message,$this->log->FATAL);
02117                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02118                 }
02119 
02120                 // GET ALL CHILDS
02121                 $query = "SELECT * FROM ".$this->table_tree." ".
02122                         "WHERE parent = '".$a_node_id."'";
02123 
02124                 $res = $this->ilDB->query($query);
02125                 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
02126                 {
02127                         // RECURSION
02128                         $this->__getSubTreeByParentRelation($row->child,$parent_childs);
02129                 }
02130                 return true;
02131         }
02132 
02133         function __validateSubtrees(&$lft_childs,$parent_childs)
02134         {
02135                 // SORT BY KEY
02136                 ksort($lft_childs);
02137                 ksort($parent_childs);
02138 
02139                 if(count($lft_childs) != count($parent_childs))
02140                 {
02141                         $message = sprintf('%s::__validateSubtrees(): (COUNT) Tree is corrupted! Left/Right subtree does not comply .'.
02142                                                            'with parent relation',
02143                                                            get_class($this));
02144                         $this->log->write($message,$this->log->FATAL);
02145                         $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02146                 }
02147 
02148                 foreach($lft_childs as $key => $value)
02149                 {
02150                         if($parent_childs[$key] != $value)
02151                         {
02152                                 $message = sprintf('%s::__validateSubtrees(): (COMPARE) Tree is corrupted! Left/Right subtree does not comply '.
02153                                                                    'with parent relation',
02154                                                                    get_class($this));
02155                                 $this->log->write($message,$this->log->FATAL);
02156                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02157                         }
02158                         if($key == ROOT_FOLDER_ID)
02159                         {
02160                                 $message = sprintf('%s::__validateSubtrees(): (ROOT_FOLDER) Tree is corrupted! Tried to delete root folder',
02161                                                                    get_class($this));
02162                                 $this->log->write($message,$this->log->FATAL);
02163                                 $this->ilErr->raiseError($message,$this->ilErr->WARNING);
02164                         }
02165                 }
02166                 return true;
02167         }
02168 
02169 } // END class.tree
02170 ?>