=encoding euc-jp

=head1 名前

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

=head1 概要

  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);

=head1 説明

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

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

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

=head1 グローバル変数

=head2 ブール値

=over 4

=item TRUE

=item FALSE

=back

=head2 全検索フラグ

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

=over 2

=item TRAVERSE_LEAFS 

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

=item TRAVERSE_NON_LEAFS

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

=item TRAVERSE_ALL 

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

=item TRAVERSE_MASK

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

=back

=head2 ORDER FLAGS

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

=over 2

=item PRE_ORDER

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

=item IN_ORDER

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

=item POST_ORDER

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

=item LEVEL_ORDER

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

=back

=head1 METHODS

=head2 new( [DATA] )

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

=head2 insert( PARENT, POSITION, NODE )

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

=head2 insert_before( PARENT, SIBLING, NODE )

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

=head2 append( PARENT, NODE )

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

=head2 prepend( PARENT, NODE )

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

=head2 insert_data( PARENT, POSITION, DATA )

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

=head2 insert_data_before( PARENT, SIBLING, DATA )

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

=head2 append_data( PARENT, DATA )

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

=head2 prepend_data( PARENT, DATA )

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

=head2 reverse_children( NODE )

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

=head2 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で
あれば、ルートとその子が検索対照となります。以後同様です。

=head2 children_foreach( NODE, FLAGS, FUNCTION, DATA )

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

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

=head2 get_root( NODE )

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

=head2 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が見付からなかった場合I<undef>を返します。

=head2 find_child( NODE, FLAGS, DATA )

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

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

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

=head2 child_index( NODE, DATA )

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

=head2 child_position( NODE, CHILD )

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

=head2 first_child( NODE )

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

=head2 last_child( NODE )

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

=head2 nth_child( NODE, INDEX )

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

=head2 first_sibling( NODE )

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

=head2 prev_sibling( NODE )

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

=head2 next_sibling( NODE )

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

=head2 last_sibling( NODE )

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

=head2 is_leaf( NODE )

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

=head2 is_root( NODE )

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

=head2 depth( NODE )

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

=head2 n_nodes( NODE, FLAGS )

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

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

=head2 n_children( NODE )

NODEの子の数を返します。

=head2 is_ancestor( NODE, DESCENDANT )

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

=head2 max_height( NODE )

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

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

=head2 unlink( NODE )

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

=head1 例

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

=head1 作者

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

=head1 COPYRIGHT

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.

=head1 参考文献

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

=head1 翻訳者

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