diff options
Diffstat (limited to 'lib/classes/TreeAbstract.php')
| -rw-r--r-- | lib/classes/TreeAbstract.php | 431 |
1 files changed, 431 insertions, 0 deletions
diff --git a/lib/classes/TreeAbstract.php b/lib/classes/TreeAbstract.php new file mode 100644 index 0000000..a1413b3 --- /dev/null +++ b/lib/classes/TreeAbstract.php @@ -0,0 +1,431 @@ +<?php +# Lifter002: TODO +# Lifter007: TODO +# Lifter003: TODO +# Lifter010: TODO +// +---------------------------------------------------------------------------+ +// This file is part of Stud.IP +// TreeAbstract.php +// Abstract Base Class to handle in-memory tree structures +// +// Copyright (c) 2002 André Noack <noack@data-quest.de> +// Suchi & Berg GmbH <info@data-quest.de> +// +---------------------------------------------------------------------------+ +// This program is free software; you can redistribute it and/or +// modify it under the terms of the GNU General Public License +// as published by the Free Software Foundation; either version 2 +// of the License, or any later version. +// +---------------------------------------------------------------------------+ +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +---------------------------------------------------------------------------+ + + +/** +* Abstract Base Class to handle in-memory tree structures +* +* This class provides an interface to basic handling of structure of tree structures +* +* @access public +* @author André Noack <noack@data-quest.de> +* @package +*/ +class TreeAbstract { + + /** + * the name of the root element + * + * @access private + * @var string $root_name + */ + var $root_name; + /** + * object to handle database queries + * + * @access private + * @var object DbView $view + */ + var $view; + /** + * array containing all tree items + * + * associative array, key is an unique identifier (eg primary key from DB table) + * value is another assoc. array containing the other fieldname/fieldvalue pairs + * these fieldnames must be used : + * parent_id, name, priority + * @access public + * @var array $tree_data + */ + var $tree_data = []; + /** + * array containing the direct childs of all items + * + * assoc. array, key is one from $tree_data, value is numeric array with keys from childs + * @access private + * @var array $tree_childs + */ + var $tree_childs = []; + + /** + * array containing the number of direct childs of all items + * + * assoc. array, key is one from $tree_data + * @access private + * @var array $tree_num_childs + */ + var $tree_num_childs = []; + + var $index_offset = 0; + + /** + * static method used to ensure that only one instance exists + * + * use this method if you need a reference to the tree object <br> + * usage: <pre>$my_tree = StudipRangeTree::GetInstance("name_of_tree_class")</pre> + * + * @param string $class_name the name of the used tree_class + * @param mixed $args argumentlist passed to the constructor in the tree_class (if needed) + * @return mixed always an object, type is one of AbstractTree s childclasses + */ + public static function GetInstance($class_name, $args = null, $invalidate_cache = false) + { + static $tree_instance; + $class_hash = ''; + if ($args){ + $class_hash = $class_name . "_" . md5(serialize($args)); + } elseif ($args === false && is_array($tree_instance)){ + foreach ($tree_instance as $key => $value){ + $tmp_name = explode("_",$key); + if ($tmp_name[0] == $class_name){ + $class_hash = $key; + break; + } + } + if (!$class_hash){ + $class_hash = $class_name; + } + } else { + $class_hash = $class_name; + } + if (empty($tree_instance[$class_hash]) || $invalidate_cache){ + $tree_instance[$class_hash] = new $class_name($args); + } + + return $tree_instance[$class_hash]; + } + + /** + * constructor + * + * do not use directly, call &GetInstance() + */ + protected function __construct() + { + $this->view = new DbView(); + $this->init(); + } + + /** + * initializes the tree + * + * stores all tree items in array $tree_data + * must be overriden + */ + public function init() + { + $this->tree_childs = []; + $this->tree_num_childs = []; + $this->tree_data = []; + $this->index_offset = 0; + $this->tree_data['root'] = ['parent_id' => null, 'name' => &$this->root_name, 'index' => 0]; + } + + /** + * store one item in tree_data array + * + * store one item in tree_data array + * + * @param string $item_id + * @param string $parent_id + * @param string $name + * @param integer $priority + * + */ + public function storeItem($item_id,$parent_id,$name,$priority) + { + $this->tree_data[$item_id]["parent_id"] = $parent_id; + $this->tree_data[$item_id]["priority"] = $priority; + $this->tree_data[$item_id]["name"] = $name; + $this->tree_childs[$parent_id][] = $item_id; + if (empty($this->tree_num_childs[$parent_id])) { + $this->tree_num_childs[$parent_id] = 0; + } + $this->tree_num_childs[$parent_id]++; + return; + } + + /** + * build an index for sorting purpose + * + * build an index for sorting purpose + * + * @param string $item_id + * + */ + public function buildIndex($item_id = false) + { + if ($item_id === false && $this->index_offset > 0) { + return; + } + if (!$item_id) { + $item_id = "root"; + } + $this->tree_data[$item_id]['index'] = $this->index_offset; + ++$this->index_offset; + if (($num_kids = $this->getNumKids($item_id))) { + for($i = 0; $i < $num_kids; ++$i){ + $this->buildIndex($this->tree_childs[$item_id][$i]); + } + } + return; + } + + /** + * returns all direct kids + * + * @param string $item_id + * @return array + */ + public function getKids($item_id) + { + return (isset($this->tree_childs[$item_id]) && is_array($this->tree_childs[$item_id])) ? $this->tree_childs[$item_id] : []; + } + + /** + * returns the number of all direct kids + * + * @param string $item_id + * @param bool $in_recursion + * @return int + */ + public function getNumKids($item_id) + { + if(!isset($this->tree_num_childs[$item_id])){ + $this->tree_num_childs[$item_id] = (!empty($this->tree_childs[$item_id]) && is_array($this->tree_childs[$item_id])) ? count($this->tree_childs[$item_id]) : 0; + } + return $this->tree_num_childs[$item_id]; + } + + /** + * returns all direct kids and kids of kids and so on... + * + * @param string $item_id + * @param bool $in_recursion only used in recursion + * @return array + */ + public function getKidsKids($item_id, $in_recursion = false) + { + static $kidskids; + if (!$kidskids || !$in_recursion){ + $kidskids = []; + } + $num_kids = $this->getNumKids($item_id); + if ($num_kids){ + $kids = $this->getKids($item_id); + $kidskids = array_merge((array)$kidskids, (array)$kids); + for ($i = 0; $i < $num_kids; ++$i){ + $this->getKidsKids($kids[$i],true); + } + } + return (!$in_recursion) ? $kidskids : []; + } + + /** + * returns the number of all kids and kidskids... + * + * @param string $item_id + * @param bool $in_recursion + * @return int + */ + public function getNumKidsKids($item_id, $in_recursion = false) + { + static $num_kidskids; + if (!$num_kidskids || !$in_recursion){ + $num_kidskids = 0; + } + $num_kids = $this->getNumKids($item_id); + if ($num_kids){ + $kids = $this->getKids($item_id); + $num_kidskids += $num_kids; + for ($i = 0; $i < $num_kids; ++$i){ + $this->getNumKidsKids($kids[$i],true); + } + } + return (!$in_recursion) ? $num_kidskids : 0; + } + + /** + * checks if item is the last kid + * + * @param string $item_id + * @return boolean + */ + public function isLastKid($item_id) + { + $parent_id = $this->tree_data[$item_id]['parent_id']; + $num_kids = $this->getNumKids($parent_id); + if (!$parent_id || !$num_kids) { + return false; + } + return $this->tree_childs[$parent_id][$num_kids-1] == $item_id; + } + + /** + * checks if item is the first kid + * + * @param string $item_id + * @return boolean + */ + public function isFirstKid($item_id) + { + $parent_id = $this->tree_data[$item_id]['parent_id']; + $num_kids = $this->getNumKids($parent_id); + if (!$parent_id || !$num_kids) { + return false; + } + return $this->tree_childs[$parent_id][0] == $item_id; + } + + /** + * checks if given item is a kid or kidkid...of given ancestor + * + * checks if given item is a kid or kidkid...of given ancestor + * + * @param string $ancestor_id + * @param string $item_id + * @return boolean + */ + public function isChildOf($ancestor_id,$item_id) + { + return in_array($item_id,$this->getKidsKids($ancestor_id)); + } + + /** + * checks if item has one or more kids + * + * @param string $item_id + * @return boolean + */ + public function hasKids($item_id) + { + return $this->getNumKids($item_id) > 0; + } + + /** + * Returns tree path + * + * returns a string with the item and all parents separated with a slash + * + * @param string $item_id + * @return string + */ + public function getItemPath($item_id) + { + if (!$this->tree_data[$item_id]) { + return false; + } + + $path = $this->tree_data[$item_id]['name']; + while($item_id && $item_id !== 'root') { + $item_id = $this->tree_data[$item_id]['parent_id']; + $path = $this->tree_data[$item_id]['name'] . " / " . $path; + } + return $path; + } + + /** + * Returns tree path as array of item_id s + * + * returns an array containing all parents of given item + * + * @param string $item_id + * @return array + */ + public function getParents($item_id) + { + if (empty($this->tree_data[$item_id])) { + return []; + } + + $result = []; + while ($item_id && $item_id !== 'root') { + $item_id = $this->tree_data[$item_id]['parent_id']; + $result[] = $item_id; + } + return $result; + } + + public function getShortPath($item_id, $length = null, $delimeter = ">", $offset = 0) + { + if (!$this->tree_data[$item_id] || $item_id === 'root') { + return false; + } + $parents = array_reverse($this->getParents($item_id)); + array_shift($parents); + array_push($parents, $item_id); + $that = $this; + $parents_names = array_map(function($i) use ($that) {return $that->tree_data[$i]['name'];}, array_slice($parents, $offset, $length ? $length : null)); + return join(" $delimeter ", $parents_names); + } + + /** + * Returns the maximum priority value from a parents child + * + * @param string $parent_id + * @return int + */ + public function getMaxPriority($parent_id) + { + $children = $this->getKids($parent_id); + $last = $this->getNumKids($parent_id) - 1; + return (int) $this->tree_data[$children[$last]]['priority']; + } + + public function getNumEntries($item_id, $num_entries_from_kids = false) + { + if (!$num_entries_from_kids || !$this->hasKids($item_id)){ + return $this->tree_data[$item_id]["entries"]; + } else { + return $this->getNumEntriesKids($item_id); + } + } + + public function getNumEntriesKids($item_id, $in_recursion = false) + { + static $num_entries; + if (!$in_recursion){ + $num_entries = 0; + } + $num_entries += $this->tree_data[$item_id]["entries"]; + $num_kids = $this->getNumKids($item_id); + if ($num_kids){ + $kids = $this->getKids($item_id); + for ($i = 0; $i < $num_kids; ++$i){ + $this->getNumEntriesKids($kids[$i],true); + } + } + return (!$in_recursion) ? $num_entries : null; + } + + public function getValue($item_id, $field) + { + return isset($this->tree_data[$item_id][$field]) + ? $this->tree_data[$item_id][$field] + : null; + } +} |