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

   1 <!-- ##### SECTION Title ##### -->
   2 Balanced Binary Trees
   3
   4 <!-- ##### SECTION Short_Description ##### -->
   5 a sorted collection of key/value pairs optimised for searching
   6 and traversing in order.
   7
   8 <!-- ##### SECTION Long_Description ##### -->
   9 <para>
  10 The #GTree structure and its associated functions provide a sorted collection
  11 of key/value pairs optimised for searching and traversing in order.
  12 </para>
  13 <para>
  14 To create a new #GTree use g_tree_new().
  15 </para>
  16 <para>
  17 To insert a key/value pair into a #GTree use g_tree_insert().
  18 </para>
  19 <para>
  20 To lookup the value corresponding to a given key, use g_tree_lookup().
  21 </para>
  22 <para>
  23 To find out the number of nodes in a #GTree, use g_tree_nnodes().
  24 To get the height of a #GTree, use g_tree_height().
  25 </para>
  26 <para>
  27 To traverse a #GTree, calling a function for each node visited in the
  28 traversal, use g_tree_traverse().
  29 </para>
  30 <para>
  31 To remove a key/value pair use g_tree_remove().
  32 </para>
  33 <para>
  34 To destroy a #GTree, use g_tree_destroy().
  35 </para>
  36
  37 <!-- ##### SECTION See_Also ##### -->
  38 <para>
  39
  40 </para>
  41
  42 <!-- ##### STRUCT GTree ##### -->
  43 <para>
  44 The #GTree struct is an opaque data structure representing a
  45 <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>.
  46 It should be accessed only by using the following functions.
  47 </para>
  48
  49
  50 <!-- ##### FUNCTION g_tree_new ##### -->
  51 <para>
  52 Creates a new GTree.
  53 </para>
  54
  55 @key_compare_func: the function used to order the nodes in the #GTree.
  56 It should return values similar to the standard <function>strcmp()</function>
  57 function -
  58 0 if the two arguments are equal, a negative value if the first argument comes
  59 before the second, or a positive value if the first argument comes after the
  60 second.
  61 @Returns: a new #GTree.
  62
  63
  64 <!-- ##### FUNCTION g_tree_insert ##### -->
  65 <para>
  66 Inserts a key/value pair into a #GTree.
  67 If the given key already exists in the #GTree it is set to the new value.
  68 (If you are using dynamically allocated keys and values you should be careful
  69 to ensure that the old values are freed.)
  70 </para>
  71 <para>
  72 The tree is automatically 'balanced' as new key/value pairs are added,
  73 so that the distance from the root to every leaf is as small as possible.
  74 </para>
  75
  76 @tree: a #GTree.
  77 @key: the key to insert.
  78 @value: the value corresponding to the key.
  79
  80
  81 <!-- ##### FUNCTION g_tree_nnodes ##### -->
  82 <para>
  83 Gets the number of nodes in a #GTree.
  84 </para>
  85
  86 @tree: a #GTree.
  87 @Returns: the number of nodes in the #GTree.
  88
  89
  90 <!-- ##### FUNCTION g_tree_height ##### -->
  91 <para>
  92 Gets the height of a #GTree.
  93 </para>
  94 <para>
  95 If the #GTree contains no nodes, the height is 0.
  96 If the #GTree contains only one root node the height is 1.
  97 If the root node has children the height is 2, etc.
  98 </para>
  99
 100 @tree: a #GTree.
 101 @Returns: the height of the #GTree.
 102
 103
 104 <!-- ##### FUNCTION g_tree_lookup ##### -->
 105 <para>
 106 Gets the value corresponding to the given key.
 107 Since a #GTree is automatically balanced as key/value pairs are
 108 added, key lookup is very fast.
 109 </para>
 110
 111 @tree: a #GTree.
 112 @key: the key to look up.
 113 @Returns: the value corresponding to the key.
 114
 115
 116 <!-- ##### FUNCTION g_tree_search ##### -->
 117 <para>
 118 Searches a #GTree using an alternative form of the comparison function.
 119 </para>
 120 <para>
 121 This function is not as useful as it sounds.
 122 It allows you to use a different function for performing the lookup of
 123 a key. However, since the tree is ordered according to the @key_compare_func
 124 function passed to g_tree_new(), the function you pass to g_tree_search() must
 125 return exactly the same value as would be returned by the comparison function,
 126 for each pair of tree nodes, or the search will not work.
 127 </para>
 128 <para>
 129 To search for a specific value, you can use g_tree_traverse().
 130 </para>
 131
 132 @tree: a #GTree.
 133 @search_func: the comparison function used to search the #GTree.
 134 @data: the data passed as the second argument to the @search_func function.
 135 @Returns: the value corresponding to the found key, or NULL if the key is
 136 not found.
 137
 138
 139 <!-- ##### FUNCTION g_tree_traverse ##### -->
 140 <para>
 141 Calls the given function for each node in the GTree.
 142 </para>
 143
 144 @tree: a #GTree.
 145 @traverse_func: the function to call for each node visited. If this function
 146 returns TRUE, the traversal is stopped.
 147 @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 148 %G_PRE_ORDER and %G_POST_ORDER.
 149 @data: user data to pass to the traverse function.
 150
 151
 152 <!-- ##### USER_FUNCTION GTraverseFunc ##### -->
 153 <para>
 154 Specifies the type of function passed to g_tree_traverse().
 155 It is passed the key and value of each node, together with
 156 the @user_data parameter passed to g_tree_traverse().
 157 If the function returns TRUE, the traversal is stopped.
 158 </para>
 159
 160 @key: a key of a #GTree node.
 161 @value: the value corresponding to the key.
 162 @data: user data passed to g_tree_traverse().
 163 @Returns: TRUE to stop the traversal.
 164
 165
 166 <!-- ##### ENUM GTraverseType ##### -->
 167 <para>
 168 Specifies the type of traveral performed by g_tree_traverse(),
 169 g_node_traverse() and g_node_find().
 170 <itemizedlist>
 171 <listitem><para>
 172 %G_PRE_ORDER visits a node, then its children.
 173 </para></listitem>
 174 <listitem><para>
 175 %G_IN_ORDER vists a node's left child first, then the node itself, then its
 176 right child. This is the one to use if you want the output sorted according
 177 to the compare function.
 178 </para></listitem>
 179 <listitem><para>
 180 %G_POST_ORDER visits the node's children, then the node itself.
 181 </para></listitem>
 182 <listitem><para>
 183 %G_LEVEL_ORDER is not implemented for
 184 <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Trees</link>.
 185 For <link linkend="glib-N-ary-Trees">N-ary Trees</link>
 186 it calls the function for each child of the node, then it recursively visits
 187 each child.
 188 </para></listitem>
 189 </itemizedlist>
 190 </para>
 191
 192 @G_IN_ORDER:
 193 @G_PRE_ORDER:
 194 @G_POST_ORDER:
 195 @G_LEVEL_ORDER:
 196
 197 <!-- ##### FUNCTION g_tree_remove ##### -->
 198 <para>
 199 Removes a key/value pair from a #GTree.
 200 If the key or value is dynamically allocated you must remember to free them
 201 yourself.
 202 </para>
 203
 204 @tree: a #GTree.
 205 @key: the key to remove.
 206
 207
 208 <!-- ##### FUNCTION g_tree_destroy ##### -->
 209 <para>
 210 Destroys the #GTree, freeing all of the memory allocated.
 211 But it doesn't free keys or values.
 212 </para>
 213
 214 @tree: a #GTree.
 215
 216