GLib.Tree¶
Fields¶
None
Methods¶
class 
















































Details¶
 class GLib.Tree¶
The
GLib.Tree
struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions. classmethod new_full(key_compare_func, key_compare_data, key_destroy_func)[source]¶
 Parameters:
key_compare_func (
GLib.CompareDataFunc
) – qsort()style comparison functionkey_compare_data (
object
orNone
) – data to pass to comparison functionkey_destroy_func (
GLib.DestroyNotify
) – a function to free the memory allocated for the key used when removing the entry from theGLib.Tree
orNone
if you don’t want to supply such a function
 Returns:
a newly allocated
GLib.Tree
 Return type:
Creates a new
GLib.Tree
like g_tree_new() and allows to specify functions to free the memory allocated for the key and value that get called when removing the entry from theGLib.Tree
.
 destroy()[source]¶
Removes all keys and values from the
GLib.Tree
and decreases its reference count by one. If keys and/or values are dynamically allocated, you should either free them first or create theGLib.Tree
usingGLib.Tree.new_full
(). In the latter case the destroy functions you supplied will be called on all keys and values before destroying theGLib.Tree
.
 foreach(func, *user_data)[source]¶
 Parameters:
func (
GLib.TraverseFunc
) – the function to call for each node visited. If this function returnsTrue
, the traversal is stopped.user_data (
object
orNone
) – user data to pass to the function
Calls the given function for each of the key/value pairs in the
GLib.Tree
. The function is passed the key and value of each pair, and the given data parameter. The tree is traversed in sorted order.The tree may not be modified while iterating over it (you can’t add/remove items). To remove all items matching a predicate, you need to add each item to a list in your
GLib.TraverseFunc
as you walk over the tree, then walk the list and remove each item.
 foreach_node(func, *user_data)[source]¶
 Parameters:
func (
GLib.TraverseNodeFunc
) – the function to call for each node visited. If this function returnsTrue
, the traversal is stopped.user_data (
object
orNone
) – user data to pass to the function
Calls the given function for each of the nodes in the
GLib.Tree
. The function is passed the pointer to the particular node, and the given data parameter. The tree traversal happens inorder.The tree may not be modified while iterating over it (you can’t add/remove items). To remove all items matching a predicate, you need to add each item to a list in your
GLib.TraverseFunc
as you walk over the tree, then walk the list and remove each item.New in version 2.68.
 height()[source]¶
 Returns:
the height of self
 Return type:
Gets the height of a
GLib.Tree
.If the
GLib.Tree
contains no nodes, the height is 0. If theGLib.Tree
contains only one root node the height is 1. If the root node has children the height is 2, etc.
 insert(key, value)[source]¶
 Parameters:
Inserts a key/value pair into a
GLib.Tree
.Inserts a new key and value into a
GLib.Tree
asGLib.Tree.insert_node
() does, only this function does not return the inserted or set node.
 insert_node(key, value)[source]¶
 Parameters:
 Returns:
the inserted (or set) node or
None
if insertion would overflow the tree node counter. Return type:
Inserts a key/value pair into a
GLib.Tree
.If the given key already exists in the
GLib.Tree
its corresponding value is set to the new value. If you supplied a value_destroy_func when creating theGLib.Tree
, the old value is freed using that function. If you supplied a key_destroy_func when creating theGLib.Tree
, the passed key is freed using that function.The tree is automatically ‘balanced’ as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible. The cost of maintaining a balanced tree while inserting new key/value result in a O(n log(n)) operation where most of the other operations are O(log(n)).
New in version 2.68.
 lookup(key)[source]¶
 Parameters:
 Returns:
the value corresponding to the key, or
None
if the key was not found Return type:
Gets the value corresponding to the given key. Since a
GLib.Tree
is automatically balanced as key/value pairs are added, key lookup is O(log n) (where n is the number of key/value pairs in the tree).
 lookup_extended(lookup_key)[source]¶
 Parameters:
 Returns:
True
if the key was found in theGLib.Tree
 orig_key:
returns the original key
 value:
returns the value associated with the key
 Return type:
Looks up a key in the
GLib.Tree
, returning the original key and the associated value. This is useful if you need to free the memory allocated for the original key, for example before callingGLib.Tree.remove
().
 lookup_node(key)[source]¶
 Parameters:
 Returns:
the tree node corresponding to the key, or
None
if the key was not found Return type:
Gets the tree node corresponding to the given key. Since a
GLib.Tree
is automatically balanced as key/value pairs are added, key lookup is O(log n) (where n is the number of key/value pairs in the tree).New in version 2.68.
 lower_bound(key)[source]¶
 Parameters:
key (
object
orNone
) – the key to calculate the lower bound for Returns:
the tree node corresponding to the lower bound, or
None
if the tree is empty or has only keys strictly lower than the searched key. Return type:
Gets the lower bound node corresponding to the given key, or
None
if the tree is empty or all the nodes in the tree have keys that are strictly lower than the searched key.The lower bound is the first node that has its key greater than or equal to the searched key.
New in version 2.68.
 nnodes()[source]¶
 Returns:
