Class Tree

java.lang.Object

org.javagi.base.ProxyInstance

org.gnome.glib.Tree

All Implemented Interfaces:

Proxy

@Generated("org.javagi.JavaGI")
public class Tree
extends ProxyInstance

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

Constructor Summary

Constructors

Constructor	Description
Tree(MemorySegment address)	Create a Tree proxy instance for the provided memory address.
Tree(@Nullable CompareFunc keyCompareFunc)	Creates a new GTree.

Method Summary

Modifier and Type	Method	Description
void	destroy()	Removes all keys and values from the GTree and decreases its reference count by one.
void	foreach(@Nullable TraverseFunc func)	Calls the given function for each of the key/value pairs in the GTree.
void	foreachNode(@Nullable TraverseNodeFunc func)	Calls the given function for each of the nodes in the GTree.
static Tree	full(@Nullable CompareDataFunc keyCompareFunc)	Creates a new GTree 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 GTree.
static MemoryLayout	getMemoryLayout()	The memory layout of the native struct.
static @Nullable Type	getType()	Get the GType of the Tree class.
int	height()	Gets the height of a GTree.
void	insert(@Nullable MemorySegment key, @Nullable MemorySegment value)	Inserts a key/value pair into a GTree.
@Nullable TreeNode	insertNode(@Nullable MemorySegment key, @Nullable MemorySegment value)	Inserts a key/value pair into a GTree.
@Nullable MemorySegment	lookup(@Nullable MemorySegment key)	Gets the value corresponding to the given key.
boolean	lookupExtended(@Nullable MemorySegment lookupKey, @Nullable Out<MemorySegment> origKey, @Nullable Out<MemorySegment> value)	Looks up a key in the GTree, returning the original key and the associated value.
@Nullable TreeNode	lookupNode(@Nullable MemorySegment key)	Gets the tree node corresponding to the given key.
@Nullable TreeNode	lowerBound(@Nullable MemorySegment key)	Gets the lower bound node corresponding to the given key, or null if the tree is empty or all the nodes in the tree have keys that are strictly lower than the searched key.
int	nnodes()	Gets the number of nodes in a GTree.
@Nullable TreeNode	nodeFirst()	Returns the first in-order node of the tree, or null for an empty tree.
@Nullable TreeNode	nodeLast()	Returns the last in-order node of the tree, or null for an empty tree.
Tree	ref()	Increments the reference count of this Tree by one.
boolean	remove(@Nullable MemorySegment key)	Removes a key/value pair from a GTree.
void	removeAll()	Removes all nodes from a GTree and destroys their keys and values, then resets the GTree’s root to null.
void	replace(@Nullable MemorySegment key, @Nullable MemorySegment value)	Inserts a new key and value into a GTree as g_tree_replace_node() does, only this function does not return the inserted or set node.
@Nullable TreeNode	replaceNode(@Nullable MemorySegment key, @Nullable MemorySegment value)	Inserts a new key and value into a GTree similar to g_tree_insert_node().
@Nullable MemorySegment	search(@Nullable CompareFunc searchFunc)	Searches a GTree using searchFunc.
@Nullable TreeNode	searchNode(@Nullable CompareFunc searchFunc)	Searches a GTree using searchFunc.
boolean	steal(@Nullable MemorySegment key)	Removes a key and its associated value from a GTree without calling the key and value destroy functions.
void	traverse(@Nullable TraverseFunc traverseFunc, TraverseType traverseType)	Deprecated. The order of a balanced tree is somewhat arbitrary.
void	unref()	Decrements the reference count of this Tree by one.
@Nullable TreeNode	upperBound(@Nullable MemorySegment key)	Gets the upper bound node corresponding to the given key, or null if the tree is empty or all the nodes in the tree have keys that are lower than or equal to the searched key.
static Tree	withData(@Nullable CompareDataFunc keyCompareFunc)	Creates a new GTree with a comparison function that accepts user data.

Methods inherited from class ProxyInstance

equals, handle, hashCode

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Tree

public Tree(MemorySegment address)

Create a Tree proxy instance for the provided memory address.

Parameters:

address - the memory address of the native object

Tree

public Tree(@Nullable CompareFunc keyCompareFunc)

Creates a new GTree.

Parameters:

keyCompareFunc - the function used to order the nodes in the GTree. It should return values similar to the standard strcmp() function - 0 if the two arguments are equal, a negative value if the first argument comes before the second, or a positive value if the first argument comes after the second.

Method Details

getType

public static @Nullable Type getType()

Get the GType of the Tree class.

Returns:

the GType

getMemoryLayout

public static MemoryLayout getMemoryLayout()

The memory layout of the native struct.

Returns:

the memory layout

full

public static Tree full(@Nullable CompareDataFunc keyCompareFunc)

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

Parameters:

keyCompareFunc - qsort()-style comparison function

Returns:

a newly allocated GTree

withData

public static Tree withData(@Nullable CompareDataFunc keyCompareFunc)

Creates a new GTree with a comparison function that accepts user data. See g_tree_new() for more details.

Parameters:

keyCompareFunc - qsort()-style comparison function

Returns:

a newly allocated GTree

destroy

public void destroy()

Removes all keys and values from the GTree and decreases its reference count by one. If keys and/or values are dynamically allocated, you should either free them first or create the GTree 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 GTree.

foreach

public void foreach(@Nullable TraverseFunc func)

Calls the given function for each of the key/value pairs in the GTree. 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.

