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