202 lines
5.4 KiB
PHP
202 lines
5.4 KiB
PHP
<?php
|
||
|
||
/**
|
||
* $Id: Tree.php 58820 2015-01-16 16:29:33Z caoyangmin $
|
||
* @author caoyangmin(caoyangmin@baidu.com)
|
||
* @brief Tree
|
||
*/
|
||
namespace phprs\util;
|
||
class Tree {
|
||
/**
|
||
* 插入一个节点
|
||
* 插入时允许使用通配符*
|
||
* @param array $path
|
||
* @param unknown $value
|
||
* @param string $replace_exits 是否替换已存在的
|
||
* @param mixed $replaced 被替换的原始值
|
||
* @return boolean
|
||
*/
|
||
public function insert( $path, $value, $replace_exits=false, &$replaced=null){
|
||
assert(count($path));
|
||
$left = $path;
|
||
$cur = array_shift($left);//剩余未遍历的
|
||
if(!array_key_exists($cur,$this->arr)){
|
||
$this->arr[$cur] = array();
|
||
}
|
||
$insert= false;
|
||
$this->visitNode($path,function ($name,&$node)use(&$insert,&$left,$value,$replace_exits, &$replaced){
|
||
$cur = array_shift($left);
|
||
if($cur === null){
|
||
if(array_key_exists('value',$node)){//是否已存在
|
||
if(!$replace_exits){
|
||
return false;
|
||
}
|
||
$replaced = $node['value'];
|
||
}
|
||
$node['value'] = $value;
|
||
$insert = true;
|
||
return false;//停止遍历
|
||
}else{
|
||
if(!array_key_exists('next',$node)){
|
||
$node['next'] = array();
|
||
}
|
||
if(!array_key_exists($cur,$node['next'])){
|
||
$node['next'][$cur]= array();
|
||
}
|
||
}
|
||
return true;
|
||
}, true);
|
||
return $insert;
|
||
}
|
||
/**
|
||
* 删除一个路径下的所有节点
|
||
* @param array $path
|
||
* @return boolean
|
||
*/
|
||
public function erase(array $path){
|
||
if(count($path)==0){
|
||
return false;
|
||
}
|
||
$size = count($path);
|
||
$key = $path[$size-1];
|
||
if($size ==1){
|
||
if(array_key_exists($key, $this->arr)){
|
||
unset($this->arr[$key]);
|
||
return true;
|
||
}
|
||
return false;
|
||
}
|
||
$i = 0;
|
||
$res = false;
|
||
$full = $this->visitNode($path,function ($name,&$node)use(&$i,$size,$key,&$res){
|
||
if(++$i == $size-1){
|
||
if(isset($node['next']) && isset($node['next'][$key])){
|
||
unset($node['next'][$key]);
|
||
$res = true;
|
||
}
|
||
return false;
|
||
}
|
||
return true;
|
||
}, true);
|
||
return $res;
|
||
}
|
||
/**
|
||
* 遍历路径
|
||
* @param array $path
|
||
* @return boolean 全部遍历完返回true，否则返回false
|
||
*/
|
||
public function visit( $path ,$vistor, $exact_match=false){
|
||
return $this->visitNode($path,function ($name,$node)use($vistor){
|
||
return $vistor($name,array_key_exists('value',$node)?$node['value']:null);
|
||
}, $exact_match);
|
||
}
|
||
/**
|
||
* 查找指定路径的节点
|
||
* @param array $path
|
||
* @param boolean $exact_match 是否精确匹配,如果是,则通配符被认为与其他值不同
|
||
* @return 返回节点的值, 或者null
|
||
*/
|
||
public function find(array $path, $exact_match=false){
|
||
$found = null;
|
||
$full = $this->visitNode($path,function ($name,$node)use(&$found){
|
||
$found = array_key_exists('value',$node)?$node['value']:null;
|
||
return true;
|
||
}, $exact_match);
|
||
return $full?$found:null;
|
||
}
|
||
/**
|
||
* 查找指定路径的节点
|
||
* @param array $path
|
||
* @param boolean $exact_match 是否精确匹配,如果是,则通配符被认为与其他值不同
|
||
* @param boolean $all_req_paths 是否要求查询路径的所有元素都必须遍历到
|
||
* @param boolean $all_paths 是否
|
||
* @return 返回节点的, 或者null
|
||
*/
|
||
public function findNode(array $path, $exact_match=false, $all_req_paths=false){
|
||
$found = null;
|
||
$full = $this->visitNode($path,function ($name,$node)use(&$found){
|
||
$found = $node;
|
||
return true;
|
||
}, $exact_match, $all_req_paths);
|
||
return $full?$found:null;
|
||
}
|
||
/**
|
||
* 遍历路径
|
||
* @param array $path
|
||
* @param boolean $exact_match 是否精确匹配,如果是,则通配符被认为与其他值不同
|
||
* @param boolean $all_req_paths 是否要求查询路径的所有元素都必须遍历到
|
||
* @return boolean 变量完成返回true，遍历未完成时终止返回false
|
||
*/
|
||
private function visitNode( $path, $vistor, $exact_match=false, $all_req_paths=false){
|
||
assert(count($path));
|
||
$pos = &$this->arr;
|
||
$next = &$pos;
|
||
foreach ($path as $i){
|
||
if(is_null($next)) {
|
||
return !$all_req_paths;
|
||
}
|
||
if(!array_key_exists($i, $next)){
|
||
if($exact_match){
|
||
return false;
|
||
}
|
||
if($i == self::$end){
|
||
return false;
|
||
}
|
||
//不要求完全匹配, 尝试匹配通配符
|
||
if(!array_key_exists(self::$wildcard, $next)){
|
||
return false;
|
||
}
|
||
$pos = &$next[self::$wildcard];
|
||
}else{
|
||
$pos = &$next[$i];
|
||
}
|
||
if(!$vistor($i,$pos)){
|
||
return false;
|
||
}
|
||
if(array_key_exists('next',$pos)){
|
||
$next = &$pos['next'];
|
||
}else{
|
||
$nul = null;
|
||
$next = &$nul; //$next = null 会导致引用的对象被赋值，而不是next被赋值
|
||
}
|
||
}
|
||
return true;
|
||
}
|
||
/**
|
||
* 树打平输出成数组
|
||
* @return array
|
||
*/
|
||
public function export(){
|
||
$res=array();
|
||
self::treeToArray($this->arr, $res);
|
||
return $res;
|
||
}
|
||
/**
|
||
*
|
||
* @param array $tree
|
||
* @param array $res
|
||
* @return void
|
||
*/
|
||
static private function treeToArray($tree, &$res){
|
||
foreach ($tree as $name=>$node){
|
||
if($node === null){
|
||
continue;
|
||
}
|
||
if( isset($node['value']) ){
|
||
$res[] = array(array($name), $node['value']);
|
||
}
|
||
if( isset($node['next']) ){
|
||
$tmp = array();
|
||
self::treeToArray($node['next'], $tmp);
|
||
foreach ($tmp as $v){
|
||
array_unshift($v[0], $name);
|
||
$res[] = array($v[0], $v[1]);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
private $arr=array();
|
||
static public $end="\n";
|
||
static public $wildcard='*';
|
||
}
|