名前¶

Tree::Nary - n分探索木のPerlによる実装

概要¶

  use Tree::Nary;

  $node = new Tree::Nary;

  $inserted_node = $node->insert($parent, $position, $node);
  $inserted_node = $node->insert_before($parent, $sibling, $node);
  $inserted_node = $node->append($parent, $node);
  $inserted_node = $node->prepend($parent, $node);
  $inserted_node = $node->insert_data($parent, $position, $data);
  $inserted_node = $node->insert_data_before($parent, $sibling, $data);
  $inserted_node = $node->append_data($parent, $data);
  $inserted_node = $node->prepend_data($parent, $data);

  $node->reverse_children($node);

  $node->traverse($node, $order, $flags, $maxdepth, $funcref, $argref);

  $node->children_foreach($node, $flags, $funcref, $argref);

  $root_node = $obj->get_root($node);

  $found_node = $node->find($node, $order, $flags, $data);
  $found_child_node = $node->find_child($node, $flags, $data);

  $index = $node->child_index($node, $data);
  $position = $node->child_position($node, $child);

  $first_child_node = $node->first_child($node);
  $last_child_node = $node->last_child($node);

  $nth_child_node = $node->nth_child($node, $index);

  $first_sibling = $node->first_sibling($node);
  $next_sibling = $node->next_sibling($node);
  $prev_sibling = $node->prev_sibling($node);
  $last_sibling = $node->last_sibling($node);

  $bool = $node->is_leaf($node);
  $bool = $node->is_root($node);

  $cnt = $node->depth($node);

  $cnt = $node->n_nodes($node);
  $cnt = $node->n_children($node);

  $bool = $node->is_ancestor($node);

  $cnt = $obj->max_height($node);

  $node->unlink($node);

説明¶

Tree::Naryクラスはn分木の実装クラス(枝の数に制限の無い木データ構造)で、 いくつものノードを持つ木構造の組織(コレクション)を提供しますが、 どの具体的なノードの型については全く感知しません。このデータ構造は 内部アプリケーションのデータベース全体の統計を表現するのに用いられます (NISネットグループファイルがそんな例の一つです)。本モジュールでは 木のノードを選択したり、取り付けたりする機能を提供します。 取り付けの際は複数の子ノードをサポートすることが可能です。

dataフィールドはそのノードにおける実際のデータを含んでいます。nextとprevious フィールドはそのnodeの兄弟を指し示しています(兄弟とは同じ親を持つ異なるノード です)。parentフィールドはそのノードの親を指し示しているか、もし木のルートで あればundefです。childrenフィールドはそのノードの最初の子を示しています。 他の子はそれぞれの子のnextポインタを用いることによってアクセスされます。

このモジュールは(たとえ直接でなくても)n分木のCにおける実装を移植したもので、 GLIB distributionで利用可能です。(参考文献の欄を御覧下さい。)

グローバル変数¶

ブール値¶

TRUE

FALSE

全検索フラグ¶

traverse()やfind()を含むいくつかの木の関数によって検索対照となるノードを 示します。

TRAVERSE_LEAFS

検索対照となるべきは葉ノードのみであることを示します。

TRAVERSE_NON_LEAFS

検索対照となるべきは葉ノード以外であることを示します。

TRAVERSE_ALL

検索対照となるべきは全てのノードであることを示します。

TRAVERSE_MASK

複数の全検索フラグのコンビネーションです。

ORDER FLAGS¶

traverse()及びfind()によって行われる全探索のタイプを示します。

PRE_ORDER

あるノードを検索対照とし、それからその子を検索対照とします。

IN_ORDER

まず左の子を最初の検索対照とし、それからノード自身を、その後に右の子を 検索対照とします。もしあなたが比較関数によってソートされたものを出力したい 場合、これは一つの方法です。

POST_ORDER

訪れたノードの子を検索対照とし、それからそのノード自身を検索対照とします。

