docs/reference/glib/tmpl/trees-nary.sgml

   1 <!-- ##### SECTION Title ##### -->
   2 N-ary Trees
   3
   4 <!-- ##### SECTION Short_Description ##### -->
   5 trees of data with any number of branches.
   6
   7 <!-- ##### SECTION Long_Description ##### -->
   8 <para>
   9 The #GNode struct and its associated functions provide a N-ary tree data
  10 structure, where nodes in the tree can contain arbitrary data.
  11 </para>
  12 <para>
  13 To create a new tree use g_node_new().
  14 </para>
  15 <para>
  16 To insert a node into a tree use g_node_insert(), g_node_insert_before(),
  17 g_node_append() and g_node_prepend().
  18 </para>
  19 <para>
  20 To create a new node and insert it into a tree use g_node_insert_data(),
  21 g_node_insert_data_before(), g_node_append_data() and g_node_prepend_data().
  22 </para>
  23 <para>
  24 To reverse the children of a node use g_node_reverse_children().
  25 </para>
  26 <para>
  27 To find a node use g_node_get_root(), g_node_find(), g_node_find_child(),
  28 g_node_child_index(), g_node_child_position(),
  29 g_node_first_child(), g_node_last_child(),
  30 g_node_nth_child(), g_node_first_sibling(), g_node_prev_sibling(),
  31 g_node_next_sibling() or g_node_last_sibling().
  32 </para>
  33 <para>
  34 To get information about a node or tree use G_NODE_IS_LEAF(),
  35 G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(), g_node_n_children(),
  36 g_node_is_ancestor() or g_node_max_height().
  37 </para>
  38 <para>
  39 To traverse a tree, calling a function for each node visited in the
  40 traversal, use g_node_traverse() or g_node_children_foreach().
  41 </para>
  42 <para>
  43 To remove a node or subtree from a tree use g_node_unlink() or
  44 g_node_destroy().
  45 </para>
  46
  47 <!-- ##### SECTION See_Also ##### -->
  48 <para>
  49
  50 </para>
  51
  52 <!-- ##### STRUCT GNode ##### -->
  53 <para>
  54 The #GNode struct represents one node in a
  55 <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
  56 The <structfield>data</structfield> field contains the actual data of the node.
  57 The <structfield>next</structfield> and <structfield>prev</structfield>
  58 fields point to the node's siblings (a sibling is another #GNode with the
  59 same parent).
  60 The <structfield>parent</structfield> field points to the parent of the #GNode,
  61 or is NULL if the #GNode is the root of the tree.
  62 The <structfield>children</structfield> field points to the first child of the
  63 #GNode. The other children are accessed by using the
  64 <structfield>next</structfield> pointer of each child.
  65 </para>
  66
  67 @data:
  68 @next:
  69 @prev:
  70 @parent:
  71 @children:
  72
  73 <!-- ##### FUNCTION g_node_new ##### -->
  74 <para>
  75 Creates a new #GNode containing the given data.
  76 Used to create the first node in a tree.
  77 </para>
  78
  79 @data: the data of the new node.
  80 @Returns: a new #GNode.
  81
  82
  83 <!-- ##### FUNCTION g_node_copy ##### -->
  84 <para>
  85
  86 </para>
  87
  88 @node:
  89 @Returns:
  90
  91
  92 <!-- ##### FUNCTION g_node_insert ##### -->
  93 <para>
  94 Inserts a #GNode beneath the parent at the given position.
  95 </para>
  96
  97 @parent: the #GNode to place @node under.
  98 @position: the position to place @node at, with respect to its siblings.
  99 If position is -1, @node is inserted as the last child of @parent.
 100 @node: the #GNode to insert.
 101 @Returns: the inserted #GNode.
 102
 103
 104 <!-- ##### FUNCTION g_node_insert_before ##### -->
 105 <para>
 106 Inserts a #GNode beneath the parent before the given sibling.
 107 </para>
 108
 109 @parent: the #GNode to place @node under.
 110 @sibling: the sibling #GNode to place @node before. If sibling is NULL,
 111 the node is inserted as the last child of @parent.
 112 @node: the #GNode to insert.
 113 @Returns: the inserted #GNode.
 114
 115
 116 <!-- ##### MACRO g_node_append ##### -->
 117 <para>
 118 Inserts a #GNode as the last child of the given parent.
 119 </para>
 120
 121 @parent: the #GNode to place the new #GNode under.
 122 @node: the #GNode to insert.
 123 @Returns: the inserted #GNode.
 124
 125
 126 <!-- ##### FUNCTION g_node_prepend ##### -->
 127 <para>
 128 Inserts a #GNode as the first child of the given parent.
 129 </para>
 130
 131 @parent: the #GNode to place the new #GNode under.
 132 @node: the #GNode to insert.
 133 @Returns: the inserted #GNode.
 134
 135
 136 <!-- ##### MACRO g_node_insert_data ##### -->
 137 <para>
 138 Inserts a new #GNode at the given position.
 139 </para>
 140
 141 @parent: the #GNode to place the new #GNode under.
 142 @position: the position to place the new #GNode at.
 143 If position is -1, the new #GNode is inserted as the last child of @parent.
 144 @data: the data for the new #GNode.
 145 @Returns: the new #GNode.
 146
 147
 148 <!-- ##### MACRO g_node_insert_data_before ##### -->
 149 <para>
 150 Inserts a new #GNode before the given sibling.
 151 </para>
 152
 153 @parent: the #GNode to place the new #GNode under.
 154 @sibling: the sibling #GNode to place the new #GNode before.
 155 @data: the data for the new #GNode.
 156 @Returns: the new #GNode.
 157
 158
 159 <!-- ##### MACRO g_node_append_data ##### -->
 160 <para>
 161 Inserts a new #GNode as the last child of the given parent.
 162 </para>
 163
 164 @parent: the #GNode to place the new #GNode under.
 165 @data: the data for the new #GNode.
 166 @Returns: the new #GNode.
 167
 168
 169 <!-- ##### MACRO g_node_prepend_data ##### -->
 170 <para>
 171 Inserts a new #GNode as the first child of the given parent.
 172 </para>
 173
 174 @parent: the #GNode to place the new #GNode under.
 175 @data: the data for the new #GNode.
 176 @Returns: the new #GNode.
 177
 178
 179 <!-- ##### FUNCTION g_node_reverse_children ##### -->
 180 <para>
 181 Reverses the order of the children of a #GNode.
 182 (It doesn't change the order of the grandchildren.)
 183 </para>
 184
 185 @node: a #GNode.
 186
 187
 188 <!-- ##### FUNCTION g_node_traverse ##### -->
 189 <para>
 190 Traverses a tree starting at the given root #GNode.
 191 It calls the given function for each node visited.
 192 The traversal can be halted at any point by returning TRUE from @func.
 193 </para>
 194
 195 @root: the root #GNode of the tree to traverse.
 196 @order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
 197 %G_POST_ORDER, or %G_LEVEL_ORDER.
 198 @flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
 199 %G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
 200 @max_depth: the maximum depth of the traversal. Nodes below this
 201 depth will not be visited. If max_depth is -1 all nodes in the tree are
 202 visited. If depth is 1, only the root is visited. If depth is 2, the root
 203 and its children are visited. And so on.
 204 @func: the function to call for each visited #GNode.
 205 @data: user data to pass to the function.
 206
 207
 208 <!-- ##### ENUM GTraverseFlags ##### -->
 209 <para>
 210 Specifies which nodes are visited during several of the tree functions,
 211 including g_node_traverse() and g_node_find().
 212 <itemizedlist>
 213 <listitem><para>
 214 %G_TRAVERSE_LEAFS specifies that only leaf nodes should be visited.
 215 </para></listitem>
 216 <listitem><para>
 217 %G_TRAVERSE_NON_LEAFS specifies that only non-leaf nodes should be visited.
 218 </para></listitem>
 219 <listitem><para>
 220 %G_TRAVERSE_ALL specifies that all nodes should be visited.
 221 </para></listitem>
 222 </itemizedlist>
 223 </para>
 224
 225 @G_TRAVERSE_LEAFS:
 226 @G_TRAVERSE_NON_LEAFS:
 227 @G_TRAVERSE_ALL:
 228 @G_TRAVERSE_MASK:
 229
 230 <!-- ##### USER_FUNCTION GNodeTraverseFunc ##### -->
 231 <para>
 232 Specifies the type of function passed to g_node_traverse().
 233 The function is called with each of the nodes visited, together with the
 234 user data passed to g_node_traverse().
 235 If the function returns TRUE, then the traversal is stopped.
 236 </para>
 237
 238 @node: a #GNode.
 239 @data: user data passed to g_node_traverse().
 240 @Returns: TRUE to stop the traversal.
 241
 242
 243 <!-- ##### FUNCTION g_node_children_foreach ##### -->
 244 <para>
 245 Calls a function for each of the children of a #GNode.
 246 Note that it doesn't descend beneath the child nodes.
 247 </para>
 248
 249 @node: a #GNode.
 250 @flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
 251 %G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
 252 @func: the function to call for each visited node.
 253 @data: user data to pass to the function.
 254
 255
 256 <!-- ##### USER_FUNCTION GNodeForeachFunc ##### -->
 257 <para>
 258 Specifies the type of function passed to g_node_children_foreach().
 259 The function is called with each child node, together with the user data
 260 passed to g_node_children_foreach().
 261 </para>
 262
 263 @node: a #GNode.
 264 @data: user data passed to g_node_children_foreach().
 265
 266
 267 <!-- ##### FUNCTION g_node_get_root ##### -->
 268 <para>
 269 Gets the root of a tree.
 270 </para>
 271
 272 @node: a #GNode.
 273 @Returns: the root of the tree.
 274
 275
 276 <!-- ##### FUNCTION g_node_find ##### -->
 277 <para>
 278 Finds a #GNode in a tree.
 279 </para>
 280
 281 @root: the root #GNode of the tree to search.
 282 @order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
 283 %G_POST_ORDER, or %G_LEVEL_ORDER.
 284 @flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
 285 %G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
 286 @data: the data to find.
 287 @Returns: the found #GNode, or NULL if the data is not found.
 288
 289
 290 <!-- ##### FUNCTION g_node_find_child ##### -->
 291 <para>
 292 Finds the first child of a #GNode with the given data.
 293 </para>
 294
 295 @node: a #GNode.
 296 @flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
 297 %G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
 298 @data: the data to find.
 299 @Returns: the found child #GNode, or NULL if the data is not found.
 300
 301
 302 <!-- ##### FUNCTION g_node_child_index ##### -->
 303 <para>
 304 Gets the position of the first child of a #GNode which contains the given data.
 305 </para>
 306
 307 @node: a #GNode.
 308 @data: the data to find.
 309 @Returns: the index of the child of @node which contains @data, or -1
 310 if the data is not found.
 311
 312
 313 <!-- ##### FUNCTION g_node_child_position ##### -->
 314 <para>
 315 Gets the position of a #GNode with respect to its siblings.
 316 @child must be a child of @node.
 317 The first child is numbered 0, the second 1, and so on.
 318 </para>
 319
 320 @node: a #GNode.
 321 @child: a child of @node.
 322 @Returns: the position of @child with respect to its siblings.
 323
 324
 325 <!-- ##### MACRO g_node_first_child ##### -->
 326 <para>
 327 Gets the first child of a #GNode.
 328 </para>
 329
 330 @node: a #GNode.
 331 @Returns: the last child of @node, or NULL if @node is NULL or has no children.
 332
 333
 334 <!-- ##### FUNCTION g_node_last_child ##### -->
 335 <para>
 336 Gets the last child of a #GNode.
 337 </para>
 338
 339 @node: a #GNode (must not be NULL).
 340 @Returns: the last child of @node, or NULL if @node has no children.
 341
 342
 343 <!-- ##### FUNCTION g_node_nth_child ##### -->
 344 <para>
 345 Gets a child of a #GNode, using the given index.
 346 The first child is at index 0. If the index is too big, NULL is returned.
 347 </para>
 348
 349 @node: a #GNode.
 350 @n: the index of the desired child.
 351 @Returns: the child of @node at index @n.
 352
 353
 354 <!-- ##### FUNCTION g_node_first_sibling ##### -->
 355 <para>
 356 Gets the first sibling of a #GNode.
 357 This could possibly be the node itself.
 358 </para>
 359
 360 @node: a #GNode.
 361 @Returns: the first sibling of @node.
 362
 363
 364 <!-- ##### MACRO g_node_next_sibling ##### -->
 365 <para>
 366 Gets the next sibling of a #GNode.
 367 </para>
 368
 369 @node: a #GNode.
 370 @Returns: the next sibling of @node, or NULL if @node is NULL.
 371
 372
 373 <!-- ##### MACRO g_node_prev_sibling ##### -->
 374 <para>
 375 Gets the previous sibling of a #GNode.
 376 </para>
 377
 378 @node: a #GNode.
 379 @Returns: the previous sibling of @node, or NULL if @node is NULL.
 380
 381
 382 <!-- ##### FUNCTION g_node_last_sibling ##### -->
 383 <para>
 384 Gets the last sibling of a #GNode.
 385 This could possibly be the node itself.
 386 </para>
 387
 388 @node: a #GNode.
 389 @Returns: the last sibling of @node.
 390
 391
 392 <!-- ##### MACRO G_NODE_IS_LEAF ##### -->
 393 <para>
 394 Returns TRUE if a #GNode is a leaf node.
 395 </para>
 396
 397 @node: a #GNode.
 398 @Returns: TRUE if the #GNode is a leaf node (i.e. it has no children).
 399
 400
 401 <!-- ##### MACRO G_NODE_IS_ROOT ##### -->
 402 <para>
 403 Returns TRUE if a #GNode is the root of a tree.
 404 </para>
 405
 406 @node: a #GNode.
 407 @Returns: TRUE if the #GNode is the root of a tree (i.e. it has no parent
 408 or siblings).
 409
 410
 411 <!-- ##### FUNCTION g_node_depth ##### -->
 412 <para>
 413 Gets the depth of a #GNode.
 414 </para>
 415 <para>
 416 If @node is NULL the depth is 0.
 417 The root node has a depth of 1.
 418 For the children of the root node the depth is 2. And so on.
 419 </para>
 420
 421 @node: a #GNode.
 422 @Returns: the depth of the #GNode.
 423
 424
 425 <!-- ##### FUNCTION g_node_n_nodes ##### -->
 426 <para>
 427 Gets the number of nodes in a tree.
 428 </para>
 429
 430 @root: a #GNode.
 431 @flags: which types of children are to be counted, one of %G_TRAVERSE_ALL,
 432 %G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
 433 @Returns: the number of nodes in the tree.
 434
 435
 436 <!-- ##### FUNCTION g_node_n_children ##### -->
 437 <para>
 438 Gets the number of children of a #GNode.
 439 </para>
 440
 441 @node: a #GNode.
 442 @Returns: the number of children of @node.
 443
 444
 445 <!-- ##### FUNCTION g_node_is_ancestor ##### -->
 446 <para>
 447 Returns TRUE if @node is an ancestor of @descendant.
 448 This is true if node is the parent of descendant, or if node is the
 449 grandparent of descendant etc.
 450 </para>
 451
 452 @node: a #GNode.
 453 @descendant: a #GNode.
 454 @Returns: TRUE if @node is an ancestor of @descendant.
 455
 456
 457 <!-- ##### FUNCTION g_node_max_height ##### -->
 458 <para>
 459 Gets the maximum height of all branches beneath a #GNode.
 460 This is the maximum distance from the #GNode to all leaf nodes.
 461 </para>
 462 <para>
 463 If @root is NULL, 0 is returned. If @root has no children, 1 is returned.
 464 If @root has children, 2 is returned. And so on.
 465 </para>
 466
 467 @root: a #GNode.
 468 @Returns: the maximum height of the tree beneath @root.
 469
 470
 471 <!-- ##### FUNCTION g_node_unlink ##### -->
 472 <para>
 473 Unlinks a #GNode from a tree, resulting in two separate trees.
 474 </para>
 475
 476 @node: the #GNode to unlink, which becomes the root of a new tree.
 477
 478
 479 <!-- ##### FUNCTION g_node_destroy ##### -->
 480 <para>
 481 Removes the #GNode and its children from the tree, freeing any memory
 482 allocated.
 483 </para>
 484
 485 @root: the root of the tree/subtree to destroy.
 486
 487
 488 <!-- ##### FUNCTION g_node_push_allocator ##### -->
 489 <para>
 490 Sets the allocator to use to allocate #GNode elements.
 491 Use g_node_pop_allocator() to restore the previous allocator.
 492 </para>
 493
 494 @allocator: the #GAllocator to use when allocating #GNode elements.
 495
 496
 497 <!-- ##### FUNCTION g_node_pop_allocator ##### -->
 498 <para>
 499 Restores the previous #GAllocator, used when allocating #GNode elements.
 500 </para>
 501
 502
 503