git.itanic.dy.fi Git - sdl-planets/blob - quadtree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "quadtree.h"
   5
   6 #ifdef DEBUG
   7 #define debug 1
   8 #else
   9 #define debug 0
  10 #endif
  11
  12 static void trap(void )
  13 {
  14         if (debug)
  15                 exit(1);
  16 }
  17
  18 static void validate_subtree(const struct quadtree *node)
  19 {
  20         int i;
  21
  22         for (i = 0; i < 4; i++) {
  23                 if (!node->child[i])
  24                         continue;
  25
  26                 if (node->child[i]->parent != node) {
  27                         printf("%s:%d Fatal! Tree inconsistency detected "
  28                                "at child %d in node %p\n",
  29                                __FUNCTION__, __LINE__, i, node);
  30                         trap();
  31                 }
  32                 if (node->parent) {
  33                         if (node->child[i] == node->parent) {
  34                         printf("%s:%d Fatal! Tree loop detected "
  35                                "at child %d in node %p\n",
  36                                __FUNCTION__, __LINE__, i, node);
  37                         trap();
  38                         }
  39                 }
  40
  41                 validate_subtree(node->child[i]);
  42         }
  43 }
  44
  45 static void validate_tree(const struct quadtree *node)
  46 {
  47         if (debug)
  48                 validate_subtree(quadtree_find_parent(node));
  49 }
  50
  51 /**
  52  * quadtree_add - add a node to a quadtree
  53  * @parent: parent node
  54  * @new: the new node to be added
  55  * @compare: pointer to a comparison function
  56  *
  57  * Add a node to a quadtree. The tree is kept in order, the new node
  58  * is placed in the end of appropriate branch. The compare function is
  59  * used to compare the new node against a branch in the tree. The
  60  * comparison function must have following return value depending on
  61  * the position of node a compared to the position of node b:
  62  *
  63  * 0: upper left
  64  * 1: upper right
  65  * 2: lower left
  66  * 3: lower right
  67  *
  68  * The case of nodes sharing identical coordinates is not taken into
  69  * account at all.
  70  */
  71
  72 struct quadtree *quadtree_add(struct quadtree *parent,
  73                               struct quadtree *new,
  74                               int (*compare)(struct quadtree *a,
  75                                              struct quadtree *b))
  76 {
  77         int ret;
  78         if (parent == new)
  79                 trap();
  80
  81         validate_tree(parent);
  82
  83         ret = compare(parent, new);
  84
  85         if (ret < 0 || ret >= 4) {
  86                 printf("Invalid comparison result of %d\n", ret);
  87                 return 0;
  88         }
  89
  90         if (parent->child[ret])
  91                 return quadtree_add(parent->child[ret], new, compare);
  92
  93         parent->child[ret] = new;
  94         new->parent = parent;
  95
  96         validate_tree(new);
  97
  98         return new;
  99 }
 100
 101 /*
 102  * _quadtree_reposition_reqursively - Move everything under and
 103  * including a given node under the new root node
 104  */
 105
 106 static void
 107 _quadtree_reposition_reqursively(struct quadtree *root,
 108                                  struct quadtree *node,
 109                                  int (*compare)(struct quadtree *a,
 110                                                 struct quadtree *b))
 111 {
 112         int i;
 113
 114         validate_tree(node);
 115
 116         /* First remove all children, if any */
 117
 118         for (i = 0; i < 4; i++) {
 119                 if (!node->child[i])
 120                         continue;
 121
 122                 if (node->child[i] == node ||
 123                     node->child[i] == node->parent)
 124                         trap();
 125
 126                 _quadtree_reposition_reqursively(root, node->child[i], compare);
 127                 node->child[i] = 0;
 128         }
 129
 130         /* Then remove this node under the new root. */
 131         quadtree_add(root, node, compare);
 132 }
 133
 134 /*
 135  * quadtree_del - Detach a node from the tree
 136  *
 137  * Return value: The new root node of the tree. If we are detaching
 138  * anything but the root node of the entire tree, the returned root
 139  * value will be the original root of the tree.
 140  */
 141 struct quadtree *quadtree_del(struct quadtree *node,
 142                               int (*compare)(struct quadtree *a,
 143                                              struct quadtree *b))
 144 {
 145         struct quadtree *parent = 0;
 146         int i;
 147
 148         /*
 149          * We are deleting the root node. This means we have to select
 150          * a new root node and reconstruct the entire tree under it
 151          * again.
 152          */
 153         if (!node->parent) {
 154                 for (i = 0; i < 4; i++) {
 155                         if (!node->child[i])
 156                                 continue;
 157
 158                         if (!parent) {
 159                                 parent = node->child[i];
 160                                 continue;
 161                         }
 162                         _quadtree_reposition_reqursively(parent,
 163                                                          node->child[i],
 164                                                          compare);
 165                         node->child[i] = 0;
 166                 }
 167
 168                 return parent;
 169         }
 170
 171         /*
 172          * We are not deleting the parent. Detach the node from the
 173          * parent abd relocate the children. The node will be then
 174          * detached from the tree.
 175          */
 176
 177         for (i = 0; i < 4; i++) {
 178                 if (node->parent->child[i] == node) {
 179                         node->parent->child[i] = 0;
 180                         break;
 181                 }
 182         }
 183         if (i == 4) {
 184                 printf("%s:%d Fatal! Tree inconsistency detected\n",
 185                        __FUNCTION__, __LINE__);
 186                 trap();
 187         }
 188
 189         /*
 190          * The sub branch is now detached from the main tree. Continue
 191          * relocating the detached branch.
 192          */
 193
 194         for (i = 0; i < 4; i++) {
 195                 if (!node->child[i])
 196                         continue;
 197
 198                 _quadtree_reposition_reqursively(node->parent, node->child[i],
 199                                                  compare);
 200                 node->child[i] = 0;
 201         }
 202
 203         parent = quadtree_find_parent(node);
 204         node->parent = 0;
 205
 206         validate_tree(parent);
 207         return parent;
 208 }
 209
 210
 211 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 212 {
 213         int direction, count = 0;
 214
 215         direction = it->direction(head, it->ptr);
 216
 217         if ((direction & QUADTREE_UPLEFT) && head->child[0])
 218                 count += _walk_tree(head->child[0], it);
 219
 220         if ((direction & QUADTREE_UPRIGHT) && head->child[1])
 221                 count += _walk_tree(head->child[1], it);
 222
 223         if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
 224                 count += _walk_tree(head->child[2], it);
 225
 226         if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
 227                 count += _walk_tree(head->child[3], it);
 228
 229         if ((direction & QUADTREE_SELF) && it->callback) {
 230                 it->callback(head, it->ptr);
 231                 count++;
 232         }
 233
 234         return count;
 235 }
 236
 237 int walk_quadtree(const struct quadtree_iterator *it)
 238 {
 239         return _walk_tree(it->head, it);
 240 }