<?php
class tree {
	var $_idkey; //定义数据表关键字的键名
	var $_pidkey; //定义数据表的父亲字段的键名
	var $_isordered = false; //定义原数据是否按层级排序
	var $_rootid = 0; //定义根结点
	var $_tmparr = array(); //定义一个数组用来接受传进来的数组
	var $_tree = array(); //定义一个数组用以生成树
	var $_menu = array();

	function tree($arr){
		$this->__construct($arr);
	}

	function __construct($arr) {
		$this -> _tmparr = $arr;
		$keys = $this -> getkeys();
		$this -> _idkey = $keys[0];
		$this -> _pidkey = $keys[1];

		$this -> _rootid = $this -> get_rootid();
		$this -> _tree = $this -> make_tree();
	} 

	function getkeys() {
		$arr = $this -> _tmparr[0];
		return array_keys($arr);
	} 

	function get_rootid() {
		$numargs = func_num_args();
		$tmparr = ($numargs == 0) ? $this -> _tmparr : func_get_arg(0);
		$size = count($tmparr);

		$arr = array();

		foreach($tmparr as $key => $val) {
			for($i = ($this -> _isordered) ? ($key + 1):0; $i < $size; $i++) {
				$isfind = false;
				if ($tmparr[$i][$this -> _idkey] == $val[$this -> _pidkey]) {
					$isfind = true;
					break;
				} 

				if ($i == $size-1 && $isfind == false) {
					$arr[count($arr)] = $val[$this -> _pidkey];
				} 
			} 
		} 

		if (count(array_count_values($arr)) > 1) {
			return false; //不完整，不可能得到树
		} 

		unset($tmparr);
		return $arr[0]; //返回根结点
	} 
	// $this->_isordered为true表示已经按层级排序，否则没有
	function make_tree() {
		// 本方法可带一个参数$root_id，即根结点
		$numargs = func_num_args();
		$root_id = ($numargs == 0) ? $this -> _rootid : func_get_arg(0);

		if ($root_id = $this -> _rootid && !empty($this -> _tree)) {
			return $this -> _tree;
		} 
		$arr = $this -> _tmparr;
		$tree = array(); //目标数组
		$index = array(); //索引数组（堆栈）
		$arr_size = count($arr); 
		$vlayer = 0; //定义$tree的初始层级为1
		$i = 0;
		while ($i < $arr_size) {
			if ($arr[$i][$this -> _pidkey] == $root_id && empty($arr[$i]['yes'])) {
				$tree[count($tree)] = $arr[$i];
				$tree[count($tree)-1]['vlayer'] = $vlayer;
				$vlayer++;

				$index[count($index)][$this -> _pidkey] = $arr[$i][$this -> _pidkey];

				$arr[$i]['yes'] = 1;
				$root_id = $arr[$i][$this -> _idkey]; //改变当前根结点 
				if ($this -> _isordered == false) {
					$i = -1;
				} 
			} 

			if ($i == $arr_size-1) {
				if (count($index) == 0) {
					break;
				} 

				$i = ($this -> _isordered == false) ? 0:$index[count($index) -1]['index']; //如果未排序按默认算法$i回到0，否则按最优算法直接往下继续
				$root_id = $index[count($index) -1][$this -> _pidkey];
				array_pop($index);
				$vlayer--;
			} 

			if (count($tree) == $arr_size) {
				break;
			} 

			$i++;
		} 

		unset($arr);
		unset($index);
		unset($arr_size);
		return $this -> _tree = $tree;
	} 

	function make_subtree() {
		$numargs = func_num_args();
		if ($numargs == 0 || func_get_arg(0) == $this -> _rootid) {
			return $this -> _tree;
		} 

		$root_id = func_get_arg(0); //第一个参数
		$tree = ($numargs == 1) ? $this -> _tree:func_get_arg(1); //第2个参数
		$subtree = array();
		foreach($tree as $key => $val) {
			if ($val[$this -> _idkey] == $root_id) {
				$subtree[0] = $val;
				$subtree[0]['vlayer'] = 1;
				$src_vlayer = $val['vlayer'];
				$isok = false;
				$size = count($tree);

				for($i = $key + 1; $i < $size; $i++) {
					if ($tree[$i]['vlayer'] <= $src_vlayer) {
						$isok = true;
						break;
					} 
					$subtree[count($subtree)] = $tree[$i];
					$subtree[count($subtree)-1]['vlayer'] = $subtree[count($subtree)-2]['vlayer'] + 1;
				} 
			} 

			if ($isok == true) {
				break;
			} 
		} 

		return $subtree;
	} 

