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