GLib.Tree

Fields

None

Methods

	destroy ()
	height ()
	insert (key, value)
	lookup (key)
	lookup_extended (lookup_key)
	nnodes ()
	remove (key)
	replace (key, value)
	steal (key)
	unref ()

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.

destroy()

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 the GLib.Tree using g_tree_new_full(). In the latter case the destroy functions you supplied will be called on all keys and values before destroying the GLib.Tree.

height()

Returns:the height of self Return type:int

Gets the height of a GLib.Tree.

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

insert(key, value)

Parameters:

• key (object or None) – the key to insert
• value (object or None) – the value corresponding to the key

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 the GLib.Tree, the old value is freed using that function. If you supplied a key_destroy_func when creating the 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)).

lookup(key)

Parameters:key (object or None) – the key to look up Returns:the value corresponding to the key, or None if the key was not found Return type:object or None

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)

Parameters:lookup_key (object or None) – the key to look up Returns:True if the key was found in the GLib.Tree

orig_key:returns the original key value:returns the value associated with the key

Return type:(bool, orig_key: object, value: object)

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 calling GLib.Tree.remove().

nnodes()

Returns:the number of nodes in self Return type:int

Gets the number of nodes in a GLib.Tree.

remove(key)

Parameters:key (object or None) – the key to remove Returns:True if the key was found (prior to 2.8, this function returned nothing) Return type:bool

Removes a key/value pair from a GLib.Tree.

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

replace(key, value)

Parameters:

• key (object or None) – the key to insert
• value (object or None) – the value corresponding to the key

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

steal(key)

Parameters:key (object or None) – the key to remove Returns:True if the key was found (prior to 2.8, this function returned nothing) Return type:bool

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.

unref()

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.