#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include <string.h>

#include "utils.h"
#include "vector.h"

struct quadtree {
	struct vector pos;
	struct quadtree *child[4];
	struct quadtree *parent;

	/* statistics */
	long int children;	/* The total number of children */
	long int depth;		/* The deepest subtree branch */
};

struct quadtree_ops {
	/*
	 * Calculates required statistical information for a node
	 */
	void (*recalculate_stats)(struct quadtree *node);
};

static inline void init_quadtree(struct quadtree *t)
{
	memset(t, 0, sizeof(*t));
}

#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,
			      struct quadtree_ops *ops);

struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
			struct quadtree_ops *ops);

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;
}

/*
 * Recursively walk through the tree and propagate changes made to the
 * given node up until the highest parent.
 */
static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
						     struct quadtree_ops *ops)
{
	int i;

	while (node) {
		node->depth = 0;
		node->children = 0;

		for (i = 0; i < 4; i++) {
			if (!node->child[i])
				continue;

			node->depth = MAX(node->depth,
					  node->child[i]->depth + 1);
			node->children += node->child[i]->children + 1;
		}

		if (ops->recalculate_stats)
			ops->recalculate_stats(node);

		node = node->parent;
	}
}

#endif