#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include <string.h>

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

struct quadtree {
	struct vector pos;

	/*
	 * Each node divide the sub-tree in following quadtrants:
	 *
	 *	 up left (0)  |  up right (1)
	 *	-----------------------------
	 *	down left (2) | down right (3)
	 */
	struct quadtree *child[4];
	struct quadtree *parent;

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

	/*
	 * Corner points that indicate the space that is covered by
	 * the tree. Upper left and lower right points are stored.
	 */
	struct vector corner[2];
};

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

extern long int quadtree_rebalance_events;
extern long int quadtree_rebalanced_nodes;

#endif