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

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