#ifndef _QUADTREE_H_
#define _QUADTREE_H_

struct quadtree {
	struct quadtree *child[4];
	struct quadtree *parent;
};

static inline void init_quadtree(struct quadtree *t)
{
	int i;

	for (i = 0; i < 4; i++)
		t->child[i] = 0;
	t->parent = 0;
}

#define QUADTREE_UPLEFT		0x1
#define QUADTREE_UPRIGHT	0x2
#define QUADTREE_DOWNLEFT	0x4
#define QUADTREE_DOWNRIGHT	0x8
#define QUADTREE_SELF		0x10

struct quadtree_iterator {
	struct quadtree *head;
	void *ptr;

	int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
	void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
};

struct quadtree *quadtree_add(struct quadtree *parent,
			      struct quadtree *new,
			      int (*compare)(struct quadtree *a,
					     struct quadtree *b));

struct quadtree *quadtree_del(struct quadtree *node,
			      int (*compare)(struct quadtree *a,
					     struct quadtree *b));

int walk_quadtree(const struct quadtree_iterator *iterator);


/* quadtree_find_parent - return the highest parent of the node */
static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
{
	struct quadtree *t = (struct quadtree *)node;
	while (t->parent)
		t = t->parent;

	return t;
}

#endif