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