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

   1 #ifndef _QUADTREE_H_
   2 #define _QUADTREE_H_
   3
   4 #include <string.h>
   5
   6 #include "utils.h"
   7
   8 struct quadtree {
   9         struct quadtree *child[4];
  10         struct quadtree *parent;
  11
  12         /* statistics */
  13         long int children;      /* The total number of children */
  14         long int depth;         /* The deepest subtree branch */
  15 };
  16
  17 struct quadtree_ops {
  18         int (*compare)(struct quadtree *a, struct quadtree *b);
  19 };
  20
  21 static inline void init_quadtree(struct quadtree *t)
  22 {
  23         memset(t, 0, sizeof(*t));
  24 }
  25
  26 #define QUADTREE_UPLEFT         0x1
  27 #define QUADTREE_UPRIGHT        0x2
  28 #define QUADTREE_DOWNLEFT       0x4
  29 #define QUADTREE_DOWNRIGHT      0x8
  30 #define QUADTREE_SELF           0x10
  31
  32 struct quadtree_iterator {
  33         struct quadtree *head;
  34         void *ptr;
  35
  36         int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
  37         void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
  38 };
  39
  40 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
  41                               struct quadtree_ops *ops);
  42
  43 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
  44
  45 int walk_quadtree(const struct quadtree_iterator *iterator);
  46
  47
  48 /* quadtree_find_parent - return the highest parent of the node */
  49 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
  50 {
  51         struct quadtree *t = (struct quadtree *)node;
  52         while (t->parent)
  53                 t = t->parent;
  54
  55         return t;
  56 }
  57
  58 /*
  59  * Recursively walk through the tree and propagate changes made to the
  60  * given node up until the highest parent.
  61  */
  62 static inline void quadtree_recalculate_parent_stats(struct quadtree *node)
  63 {
  64         int i;
  65
  66         while (node) {
  67                 node->depth = 0;
  68                 node->children = 0;
  69
  70                 for (i = 0; i < 4; i++) {
  71                         if (!node->child[i])
  72                                 continue;
  73
  74                         node->depth = MAX(node->depth,
  75                                           node->child[i]->depth + 1);
  76                         node->children += node->child[i]->children + 1;
  77                 }
  78
  79                 node = node->parent;
  80         }
  81 }
  82
  83 #endif