| Copyright | Will Thompson and Iñaki García Etxebarria |
|---|---|
| License | LGPL-2.1 |
| Maintainer | Iñaki García Etxebarria |
| Safe Haskell | None |
| Language | Haskell2010 |
GI.GLib.Structs.Tree
Description
The GTree struct is an opaque data structure representing a balanced binary tree. It should be accessed only by using the following functions.
Synopsis
- newtype Tree = Tree (ManagedPtr Tree)
- type family ResolveTreeMethod (t :: Symbol) o where ...
- data TreeDestroyMethodInfo
- treeDestroy :: (HasCallStack, MonadIO m) => Tree -> m ()
- data TreeForeachMethodInfo
- treeForeach :: (HasCallStack, MonadIO m) => Tree -> TraverseFunc -> m ()
- data TreeForeachNodeMethodInfo
- treeForeachNode :: (HasCallStack, MonadIO m) => Tree -> TraverseNodeFunc -> m ()
- data TreeHeightMethodInfo
- treeHeight :: (HasCallStack, MonadIO m) => Tree -> m Int32
- data TreeInsertMethodInfo
- treeInsert :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m ()
- data TreeInsertNodeMethodInfo
- treeInsertNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m (Maybe TreeNode)
- data TreeLookupMethodInfo
- treeLookup :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Ptr ())
- data TreeLookupExtendedMethodInfo
- treeLookupExtended :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Bool, Ptr (), Ptr ())
- data TreeLookupNodeMethodInfo
- treeLookupNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
- data TreeLowerBoundMethodInfo
- treeLowerBound :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
- treeNewFull :: (HasCallStack, MonadIO m) => CompareDataFunc -> DestroyNotify -> m Tree
- data TreeNnodesMethodInfo
- treeNnodes :: (HasCallStack, MonadIO m) => Tree -> m Int32
- data TreeNodeFirstMethodInfo
- treeNodeFirst :: (HasCallStack, MonadIO m) => Tree -> m (Maybe TreeNode)
- data TreeNodeLastMethodInfo
- treeNodeLast :: (HasCallStack, MonadIO m) => Tree -> m (Maybe TreeNode)
- data TreeRefMethodInfo
- treeRef :: (HasCallStack, MonadIO m) => Tree -> m Tree
- data TreeRemoveMethodInfo
- treeRemove :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m Bool
- data TreeRemoveAllMethodInfo
- treeRemoveAll :: (HasCallStack, MonadIO m) => Tree -> m ()
- data TreeReplaceMethodInfo
- treeReplace :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m ()
- data TreeReplaceNodeMethodInfo
- treeReplaceNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m (Maybe TreeNode)
- data TreeSearchMethodInfo
- treeSearch :: (HasCallStack, MonadIO m) => Tree -> CompareFunc -> m (Ptr ())
- data TreeSearchNodeMethodInfo
- treeSearchNode :: (HasCallStack, MonadIO m) => Tree -> CompareFunc -> m (Maybe TreeNode)
- data TreeStealMethodInfo
- treeSteal :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m Bool
- data TreeTraverseMethodInfo
- treeTraverse :: (HasCallStack, MonadIO m) => Tree -> TraverseFunc -> TraverseType -> m ()
- data TreeUnrefMethodInfo
- treeUnref :: (HasCallStack, MonadIO m) => Tree -> m ()
- data TreeUpperBoundMethodInfo
- treeUpperBound :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
Exported types
Memory-managed wrapper type.
Constructors
| Tree (ManagedPtr Tree) |
Instances
Methods
Click to display all available methods, including inherited ones
Methods
destroy, foreach, foreachNode, height, insert, insertNode, lookup, lookupExtended, lookupNode, lowerBound, nnodes, nodeFirst, nodeLast, ref, remove, removeAll, replace, replaceNode, search, searchNode, steal, traverse, unref, upperBound.
Getters
None.
Setters
None.
type family ResolveTreeMethod (t :: Symbol) o where ... Source #
Equations
destroy
data TreeDestroyMethodInfo Source #
Instances
| (signature ~ m (), MonadIO m) => OverloadedMethod TreeDestroyMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeDestroyMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m () |
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 treeNewFull. In the latter case the destroy functions
you supplied will be called on all keys and values before destroying
the Tree.
foreach
data TreeForeachMethodInfo Source #
Instances
| (signature ~ (TraverseFunc -> m ()), MonadIO m) => OverloadedMethod TreeForeachMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeForeachMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> TraverseFunc |
|
| -> m () |
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 TraverseFunc as you walk over
the tree, then walk the list and remove each item.
foreachNode
data TreeForeachNodeMethodInfo Source #
Instances
| (signature ~ (TraverseNodeFunc -> m ()), MonadIO m) => OverloadedMethod TreeForeachNodeMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeForeachNodeMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> TraverseNodeFunc |
|
| -> m () |
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 TraverseFunc as you walk over
the tree, then walk the list and remove each item.
Since: 2.68
height
data TreeHeightMethodInfo Source #
Instances
| (signature ~ m Int32, MonadIO m) => OverloadedMethod TreeHeightMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeHeightMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m Int32 | Returns: the height of |
insert
data TreeInsertMethodInfo Source #
Instances
| (signature ~ (Ptr () -> Ptr () -> m ()), MonadIO m) => OverloadedMethod TreeInsertMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeInsertMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> Ptr () |
|
| -> m () |
Inserts a key/value pair into a Tree.
Inserts a new key and value into a Tree as treeInsertNode does,
only this function does not return the inserted or set node.
insertNode
data TreeInsertNodeMethodInfo Source #
Instances
| (signature ~ (Ptr () -> Ptr () -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeInsertNodeMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeInsertNodeMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> Ptr () |
|
| -> m (Maybe TreeNode) | Returns: the inserted (or set) node or |
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 valueDestroyFunc when
creating the Tree, the old value is freed using that function. If
you supplied a keyDestroyFunc 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)).
Since: 2.68
lookup
data TreeLookupMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m (Ptr ())), MonadIO m) => OverloadedMethod TreeLookupMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeLookupMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m (Ptr ()) | Returns: the value corresponding to the key, or |
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).
lookupExtended
data TreeLookupExtendedMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m (Bool, Ptr (), Ptr ())), MonadIO m) => OverloadedMethod TreeLookupExtendedMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeLookupExtendedMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m (Bool, Ptr (), Ptr ()) |
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
treeRemove.
lookupNode
data TreeLookupNodeMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeLookupNodeMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeLookupNodeMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m (Maybe TreeNode) | Returns: the tree node corresponding to
the key, or |
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).
Since: 2.68
lowerBound
data TreeLowerBoundMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeLowerBoundMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeLowerBoundMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m (Maybe TreeNode) | Returns: the tree node corresponding to
the lower bound, or |
Gets the lower bound node corresponding to the given key,
or Nothing 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.
Since: 2.68
newFull
Arguments
| :: (HasCallStack, MonadIO m) | |
| => CompareDataFunc |
|
| -> DestroyNotify |
|
| -> m Tree | Returns: a newly allocated |
nnodes
data TreeNnodesMethodInfo Source #
Instances
| (signature ~ m Int32, MonadIO m) => OverloadedMethod TreeNnodesMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeNnodesMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m Int32 | Returns: the number of nodes in The node counter value type is really a |
Gets the number of nodes in a Tree.
nodeFirst
data TreeNodeFirstMethodInfo Source #
Instances
| (signature ~ m (Maybe TreeNode), MonadIO m) => OverloadedMethod TreeNodeFirstMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeNodeFirstMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m (Maybe TreeNode) | Returns: the first node in the tree |
Returns the first in-order node of the tree, or Nothing
for an empty tree.
Since: 2.68
nodeLast
data TreeNodeLastMethodInfo Source #
Instances
| (signature ~ m (Maybe TreeNode), MonadIO m) => OverloadedMethod TreeNodeLastMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeNodeLastMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m (Maybe TreeNode) | Returns: the last node in the tree |
Returns the last in-order node of the tree, or Nothing
for an empty tree.
Since: 2.68
ref
data TreeRefMethodInfo Source #
Instances
| (signature ~ m Tree, MonadIO m) => OverloadedMethod TreeRefMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeRefMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Increments the reference count of tree by one.
It is safe to call this function from any thread.
Since: 2.22
remove
data TreeRemoveMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m Bool), MonadIO m) => OverloadedMethod TreeRemoveMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeRemoveMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m Bool | Returns: |
Removes a key/value pair from a Tree.
If the Tree was created using treeNewFull, 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)).
removeAll
data TreeRemoveAllMethodInfo Source #
Instances
| (signature ~ m (), MonadIO m) => OverloadedMethod TreeRemoveAllMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeRemoveAllMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m () |
replace
data TreeReplaceMethodInfo Source #
Instances
| (signature ~ (Ptr () -> Ptr () -> m ()), MonadIO m) => OverloadedMethod TreeReplaceMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeReplaceMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> Ptr () |
|
| -> m () |
Inserts a new key and value into a Tree as treeReplaceNode does,
only this function does not return the inserted or set node.
replaceNode
data TreeReplaceNodeMethodInfo Source #
Instances
| (signature ~ (Ptr () -> Ptr () -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeReplaceNodeMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeReplaceNodeMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> Ptr () |
|
| -> m (Maybe TreeNode) | Returns: the inserted (or set) node or |
Inserts a new key and value into a Tree similar to treeInsertNode.
The difference is that if the key already exists in the Tree, it gets
replaced by the new key. If you supplied a valueDestroyFunc when
creating the Tree, the old value is freed using that function. If you
supplied a keyDestroyFunc 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.
Since: 2.68
search
data TreeSearchMethodInfo Source #
Instances
| (signature ~ (CompareFunc -> m (Ptr ())), MonadIO m) => OverloadedMethod TreeSearchMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeSearchMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> CompareFunc |
|
| -> m (Ptr ()) | Returns: the value corresponding to the found key, or |
Searches a Tree 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 treeSearch. 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.
searchNode
data TreeSearchNodeMethodInfo Source #
Instances
| (signature ~ (CompareFunc -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeSearchNodeMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeSearchNodeMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> CompareFunc |
|
| -> m (Maybe TreeNode) | Returns: the node corresponding to the
found key, or |
Searches a Tree 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 treeSearch. 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.
Since: 2.68
steal
data TreeStealMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m Bool), MonadIO m) => OverloadedMethod TreeStealMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeStealMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
traverse
data TreeTraverseMethodInfo Source #
Instances
| (signature ~ (TraverseFunc -> TraverseType -> m ()), MonadIO m) => OverloadedMethod TreeTraverseMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeTraverseMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> TraverseFunc |
|
| -> TraverseType |
|
| -> m () |
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, usetreeForeach instead. If you really need to visit nodes ina different order, consider using an n-ary tree.
Calls the given function for each node in the Tree.
unref
data TreeUnrefMethodInfo Source #
Instances
| (signature ~ m (), MonadIO m) => OverloadedMethod TreeUnrefMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeUnrefMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> m () |
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.
Since: 2.22
upperBound
data TreeUpperBoundMethodInfo Source #
Instances
| (signature ~ (Ptr () -> m (Maybe TreeNode)), MonadIO m) => OverloadedMethod TreeUpperBoundMethodInfo Tree signature Source # | |
Defined in GI.GLib.Structs.Tree Methods overloadedMethod :: Tree -> signature # | |
| OverloadedMethodInfo TreeUpperBoundMethodInfo Tree Source # | |
Defined in GI.GLib.Structs.Tree Methods | |
Arguments
| :: (HasCallStack, MonadIO m) | |
| => Tree |
|
| -> Ptr () |
|
| -> m (Maybe TreeNode) | Returns: the tree node corresponding to the
upper bound, or |
Gets the upper bound node corresponding to the given key,
or Nothing 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.
Since: 2.68