GLib.Tree¶

record (struct)

The GTree struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions.

Constructors¶

new_full¶

@classmethod
def new_full(cls, key_compare_func: CompareDataFunc, key_destroy_func: DestroyNotify) -> Tree

Creates a new 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 the Tree.

Parameters:

key_compare_func — qsort()-style comparison function
key_destroy_func — a function to free the memory allocated for the key used when removing the entry from the Tree or None if you don't want to supply such a function

Methods¶

destroy¶

def destroy(self) -> None

Removes all keys and values from the Tree and decreases its reference count by one. If keys and/or values are dynamically allocated, you should either free them first or create the Tree using Tree.new_full. In the latter case the destroy functions you supplied will be called on all keys and values before destroying the Tree.

foreach¶

def foreach(self, func: TraverseFunc) -> None

Calls the given function for each of the key/value pairs in the 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 GTraverseFunc as you walk over the tree, then walk the list and remove each item.

Parameters:

func — the function to call for each node visited. If this function returns True, the traversal is stopped.

foreach_node¶

def foreach_node(self, func: TraverseNodeFunc) -> None

Calls the given function for each of the nodes in the Tree. The function is passed the pointer to the particular node, and the given data parameter. The tree traversal happens in-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 GTraverseFunc as you walk over the tree, then walk the list and remove each item.

Parameters:

func — the function to call for each node visited. If this function returns True, the traversal is stopped.

height¶

def height(self) -> int

Gets the height of a Tree.

If the Tree contains no nodes, the height is 0. If the Tree contains only one root node the height is 1. If the root node has children the height is 2, etc.

insert¶

def insert(self, key: int | None = ..., value: int | None = ...) -> None

Inserts a key/value pair into a Tree.

Inserts a new key and value into a Tree as Tree.insert_node does, only this function does not return the inserted or set node.

Parameters:

key — the key to insert
value — the value corresponding to the key

insert_node¶

def insert_node(self, key: int | None = ..., value: int | None = ...) -> TreeNode | None

Inserts a key/value pair into a Tree.

If the given key already exists in the Tree its corresponding value is set to the new value. If you supplied a value_destroy_func when creating the Tree, the old value is freed using that function. If you supplied a key_destroy_func when creating the 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)).

Parameters:

key — the key to insert
value — the value corresponding to the key

lookup¶

def lookup(self, key: int | None = ...) -> int | None

Gets the value corresponding to the given key. Since a 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).

Parameters:

key — the key to look up

lookup_extended¶

def lookup_extended(self, lookup_key: int | None = ...) -> tuple[bool, int, int]

Looks up a key in the 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 calling Tree.remove.

Parameters:

lookup_key — the key to look up

lookup_node¶

def lookup_node(self, key: int | None = ...) -> TreeNode | None

Gets the tree node corresponding to the given key. Since a 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).

Parameters:

key — the key to look up

lower_bound¶

def lower_bound(self, key: int | None = ...) -> TreeNode | None

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.

Parameters:

key — the key to calculate the lower bound for

nnodes¶

def nnodes(self) -> int

Gets the number of nodes in a Tree.

node_first¶

def node_first(self) -> TreeNode | None

Returns the first in-order node of the tree, or None for an empty tree.

node_last¶

def node_last(self) -> TreeNode | None

Returns the last in-order node of the tree, or None for an empty tree.

ref¶

def ref(self) -> Tree

Increments the reference count of tree by one.

It is safe to call this function from any thread.

remove¶

def remove(self, key: int | None = ...) -> bool

Removes a key/value pair from a Tree.

If the Tree was created using 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 the 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)).

Parameters:

key — the key to remove

remove_all¶

def remove_all(self) -> None

Removes all nodes from a Tree and destroys their keys and values, then resets the Tree’s root to None.

replace¶

def replace(self, key: int | None = ..., value: int | None = ...) -> None

Inserts a new key and value into a Tree as Tree.replace_node does, only this function does not return the inserted or set node.

Parameters:

key — the key to insert
value — the value corresponding to the key

replace_node¶

def replace_node(self, key: int | None = ..., value: int | None = ...) -> TreeNode | None

Inserts a new key and value into a Tree similar to Tree.insert_node. The difference is that if the key already exists in the Tree, it gets replaced by the new key. If you supplied a value_destroy_func when creating the Tree, the old value is freed using that function. If you supplied a key_destroy_func when creating the 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.

Parameters:

key — the key to insert
value — the value corresponding to the key

search¶

def search(self, search_func: CompareFunc) -> int | None

Searches a 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 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.

Parameters:

search_func — a function used to search the Tree

search_node¶

def search_node(self, search_func: CompareFunc) -> TreeNode | None

Searches a 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 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.

Parameters:

search_func — a function used to search the Tree

steal¶

def steal(self, key: int | None = ...) -> bool

Removes a key and its associated value from a Tree without calling the key and value destroy functions.

If the key does not exist in the Tree, the function does nothing.

Parameters:

key — the key to remove

traverse¶

def traverse(self, traverse_func: TraverseFunc, traverse_type: TraverseType | int) -> None

:::warning Deprecated since 2.2 This API is deprecated. :::

Calls the given function for each node in the Tree.

Parameters:

traverse_func — the function to call for each node visited. If this function returns True, the traversal is stopped.
traverse_type — the order in which nodes are visited, one of TraverseType.IN_ORDER, TraverseType.PRE_ORDER and TraverseType.POST_ORDER

unref¶

def unref(self) -> None

Decrements the reference count of tree 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 tree will be released.

It is safe to call this function from any thread.

upper_bound¶

def upper_bound(self, key: int | None = ...) -> TreeNode | None

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.

Parameters:

key — the key to calculate the upper bound for