foreachNode

public void foreachNode(@Nullable TraverseNodeFunc func)

Calls the given function for each of the nodes in the GTree. 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.

Since:

2.68

height

public int height()

Gets the height of a GTree.

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

Returns:

the height of this Tree

insert

public void insert(@Nullable MemorySegment key,
 @Nullable MemorySegment value)

Inserts a key/value pair into a GTree.

Inserts a new key and value into a GTree as g_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

insertNode

public @Nullable TreeNode insertNode(@Nullable MemorySegment key,
 @Nullable MemorySegment value)

Inserts a key/value pair into a GTree.

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

Returns:

the inserted (or set) node or null if insertion would overflow the tree node counter.

Since:

2.68

lookup

public @Nullable MemorySegment lookup(@Nullable MemorySegment key)

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

Returns:

the value corresponding to the key, or null if the key was not found

lookupExtended

public boolean lookupExtended(@Nullable MemorySegment lookupKey,
 @Nullable Out<MemorySegment> origKey,
 @Nullable Out<MemorySegment> value)

Looks up a key in the GTree, 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 g_tree_remove().

Parameters:

lookupKey - the key to look up

origKey - returns the original key

value - returns the value associated with the key

Returns:

true if the key was found in the GTree

lookupNode

public @Nullable TreeNode lookupNode(@Nullable MemorySegment key)

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

Returns:

the tree node corresponding to the key, or null if the key was not found

Since:

2.68

lowerBound

public @Nullable TreeNode lowerBound(@Nullable MemorySegment key)

Gets the lower bound node corresponding to the given key, or null 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

Returns:

the tree node corresponding to the lower bound, or null if the tree is empty or has only keys strictly lower than the searched key.

Since:

2.68

nnodes

public int nnodes()

Gets the number of nodes in a GTree.

Returns:

the number of nodes in this Tree

The node counter value type is really a guint, but it is returned as a gint due to backward compatibility issues (can be cast back to guint to support its full range of values).

nodeFirst

public @Nullable TreeNode nodeFirst()

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

Returns:

the first node in the tree

Since:

2.68

nodeLast

public @Nullable TreeNode nodeLast()

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

Returns:

the last node in the tree

Since:

2.68

ref

public Tree ref()

Increments the reference count of this Tree by one.

It is safe to call this function from any thread.

Returns:

the passed in GTree

Since:

2.22

remove

public boolean remove(@Nullable MemorySegment key)

Removes a key/value pair from a GTree.

If the GTree 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 GTree, 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:

true if the key was found (prior to 2.8, this function returned nothing)

removeAll

public void removeAll()

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

Since:

2.70

replace

public void replace(@Nullable MemorySegment key,
 @Nullable MemorySegment value)

Inserts a new key and value into a GTree as g_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

replaceNode

public @Nullable TreeNode replaceNode(@Nullable MemorySegment key,
 @Nullable MemorySegment value)

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

Returns:

the inserted (or set) node or null if insertion would overflow the tree node counter.

Since:

2.68

search

public @Nullable MemorySegment search(@Nullable CompareFunc searchFunc)

Searches a GTree using searchFunc.

The searchFunc is called with a pointer to the key of a key/value pair in the tree, and the passed in userData. If searchFunc returns 0 for a key/value pair, then the corresponding value is returned as the result of g_tree_search(). If searchFunc returns -1, searching will proceed among the key/value pairs that have a smaller key; if searchFunc returns 1, searching will proceed among the key/value pairs that have a larger key.

Parameters:

searchFunc - a function used to search the GTree

Returns:

the value corresponding to the found key, or null if the key was not found

searchNode

public @Nullable TreeNode searchNode(@Nullable CompareFunc searchFunc)

Searches a GTree using searchFunc.

The searchFunc is called with a pointer to the key of a key/value pair in the tree, and the passed in userData. If searchFunc returns 0 for a key/value pair, then the corresponding node is returned as the result of g_tree_search(). If searchFunc returns -1, searching will proceed among the key/value pairs that have a smaller key; if searchFunc returns 1, searching will proceed among the key/value pairs that have a larger key.

Parameters:

searchFunc - a function used to search the GTree

Returns:

the node corresponding to the found key, or null if the key was not found

Since:

2.68

steal

public boolean steal(@Nullable MemorySegment key)

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

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

Parameters:

key - the key to remove

Returns:

true if the key was found (prior to 2.8, this function returned nothing)

traverse

@Deprecated
public void traverse(@Nullable TraverseFunc traverseFunc,
 TraverseType traverseType)

Deprecated.

The order of a balanced tree is somewhat arbitrary. If you just want to visit all nodes in sorted order, use g_tree_foreach() instead. If you really need to visit nodes in a different order, consider using an n-ary tree.

Calls the given function for each node in the GTree.

Parameters:

traverseFunc - the function to call for each node visited. If this function returns true, the traversal is stopped.

traverseType - the order in which nodes are visited, one of TraverseType.IN_ORDER, TraverseType.PRE_ORDER and TraverseType.POST_ORDER

unref

public void unref()

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

It is safe to call this function from any thread.

Since:

2.22

upperBound

public @Nullable TreeNode upperBound(@Nullable MemorySegment key)

Gets the upper bound node corresponding to the given key, or null 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

Returns:

the tree node corresponding to the upper bound, or null if the tree is empty or has only keys lower than or equal to the searched key.

Since:

2.68