LEVEL_ORDER

それぞれのノードの子に対して関数が呼び出され、再帰的に子を検索対照とします。

メソッド¶

new( [DATA] )¶

Tree::Naryオブジェクトを新たに生成します。木の最初のノードを生成するのに 用いられます。生成されたノードにオプショナルなDATAを挿入します。

insert( PARENT, POSITION, NODE )¶

NODEをPARENTの下の与えられたPOSITIONに挿入し、挿入されたNODEを返します。 もしPOSITIONが-1のならば、NODEはPARENTの最後の子として挿入されます。

insert_before( PARENT, SIBLING, NODE )¶

NODEをPARENTの下の与えられたSIBLING(兄弟)の直前に挿入し、挿入されたNODEを 返します。もしSIBLINGがundefであるならば、ノードは親の最後の子として 挿入されます。

append( PARENT, NODE )¶

NODEを与えられたPARENTの最後の子として挿入し、挿入されたNODEを返します。

prepend( PARENT, NODE )¶

NODEを与えられた親の最初の子として挿入し、挿入されたNODEを返します。

insert_data( PARENT, POSITION, DATA )¶

新しいDATAを含むノードを、親の下の与えられたPOSITIONに挿入します。 また、挿入された新たなノードを返します。

insert_data_before( PARENT, SIBLING, DATA )¶

新しいDATAを含むノードをPARENTの下のSIBLINGの直前に挿入します。 また、挿入された新たなノードを返します。

append_data( PARENT, DATA )¶

新しいDATAを含むノードを与えられたPARENTの最後の子として挿入します。 また、挿入された新たなノードを返します。

prepend_data( PARENT, DATA )¶

新しいDATAを含むノードを与えられたPARENTの最初の子として挿入します。 また、挿入された新たなノードを返します。

reverse_children( NODE )¶

NODEの子の並び順を逆転します。孫の並び順は変更されません。

traverse( NODE, ORDER, FLAGS, MAXDEPTH, FUNCTION, DATA )¶

与えられたルートNODEを出発点として木を順次に全検索します。 この関数では与えられたFUNCTIONを検索対象となったそれぞれのノードに対して 呼び出します(オプショナルなFUNCTIONに渡すユーザーのDATAを伴って)。

全検索はFUNCTIONの返り値TRUEによっていかなる場所でも停止させることが 可能です。

ノードの検索順(ORDER)をIN_ORDER, PRE_ORDER, POST_ORDER, LEVEL_ORDERの うちで１つを選んで下さい。

FLAGSは検索対象となる子のタイプを示します。TRAVERSE_ALL, TRAVERSE_LEAFS及び TRAVERSE_NON_LEAFSのうちから一つを選んで下さい。

MAXDEPTHは全検索の最大深度です。この深さより向こうのノードは検索対象には ならないでしょう。もしMAXDEPTHが-1ならば、全てのノードが検索対象になります。 もしMAXDEPTHが１であれば、ルートのみが検索対照になります。MAXDEPTHが2で あれば、ルートとその子が検索対照となります。以後同様です。

children_foreach( NODE, FLAGS, FUNCTION, DATA )¶

FUNCTIONをNODEに関するめいめいの子に対して呼び出します(オプショナルなFUNCTIONに渡す ユーザーのDATAを伴って)。そこで覚えておいて欲しいことですが、子ノードより下に 降りて行くことはしません。

FLAGSは検索対照となる子のタイプを示します。TRAVERSE_ALL、TRAVERSE_LEAFS及び TRAVERSE_NON_LEAFSのうちの一つを選んで下さい。

get_root( NODE )¶

NODEを出発点として、木のルートノードを取得します。

find( NODE, ORDER, FLAGS, DATA )¶

与えられたDATAについて木の中のNODEを検索します。

ノードの検索順(ORDER)をIN_ORDER, PRE_ORDER, POST_ORDER, LEVEL_ORDERの うちで１つを選んで下さい。

