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