Copyright | Will Thompson and Iñaki García Etxebarria |
---|---|
License | LGPL-2.1 |
Maintainer | Iñaki García Etxebarria |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
Synopsis
- newtype Tree = Tree (ManagedPtr Tree)
- treeDestroy :: (HasCallStack, MonadIO m) => Tree -> m ()
- treeForeach :: (HasCallStack, MonadIO m) => Tree -> TraverseFunc -> m ()
- treeForeachNode :: (HasCallStack, MonadIO m) => Tree -> TraverseNodeFunc -> m ()
- treeHeight :: (HasCallStack, MonadIO m) => Tree -> m Int32
- treeInsert :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m ()
- treeInsertNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m (Maybe TreeNode)
- treeLookup :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Ptr ())
- treeLookupExtended :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Bool, Ptr (), Ptr ())
- treeLookupNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
- treeLowerBound :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
- treeNewFull :: (HasCallStack, MonadIO m) => CompareDataFunc -> DestroyNotify -> m Tree
- treeNnodes :: (HasCallStack, MonadIO m) => Tree -> m Int32
- treeNodeFirst :: (HasCallStack, MonadIO m) => Tree -> m (Maybe TreeNode)
- treeNodeLast :: (HasCallStack, MonadIO m) => Tree -> m (Maybe TreeNode)
- treeRef :: (HasCallStack, MonadIO m) => Tree -> m Tree
- treeRemove :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m Bool
- treeRemoveAll :: (HasCallStack, MonadIO m) => Tree -> m ()
- treeReplace :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m ()
- treeReplaceNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m (Maybe TreeNode)
- treeSearch :: (HasCallStack, MonadIO m) => Tree -> CompareFunc -> m (Ptr ())
- treeSearchNode :: (HasCallStack, MonadIO m) => Tree -> CompareFunc -> m (Maybe TreeNode)
- treeSteal :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m Bool
- treeTraverse :: (HasCallStack, MonadIO m) => Tree -> TraverseFunc -> TraverseType -> m ()
- treeUnref :: (HasCallStack, MonadIO m) => Tree -> m ()
- treeUpperBound :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m (Maybe TreeNode)
Exported types
Memory-managed wrapper type.
Instances
Eq Tree Source # | |
GBoxed Tree Source # | |
Defined in GI.GLib.Structs.Tree | |
ManagedPtrNewtype Tree Source # | |
Defined in GI.GLib.Structs.Tree toManagedPtr :: Tree -> ManagedPtr Tree | |
TypedObject Tree Source # | |
Defined in GI.GLib.Structs.Tree | |
HasParentTypes Tree Source # | |
Defined in GI.GLib.Structs.Tree | |
IsGValue (Maybe Tree) Source # | Convert |
Defined in GI.GLib.Structs.Tree gvalueGType_ :: IO GType gvalueSet_ :: Ptr GValue -> Maybe Tree -> IO () gvalueGet_ :: Ptr GValue -> IO (Maybe Tree) | |
type ParentTypes Tree Source # | |
Defined in GI.GLib.Structs.Tree |
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.
destroy
:: (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
:: (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
:: (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
:: (HasCallStack, MonadIO m) | |
=> Tree |
|
-> m Int32 | Returns: the height of |
insert
:: (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
:: (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
:: (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
:: (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
:: (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
:: (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
:: (HasCallStack, MonadIO m) | |
=> CompareDataFunc |
|
-> DestroyNotify |
|
-> m Tree | Returns: a newly allocated |
nnodes
:: (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
:: (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
:: (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
Increments the reference count of tree
by one.
It is safe to call this function from any thread.
Since: 2.22
remove
:: (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
:: (HasCallStack, MonadIO m) | |
=> Tree |
|
-> m () |
replace
:: (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
:: (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
:: (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
:: (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
traverse
:: (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, use treeForeach
instead. If you really need to visit nodes in a different order, consider using an [n-ary tree][glib-N-ary-Trees].
Calls the given function for each node in the Tree
.
unref
:: (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
:: (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