nanocoat/include/sjme/tree.h

   1 /* -*- Mode: C; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the Mozilla Public License Version 2.0.
   7 // See license.mkd for licensing and copyright information.
   8 // -------------------------------------------------------------------------*/
   9
  10 /**
  11  * Support for binary trees.
  12  *
  13  * The algorithm is derived from Robert Sedgewick's (of Princeton University)
  14  * 2008 variant of Red-Black Trees called Left Leaning Red-Black Trees.
  15  *
  16  * @since 2024/01/03
  17  */
  18
  19 #ifndef SQUIRRELJME_TREE_H
  20 #define SQUIRRELJME_TREE_H
  21
  22 #include "sjme/stdTypes.h"
  23 #include "sjme/tokenUtils.h"
  24 #include "sjme/comparator.h"
  25 #include "sjme/list.h"
  26
  27 /* Anti-C++. */
  28 #ifdef __cplusplus
  29         #ifndef SJME_CXX_IS_EXTERNED
  30                 #define SJME_CXX_IS_EXTERNED
  31                 #define SJME_CXX_SQUIRRELJME_TREE_H
  32 extern "C" {
  33         #endif /* #ifdef SJME_CXX_IS_EXTERNED */
  34 #endif     /* #ifdef __cplusplus */
  35
  36 /*--------------------------------------------------------------------------*/
  37
  38 /**
  39  * Determines the basic type name for a tree.
  40  *
  41  * @param type The type used.
  42  * @param numPointerStars The number of pointer stars.
  43  * @since 2023/12/17
  44  */
  45 #define SJME_TREE_TYPE_NAME(type, numPointerStars) \
  46         SJME_TOKEN_PASTE_PP(type, \
  47                 SJME_TOKEN_SINGLE(SJME_TOKEN_STARS_C##numPointerStars))
  48
  49 /**
  50  * Determines the name of a tree for the given type.
  51  *
  52  * @param type The type to store within the tree.
  53  * @param numPointerStars The number of pointer stars.
  54  * @return The resultant name.
  55  * @since 2024/01/03
  56  */
  57 #define SJME_TREE_NAME(type, numPointerStars) \
  58         SJME_TOKEN_PASTE_PP(sjme_tree_, \
  59                 SJME_TREE_TYPE_NAME(type, numPointerStars))
  60
  61 /**
  62  * Determines the name of a tree node for the given type.
  63  *
  64  * @param type The type to store within the tree.
  65  * @param numPointerStars The number of pointer stars.
  66  * @return The resultant name.
  67  * @since 2024/01/03
  68  */
  69 #define SJME_TREE_NODE_NAME(type, numPointerStars) \
  70         SJME_TOKEN_PASTE_PP(sjme_tree_node_, \
  71                 SJME_TREE_TYPE_NAME(type, numPointerStars))
  72
  73 /**
  74  * The combine value of a map key and value set.
  75  *
  76  * @param keyType The key type.
  77  * @param keyNumPointerStars The pointer stars for the key.
  78  * @param valueType The value type.
  79  * @param valueNumPointerStars The pointer stars for the value.
  80  * @return The resultant name.
  81  * @since 2024/01/03
  82  */
  83 #define SJME_TREE_MAP_TYPE_NAME(keyType, keyNumPointerStars, \
  84         valueType, valueNumPointerStars) \
  85         SJME_TOKEN_PASTE3_PP(SJME_TREE_TYPE_NAME(keyType, keyNumPointerStars), \
  86         __, SJME_TREE_TYPE_NAME(valueType, valueNumPointerStars))
  87
  88 /**
  89  * Determines the name of a map for the given type.
  90  *
  91  * @param keyType The key type.
  92  * @param keyNumPointerStars The pointer stars for the key.
  93  * @param valueType The value type.
  94  * @param valueNumPointerStars The pointer stars for the value.
  95  * @return The resultant name.
  96  * @since 2024/01/03
  97  */
  98 #define SJME_TREE_MAP_NAME(keyType, keyNumPointerStars, \
  99         valueType, valueNumPointerStars) \
 100         SJME_TOKEN_PASTE_PP(sjme_tree_map_, \
 101                 SJME_TREE_MAP_TYPE_NAME(keyType, keyNumPointerStars, \
 102                 valueType, valueNumPointerStars))
 103
 104 /**
 105  * Determines the name of a map node for the given type.
 106  *
 107  * @param keyType The key type.
 108  * @param keyNumPointerStars The pointer stars for the key.
 109  * @param valueType The value type.
 110  * @param valueNumPointerStars The pointer stars for the value.
 111  * @return The resultant name.
 112  * @since 2024/01/03
 113  */
 114 #define SJME_TREE_MAP_NODE_NAME(keyType, keyNumPointerStars, \
 115         valueType, valueNumPointerStars) \
 116         SJME_TOKEN_PASTE_PP(sjme_tree_map_node_, \
 117                 SJME_TREE_MAP_TYPE_NAME(keyType, keyNumPointerStars, \
 118                 valueType, valueNumPointerStars))
 119
 120 /**
 121  * Determines the name of a map entry for the given type.
 122  *
 123  * @param keyType The key type.
 124  * @param keyNumPointerStars The pointer stars for the key.
 125  * @param valueType The value type.
 126  * @param valueNumPointerStars The pointer stars for the value.
 127  * @return The resultant name.
 128  * @since 2024/01/03
 129  */
 130 #define SJME_TREE_MAP_ENTRY_NAME(keyType, keyNumPointerStars, \
 131         valueType, valueNumPointerStars) \
 132         SJME_TOKEN_PASTE_PP(sjme_tree_map_entry_, \
 133                 SJME_TREE_MAP_TYPE_NAME(keyType, keyNumPointerStars, \
 134                 valueType, valueNumPointerStars))
 135
 136 /**
 137  * Declares a tree with its base type and nodes.
 138  *
 139  * @param rawTreeName The raw tree name to use.
 140  * @param rawNodeName The raw node name to use.
 141  * @param rawElementName The raw element name to use.
 142  * @param type The type to store within the tree.
 143  * @param numPointerStars The number of pointer stars.
 144  * @since 2024/01/03
 145  */
 146 #define SJME_TREE_DECLARE_RAW(rawTreeName, rawNodeName, rawElementName, \
 147         type, numPointerStars) \
 148         /** Binary tree node for @c type and @c numPointerStars . */ \
 149         typedef struct rawNodeName rawNodeName; \
 150         \
 151         struct rawNodeName \
 152         { \
 153                 /** Is this red? Or black? */ \
 154                 sjme_jboolean red : 1; \
 155         \
 156                 /** The node to the left. */ \
 157                 rawNodeName* left; \
 158         \
 159                 /** The node to the right. */ \
 160                 rawNodeName* right; \
 161         \
 162                 /** The entry within the tree. */ \
 163                 rawElementName entry; \
 164         }; \
 165         \
 166         /** Binary tree for @c type and @c numPointerStars . */ \
 167         typedef struct rawTreeName \
 168         { \
 169                 /** The root node. */ \
 170                 rawNodeName* root; \
 171         \
 172                 /** The size of individual elements within the tree. */\
 173                 sjme_jint elementSize;\
 174         } rawTreeName
 175
 176 /**
 177  * Declares a tree with its base type and nodes.
 178  *
 179  * @param type The type to store within the tree.
 180  * @param numPointerStars The number of pointer stars.
 181  * @since 2024/01/03
 182  */
 183 #define SJME_TREE_DECLARE(type, numPointerStars) \
 184         SJME_TREE_DECLARE_RAW(SJME_TREE_NAME(type, numPointerStars), \
 185                 SJME_TREE_NODE_NAME(type, numPointerStars), \
 186         SJME_TOKEN_TYPE(type, numPointerStars), \
 187                 type, numPointerStars)
 188
 189 /**
 190  * Declares a tree map using the given keys and values.
 191  *
 192  * @param keyType The key type.
 193  * @param keyNumPointerStars The pointer stars for the key.
 194  * @param valueType The value type.
 195  * @param valueNumPointerStars The pointer stars for the value.
 196  * @since 2024/01/03
 197  */
 198 #define SJME_TREE_MAP_DECLARE(keyType, keyNumPointerStars, \
 199         valueType, valueNumPointerStars) \
 200         typedef struct SJME_TREE_MAP_ENTRY_NAME(keyType, keyNumPointerStars, \
 201                 valueType, valueNumPointerStars) \
 202         { \
 203                 /** The key type. */ \
 204                 SJME_TOKEN_TYPE(keyType, keyNumPointerStars) key; \
 205         \
 206                 /** The value type. */ \
 207                 SJME_TOKEN_TYPE(valueType, valueNumPointerStars) value; \
 208         } SJME_TREE_MAP_ENTRY_NAME(keyType, keyNumPointerStars, \
 209                 valueType, valueNumPointerStars); \
 210         \
 211         SJME_TREE_DECLARE_RAW(SJME_TREE_MAP_NAME(keyType, keyNumPointerStars, \
 212                         valueType, valueNumPointerStars), \
 213                 SJME_TREE_MAP_NODE_NAME(keyType, keyNumPointerStars, \
 214                         valueType, valueNumPointerStars), \
 215                 SJME_TREE_MAP_ENTRY_NAME(keyType, keyNumPointerStars, \
 216                         valueType, valueNumPointerStars), \
 217                 type, numPointerStars)
 218
 219 /** A tree of @c sjme_jint . */
 220 SJME_TREE_DECLARE(sjme_jint, 0);
 221
 222 /*--------------------------------------------------------------------------*/
 223
 224 /* Anti-C++. */
 225 #ifdef __cplusplus
 226         #ifdef SJME_CXX_SQUIRRELJME_TREE_H
 227 }
 228                 #undef SJME_CXX_SQUIRRELJME_TREE_H
 229                 #undef SJME_CXX_IS_EXTERNED
 230         #endif /* #ifdef SJME_CXX_SQUIRRELJME_TREE_H */
 231 #endif     /* #ifdef __cplusplus */
 232
 233 #endif /* SQUIRRELJME_TREE_H */