[共有] PHPキャッシングツリーの再帰表示

[共有] PHP実装ツリーの再帰表示
元ブログアドレス: http://blog.csdn.net/lgg201/article/details/7973971

使用方法:

PHPコード

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
usage: 
php tree-display.php <tree deepth>

テスト出力:

PHP コード

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
$ php tree-display.php 3
 name-00000001[1]
┇    ┠ name-00000002[2]
┇    ┇    ┠ name-00000003[3]
┇    ┇    ┠ name-00000004[4]
┇    ┇    ┗ name-00000005[5]
┇    ┠ name-00000006[6]
┇    ┇    ┠ name-00000007[7]
┇    ┇    ┠ name-00000008[8]
┇    ┇    ┗ name-00000009[9]
┇    ┗ name-00000010[10]
┇         ┠ name-00000011[11]
┇         ┠ name-00000012[12]
┇         ┗ name-00000013[13]
┠ name-00000014[14]
┇    ┠ name-00000015[15]
┇    ┇    ┠ name-00000016[16]
┇    ┇    ┠ name-00000017[17]
┇    ┇    ┗ name-00000018[18]
┇    ┠ name-00000019[19]
┇    ┇    ┠ name-00000020[20]
┇    ┇    ┠ name-00000021[21]
┇    ┇    ┗ name-00000022[22]
┇    ┗ name-00000023[23]
┇         ┠ name-00000024[24]
┇         ┠ name-00000025[25]
┇         ┗ name-00000026[26]
┗ name-00000027[27]
     ┠ name-00000028[28]
     ┇    ┠ name-00000029[29]
     ┇    ┠ name-00000030[30]
     ┇    ┗ name-00000031[31]
     ┠ name-00000032[32]
     ┇    ┠ name-00000033[33]
     ┇    ┠ name-00000034[34]
     ┇    ┗ name-00000035[35]
     ┗ name-00000036[36]
          ┠ name-00000037[37]
          ┠ name-00000038[38]
          ┗ name-00000039[39]


resource usage[level: 3, node number: 39]: 
        clock time: 0.001967s
        system cpu: 0.000169s
          user cpu: 0.001013s
      memory usage: 7208 byte

PHP コード

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
<?php
/*** 無限レベル (末尾ノード記述アルゴリズムによって制限されます。詳細については、tree_parse コメントを参照してください) 再帰メニュー
 * 著者: selfimpr
 *ブログ：http://blog.csdn.net/lgg201
 * メール: lgg860911@yahoo.com.cn*/

define('MAX_NODES', 3); /* 子ノードの最大数 */
define('MAX_NODE_INDEX', MAX_NODES - 1); /* 子ノードの最大インデックス値 */
define('NAME_FMT', 'name-%08d'); /* ノード内容の出力形式文字列 */

/* ツリーノードのデータ構造 */
定義('K_ID', 'id');
定義('K_NAME', '名前');
定義('K_CHILD', '子供');

/* 構築に使用されるアセンブリ文字を出力します */
define('PREFIX_TOP', '┏'); /* 最初の層の最初のノードの識別子 */
define('PREFIX_BOTTOM', '┗'); /* 各親ノードの最後の子ノードの識別子 */
define('PREFIX_MIDDLE', '┠'); /* 上記 2 つのケースに当てはまらないすべてのノードの識別子 */
define('PREFIX_LINE', '┇'); /* 祖先ノードのコネクタ */
define('SPACE', ' '); /* 空白のプレースホルダー (すべての末尾ノードにはハイフンが表示されません) */
define('WIDE_SPACE', str_repeat(SPACE, 4)); /* ツリーの階層を明確にするための広い空白のプレースホルダー */


/***データビルド
 * ノードを構築する
 * @param 混合 $id ノード ID
 * @paramは、$is_leafが葉であるかどうかを混合しました
 * @アクセスパブリック
 * @return void*/
関数node_build($id, $is_leaf = FALSE) {
    戻り配列(
        K_ID => $id、
        K_NAME => sprintf(NAME_FMT, $id),
        K_CHILD => $is_leaf : array(),
    );
}
/***ツリービルド
 * ツリーを構築します (ツリー内の各ノードの子ノードの数は MAX_NODES によって決まります)
 * @parammixed $datas 返されるツリー参照
 * @param 混合 $id 開始 ID
 * @parammixed $level ツリーのレベル
 * @アクセスパブリック
 * @return void*/
関数tree_build(&$datas, &$id, $level) {
    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;
    }
}
/***ノードアウト
 * ノードを出力する
 * @parammixed $string 結果の文字列を返します (値渡し)
 * @parammixed $data 処理対象のノードデータ
 * @param 混合 $level ノードの深さ
 * @parammixed $i 親ノード内のノードのインデックス(添字)
 * @parammixed $is_last 現在のノードのすべての祖先ノード (含む) が末尾ノード マーカーであるかどうか
 * @アクセスパブリック
 * @return void*/
関数 node_out(&$string, $data, $level, $i, $is_last) {
    /* プレフィックス文字列を処理します: 祖先コネクタと空白 */
    ノードプレフィックス($string, $level, $is_last);
    /* このノードの識別子を処理します */
    ノードサイン($string, $level, $i);
    /* このノードのデータ情報を処理します */
    ノードstr($string, $data);
    /*改行を追加 */
    $string .= "n";
}/*** ツリー_パース
 * ツリーを出力します
 * 1. 整数 $is_last は祖先が末尾ノードであるかどうかのマークとして使用されるため、PHP_INT_MAX の最大の深さがサポートされます。
 * 2. 拡張が必要な​​場合は、$is_lastのデータ型と検証方法を変更するだけです
 * @parammixed $string 結果の文字列を返します (値渡し)
 * @parammixed $datas 処理対象のツリーデータ
 * @param int $level 現在の処理深度
 * @param int $is_last 現在の深さのすべての祖先が末尾ノードでマークされているかどうか
 * @アクセスパブリック
 * @return void*/
関数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 & $i == $max_index;
        /* 現在のノードを出力します */
        node_out($string, $data, $level, $i, $tmp_is_last);
        /* 子ノードがある場合は、子ノードを再帰します */
        if ( is_array($data[K_CHILD]) && !empty($data[K_CHILD]) )
            Tree_parse($string, $data[K_CHILD], $level + 1, $tmp_is_last);
    }
}

/* 実際のノード数を計算します */
関数 n_node($n, $s) {
    $sum = 0;
    while ( $n > 0 )
        $sum += pow($s, $n --);
    $sum を返します。
}
/* ルアージュ時間を計算します */
関数 ru_time($info, $type) {
    $info[$type .'.tv_sec'] + $info[$type .'.tv_usec'] / 1000000を返します。
}
/* リソース使用量を出力します */
関数 resource_usage($lv, $nodes, $cb, $ce, $mb, $me, $rb, $re) {
    printf("nリソース使用量[レベル: %d、ノード番号: %d]: n%20s%0.6fsn%20s%0.6fsn%20s%0.6fsn%20s%d バイト",
        $lv、$nodes、
        'クロック時間: '、$ce - $cb、
        'システム CPU: ', ru_time($re, 'ru_stime') - ru_time($rb, 'ru_stime'),
        'ユーザー CPU: ', ru_time($re, 'ru_utime') - ru_time($rb, 'ru_utime'),
        'メモリ使用量: ', $me - $mb);
}
/* 使用法 */
関数の使用法($cmd) {
    printf("使用法: n%s n", $cmd);
    出口;
}

/* テスト入力関数 */
関数 run() {
    グローバル $argc、$argv;

    if ( $argc != 2 || intval($argv[1])