1Tree::Nary extension module for Perl
2------------------------------------
3
4Author: Frederic Soriano [FSORIANO]
5 best reached at : fsoriano@cpan.org
6
7Version: 1.3
8
9Date: January 2004
10
11DSLI: RdpO
12 - stable release
13 - support by developer
14 - plain functions, no references used
15
16Copyright: Public domain
17
18Documentation is in pod format at the end of Tree::Nary.pm.
19Installation hints are in a file named INSTALL inside this package.
20See also CHANGES for a history of updates to this module.
21
22-----------------------------------------------------------------------------
23 THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
24 IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
25 WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
26-----------------------------------------------------------------------------
27
28NAME
29
30 Tree::Nary - Perl implementation of N-ary search trees.
31
32SYNOPSIS
33
34 use Tree::Nary;
35
36 $node = new Tree::Nary;
37
38 $inserted_node = $node->insert($parent, $position, $node);
39 $inserted_node = $node->insert_before($parent, $sibling, $node);
40 $inserted_node = $node->append($parent, $node);
41 $inserted_node = $node->prepend($parent, $node);
42 $inserted_node = $node->insert_data($parent, $position, $data);
43 $inserted_node = $node->insert_data_before($parent, $sibling, $data);
44 $inserted_node = $node->append_data($parent, $data);
45 $inserted_node = $node->prepend_data($parent, $data);
46
47 $node->reverse_children($node);
48
49 $node->traverse($node, $order, $flags, $maxdepth, $funcref, $argref);
50
51 $node->children_foreach($node, $flags, $funcref, $argref);
52
53 $root_node = $obj->get_root($node);
54
55 $found_node = $node->find($node, $order, $flags, $data);
56 $found_child_node = $node->find_child($node, $flags, $data);
57
58 $index = $node->child_index($node, $data);
59 $position = $node->child_position($node, $child);
60
61 $first_child_node = $node->first_child($node);
62 $last_child_node = $node->last_child($node);
63
64 $nth_child_node = $node->nth_child($node, $index);
65
66 $first_sibling = $node->first_sibling($node);
67 $next_sibling = $node->next_sibling($node);
68 $prev_sibling = $node->prev_sibling($node);
69 $last_sibling = $node->last_sibling($node);
70
71 $bool = $node->is_leaf($node);
72 $bool = $node->is_root($node);
73
74 $cnt = $node->depth($node);
75
76 $cnt = $node->n_nodes($node);
77 $cnt = $node->n_children($node);
78
79 $bool = $node->is_ancestor($node);
80
81 $cnt = $obj->max_height($node);
82
83 $node->tsort($node);
84
85 $normalized_node = $node->normalize($node);
86
87 $bool = $node->is_identical($node, $another_node);
88 $bool = $node->has_same_struct($node, $another_node);
89
90 $node->unlink($node);
91
92DESCRIPTION
93
94 The Tree::Nary class implements N-ary trees (trees of data with any
95 number of branches), providing the organizational structure for a tree (collection)
96 of any number of nodes, but knowing nothing about the specific type of node used.
97 It can be used to display hierarchical database entries in an internal application (the
98 NIS netgroup file is an example of such a database). It offers the capability to select
99 nodes on the tree, and attachment points for nodes on the tree. Each attachment point
100 can support multiple child nodes.
101
102 The data field contains the actual data of the node. The next and previous fields point
103 to the node's siblings (a sibling is another node with the same parent). The parent
104 field points to the parent of the node, or is undef if the node is the root of the
105 tree. The children field points to the first child of the node. The other children are
106 accessed by using the next pointer of each child.
107
108 This module is a translation (albeit not a direct one) from the C implementation of
109 N-ary trees, available in the GLIB distribution (see SEE ALSO).
110
111GLOBAL VARIABLES
112
113 BOOLEANS
114
115 TRUE
116
117 FALSE
118
119 TRAVERSE FLAGS
120
121 Specifies which nodes are visited during several of the tree functions, including
122 traverse() and find().
123
124 TRAVERSE_LEAFS
125
126 Specifies that only leaf nodes should be visited.
127
128 TRAVERSE_NON_LEAFS
129
130 Specifies that only non-leaf nodes should be visited.
131
132 TRAVERSE_ALL
133
134 Specifies that all nodes should be visited.
135
136 TRAVERSE_MASK
137
138 Combination of multiple traverse flags.
139
140 ORDER FLAGS
141
142 Specifies the type of traversal performed by traverse() and find().
143
144 PRE_ORDER
145
146 Visits a node, then its children.
147
148 IN_ORDER
149
150 Visits a node's left child first, then the node itself, then its right child.
151 This is the one to use if you want the output sorted according to the compare
152 function.
153
154 POST_ORDER
155
156 Visits the node's children, then the node itself.
157
158 LEVEL_ORDER
159
160 Calls the function for each child of the node, then recursively visits each child.
161
162METHODS
163
164 new( [DATA] )
165
166 Creates a new Tree::Nary object. Used to create the first node in a tree.
167 Insert optional DATA into new created node.
168
169 insert( PARENT, POSITION, NODE )
170
171 Inserts a NODE beneath the PARENT at the given POSITION, returning
172 inserted NODE. If POSITION is -1, NODE is inserted as the last child
173 of PARENT.
174
175 insert_before( PARENT, SIBLING, NODE )
176
177 Inserts a NODE beneath the PARENT before the given SIBLING, returning
178 inserted NODE. If SIBLING is undef, the NODE is inserted as the last child
179 of PARENT.
180
181 append( PARENT, NODE )
182
183 Inserts a NODE as the last child of the given PARENT, returning inserted NODE.
184
185 prepend( PARENT, NODE )
186
187 Inserts a NODE as the first child of the given PARENT, returning inserted NODE.
188
189 insert_data( PARENT, POSITION, DATA )
190
191 Inserts a new node containing DATA, beneath the PARENT at the given POSITION.
192 Returns the new inserted node.
193
194 insert_data_before( PARENT, SIBLING, DATA )
195
196 Inserts a new node containing DATA, beneath the PARENT, before the given
197 SIBLING. Returns the new inserted node.
198
199 append_data( PARENT, DATA )
200
201 Inserts a new node containing DATA as the last child of the given PARENT.
202 Returns the new inserted node.
203
204 prepend_data( PARENT, DATA )
205
206 Inserts a new node containing DATA as the first child of the given PARENT.
207 Returns the new inserted node.
208
209 reverse_children( NODE )
210
211 Reverses the order of the children of NODE.
212 It doesn't change the order of the grandchildren.
213
214 traverse( NODE, ORDER, FLAGS, MAXDEPTH, FUNCTION, DATA )
215
216 Traverses a tree starting at the given root NODE. It calls the given FUNCTION
217 (with optional user DATA to pass to the FUNCTION) for each node visited.
218
219 The traversal can be halted at any point by returning TRUE from FUNCTION.
220
221 The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and
222 LEVEL_ORDER.
223
224 FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL,
225 TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.
226
227 MAXDEPTH is the maximum depth of the traversal. Nodes below this depth will not
228 be visited. If MAXDEPTH is -1, all nodes in the tree are visited. If MAXDEPTH
229 is 1, only the root is visited. If MAXDEPTH is 2, the root and its children are
230 visited. And so on.
231
232 children_foreach( NODE, FLAGS, FUNCTION, DATA )
233
234 Calls a FUNCTION (with optional user DATA to pass to the FUNCTION) for each
235 of the children of a NODE. Note that it doesn't descend beneath the child nodes.
236 FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL,
237 TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.
238
239 get_root( NODE )
240
241 Gets the root node of a tree, starting from NODE.
242
243 find( NODE, ORDER, FLAGS, DATA )
244
245 Finds a NODE in a tree with the given DATA.
246
247 The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and
248 LEVEL_ORDER.
249
250 FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL,
251 TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.
252
253 Returns the found node, or undef if the DATA is not found.
254
255 find_child( NODE, FLAGS, DATA )
256
257 Finds the first child of a NODE with the given DATA.
258
259 FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL,
260 TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.
261
262 Returns the found child node, or undef if the DATA is not found.
263
264 child_index( NODE, DATA )
265
266 Gets the position of the first child of a NODE which contains the given DATA.
267 Returns the index of the child of node which contains data, or -1 if DATA is
268 not found.
269
270 child_position( NODE, CHILD )
271
272 Gets the position of a NODE with respect to its siblings. CHILD must be a child
273 of NODE. The first child is numbered 0, the second 1, and so on. Returns the position
274 of CHILD with respect to its siblings.
275
276 first_child( NODE )
277
278 Returns the first child of a NODE. Returns undef if NODE is undef or has
279 no children.
280
281 last_child( NODE )
282
283 Returns the last child of a NODE. Returns undef if NODE is undef or has
284 no children.
285
286 nth_child( NODE, INDEX )
287
288 Gets a child of a NODE, using the given INDEX. The first child is at INDEX 0.
289 If the INDEX is too big, undef is returned. Returns the child of NODE at INDEX.
290
291 first_sibling( NODE )
292
293 Returns the first sibling of a NODE. This could possibly be the NODE itself.
294
295 prev_sibling( NODE )
296
297 Returns the previous sibling of a NODE.
298
299 next_sibling( NODE )
300
301 Returns the next sibling of a NODE.
302
303 last_sibling( NODE )
304
305 Returns the last sibling of a NODE. This could possibly be the NODE itself.
306
307 is_leaf( NODE )
308
309 Returns TRUE if NODE is a leaf node (no children).
310
311 is_root( NODE )
312
313 Returns TRUE if NODE is a root node (no parent nor siblings).
314
315 depth( NODE )
316
317 Returns the depth of NODE. If NODE is undef, the depth is 0. The root node has
318 a depth of 1. For the children of the root node, the depth is 2. And so on.
319
320 n_nodes( NODE, FLAGS )
321
322 Returns the number of nodes in a tree.
323
324 FLAGS specifies which types of children are to be counted, one of TRAVERSE_ALL,
325 TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS.
326
327 n_children( NODE )
328
329 Returns the number of children of NODE.
330
331 is_ancestor( NODE, DESCENDANT )
332
333 Returns TRUE if NODE is an ancestor of DESCENDANT. This is true if NODE is the
334 parent of DESCENDANT, or if NODE is the grandparent of DESCENDANT, etc.
335
336 max_height( NODE )
337
338 Returns the maximum height of all branches beneath NODE. This is the maximum
339 distance from NODE to all leaf nodes.
340
341 If NODE is undef, 0 is returned. If NODE has no children, 1 is returned.
342 If NODE has children, 2 is returned. And so on.
343
344 tsort( NODE )
345
346 Sorts all the children references of NODE according to the data field.
347
348 normalize( NODE )
349
350 Returns the normalized shape of NODE.
351
352 is_identical( NODE, ANOTHER_NODE )
353
354 Returns TRUE if NODE and ANOTHER_NODE have same structures and contents.
355
356 has_same_struct( NODE, ANOTHER_NODE )
357
358 Returns TRUE if the structure of NODE and ANOTHER_NODE are identical.
359
360 unlink( NODE )
361
362 Unlinks NODE from a tree, resulting in two separate trees.
363 The NODE to unlink becomes the root of a new tree.
364
365EXAMPLES
366
367 An example for each function can be found in the test suite bundled with
368 Tree::Nary.
369
370AUTHOR
371
372 Frederic Soriano, <fsoriano@cpan.org>
373
374COPYRIGHT
375
376 This package is free software and is provided "as is" without express or
377 implied warranty. It may be used, redistributed and/or modified under the
378 same terms as Perl itself.
379
380SEE ALSO
381
382 API from the GLIB project,
383 http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html.
384