FLAGSは検索対照となる子のタイプを示します。TRAVERSE_ALL、TRAVERSE_LEAFS及び TRAVERSE_NON_LEAFSのうちの一つを選んで下さい。

見付かった子ノードを返すか、DATAが見付からなかった場合undefを返します。

find_child( NODE, FLAGS, DATA )¶

与えられたデータについて、NODEの最初の子を探します。

FLAGSは検索対照となる子のタイプを示します。TRAVERSE_ALL、TRAVERSE_LEAFS及び TRAVERSE_NON_LEAFSのうちから一つを選んで下さい。

見付かった子ノードを返すか、DATAが見付からなかった場合undefを返します。

child_index( NODE, DATA )¶

DATAを含むNODEの最初の子ポジションを得ます。dataを含むノードの子の インデックスを返すか、DATAが見付からなかった場合は-1を返します。

child_position( NODE, CHILD )¶

兄弟を考慮に居れたNODEのポジションを得ます。CHILDはNODEの子ノードでなくては なりません(MUST)。始めのノードは0と言う数字が割り当てられ、２番目が1になり、 以下同様です。兄弟を考慮したCHILDのポジションを返します。

first_child( NODE )¶

NODEの最初の子を返します。NODEがundefか、子を持っていない場合はundefを 返します。

last_child( NODE )¶

ノードの最後の子を返します。NODEがundefか、子を持っていない場合はundefを 返します。

nth_child( NODE, INDEX )¶

与えられたINDEXを用いて、NODEの子を得ます。最初の子のINDEXは0です。もし INDEXが大きすぎる場合、undefが返されます。INDEXの場所のNODEの子を返します。

first_sibling( NODE )¶

NODEの最初の兄弟を返します。これはNODE自身である場合もありえます。

prev_sibling( NODE )¶

NODEの直前の兄弟を返します。

next_sibling( NODE )¶

NODEの直後の兄弟を返します。

last_sibling( NODE )¶

NODEの最後の兄弟を返します。これはNODE自身である場合もありえます。

is_leaf( NODE )¶

NODEが葉ノードである(子ノードが無い)場合TRUEを返します。

is_root( NODE )¶

ルートノードである(親が無く兄弟も無い)場合TRUEを返します。

depth( NODE )¶

NODEの深さを返します。もしNODEがundefの場合、深さは0です。ルートノードは 深度1です。ルートノードの子では深度2になります。以後同様です。

n_nodes( NODE, FLAGS )¶

木のノードの数を返します。

FLAGSはカウント対照となる子のタイプを示します。TRAVERSE_ALL、TRAVERSE_LEAFS及び TRAVERSE_NON_LEAFSのうちから一つ選んで下さい。

n_children( NODE )¶

NODEの子の数を返します。

is_ancestor( NODE, DESCENDANT )¶

もしNODEがDESCENDANTNの祖先であるならばTRUEを返します。これはNODEが DESCENDANTの親であるか、もしくはDESCENDANTの親の親であるなどの場合に TRUEを返します。

max_height( NODE )¶

NODEの下にある全ての枝に関して最大の高さを返します。これは全ての葉ノードと NODE間との最大の距離を示します。

もしNODEがundefならば、0が返ります。もしNODEが子を持っていないならば、 1が返ります。もしNODEが子を持っているならば、2を返します。以後同様です。

unlink( NODE )¶

NODEを木から切り離し、その結果二つの分断された木ができます。 切り離されたNODEは新しい木のルートとなります。

例¶

テストスクリプトtest.plにそれぞれの例が載っています。

作者¶

Frederic Soriano, <frederic.soriano@alcatel.fr>

コピーライト¶

This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the same terms as Perl itself.

参考文献¶

APIはGLIBプロジェクトに由来します, http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html.

翻訳者¶

三浦真磁<snj@users.sourceforge.jp>