/**

• 树形结构数据存取类
• 用于对树形结构数据进行快速的存取
• @param array $arr 参数必须为标准的二维数组，包含索引字段（id）与表示树形结构的字段(path),如example中所示
• @example
• $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());

• */
  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;
}
}
?>