	function make_truetree($arr) {
		// 生成一颗真实的树
		if (!array_key_exists('vlayer', $arr[0])) {
			return false;
		} 
		$index = array();
		$truetree = array();
		$j = 0;
		$index[0]['index_str'] = '$truetree';
		foreach($arr as $key => $val) {
			$str = $index[$j]['index_str'];
			eval('$counts = count(' . $str . ');');
			eval($str . '[$counts] = $val;');
			eval($str . '[$counts][\'child\'] = array();');
			eval($str . '[$counts][\'paths\'] = array();');

			if ($arr[$key + 1]['vlayer'] > $val['vlayer']) {
				$j++;
				$index[$j]['index_str'] = $index[$j-1]['index_str'] . "[" . $counts . "]['child']";
			} 

			if ($arr[$key + 1]['vlayer'] < $val['vlayer']) {
				array_pop($index);
				$j -= $val['vlayer'] - $arr[$key + 1]['vlayer'];
			}
		} 

		unset($index);
		unset($j);
		return $truetree;
	} 

	function make_chilrens(&$data) {
		foreach($data as $key => &$val) {
			$val['childrens'][] = $val[$this -> _idkey];
			$val['children'] = array();
			$val['paths'][] = $val['path'];
			if (!empty($val['child'])) {
				foreach($val['child'] as $k => &$v) {
					$v['paths'] = array_merge($val['paths'], $v['paths']);
					$val['children'][] = $v['id'];
				} 
				$val['child'] = $this -> make_chilrens($val['child']);
				foreach($val['child'] as &$vv) {
					$val['childrens'] = array_merge($data[$key]['childrens'], $vv['childrens']);
				} 
			} 
		} 
		return $data;
	} 

	function make_sort(&$data) {
		$this -> _menu = array();
		return $this -> make_sort_item($data);
	} 

	function make_sort_item(&$data) {
		foreach($data as $key => &$val) {
			$temp = $val['child'];
			unset($val['child']);
			$index = array_search($val[$this -> _idkey], $val['childrens']);
			$val['children'] = array_slice($val['childrens'], 0, $index) + array_slice($val['childrens'], $index + 1);
			$val['ciddir'] = implode("/", $val['paths']);
			$val['child'] = count($val['children']) > 0 ? 1 : 0;
			$this -> _menu[] = $val;
			$this -> make_sort_item($temp);
		} 
		return $this -> _menu;
	} 



	function addnode($arr) {
		$counts = count($this -> _tmparr);
		foreach($arr as $key => $val) {
			$this -> _tmparr[$counts] = $val;
			$counts++;
		} 
		// 并且添加到当前树中
		foreach($arr as $key => $val) {
			$pos = 0;
			foreach($this -> _tree as $key2 => $val2) {
				if ($val[$this -> _idkey] > 0 && $val[$this -> _idkey] == $val2[$this -> _pidkey]) {
					$tmp[0] = $val;
					$this -> _tree = array_merge($tmp, $this -> _tree);
					break;
				} 

				if ($val[$this -> _pidkey] == $val2[$this -> _idkey]) {
					$pos = $key2 + 1;
					$merge_l = array_slice($this -> _tree, 0, $pos);
					$merge_r = array_slice($this -> _tree, $pos);
					$tmp[0] = $val;
					$merge = array_merge($merge_l, $tmp);
					$merge = array_merge($merge, $merge_r);
					$this -> _tree = $merge;
					break;
				} 
			} 
		} 
	} 

	function delnode($id) {
		// 注，只能删除叶子结点
		$is_leaf = false;
		foreach($this -> _tree as $key => $val) {
			if ($val[$this -> _idkey] == $id) {
				if (!isset($this -> _tree[$key + 1]) || $this -> _tree[$key + 1]['vlayer'] <= $val['vlayer']) {
					$is_leaf = true; //是叶子结点
					array_splice($this -> _tree, $pos, 1);
				} 
				break;
			} 
		} 

		if ($is_leaf) {
			foreach($this -> _tmparr as $key => $val) {
				if ($val[$this -> _idkey] == $id) {
					array_splice($this -> _tmparr, $key, 1);
					break;
				} 
			} 
		} 

		return $is_leaf;
	} 

	function get_leafs() {
		$numargs = func_num_args();
		$tree = ($numargs == 0) ? $this -> _tree : func_get_arg(0);

		$leafs = array();
		foreach($tree as $key => $val) {
			if (!isset($tree[$key + 1]) || $tree[$key + 1]['vlayer'] <= $val['vlayer']) {
				$leafs[] = $val;
			} 
		} 
		return $leafs;
	} 
} 
?>