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

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