the number of nodes in self
The node counter value type is really a
int
, but it is returned as aint
due to backward compatibility issues (can be cast back toint
to support its full range of values). Return type:
Gets the number of nodes in a
GLib.Tree
.
 node_first()[source]¶
 Returns:
the first node in the tree
 Return type:
Returns the first inorder node of the tree, or
None
for an empty tree.New in version 2.68.
 node_last()[source]¶
 Returns:
the last node in the tree
 Return type:
Returns the last inorder node of the tree, or
None
for an empty tree.New in version 2.68.
 ref()[source]¶

Increments the reference count of self by one.
It is safe to call this function from any thread.
New in version 2.22.
 remove(key)[source]¶
 Parameters:
 Returns:
True
if the key was found (prior to 2.8, this function returned nothing) Return type:
Removes a key/value pair from a
GLib.Tree
.If the
GLib.Tree
was created usingGLib.Tree.new_full
(), the key and value are freed using the supplied destroy functions, otherwise you have to make sure that any dynamically allocated values are freed yourself. If the key does not exist in theGLib.Tree
, the function does nothing.The cost of maintaining a balanced tree while removing a key/value result in a O(n log(n)) operation where most of the other operations are O(log(n)).
 remove_all()[source]¶
Removes all nodes from a
GLib.Tree
and destroys their keys and values, then resets theGLib.Tree
’s root toNone
.New in version 2.70.
 replace(key, value)[source]¶
 Parameters:
Inserts a new key and value into a
GLib.Tree
asGLib.Tree.replace_node
() does, only this function does not return the inserted or set node.
 replace_node(key, value)[source]¶
 Parameters:
 Returns:
the inserted (or set) node or
None
if insertion would overflow the tree node counter. Return type:
Inserts a new key and value into a
GLib.Tree
similar toGLib.Tree.insert_node
(). The difference is that if the key already exists in theGLib.Tree
, it gets replaced by the new key. If you supplied a value_destroy_func when creating theGLib.Tree
, the old value is freed using that function. If you supplied a key_destroy_func when creating theGLib.Tree
, the old key is freed using that function.The tree is automatically ‘balanced’ as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.
New in version 2.68.
 search(search_func, *user_data)[source]¶
 Parameters:
search_func (
GLib.CompareFunc
) – a function used to search theGLib.Tree
user_data (
object
orNone
) – the data passed as the second argument to search_func
 Returns:
the value corresponding to the found key, or
None
if the key was not found Return type:
Searches a
GLib.Tree
using search_func.The search_func is called with a pointer to the key of a key/value pair in the tree, and the passed in user_data. If search_func returns 0 for a key/value pair, then the corresponding value is returned as the result of
GLib.Tree.search
(). If search_func returns 1, searching will proceed among the key/value pairs that have a smaller key; if search_func returns 1, searching will proceed among the key/value pairs that have a larger key.
 search_node(search_func, *user_data)[source]¶
 Parameters:
search_func (
GLib.CompareFunc
) – a function used to search theGLib.Tree
user_data (
object
orNone
) – the data passed as the second argument to search_func
 Returns:
the node corresponding to the found key, or
None
if the key was not found Return type:
Searches a
GLib.Tree
using search_func.The search_func is called with a pointer to the key of a key/value pair in the tree, and the passed in user_data. If search_func returns 0 for a key/value pair, then the corresponding node is returned as the result of
GLib.Tree.search
(). If search_func returns 1, searching will proceed among the key/value pairs that have a smaller key; if search_func returns 1, searching will proceed among the key/value pairs that have a larger key.New in version 2.68.
 steal(key)[source]¶
 Parameters:
 Returns:
True
if the key was found (prior to 2.8, this function returned nothing) Return type:
Removes a key and its associated value from a
GLib.Tree
without calling the key and value destroy functions.If the key does not exist in the
GLib.Tree
, the function does nothing.
 traverse(traverse_func, traverse_type, *user_data)[source]¶
 Parameters:
traverse_func (
GLib.TraverseFunc
) – the function to call for each node visited. If this function returnsTrue
, the traversal is stopped.traverse_type (
GLib.TraverseType
) – the order in which nodes are visited, one ofGLib.TraverseType.IN_ORDER
,GLib.TraverseType.PRE_ORDER
andGLib.TraverseType.POST_ORDER
user_data (
object
orNone
) – user data to pass to the function
Calls the given function for each node in the
GLib.Tree
.Deprecated since version 2.2: The order of a balanced tree is somewhat arbitrary. If you just want to visit all nodes in sorted order, use
GLib.Tree.foreach
() instead. If you really need to visit nodes in a different order, consider using an nary tree.
 unref()[source]¶
Decrements the reference count of self by one. If the reference count drops to 0, all keys and values will be destroyed (if destroy functions were specified) and all memory allocated by self will be released.
It is safe to call this function from any thread.
New in version 2.22.
 upper_bound(key)[source]¶
 Parameters:
key (
object
orNone
) – the key to calculate the upper bound for Returns:
the tree node corresponding to the upper bound, or
None
if the tree is empty or has only keys lower than or equal to the searched key. Return type:
Gets the upper bound node corresponding to the given key, or
None
if the tree is empty or all the nodes in the tree have keys that are lower than or equal to the searched key.The upper bound is the first node that has its key strictly greater than the searched key.
New in version 2.68.