<?php 
/** 
 * Tanphp framework 
 * 
 * 
 * @category   Tanphp 
 * @package    Data_structure 
 * @version    $Id: Tree.php 25024 2012-11-26 22:22:22 tanbo $ 
 */ 
 
/** 
 * 樹形結構數據存取類 
 *  
 * 用于對樹形結構數據進行快速的存取 
 *  
 * @param array $arr 參數必須為標準的二維數組，包含索引字段（id）與表示樹形結構的字段(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;                             //節點信息 
    public  $_child = array();                  //子節點 
    private $_parent;                           //父節點 
    private $_data;                             //當前操作的臨時數據 
    private static $_indexs         = array();  //所有節點的索引 
    private static $_index_key      = 'id';     //索引鍵 
    private static $_tree_key       = 'path';   //樹形結構表達鍵 
    private static $_tree_delimiter = '-';      //屬性結構表達分割符 
     
    /** 
     * 構造函數 
     *  
     * @param array $arr 
     * @param boole $force_sort 如果為真，將會強制對$arr 進行排序 
     * @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); 
        } 
    } 
     
    /** 
     * 初始存儲樹形數據 
     *  
     * @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                                   //如果有父級 
                && array_key_exists($parent_id, self::$_indexs)      //父級已經被存入索引 
                && self::$_indexs[$parent_id] instanceof Tree    //父級為Tree對象 
            ) { 
                self::$_indexs[$parent_id]->addChild($item); 
            } elseif ($count_paths == 1) { 
                $this->addChild($item); 
            } else { 
                throw new Exception("path數據錯誤".var_export($item, true)); 
            } 
        } 
         
        //print_r(self::$_indexs); 
    } 
     
    /** 
     * 添加子節點 
     *  
     * @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());  
    } 
     
    /** 
     * 添加節點到索引 
     *  
     * @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字段不存在或者不為字符串"); 
        } 
    } 
     
    /** 
     * 獲取對自己的引用 
     *  
     * @return Tree object quote 
     */ 
    private function _getSelf() 
    { 
        return $this; 
    } 
     
    /** 
     * 獲取指定id的節點的子節點 
     *  
     * @param int $id 
     * @return Tree object 
     */ 
    public function getChild($id) 
    { 
        $data       = self::$_indexs[$id]->_child; 
        $this->_data = $data; 
        return $this; 
    } 
     
    /** 
     * 獲取指定id的節點的父節點 
     *  
     * @param int $id 
     * @return Tree object 
     */ 
    public function getParent($id) 
    { 
        $data = self::$_indexs[$id]->_parent; 
        $this->_data = $data; 
        return $this; 
    } 
     
    /** 
     * 獲取指定id的節點的同級節點 
     * 
     * @param int $id 
     * @return Tree object 
     */ 
    public function getBrother($id) 
    { 
        $data = self::$_indexs[$id]->_parent->_child; 
        $this->_data = $data; 
        return $this; 
    } 
     
    /** 
     * 將Tree對象轉化為數組 
     *  
     * @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不是數組"); 
        } 
      
        return $arr; 
    } 
     
    /** 
     * 過濾_parent等字段，以免造成無限循環 
     *  
     * @param object $obj 
     * @return void 
     */ 
    private function _getBaseInfo($obj) 
    { 
        $vars = get_object_vars($obj); 
        $baseInfo['_info']  =  $vars['_info']; 
        $baseInfo['_child'] =  $vars['_child']; 
        return $baseInfo; 
    } 
     
    /** 
     * 二維數組排序 
     * 
     * 根據指定的鍵名對二維數組進行升序或者降序排列 
     * 
     * @param array  $arr 二維數組 
     * @param string $keys 
     * @param string $type 必須為 asc或desc 
     * @throws 當參數非法時拋出異常 
     * @return 返回排序好的數組 
     */ 
    private function _array_sort(array $arr, $keys, $type = 'asc') { 
        if (!is_string($keys)) { 
            throw new Exception("非法參數keys:參數keys的類型必須為字符串"); 
        } 
     
        $keysvalue = $new_array = array(); 
        foreach ($arr as $k=>$v) { 
            if (!is_array($v) || !isset($v[$keys])) { 
                throw new Exception("參數arr不是二維數組或arr子元素中不存在鍵'{$keys}'"); 
            } 
            $keysvalue[$k] = $v[$keys]; 
        } 
     
        switch ($type) { 
            case 'asc': 
                asort($keysvalue); 
                break; 
            case 'desc': 
                arsort($keysvalue); 
                break; 
            default: 
                throw new Exception("非法參數type ：參數type的值必須為 'asc' 或 'desc'"); 
        } 
     
        reset($keysvalue); 
        foreach ($keysvalue as $k=>$v) { 
            $new_array[$k] = $arr[$k]; 
        } 
        return $new_array; 
    } 
} 
?>