<?php
/**
?* Tanphp framework
?*
?*
?* @category?? Tanphp
?* @package??? Data_structure
?* @version??? $Id: Tree.php 25024 2012-11-26 22:22:22 tanbo $
?*/
?
/**
?* 樹(shù)形結(jié)構(gòu)數(shù)據(jù)存取類
?*?
?* 用于對(duì)樹(shù)形結(jié)構(gòu)數(shù)據(jù)進(jìn)行快速的存取
?*?
?* @param array $arr 參數(shù)必須為標(biāo)準(zhǔn)的二維數(shù)組,包含索引字段(id)與表示樹(shù)形結(jié)構(gòu)的字段(path),如example中所示
?*?
?* @example <code>
?* $arr = array(
?*? array( 'id' => 1, 'name' => 'php', 'path' => '1' ),
?*? array( 'id' => 3, 'name' => 'php1', 'path' => '1-3' ),
?*? array( 'id' => 2, 'name' => 'mysql', 'path' => '2' ),
?*? array( 'id' => 6, 'name' => 'mysql1', 'path' => '2-6' ),
?*? array( 'id' => 7, 'name' => 'mysql2', 'path' => '2-7' ),
?*? array( 'id' => 5, 'name' => 'php11', 'path' => '1-3-5' ),
?*? array( 'id' => 4, 'name' => 'php2', 'path' => '1-4' ),
?*?? );
?*? $cate = new Tree($arr);
?*??
?*? $data = $cate->getChild(2);
?*??
?*? print_r($data->toArray());
?* </code>
?*?
?*/
class Tree
{
??? public? $_info;???????????????????????????? //節(jié)點(diǎn)信息
??? public? $_child = array();????????????????? //子節(jié)點(diǎn)
??? private $_parent;?????????????????????????? //父節(jié)點(diǎn)
??? private $_data;???????????????????????????? //當(dāng)前操作的臨時(shí)數(shù)據(jù)
??? private static $_indexs???????? = array();? //所有節(jié)點(diǎn)的索引
??? private static $_index_key????? = 'id';???? //索引鍵
??? private static $_tree_key?????? = 'path';?? //樹(shù)形結(jié)構(gòu)表達(dá)鍵
??? private static $_tree_delimiter = '-';????? //屬性結(jié)構(gòu)表達(dá)分割符
????
??? /**
???? * 構(gòu)造函數(shù)
???? *?
???? * @param array $arr
???? * @param boole $force_sort 如果為真,將會(huì)強(qiáng)制對(duì)$arr 進(jìn)行排序
???? * @return void
???? */
??? public function __construct(array $arr = array(),? $force_sort=true)
??? {
??????? if ($force_sort === true) {
??????????? $arr=$this->_array_sort($arr, self::$_tree_key);
??????? }
??????? if (!emptyempty($arr)) {
??????????? $this->_init($arr);
??????? }
??? }
????
??? /**
???? * 初始存儲(chǔ)樹(shù)形數(shù)據(jù)
???? *?
???? * @param array $arr
???? * @return void
???? */
??? private function _init(array $arr)
??? {
??????? foreach ($arr as $item) {
??????????? $path??????? = $item[self::$_tree_key];
??????????? $paths?????? = explode(self::$_tree_delimiter, $path);
??????????? $count_paths = count($paths);
??????????? $parent_id?? = isset($paths[$count_paths-2]) ? $paths[$count_paths-2] : NULL;
????????????
??????????? if (?? $count_paths>1?????????????????????????????????? //如果有父級(jí)
??????????????? && array_key_exists($parent_id, self::$_indexs)????? //父級(jí)已經(jīng)被存入索引
??????????????? && self::$_indexs[$parent_id] instanceof Tree??? //父級(jí)為Tree對(duì)象
??????????? ) {
??????????????? self::$_indexs[$parent_id]->addChild($item);
??????????? } elseif ($count_paths == 1) {
??????????????? $this->addChild($item);
??????????? } else {
??????????????? throw new Exception("path數(shù)據(jù)錯(cuò)誤".var_export($item, true));
??????????? }
??????? }
????????
??????? //print_r(self::$_indexs);
??? }
????
??? /**
???? * 添加子節(jié)點(diǎn)
???? *?
???? * @param array $item
???? * @return void
???? */
??? public function addChild(array $item, $parent = NULL)
??? {
??????? $child????????? = new Tree();
??????? $child->_info?? = $item;
??????? $child->_parent = $parent == NULL ? $this : $parent;
??????? $child->_parent->_child[] =? $child;
????????
??????? $this->_addIndex($item, $child->_getSelf());?
??? }
????
??? /**
???? * 添加節(jié)點(diǎn)到索引
???? *?
???? * @param array $item
???? * @param mix $value
???? * @return void
???? */
??? private function _addIndex(array $item, $value)
??? {
??????? if (array_key_exists(self::$_index_key, $item) && is_int($item[self::$_index_key])) {
??????????? self::$_indexs[$item[self::$_index_key]] = $value;
??????? } else {
??????????? throw new Exception("id字段不存在或者不為字符串");
??????? }
??? }
????
??? /**
???? * 獲取對(duì)自己的引用
???? *?
???? * @return Tree object quote
???? */
??? private function _getSelf()
??? {
??????? return $this;
??? }
????
??? /**
???? * 獲取指定id的節(jié)點(diǎn)的子節(jié)點(diǎn)
???? *?
???? * @param int $id
???? * @return Tree object
???? */
??? public function getChild($id)
??? {
??????? $data?????? = self::$_indexs[$id]->_child;
??????? $this->_data = $data;
??????? return $this;
??? }
????
??? /**
???? * 獲取指定id的節(jié)點(diǎn)的父節(jié)點(diǎn)
???? *?
???? * @param int $id
???? * @return Tree object
???? */
??? public function getParent($id)
??? {
??????? $data = self::$_indexs[$id]->_parent;
??????? $this->_data = $data;
??????? return $this;
??? }
????
??? /**
???? * 獲取指定id的節(jié)點(diǎn)的同級(jí)節(jié)點(diǎn)
???? *
???? * @param int $id
???? * @return Tree object
???? */
??? public function getBrother($id)
??? {
??????? $data = self::$_indexs[$id]->_parent->_child;
??????? $this->_data = $data;
??????? return $this;
??? }
????
??? /**
???? * 將Tree對(duì)象轉(zhuǎn)化為數(shù)組
???? *?
???? * @param? object $object
???? * @return array
???? */
???? public function toArray($obj = NULL)
???? {
??????? $obj? = ($obj === NULL) ? $this->_data : $obj;
??????? $arr? = array();
??????? $_arr = is_object($obj) ? $this->_getBaseInfo($obj) : $obj;
????????
??????? if (is_array($_arr)) {
??????????? foreach ($_arr as $key => $val){
????????????????
??????????????? $val = (is_array($val) || is_object($val)) ? $this->toArray($val) : $val;
??????????????? $arr[$key] = $val;
??????????? }
??????? } else {
??????????? throw new Exception("_arr不是數(shù)組");
??????? }
?????
??????? return $arr;
??? }
????
??? /**
???? * 過(guò)濾_parent等字段,以免造成無(wú)限循環(huán)
???? *?
???? * @param object $obj
???? * @return void
???? */
??? private function _getBaseInfo($obj)
??? {
??????? $vars = get_object_vars($obj);
??????? $baseInfo['_info']? =? $vars['_info'];
??????? $baseInfo['_child'] =? $vars['_child'];
??????? return $baseInfo;
??? }
????
??? /**
???? * 二維數(shù)組排序
???? *
???? * 根據(jù)指定的鍵名對(duì)二維數(shù)組進(jìn)行升序或者降序排列
???? *
???? * @param array? $arr 二維數(shù)組
???? * @param string $keys
???? * @param string $type 必須為 asc或desc
???? * @throws 當(dāng)參數(shù)非法時(shí)拋出異常
???? * @return 返回排序好的數(shù)組
???? */
??? private function _array_sort(array $arr, $keys, $type = 'asc') {
??????? if (!is_string($keys)) {
??????????? throw new Exception("非法參數(shù)keys:參數(shù)keys的類型必須為字符串");
??????? }
????
??????? $keysvalue = $new_array = array();
??????? foreach ($arr as $k=>$v) {
??????????? if (!is_array($v) || !isset($v[$keys])) {
??????????????? throw new Exception("參數(shù)arr不是二維數(shù)組或arr子元素中不存在鍵'{$keys}'");
??????????? }
??????????? $keysvalue[$k] = $v[$keys];
??????? }
????
??????? switch ($type) {
??????????? case 'asc':
??????????????? asort($keysvalue);
??????????????? break;
??????????? case 'desc':
??????????????? arsort($keysvalue);
??????????????? break;
??????????? default:
??????????????? throw new Exception("非法參數(shù)type ：參數(shù)type的值必須為 'asc' 或 'desc'");
??????? }
????
??????? reset($keysvalue);
??????? foreach ($keysvalue as $k=>$v) {
??????????? $new_array[$k] = $arr[$k];
??????? }
??????? return $new_array;
??? }
}
?>