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

   1 #ifndef _QUADTREE_H_
   2 #define _QUADTREE_H_
   3
   4 struct quadtree {
   5         struct quadtree *child[4];
   6         struct quadtree *parent;
   7 };
   8
   9 static inline void init_quadtree(struct quadtree *t)
  10 {
  11         int i;
  12
  13         for (i = 0; i < 4; i++)
  14                 t->child[i] = 0;
  15         t->parent = 0;
  16 }
  17
  18 #define QUADTREE_UPLEFT         0x1
  19 #define QUADTREE_UPRIGHT        0x2
  20 #define QUADTREE_DOWNLEFT       0x4
  21 #define QUADTREE_DOWNRIGHT      0x8
  22 #define QUADTREE_SELF           0x10
  23
  24 struct quadtree_iterator {
  25         struct quadtree *head;
  26         void *ptr;
  27
  28         int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
  29         void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
  30 };
  31
  32 struct quadtree *quadtree_add(struct quadtree *parent,
  33                               struct quadtree *new,
  34                               int (*compare)(struct quadtree *a,
  35                                              struct quadtree *b));
  36
  37 struct quadtree *quadtree_del(struct quadtree *node,
  38                               int (*compare)(struct quadtree *a,
  39                                              struct quadtree *b));
  40
  41 int walk_quadtree(const struct quadtree_iterator *iterator);
  42
  43
  44 /* quadtree_find_parent - return the highest parent of the node */
  45 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
  46 {
  47         struct quadtree *t = (struct quadtree *)node;
  48         while (t->parent)
  49                 t = t->parent;
  50
  51         return t;
  52 }
  53
  54 #endif