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 ()
- treeHeight :: (HasCallStack, MonadIO m) => Tree -> m Int32
- treeInsert :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m ()
- treeInsertNode :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> Ptr () -> m 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 TreeNode
- treeSteal :: (HasCallStack, MonadIO m) => Tree -> Ptr () -> m Bool
- 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, height, insert, insertNode, lookup, lookupExtended, lookupNode, lowerBound, nnodes, nodeFirst, nodeLast, ref, remove, removeAll, replace, replaceNode, steal, 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
.
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 TreeNode | Returns: the inserted (or set) node. |
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 |
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 TreeNode | Returns: the inserted (or set) node. |
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
steal
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