:right-sidebar: True Tree =================================================================== .. currentmodule:: gi.repository.GLib .. class:: Tree(*args, **kwargs) :no-contents-entry: The GTree struct is an opaque data structure representing a [balanced binary tree][glib-Balanced-Binary-Trees]. It should be accessed only by using the following functions. Constructors ------------ .. rst-class:: interim-class .. class:: Tree :no-index: .. classmethod:: new_full(key_compare_func: ~typing.Callable[[~typing.Any, ~typing.Any, ~typing.Any], int], key_compare_data: ~typing.Any, key_destroy_func: ~typing.Callable[[~typing.Any], None]) -> ~gi.repository.GLib.Tree Creates a new :obj:`~gi.repository.GLib.Tree` like :func:`~gi.repository.GLib.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 :obj:`~gi.repository.GLib.Tree`\. :param key_compare_func: qsort()-style comparison function :param key_compare_data: data to pass to comparison function :param key_destroy_func: a function to free the memory allocated for the key used when removing the entry from the :obj:`~gi.repository.GLib.Tree` or :const:`None` if you don't want to supply such a function Methods ------- .. rst-class:: interim-class .. class:: Tree :no-index: .. method:: destroy() -> None Removes all keys and values from the :obj:`~gi.repository.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 the :obj:`~gi.repository.GLib.Tree` using :func:`~gi.repository.GLib.Tree.new_full`. In the latter case the destroy functions you supplied will be called on all keys and values before destroying the :obj:`~gi.repository.GLib.Tree`\. .. method:: foreach(func: ~typing.Callable[[~typing.Any, ~typing.Any, ~typing.Any], bool], user_data: ~typing.Any = None) -> None Calls the given function for each of the key/value pairs in the :obj:`~gi.repository.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 :obj:`~gi.repository.GLib.TraverseFunc` as you walk over the tree, then walk the list and remove each item. :param func: the function to call for each node visited. If this function returns :const:`True`, the traversal is stopped. :param user_data: user data to pass to the function .. method:: foreach_node(func: ~typing.Callable[[~gi.repository.GLib.TreeNode, ~typing.Any], bool], user_data: ~typing.Any = None) -> None Calls the given function for each of the nodes in the :obj:`~gi.repository.GLib.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 :obj:`~gi.repository.GLib.TraverseFunc` as you walk over the tree, then walk the list and remove each item. .. versionadded:: 2.68 :param func: the function to call for each node visited. If this function returns :const:`True`, the traversal is stopped. :param user_data: user data to pass to the function .. method:: height() -> int Gets the height of a :obj:`~gi.repository.GLib.Tree`\. If the :obj:`~gi.repository.GLib.Tree` contains no nodes, the height is 0. If the :obj:`~gi.repository.GLib.Tree` contains only one root node the height is 1. If the root node has children the height is 2, etc. .. method:: insert(key: ~typing.Any = None, value: ~typing.Any = None) -> None Inserts a key/value pair into a :obj:`~gi.repository.GLib.Tree`\. Inserts a new key and value into a :obj:`~gi.repository.GLib.Tree` as :func:`~gi.repository.GLib.Tree.insert_node` does, only this function does not return the inserted or set node. :param key: the key to insert :param value: the value corresponding to the key .. method:: insert_node(key: ~typing.Any = None, value: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Inserts a key/value pair into a :obj:`~gi.repository.GLib.Tree`\. If the given key already exists in the :obj:`~gi.repository.GLib.Tree` its corresponding value is set to the new value. If you supplied a ``value_destroy_func`` when creating the :obj:`~gi.repository.GLib.Tree`\, the old value is freed using that function. If you supplied a ``key_destroy_func`` when creating the :obj:`~gi.repository.GLib.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)). .. versionadded:: 2.68 :param key: the key to insert :param value: the value corresponding to the key .. method:: lookup(key: ~typing.Any = None) -> ~typing.Any | None Gets the value corresponding to the given key. Since a :obj:`~gi.repository.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). :param key: the key to look up .. method:: lookup_extended(lookup_key: ~typing.Any = None) -> ~typing.Tuple[bool, ~typing.Any | None, ~typing.Any | None] Looks up a key in the :obj:`~gi.repository.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 calling :func:`~gi.repository.GLib.Tree.remove`. :param lookup_key: the key to look up .. method:: lookup_node(key: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Gets the tree node corresponding to the given key. Since a :obj:`~gi.repository.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). .. versionadded:: 2.68 :param key: the key to look up .. method:: lower_bound(key: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Gets the lower bound node corresponding to the given key, or :const:`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. .. versionadded:: 2.68 :param key: the key to calculate the lower bound for .. method:: nnodes() -> int Gets the number of nodes in a :obj:`~gi.repository.GLib.Tree`\. .. method:: node_first() -> ~gi.repository.GLib.TreeNode | None Returns the first in-order node of the tree, or :const:`None` for an empty tree. .. versionadded:: 2.68 .. method:: node_last() -> ~gi.repository.GLib.TreeNode | None Returns the last in-order node of the tree, or :const:`None` for an empty tree. .. versionadded:: 2.68 .. method:: remove(key: ~typing.Any = None) -> bool Removes a key/value pair from a :obj:`~gi.repository.GLib.Tree`\. If the :obj:`~gi.repository.GLib.Tree` was created using :func:`~gi.repository.GLib.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 :obj:`~gi.repository.GLib.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)). :param key: the key to remove :return: 0 if the file was successfully removed, -1 if an error occurred .. method:: remove_all() -> None Removes all nodes from a :obj:`~gi.repository.GLib.Tree` and destroys their keys and values, then resets the :obj:`~gi.repository.GLib.Tree`\’s root to :const:`None`. .. versionadded:: 2.70 .. method:: replace(key: ~typing.Any = None, value: ~typing.Any = None) -> None Inserts a new key and value into a :obj:`~gi.repository.GLib.Tree` as :func:`~gi.repository.GLib.Tree.replace_node` does, only this function does not return the inserted or set node. :param key: the key to insert :param value: the value corresponding to the key .. method:: replace_node(key: ~typing.Any = None, value: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Inserts a new key and value into a :obj:`~gi.repository.GLib.Tree` similar to :func:`~gi.repository.GLib.Tree.insert_node`. The difference is that if the key already exists in the :obj:`~gi.repository.GLib.Tree`\, it gets replaced by the new key. If you supplied a ``value_destroy_func`` when creating the :obj:`~gi.repository.GLib.Tree`\, the old value is freed using that function. If you supplied a ``key_destroy_func`` when creating the :obj:`~gi.repository.GLib.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. .. versionadded:: 2.68 :param key: the key to insert :param value: the value corresponding to the key .. method:: search(search_func: ~typing.Callable[[~typing.Any, ~typing.Any], int], user_data: ~typing.Any = None) -> ~typing.Any | None Searches a :obj:`~gi.repository.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 :func:`~gi.repository.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. :param search_func: a function used to search the :obj:`~gi.repository.GLib.Tree` :param user_data: the data passed as the second argument to ``search_func`` .. method:: search_node(search_func: ~typing.Callable[[~typing.Any, ~typing.Any], int], user_data: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Searches a :obj:`~gi.repository.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 :func:`~gi.repository.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. .. versionadded:: 2.68 :param search_func: a function used to search the :obj:`~gi.repository.GLib.Tree` :param user_data: the data passed as the second argument to ``search_func`` .. method:: traverse(traverse_func: ~typing.Callable[[~typing.Any, ~typing.Any, ~typing.Any], bool], traverse_type: ~gi.repository.GLib.TraverseType, user_data: ~typing.Any = None) -> None Calls the given function for each node in the :obj:`~gi.repository.GLib.Tree`\. .. deprecated:: 2.2 The order of a balanced tree is somewhat arbitrary. If you just want to visit all nodes in sorted order, use :func:`~gi.repository.GLib.Tree.foreach` instead. If you really need to visit nodes in a different order, consider using an [n-ary tree][glib-N-ary-Trees]. :param traverse_func: the function to call for each node visited. If this function returns :const:`True`, the traversal is stopped. :param traverse_type: the order in which nodes are visited, one of :const:`~gi.repository.GLib.TraverseType.IN_ORDER`, :const:`~gi.repository.GLib.TraverseType.PRE_ORDER` and :const:`~gi.repository.GLib.TraverseType.POST_ORDER` :param user_data: user data to pass to the function .. method:: upper_bound(key: ~typing.Any = None) -> ~gi.repository.GLib.TreeNode | None Gets the upper bound node corresponding to the given key, or :const:`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. .. versionadded:: 2.68 :param key: the key to calculate the upper bound for