libGimbal 0.1.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_nary_tree.h
Go to the documentation of this file.
1/*! \file
2 * \brief GblNaryTreeNode structure and related functions
3 * \todo Finish implementing commented out API operations
4 * \ingroup containers
5 *
6 * \author Falco Girgis
7 */
8
9#ifndef GIMBAL_NARY_TREE_H
10#define GIMBAL_NARY_TREE_H
11
12#include "../core/gimbal_ctx.h"
13
14#define GBL_NARY_TREE_NPOS GBL_NPOS
15#define GBL_NARY_TREE_ENTRY(node, structure, field) GBL_CONTAINER_OF(node, structure, field)
16#define GBL_NARY_TREE_TRAVERSAL_MASK(order, flags) ((order << 0x3) | (flags))
17
18#define GBL_SELF_TYPE GblNaryTreeNode
19
20GBL_DECLS_BEGIN
21
22GBL_FORWARD_DECLARE_STRUCT(GblNaryTreeNode);
23
24typedef GblBool (*GblNaryTreeIterFn)(const GblNaryTreeNode* pNode, void* pUd);
25
26typedef enum GBL_NARY_TREE_NODE_FLAGS {
27 GBL_NARY_TREE_NODE_FLAG_ROOT = 0x1,
28 GBL_NARY_TREE_NODE_FLAG_INTERNAL = 0x2,
29 GBL_NARY_TREE_NODE_FLAG_LEAF = 0x4,
30 GBL_NARY_TREE_NODE_FLAGS_ALL = 0x7
31} GBL_NARY_TREE_NODE_FLAGS;
32
33typedef enum GBL_NARY_TREE_TRAVERSAL_ORDER {
34 GBL_NARY_TREE_TRAVERSAL_ORDER_PRE,
35 GBL_NARY_TREE_TRAVERSAL_ORDER_IN,
36 GBL_NARY_TREE_TRAVERSAL_ORDER_POST,
37 GBL_NARY_TREE_TRAVERSAL_ORDER_LEVEL
38} GBL_NARY_TREE_TRAVERSAL_ORDER;
39
40/*! \brief Represents a single intrusive node within an N-Ary tree structure
41 *
42 * GblNaryTreeNode is a single node which is to be embedded within another
43 * structure, providing heirarchial relationships between its instances. As
44 * relationships are established between these instances, they become nodes
45 * comprising an aggregate tree structure.
46 *
47 * A single node contains only a pointer to its parent node plus a linked list of
48 * its child nodes, resulting in a minimal memory footprint. The API attempts to
49 * present psuedo list-style semantics for accessing ancestors, bases, siblings,
50 * and children by index; however, these are linked structures and such operations
51 * are of O(N) time complexity, requiring traversals for random access.
52 *
53 * \ingroup containers
54 */
55typedef struct GblNaryTreeNode {
56 struct GblNaryTreeNode* pParent; ///< Node's parent
57 struct GblNaryTreeNode* pChildFirst; ///< Node's first child (beginning of child linked list)
58 struct GblNaryTreeNode* pSiblingNext; ///< Node's next sibling (next entry of child linked list)
59} GblNaryTreeNode;
60
61//GBL_EXPORT size_t GblNaryTree_size (GBL_CSELF) GBL_NOEXCEPT;
62//GBL_EXPORT size_t GblNaryTree_width (GBL_CSELF, size_t depth); GBL_NOEXCEPT;
63//GBL_EXPORT size_t GblNaryTree_height (GBL_CSELF) GBL_NOEXCEPT;
64GBL_EXPORT size_t GblNaryTree_depth (GBL_CSELF) GBL_NOEXCEPT;
65//GBL_EXPORT size_t GblNaryTree_breadth (GBL_CSELF) GBL_NOEXCEPT;
66//GBL_EXPORT size_t GblNaryTree_degree (GBL_CSELF) GBL_NOEXCEPT;
67//GBL_EXPORT size_t GblNaryTree_arity (GBL_CSELF) GBL_NOEXCEPT;
68GBL_EXPORT GblFlags GblNaryTree_flags (GBL_CSELF) GBL_NOEXCEPT;
69
70GBL_EXPORT GblBool GblNaryTree_isConnected (GBL_CSELF) GBL_NOEXCEPT;
71GBL_EXPORT GblBool GblNaryTree_isRoot (GBL_CSELF) GBL_NOEXCEPT;
72GBL_EXPORT GblBool GblNaryTree_isInternal (GBL_CSELF) GBL_NOEXCEPT;
73GBL_EXPORT GblBool GblNaryTree_isLeaf (GBL_CSELF) GBL_NOEXCEPT;
74//GBL_EXPORT GblBool GblNaryTree_isBalanced (GBL_CSELF) GBL_NOEXCEPT;
75GBL_EXPORT GblBool GblNaryTree_isParent (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
76GBL_EXPORT GblBool GblNaryTree_isAncestor (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
77GBL_EXPORT GblBool GblNaryTree_isSibling (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
78GBL_EXPORT GblBool GblNaryTree_isChild (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
79GBL_EXPORT GblBool GblNaryTree_isDescendent (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
80//GBL_EXPORT GblBool GblNaryTree_isRelative (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
81
82GBL_EXPORT size_t GblNaryTree_childCount (GBL_CSELF) GBL_NOEXCEPT;
83GBL_EXPORT GblNaryTreeNode* GblNaryTree_childLast (GBL_CSELF) GBL_NOEXCEPT;
84GBL_EXPORT GblNaryTreeNode* GblNaryTree_childBefore (GBL_CSELF, const GblNaryTreeNode* pChild) GBL_NOEXCEPT;
85GBL_EXPORT GblNaryTreeNode* GblNaryTree_childAt (GBL_CSELF, size_t index) GBL_NOEXCEPT;
86GBL_EXPORT size_t GblNaryTree_childIndex (GBL_CSELF, const GblNaryTreeNode* pChild) GBL_NOEXCEPT;
87
88GBL_EXPORT void GblNaryTree_addChildFront (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
89GBL_EXPORT void GblNaryTree_addChildBack (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
90GBL_EXPORT void GblNaryTree_addChildTo (GBL_SELF, size_t index, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
91GBL_EXPORT void GblNaryTree_addChildBefore (GBL_SELF, GblNaryTreeNode* pBefore,GblNaryTreeNode* pChild) GBL_NOEXCEPT;
92GBL_EXPORT void GblNaryTree_addChildAfter (GBL_SELF, GblNaryTreeNode* pAfter, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
93
94GBL_EXPORT void GblNaryTree_moveChildFront (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
95GBL_EXPORT void GblNaryTree_moveChildBack (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
96GBL_EXPORT void GblNaryTree_moveChildTo (GBL_SELF, size_t index, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
97
98GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChild (GBL_SELF, GblNaryTreeNode* pChild) GBL_NOEXCEPT;
99GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildFront (GBL_SELF) GBL_NOEXCEPT;
100GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildBack (GBL_SELF) GBL_NOEXCEPT;
101GBL_EXPORT GblNaryTreeNode* GblNaryTree_removeChildAt (GBL_SELF, size_t index) GBL_NOEXCEPT;
102
103GBL_EXPORT void GblNaryTree_replaceChild (GBL_SELF, GblNaryTreeNode* pOld, GblNaryTreeNode* pNew) GBL_NOEXCEPT;
104GBL_EXPORT void GblNaryTree_replaceChildAt (GBL_SELF, size_t index, GblNaryTreeNode* pNewChild) GBL_NOEXCEPT;
105
106GBL_EXPORT void GblNaryTree_swapChildren (GBL_SELF, GblNaryTreeNode* pChild1, GblNaryTreeNode* pChild2) GBL_NOEXCEPT;
107GBL_EXPORT void GblNaryTree_swapChildrenAt (GBL_SELF, size_t index1, size_t index2) GBL_NOEXCEPT;
108
109GBL_EXPORT void GblNaryTree_reverseChildren (GBL_SELF) GBL_NOEXCEPT;
110
111GBL_EXPORT GblNaryTreeNode* GblNaryTree_root (GBL_SELF) GBL_NOEXCEPT;
112GBL_EXPORT GblNaryTreeNode* GblNaryTree_base (GBL_SELF, size_t depth) GBL_NOEXCEPT;
113GBL_EXPORT GblNaryTreeNode* GblNaryTree_ancestor (GBL_CSELF, size_t height) GBL_NOEXCEPT;
114GBL_EXPORT size_t GblNaryTree_ancestorHeight (GBL_CSELF, const GblNaryTreeNode* pParent) GBL_NOEXCEPT;
115
116GBL_EXPORT size_t GblNaryTree_siblingCount (GBL_CSELF) GBL_NOEXCEPT;
117GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingLast (GBL_CSELF) GBL_NOEXCEPT;
118GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingBefore (GBL_CSELF) GBL_NOEXCEPT;
119GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingFirst (GBL_CSELF) GBL_NOEXCEPT;
120GBL_EXPORT GblNaryTreeNode* GblNaryTree_siblingAt (GBL_CSELF, size_t index) GBL_NOEXCEPT;
121GBL_EXPORT size_t GblNaryTree_siblingIndex (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
122
123GBL_EXPORT void GblNaryTree_disconnect (GBL_SELF) GBL_NOEXCEPT;
124
125GBL_EXPORT GblNaryTreeNode* GblNaryTree_lowestCommonAncestor(GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
126//GBL_EXPORT size_t GblNaryTree_distance (GBL_CSELF, const GblNaryTreeNode* pOther) GBL_NOEXCEPT;
127GBL_EXPORT GblBool GblNaryTree_traverse (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIt, void* pUd) GBL_NOEXCEPT;
128GBL_EXPORT GblBool GblNaryTree_traverseInOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
129GBL_EXPORT GblBool GblNaryTree_traversePreOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
130GBL_EXPORT GblBool GblNaryTree_traversePostOrder (GBL_CSELF, GblFlags mask, GblNaryTreeIterFn pFnIter, void* pUd) GBL_NOEXCEPT;
131
132GBL_DECLS_END
133
134#undef GBL_SELF_TYPE
135
136#endif // GIMBAL_NARY_TREE_H
GBL_NOEXCEPT
#define GBL_NOEXCEPT
Definition gimbal_compiler.h:264
GBL_DECLS_BEGIN
#define GBL_DECLS_BEGIN
Definition gimbal_decls.h:23
GBL_FORWARD_DECLARE_STRUCT
#define GBL_FORWARD_DECLARE_STRUCT(S)
Definition gimbal_decls.h:160
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:232
GBL_CONTAINER_OF
#define GBL_CONTAINER_OF(ptr, type, member)
Definition gimbal_macro_utils.h:34
GblFlags
uint32_t GblFlags
Standard-sized flags type, 32-bits across platforms.
Definition gimbal_typedefs.h:37
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GBL_NPOS
#define GBL_NPOS
Definition gimbal_typedefs.h:16
GblNaryTreeNode
Represents a single intrusive node within an N-Ary tree structure.
Definition gimbal_nary_tree.h:55
GblNaryTreeNode::pParent
struct GblNaryTreeNode * pParent
Node's parent.
Definition gimbal_nary_tree.h:56
GblNaryTreeNode::pSiblingNext
struct GblNaryTreeNode * pSiblingNext
Node's next sibling (next entry of child linked list)
Definition gimbal_nary_tree.h:58
GblNaryTreeNode::pChildFirst
struct GblNaryTreeNode * pChildFirst
Node's first child (beginning of child linked list)
Definition gimbal_nary_tree.h:57