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 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
  50 {
  51         int direction, count = 0;
  52
  53         direction = it->direction(head, it->ptr);
  54
  55         if ((direction & QUADTREE_UPLEFT) && head->child[0])
  56                 count += _walk_tree(head->child[0], it);
  57
  58         if ((direction & QUADTREE_UPRIGHT) && head->child[1])
  59                 count += _walk_tree(head->child[1], it);
  60
  61         if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
  62                 count += _walk_tree(head->child[2], it);
  63
  64         if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
  65                 count += _walk_tree(head->child[3], it);
  66
  67         if ((direction & QUADTREE_SELF) && it->callback) {
  68                 it->callback(head, it->ptr);
  69                 count++;
  70         }
  71
  72         return count;
  73 }
  74
  75
  76 int walk_tree(const struct quadtree_iterator *it)
  77 {
  78         return _walk_tree(it->head, it);
  79 }