1 /* 2 This file is part of tgl-library 3 4 This library is free software; you can redistribute it and/or 5 modify it under the terms of the GNU Lesser General Public 6 License as published by the Free Software Foundation; either 7 version 2.1 of the License, or (at your option) any later version. 8 9 This library is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with this library; if not, write to the Free Software 16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 18 Copyright Vitaly Valtman 2013-2015 19 */ 20 #ifndef __TREE_H__ 21 #define __TREE_H__ 22 #include <stdio.h> 23 24 #include <memory.h> 25 #include <assert.h> 26 #include "tools.h" 27 28 #pragma pack(push,4) 29 #define DEFINE_TREE(X_NAME, X_TYPE, X_CMP, X_UNSET) \ 30 struct tree_ ## X_NAME { \ 31 struct tree_ ## X_NAME *left, *right;\ 32 X_TYPE x;\ 33 int y;\ 34 };\ 35 \ 36 static struct tree_ ## X_NAME *new_tree_node_ ## X_NAME (X_TYPE x, int y) {\ 37 struct tree_ ## X_NAME *T = talloc (sizeof (*T));\ 38 T->x = x;\ 39 T->y = y;\ 40 T->left = T->right = 0;\ 41 return T;\ 42 }\ 43 \ 44 static void delete_tree_node_ ## X_NAME (struct tree_ ## X_NAME *T) {\ 45 tfree (T, sizeof (*T));\ 46 }\ 47 \ 48 static void tree_split_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, struct tree_ ## X_NAME **L, struct tree_ ## X_NAME **R) {\ 49 if (!T) {\ 50 *L = *R = 0;\ 51 } else {\ 52 int c = X_CMP (x, T->x);\ 53 if (c < 0) {\ 54 tree_split_ ## X_NAME (T->left, x, L, &T->left);\ 55 *R = T;\ 56 } else {\ 57 tree_split_ ## X_NAME (T->right, x, &T->right, R);\ 58 *L = T;\ 59 }\ 60 }\ 61 }\ 62 \ 63 static struct tree_ ## X_NAME *tree_insert_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, int y) __attribute__ ((warn_unused_result,unused));\ 64 static struct tree_ ## X_NAME *tree_insert_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, int y) {\ 65 if (!T) {\ 66 return new_tree_node_ ## X_NAME (x, y);\ 67 } else {\ 68 if (y > T->y) {\ 69 struct tree_ ## X_NAME *N = new_tree_node_ ## X_NAME (x, y);\ 70 tree_split_ ## X_NAME (T, x, &N->left, &N->right);\ 71 return N;\ 72 } else {\ 73 int c = X_CMP (x, T->x);\ 74 assert (c);\ 75 if (c < 0) { \ 76 T->left = tree_insert_ ## X_NAME (T->left, x, y);\ 77 } else { \ 78 T->right = tree_insert_ ## X_NAME (T->right, x, y);\ 79 } \ 80 return T; \ 81 }\ 82 }\ 83 }\ 84 \ 85 static struct tree_ ## X_NAME *tree_merge_ ## X_NAME (struct tree_ ## X_NAME *L, struct tree_ ## X_NAME *R) {\ 86 if (!L || !R) {\ 87 return L ? L : R;\ 88 } else {\ 89 if (L->y > R->y) {\ 90 L->right = tree_merge_ ## X_NAME (L->right, R);\ 91 return L;\ 92 } else {\ 93 R->left = tree_merge_ ## X_NAME (L, R->left);\ 94 return R;\ 95 }\ 96 }\ 97 }\ 98 \ 99 static struct tree_ ## X_NAME *tree_delete_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) __attribute__ ((warn_unused_result,unused));\ 100 static struct tree_ ## X_NAME *tree_delete_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) {\ 101 assert (T);\ 102 int c = X_CMP (x, T->x);\ 103 if (!c) {\ 104 struct tree_ ## X_NAME *N = tree_merge_ ## X_NAME (T->left, T->right);\ 105 delete_tree_node_ ## X_NAME (T);\ 106 return N;\ 107 } else {\ 108 if (c < 0) { \ 109 T->left = tree_delete_ ## X_NAME (T->left, x); \ 110 } else { \ 111 T->right = tree_delete_ ## X_NAME (T->right, x); \ 112 } \ 113 return T; \ 114 }\ 115 }\ 116 \ 117 static X_TYPE tree_get_min_ ## X_NAME (struct tree_ ## X_NAME *t) __attribute__ ((unused));\ 118 static X_TYPE tree_get_min_ ## X_NAME (struct tree_ ## X_NAME *T) {\ 119 if (!T) { return X_UNSET; } \ 120 while (T->left) { T = T->left; }\ 121 return T->x; \ 122 } \ 123 \ 124 static X_TYPE tree_lookup_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) __attribute__ ((unused));\ 125 static X_TYPE tree_lookup_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) {\ 126 int c;\ 127 while (T && (c = X_CMP (x, T->x))) {\ 128 T = (c < 0 ? T->left : T->right);\ 129 }\ 130 return T ? T->x : X_UNSET;\ 131 }\ 132 \ 133 static void tree_act_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE)) __attribute__ ((unused));\ 134 static void tree_act_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE)) {\ 135 if (!T) { return; } \ 136 tree_act_ ## X_NAME (T->left, act); \ 137 act (T->x); \ 138 tree_act_ ## X_NAME (T->right, act); \ 139 }\ 140 \ 141 static void tree_act_ex_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE, void *), void *extra) __attribute__ ((unused));\ 142 static void tree_act_ex_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE, void *), void *extra) {\ 143 if (!T) { return; } \ 144 tree_act_ex_ ## X_NAME (T->left, act, extra); \ 145 act (T->x, extra); \ 146 tree_act_ex_ ## X_NAME (T->right, act, extra); \ 147 }\ 148 \ 149 static int tree_count_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ 150 static int tree_count_ ## X_NAME (struct tree_ ## X_NAME *T) { \ 151 if (!T) { return 0; }\ 152 return 1 + tree_count_ ## X_NAME (T->left) + tree_count_ ## X_NAME (T->right); \ 153 }\ 154 static void tree_check_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ 155 static void tree_check_ ## X_NAME (struct tree_ ## X_NAME *T) { \ 156 if (!T) { return; }\ 157 if (T->left) { \ 158 assert (T->left->y <= T->y);\ 159 assert (X_CMP (T->left->x, T->x) < 0); \ 160 }\ 161 if (T->right) { \ 162 assert (T->right->y <= T->y);\ 163 assert (X_CMP (T->right->x, T->x) > 0); \ 164 }\ 165 tree_check_ ## X_NAME (T->left); \ 166 tree_check_ ## X_NAME (T->right); \ 167 }\ 168 static struct tree_ ## X_NAME *tree_clear_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ 169 static struct tree_ ## X_NAME *tree_clear_ ## X_NAME (struct tree_ ## X_NAME *T) { \ 170 if (!T) { return 0; }\ 171 tree_clear_ ## X_NAME (T->left); \ 172 tree_clear_ ## X_NAME (T->right); \ 173 delete_tree_node_ ## X_NAME (T); \ 174 return 0; \ 175 } \ 176 177 #define int_cmp(a,b) ((a) - (b)) 178 #pragma pack(pop) 179 #endif 180