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
  72         ret = compare(parent, new);
  73
  74         if (ret < 0 || ret >= 4) {
  75                 printf("Invalid comparison result of %d\n", ret);
  76                 return 0;
  77         }
  78
  79         if (parent->child[ret])
  80                 return quadtree_add(parent->child[ret], new, compare);
  81
  82         parent->child[ret] = new;
  83         new->parent = parent;
  84
  85         return new;
  86 }
  87
  88 /*
  89  * _quadtree_reposition_reqursively - Move everything under and
  90  * including a given node under the new root node
  91  */
  92
  93 static void
  94 _quadtree_reposition_reqursively(struct quadtree *root,
  95                                  struct quadtree *node,
  96                                  int (*compare)(struct quadtree *a,
  97                                                 struct quadtree *b))
  98 {
  99         int i;
 100
 101         /* First remove all children, if any */
 102         for (i = 0; i < 4; i++) {
 103                 if (!node->child[i])
 104                         continue;
 105
 106                 _quadtree_reposition_reqursively(root, node->child[i], compare);
 107                 node->child[i] = 0;
 108         }
 109
 110         /* Then remove this node under the new root. */
 111         quadtree_add(root, node, compare);
 112 }
 113
 114 /*
 115  * quadtree_del - Detach a node from the tree
 116  *
 117  * Return value: The new root node of the tree. If we are detaching
 118  * anything but the root node of the entire tree, the returned root
 119  * value will be the original root of the tree.
 120  */
 121 struct quadtree *quadtree_del(struct quadtree *node,
 122                               int (*compare)(struct quadtree *a,
 123                                              struct quadtree *b))
 124 {
 125         struct quadtree *parent = 0;
 126         int i;
 127
 128         /*
 129          * We are deleting the root node. This means we have to select
 130          * a new root node and reconstruct the entire tree under it
 131          * again.
 132          */
 133         if (!node->parent) {
 134                 for (i = 0; i < 4; i++) {
 135                         if (!node->child[i])
 136                                 continue;
 137
 138                         if (!parent) {
 139                                 parent = node->child[i];
 140                                 continue;
 141                         }
 142                         _quadtree_reposition_reqursively(parent,
 143                                                          node->child[i],
 144                                                          compare);
 145                         node->child[i] = 0;
 146                 }
 147
 148                 return parent;
 149         }
 150
 151         /*
 152          * We are not deleting the parent. Just relocate the children
 153          * and detach the node from the tree.
 154          */
 155         for (i = 0; i < 4; i++) {
 156                 if (!node->child[i])
 157                         continue;
 158
 159                 _quadtree_reposition_reqursively(node->parent, node->child[i],
 160                                                  compare);
 161         }
 162
 163         parent = quadtree_find_parent(node);
 164         node->parent = 0;
 165
 166         return parent;
 167 }
 168
 169
 170 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 171 {
 172         int direction, count = 0;
 173
 174         direction = it->direction(head, it->ptr);
 175
 176         if ((direction & QUADTREE_UPLEFT) && head->child[0])
 177                 count += _walk_tree(head->child[0], it);
 178
 179         if ((direction & QUADTREE_UPRIGHT) && head->child[1])
 180                 count += _walk_tree(head->child[1], it);
 181
 182         if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
 183                 count += _walk_tree(head->child[2], it);
 184
 185         if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
 186                 count += _walk_tree(head->child[3], it);
 187
 188         if ((direction & QUADTREE_SELF) && it->callback) {
 189                 it->callback(head, it->ptr);
 190                 count++;
 191         }
 192
 193         return count;
 194 }
 195
 196
 197 int walk_tree(const struct quadtree_iterator *it)
 198 {
 199         return _walk_tree(it->head, it);
 200 }