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

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