Tree
- class Tree(*args, **kwargs)
- Constructors:
new_full(key_compare_func:GLib.CompareDataFunc, key_compare_data=None, key_destroy_func:GLib.DestroyNotify) -> GLib.Tree
Constructors
- class Tree
- classmethod new_full(key_compare_func: Callable[[...], int], key_destroy_func: Callable[[None], None], *key_compare_data: Any) Tree
Creates a new
Tree
likenew()
and allows to specify functions to free the memory allocated for the key and value that get called when removing the entry from theTree
.- 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
orNone
if you don’t want to supply such a functionkey_compare_data – data to pass to comparison function
Methods
- class Tree
- destroy() 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 theTree
usingnew_full()
. In the latter case the destroy functions you supplied will be called on all keys and values before destroying theTree
.
- foreach(func: Callable[[...], bool], *user_data: Any) 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 givendata
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
TraverseFunc
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.user_data – user data to pass to the function
- foreach_node(func: Callable[[...], bool], *user_data: Any) 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 givendata
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
TraverseFunc
as you walk over the tree, then walk the list and remove each item.Added in version 2.68.
- Parameters:
func – the function to call for each node visited. If this function returns
True
, the traversal is stopped.user_data – user data to pass to the function
- height() int
Gets the height of a
Tree
.If the
Tree
contains no nodes, the height is 0. If theTree
contains only one root node the height is 1. If the root node has children the height is 2, etc.
- insert(key: None, value: None) None
Inserts a key/value pair into a
Tree
.Inserts a new key and value into a
Tree
asinsert_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(key: None, value: 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 avalue_destroy_func
when creating theTree
, the old value is freed using that function. If you supplied akey_destroy_func
when creating theTree
, 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)).
Added in version 2.68.
- Parameters:
key – the key to insert
value – the value corresponding to the key
- lookup(key: None) 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(lookup_key: None) tuple[bool, None, None]
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 callingremove()
.- Parameters:
lookup_key – the key to look up
- lookup_node(key: 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).Added in version 2.68.
- Parameters:
key – the key to look up
- lower_bound(key: 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.
Added in version 2.68.
- Parameters:
key – the key to calculate the lower bound for
- node_first() TreeNode | None
Returns the first in-order node of the tree, or
None
for an empty tree.Added in version 2.68.
- node_last() TreeNode | None
Returns the last in-order node of the tree, or
None
for an empty tree.Added in version 2.68.
- remove(key: None) bool
Removes a key/value pair from a
Tree
.If the
Tree
was created usingnew_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 theTree
, 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
- Returns:
0 if the file was successfully removed, -1 if an error occurred
- remove_all() None
Removes all nodes from a
Tree
and destroys their keys and values, then resets theTree
’s root toNone
.Added in version 2.70.
- replace(key: None, value: None) None
Inserts a new key and value into a
Tree
asreplace_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(key: None, value: None) TreeNode | None
Inserts a new key and value into a
Tree
similar toinsert_node()
. The difference is that if the key already exists in theTree
, it gets replaced by the new key. If you supplied avalue_destroy_func
when creating theTree
, the old value is freed using that function. If you supplied akey_destroy_func
when creating theTree
, 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.
Added in version 2.68.
- Parameters:
key – the key to insert
value – the value corresponding to the key
- search(search_func: Callable[[...], int], *user_data: Any) None
Searches a
Tree
usingsearch_func
.The
search_func
is called with a pointer to the key of a key/value pair in the tree, and the passed inuser_data
. Ifsearch_func
returns 0 for a key/value pair, then the corresponding value is returned as the result ofsearch()
. Ifsearch_func
returns -1, searching will proceed among the key/value pairs that have a smaller key; ifsearch_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
user_data – the data passed as the second argument to
search_func
- search_node(search_func: Callable[[...], int], *user_data: Any) TreeNode | None
Searches a
Tree
usingsearch_func
.The
search_func
is called with a pointer to the key of a key/value pair in the tree, and the passed inuser_data
. Ifsearch_func
returns 0 for a key/value pair, then the corresponding node is returned as the result ofsearch()
. Ifsearch_func
returns -1, searching will proceed among the key/value pairs that have a smaller key; ifsearch_func
returns 1, searching will proceed among the key/value pairs that have a larger key.Added in version 2.68.
- Parameters:
search_func – a function used to search the
Tree
user_data – the data passed as the second argument to
search_func
- traverse(traverse_func: Callable[[...], bool], traverse_type: TraverseType, *user_data: Any) None
Calls the given function for each node in the
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
foreach()
instead. If you really need to visit nodes in a different order, consider using an [n-ary tree][glib-N-ary-Trees].- 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
IN_ORDER
,PRE_ORDER
andPOST_ORDER
user_data – user data to pass to the function
- upper_bound(key: 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.
Added in version 2.68.
- Parameters:
key – the key to calculate the upper bound for