[php]
<?php
/**
* 無限級(受尾節點描述算法限制, 詳見tree_parse注釋)遞歸菜單
* author: selfimpr
* blog: http://blog.csdn.net/lgg201
* mail: [email protected]
*/
define('MAX_NODES', 3); /* 最大子節點數 */
define('MAX_NODE_INDEX', MAX_NODES - 1); /* 子節點最大索引值 */
define('NAME_FMT', 'name-%08d'); /* 節點內容輸出格式串 */
/* 樹節點數據結構 */
define('K_ID', 'id');
define('K_NAME', 'name');
define('K_CHILD', 'children');
/* 輸出構造時使用的拼裝字符 */
define('PREFIX_TOP', '┏'); /* 第一層第一個節點的標識符 */
define('PREFIX_BOTTOM', '┗'); /* 每一個父節點的最後一個子節點的標識符 */
define('PREFIX_MIDDLE', '┠'); /* 所有非上面兩種情況的節點的標識符 */
define('PREFIX_LINE', '┇'); /* 祖先節點的連線符 */
define('SPACE', ' '); /* 空白占位(所有尾節點不顯示連線符) */
define('WIDE_SPACE', str_repeat(SPACE, 4)); /* 寬的空白占位, 為了讓樹的層次清晰 */
/**
* data_build
* 構造一個節點
* @param mixed $id 節點id
* @param mixed $is_leaf 是否葉子
* @access public
* @return void
*/
function node_build($id, $is_leaf = FALSE) {
return array(
K_ID => $id,
K_NAME => sprintf(NAME_FMT, $id),
K_CHILD => $is_leaf ? NULL : array(),
);
}
/**
* tree_build
* 構造一棵樹(樹中每個節點的子節點數由MAX_NODES確定)
* @param mixed $datas 要返回的樹引用
* @param mixed $id 起始ID
* @param mixed $level 樹的層級
* @access public
* @return void
*/
function tree_build(&$datas, &$id, $level) {
if ( $level < 1 ) return ;
$is_leaf = $level == 1;
$i = -1;
$next_level = $level - 1;
while ( ++ $i < MAX_NODES ) {
$data = node_build($id ++, $is_leaf);
if ( !$is_leaf )
tree_build($data[K_CHILD], $id, $next_level);
array_push($datas, $data);
}
}
/**
* node_str
* 輸出一個節點自身的信息
* @param mixed $string 返回結果的字符串(引用傳值)
* @param mixed $data 節點數據
* @access public
* @return void
*/
function node_str(&$string, $data) {
$string .= sprintf(' %s[%d]', $data[K_NAME], $data[K_ID]);
}
/**
* node_sign
* 輸出一個節點的標志符號
* @param mixed $string 返回結果的字符串(引用傳值)
* @param mixed $level 當前深度
* @param mixed $i 當前節點在父節點中的索引(下標)
* @access public
* @return void
*/
function node_sign(&$string, $level, $i) {
switch ( $i ) {
case 0:
$string .= $level == 0 ? PREFIX_TOP : PREFIX_MIDDLE;
break;
case MAX_NODE_INDEX:
$string .= PREFIX_BOTTOM;
break;
default:
$string .= PREFIX_MIDDLE;
break;
}
}
/**
* node_prefix
* 輸出一個節點的前綴
* @param mixed $string 返回結果的字符串(引用傳值)
* @param mixed $level 當前深度
* @param mixed $is_last 當前節點(含)所有祖先節點是否尾節點標記
* @access public
* @return void
*/
function node_prefix(&$string, $level, $is_last) {
if ( $level > 0 ) {
$i = 0;
/* 前綴格式: "父級連線" ["寬空白符" "父級連線" ...] "寬空白符" */
$string .= ($is_last & 1 << ($level - $i) ? SPACE : PREFIX_LINE);
while ( ++ $i < $level )
$string .= WIDE_SPACE . ($is_last & 1 << ($level - $i) ? SPACE : PREFIX_LINE);
$string .= WIDE_SPACE;
}
}
/**
* node_out
* 輸出一個節點
* @param mixed $string 返回結果的字符串(引用傳值)
* @param mixed $data 要處理的節點數據
* @param mixed $level 節點深度
* @param mixed $i 節點在父節點中的索引(下標)
* @param mixed $is_last 當前節點(含)所有祖先節點是否尾節點標記
* @access public
* @return void
*/
function node_out(&$string, $data, $level, $i, $is_last) {
/* 處理前綴字符串: 祖先的連接符及空白 */
node_prefix($string, $level, $is_last);
/* 處理本節點的標識符號 */
node_sign($string, $level, $i);
/* 處理本節點數據信息 */
node_str($string, $data);
/* 追加換行 */
$string .= "\n";
}
/**
* tree_parse
* 輸出一棵樹
* 1. 由於使用了整型的$is_last作為祖先是否尾節點的標記, 所以最多支持PHP_INT_MAX的深度
* 2. 如果需要擴展, 修正$is_last的數據類型及校驗方法即可
* @param mixed $string 返回結果的字符串(引用傳值)
* @param mixed $datas 要處理的樹數據
* @param int $level 當前處理的深度
* @param int $is_last 當前深度所有祖先是否尾節點標記
* @access public
* @return void
*/
function tree_parse(&$string, $datas, $level = 0, $is_last = 0) {
if ( !is_array($datas) || count($datas) < 1 ) return ;
$max_index = count($datas) - 1;
/* 處理本層的所有節點 */
foreach ( $datas as $i => $data ) {
/* 當前節點及所有祖先是否尾節點標記 */
$tmp_is_last = $is_last << 1 | 1 & $i == $max_index;
/* 輸出當前節點 */
node_out($string, $data, $level, $i, $tmp_is_last);
/* 如果有子節點, 遞歸子節點 */
if ( is_array($data[K_CHILD]) && !emptyempty($data[K_CHILD]) )
tree_parse($string, $data[K_CHILD], $level + 1, $tmp_is_last);
}
}
/* 計算實際節點數 */
function n_node($n, $s) {
$sum = 0;
while ( $n > 0 )
$sum += pow($s, $n --);
return $sum;
}
/* 計算ruage時間 */
function ru_time($info, $type) {
return floatval(sprintf('%d.%d', $info[$type . '.tv_sec'], $info[$type . '.tv_usec']));
}
/* 輸出資源使用情況 */
function resource_usage($lv, $nodes, $cb, $ce, $mb, $me, $rb, $re) {
printf("\nresource usage[level: %d, node number: %d]: \n%20s%0.6fs\n%20s%0.6fs\n%20s%0.6fs\n%20s%d byte\n",
$lv, $nodes,
'clock time: ', $ce - $cb,
'system cpu: ', ru_time($re, 'ru_stime') - ru_time($rb, 'ru_stime'),
'user cpu: ', ru_time($re, 'ru_utime') - ru_time($rb, 'ru_utime'),
'memory usage: ', $me - $mb);
}
/* 用法 */
function usage($cmd) {
printf("usage: \n%s <tree deepth>\n", $cmd);
exit;
}
/* 測試入口函數 */
function run() {
global $argc, $argv;
if ( $argc != 2 || intval($argv[1]) < 1 )
usage($argv[0]);
$datas = array();
$id = 1;
$string = '';
$level = intval($argv[1]);
/* 初始構造測試樹 */
tree_build($datas, $id, $level);
$clock_begin = microtime(TRUE);
$memory_begin = memory_get_usage();
$rusage_begin = getrusage();
/* 解析樹 */
tree_parse($string, $datas);
$rusage_end = getrusage();
$memory_end = memory_get_usage();
$clock_end = microtime(TRUE);
/* 輸出結果 */
echo $string . "\n";
resource_usage($level, n_node($level, MAX_NODES),
$clock_begin, $clock_end,
$memory_begin, $memory_end,
$rusage_begin, $rusage_end);
}
/* 執行入口函數 */
run();
/*
* Local variables:
* tab-width: 4
* c-basic-offset: 4
* indent-tabs-mode: t
* End:
*/
