#include <stdio.h>
#include <stdlib.h>

#include "quadtree.h"

long int quadtree_rebalance_events;
long int quadtree_rebalanced_nodes;

#ifdef DEBUG
#define debug 1
#else
#define debug 0
#endif

static void _trap(int line)
{
	if (debug) {
		printf("Trapped from line %d, use debugger to get backtrace\n",
			line);
		fflush(stdout);
		exit(1);
	}
}

#define trap() _trap(__LINE__)

static int quadtree_compare_coord(const struct vector *a,
				const struct vector *b)
{
	int up, left;

	up = b->y < a->y;
	left = b->x < a->x;

	if (up && left)
		return 0;
	if (up && !left)
		return 1;
	if (left)
		return 2;
	return 3;
}

static int quadtree_compare(const struct quadtree *a, const struct quadtree *b)
{
	return quadtree_compare_coord(&a->pos, &b->pos);
}

static void validate_subtree(const struct quadtree *node)
{
	int i, dir;
	long int children;
	children = 0;

	if (!node) {
		printf("Attempted to validate a null pointer\n");
		fflush(stdout);
		trap();
	}

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

		if (node->child[i]->parent != node) {
			printf("%s:%d Fatal! Tree inconsistency detected at "
			       "child %d %p in node %p, incorrent parent %p\n",
			       __func__, __LINE__, i, node->child[i], node,
			       node->child[i]->parent);
			fflush(stdout);
			trap();
		}

		if (node->parent) {
			if (node->child[i] == node->parent) {
				printf("%s:%d Fatal! Tree loop detected "
				       "at child %d in node %p\n",
				       __func__, __LINE__, i, node);
				fflush(stdout);
				trap();
			}
		}

		dir = quadtree_compare(node, node->child[i]);

		if (dir != i) {
			printf("%s:%d Fatal! Spatial inconsistency detected "
				"at child %d in node %p\n"
				"parent: (%f %f), child (%f %f), "
				"dir %d != %d\n",
				__func__, __LINE__, i, node,
				node->pos.x, node->pos.y,
				node->child[i]->pos.x, node->child[i]->pos.y,
				dir, i);
			fflush(stdout);
			trap();
		}

		children += node->child[i]->children + 1;

		validate_subtree(node->child[i]);
	}

	if (node->depth < 0) {
		printf("%s:%d Tree statistics inconsistency detected! "
		       "Negative depth: %ld\n",
		       __func__, __LINE__, node->depth);
	}

	if (node->children != children) {
		printf("%s:%d Tree statistics inconsistency detected! "
		       "child count mismatch. Expected %ld, got %ld\n",
		       __func__, __LINE__, children, node->children);
		fflush(stdout);
		trap();
	}

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

		if (node->depth == node->child[i]->depth + 1)
			break;

		if (node->child[i]->depth > node->depth) {
			printf("%s:%d Tree statistics inconsistency detected! "
			       "child depth mismatch %ld > %ld\n",
			       __func__, __LINE__, node->child[i]->depth,
			       node->depth);
		}
	}

	if (i == 4) {
		printf("%s:%d Tree statistics inconsistency detected! "
		       "child depth mismatch.",
		       __func__, __LINE__);
		fflush(stdout);
		trap();
	}
}

static void validate_tree(const struct quadtree *node)
{
	int i;

	if (!debug)
		return;

	if (!node->parent)
		return validate_subtree(node);

	for (i = 0; i < 4; i++)
		if (node->parent->child[i] == node)
			break;

	if (i == 4) {
		printf("%s:%d Tree inconsistency detected! "
			"Wrong parent %p for node %p\n",
			__func__, __LINE__, node->parent, node);
		fflush(stdout);
		trap();
	}

	validate_tree(node->parent);
}

void _quadtree_validate_tree(const struct quadtree *node)
{
	validate_tree(node);
}

static struct quadtree *_quadtree_add(struct quadtree *parent,
				struct quadtree *new)
{
	int ret, i;

	ret = quadtree_compare(parent, new);

	if (ret < 0 || ret >= 4) {
		printf("Invalid comparison result of %d\n", ret);
		return 0;
	}

	if (parent->child[ret])
		return _quadtree_add(parent->child[ret], new);

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

	return new;
}

static void _recalculate_node_area_stats(struct quadtree *node)
{
		/* The space covered by the parent node's corner
		 * points needs be as wide as its widest child node's
		 * corners.
		 */
#define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)		\
	((node)->child[ch_idx] ?				\
		(node)->child[ch_idx]->corner[cor_idx].axis :	\
		(node)->pos.axis)

		node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
					CHILD_CORNER_SAFE(node, 2, 0, x));
		node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
					CHILD_CORNER_SAFE(node, 1, 0, y));
		node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
					CHILD_CORNER_SAFE(node, 3, 1, x));
		node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
					CHILD_CORNER_SAFE(node, 3, 1, y));
#undef CHILD_CORNER_SAFE
}

static void recalculate_parent_area_stats(struct quadtree *node)
{
	struct vector old_corner[2];

	while (node) {
		memcpy(&old_corner, &node->corner, sizeof(old_corner));

		_recalculate_node_area_stats(node);

		/*
		 * Stop propagating the changes up in the tree if
		 * nothing has changed
		 */
		if (memcmp(&old_corner, &node->corner, sizeof(old_corner)))
			node = node->parent;
		else
			node = NULL;
	}
}

/*
 * Recursively walk through the tree and propagate changes made to the
 * given node up until the highest parent.
 */
static 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;
		}

		_recalculate_node_area_stats(node);

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

		node = node->parent;
	}
}

/**
 * quadtree_add - add a node to a quadtree
 * @parent: parent node
 * @new: the new node to be added
 *
 * Add a node to a quadtree. The tree is kept in order, the new node
 * is placed in the end of appropriate branch.
 *
 * The case of nodes sharing identical coordinates is not taken into
 * account at all.
 */

struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
			      struct quadtree_ops *ops)
{
	if (parent == new)
		trap();

	validate_tree(parent);

	_quadtree_add(parent, new);

	if (debug) {
		printf("adding node %p to parent %p\n", new, parent);
		fflush(stdout);
	}

	quadtree_recalculate_parent_stats(new, ops);

	validate_tree(new);

	return new;
}

static int is_within(struct vector *pos, struct vector *corner)
{
	if ((pos->x >= corner[1].x) && (pos->x <= corner[0].x) &&
	    (pos->y >= corner[1].y) && (pos->y <= corner[0].y))
		return 1;
	return 0;
}

static int rectangle_and_circle_overlap(struct vector *corner,
					struct vector *pos, double radius)
{
	int vertically_overlapping = 0, horizontally_overlapping = 0;

	if ((pos->x < corner[1].x && pos->x + radius > corner[0].x) ||
	    (pos->x > corner[0].x && pos->x - radius < corner[1].x))
		horizontally_overlapping = 1;

	if ((pos->y < corner[1].y && pos->y + radius > corner[0].y) ||
	    (pos->y > corner[0].y && pos->y - radius < corner[1].y))
		vertically_overlapping = 1;

	return horizontally_overlapping && vertically_overlapping;
}

static int quadrants_to_search(struct quadtree *node, struct vector *pos,
			double dist)
{
	int direction = 0;

	if (dist <= 0)
		return 0xf;

	if (node->child[0] &&
		rectangle_and_circle_overlap(node->child[0]->corner, pos, dist))
		direction |= QUADTREE_UPLEFT;

	if (node->child[1] &&
		rectangle_and_circle_overlap(node->child[1]->corner, pos, dist))
		direction |= QUADTREE_UPRIGHT;

	if (node->child[2] &&
		rectangle_and_circle_overlap(node->child[2]->corner, pos, dist))
		direction |= QUADTREE_DOWNLEFT;

	if (node->child[3] &&
		rectangle_and_circle_overlap(node->child[3]->corner, pos, dist))
		direction |= QUADTREE_DOWNRIGHT;

	return direction;
}

static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
					struct vector *pos,
					struct vector *corner,
					struct quadtree *nearest,
					int depth)
{
	struct vector tmp;
	struct quadtree *node;
	double distance = 0, dist;
	int i, directions;

	if (nearest == NULL)
		nearest = tree;

	vector_sub(&nearest->pos, pos, &tmp);
	distance = vector_abs_squared(&tmp);

	if (tree != nearest) {
		vector_sub(&tree->pos, pos, &tmp);
		dist = vector_abs_squared(&tmp);
		if (dist < distance) {
			nearest = tree;
			distance = dist;
		}
	}

	if (!is_within(&nearest->pos, corner)) {
		if (debug)
			printf("Discarding nearest %p "
				"as outside of search window\n", nearest);
		nearest = NULL;
		distance = -1;
	}

	directions = quadrants_to_search(tree, pos, distance);
	if (debug)
		printf("%d: Directions: %x\n", depth, directions);
	for (i = 0; i < 4; i++) {
		if (!tree->child[i])
			continue;

		if (!(directions & (1 << i)))
			continue;


		node = quadtree_find_nearest(tree->child[i], pos, corner,
					nearest, depth + 1);

		if (!node)
			continue;

		if (node != nearest) {
			vector_sub(&node->pos, pos, &tmp);
			dist = vector_abs_squared(&tmp);
			if (dist < distance || !nearest) {
				nearest = node;
				distance = dist;
			}
			/*
			 * Update the directions where to search for
			 * since those may not be valid any more
			 */
			directions = quadrants_to_search(tree, pos, distance);
			continue;
		}
	}

	if (nearest && !is_within(&nearest->pos, corner)) {
		if (debug)
			printf("%d: Node %p (%f %f) is not within "
				"search window (%f %f) (%f %f)\n", depth,
				nearest, nearest->pos.x, nearest->pos.y,
				corner[0].x, corner[0].y,
				corner[1].x, corner[1].y);
		return NULL;
	}
	if (debug)
		printf("%d: Node %p (%f %f) is nearest node, dist %f\n",
			depth, nearest,
			nearest ? nearest->pos.x : -1,
			nearest ? nearest->pos.y : -1,
			nearest ? distance : -1);
	return nearest;
}

static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
						struct vector *pos,
						struct vector *corner)
{
	struct quadtree *nearest = NULL;
	struct vector sub;
	struct quadtree *node;
	double dist = 0, dist2;
	int i;

	nearest = quadtree_find_nearest(tree, pos, corner, nearest, 0);

	if (nearest != tree)
		goto out;

	if (debug)
		printf("Avoiding parent or NULL node %p\n", nearest);

	/*
	 * oops, we don't want to pick the parent node, let's choose
	 * another one
	 */
	nearest = NULL;
	for (i = 0; i < 4; i++) {
		if (!tree->child[i])
			continue;

		if (!nearest) {
			nearest = quadtree_find_nearest(tree->child[i], pos,
							corner, nearest, 0);

			if (nearest == NULL)
				continue;

			vector_sub(pos, &nearest->pos, &sub);
			dist = vector_abs_squared(&sub);
			continue;
		}
		node = quadtree_find_nearest(tree->child[i], pos, corner,
					nearest, 0);

		if (node == NULL)
			continue;

		vector_sub(pos, &node->pos, &sub);
		dist2 = vector_abs_squared(&sub);

		if (dist2 < dist) {
			nearest = node;
			dist = dist2;
		}
	}

out:
	return nearest;
}

static void get_middle_point(struct vector *corner, struct vector *middle)
{
	middle->x = (corner[0].x + corner[1].x) / (double)2;
	middle->y = (corner[0].y + corner[1].y) / (double)2;
}

static int quadtree_split_by_node(struct quadtree *node,
				struct vector *corner, int dir)
{
	if (!is_within(&node->pos, corner)) {
		if (debug)
			printf("Not within search rectangle\n");
		return 0;
	}

	if (debug)
		printf("Search rectangle was before (%f %f) (%f %f), (%f %f)\n",
			corner[0].x, corner[0].y,
			corner[1].x, corner[1].y,
			node->pos.x, node->pos.y);

	switch (dir) {
	case QUADTREE_UPLEFT:
		corner[0] = node->pos;
		break;
	case QUADTREE_UPRIGHT:
		corner[0].y = node->pos.y;
		corner[1].x = node->pos.x;
		break;
	case QUADTREE_DOWNRIGHT:
		corner[1] = node->pos;
		break;
	case QUADTREE_DOWNLEFT:
		corner[0].x = node->pos.x;
		corner[1].y = node->pos.y;
		break;
	default:
		trap();
	}

	if (debug)
		printf("Search rectangle is now (%f %f) (%f %f), (%f %f)\n",
			corner[0].x, corner[0].y,
			corner[1].x, corner[1].y,
			node->pos.x, node->pos.y);

	if ((corner[0].x < corner[1].x) ||
	    (corner[0].y < corner[1].y))
		trap();

	return 1;
}

/**
 * Quickly detach a node from a tree. Move all child nodes under
 * @parent node.
 */
static int _quadtree_del(struct quadtree *node, struct quadtree *parent)
{
	struct quadtree *n;
	int i;

	/* Detach from the tree */
	if (node->parent)
		for (i = 0; i < 4; i++) {
			if (node->parent->child[i] == node) {
				node->parent->child[i] = 0;
				break;
			}
		}

	if (i == 4)
		trap();

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

		n = node->child[i];
		_quadtree_del(n, parent);
		_quadtree_add(parent, n);
		recalculate_parent_area_stats(n);
	}

	return 0;
}

/**
 * Move everything under @tree node to @parent node, everything
 * else except the @tree node itself
 */
static int optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
			struct vector *corner_orig,
			struct quadtree_ops *ops)
{
	struct vector corner[2], mid;
	struct quadtree *t;
	int moved = 0;

	get_middle_point(corner_orig, &mid);
	t = quadtree_find_nearest_noparent(tree, &mid, corner_orig);

	if (!t) {
		if (debug)
			printf("Cannot find nearest node\n");

		goto out;
	}

	/*
	 * Now we have the t node which contains the object of the
	 * spatial middle coordinates of the tree.
	 */

	if (debug) {
		printf("Relocating node %p (%f %f) under parent %p\n", t,
			t->pos.x, t->pos.y, parent);
		printf("There are %ld child nodes left\n", tree->children);
		fflush(stdout);
	}
	_quadtree_del(t, tree);
	quadtree_add(parent, t, ops);

	moved++;
	tree->children--;
	if (!tree->children)
		goto out;

	/*
	 * Now split the search rectangle in quadtres and do the same
	 * with all of the quarters.
	 */

	corner[0] = corner_orig[0];
	corner[1] = corner_orig[1];
	if (quadtree_split_by_node(t, corner, QUADTREE_UPLEFT))
		moved += optimally_move_tree(tree, parent, corner, ops);

	corner[0] = corner_orig[0];
	corner[1] = corner_orig[1];
	if (quadtree_split_by_node(t, corner, QUADTREE_UPRIGHT))
		moved += optimally_move_tree(tree, parent, corner, ops);

	corner[0] = corner_orig[0];
	corner[1] = corner_orig[1];
	if (quadtree_split_by_node(t, corner, QUADTREE_DOWNLEFT))
		moved += optimally_move_tree(tree, parent, corner, ops);

	corner[0] = corner_orig[0];
	corner[1] = corner_orig[1];
	if (quadtree_split_by_node(t, corner, QUADTREE_DOWNRIGHT))
		moved += optimally_move_tree(tree, parent, corner, ops);

out:
	if (debug)
		printf("Now moved %d nodes, %ld left\n", moved, tree->children);

	return moved;
}

/*
 * quadtree_del - Detach a node from the tree
 *
 * Return value: The new root node of the tree. If we are detaching
 * anything but the root node of the entire tree, the returned root
 * value will be the original root of the tree.
 */
struct quadtree *quadtree_del(struct quadtree *node,
			      struct quadtree_ops *ops)
{
	struct quadtree *parent = NULL;
	struct vector corner[2];
	int i, children = node->children, moved;

	validate_tree(node);

	if (debug) {
		printf("Deleting node %p under parent %p\n",
			       node, node->parent);
		printf("Relocating %ld children\n", node->children);
		fflush(stdout);
	}

	if (!node->parent) {
		/*
		 * We are deleting the root node. This means we have
		 * to select a new root node and reconstruct the
		 * entire tree under it again.
		 */
		if (debug) {
			printf("Deleting root node\n");
			fflush(stdout);
		}
		for (i = 0; i < 4; i++) {
			if (!node->child[i])
				continue;

			parent = node->child[i];
			_quadtree_del(parent, node);
			parent->parent = 0;
			quadtree_recalculate_parent_stats(parent, ops);
			break;
		}
	} else {
		/*
		 * The node has a parent. Detach the node from it and
		 * relocate the children.
		 */

		for (i = 0; i < 4; i++) {
			if (node->parent->child[i] == node) {
				node->parent->child[i] = 0;
				break;
			}
		}
		if (i == 4)
			trap();

		parent = node->parent;
		node->parent = NULL;

		/*
		 * The sub branch is now detached from the main
		 * tree. Fix the stats.
		 */
		quadtree_recalculate_parent_stats(parent, ops);
	}

	validate_tree(parent);

	if (!node->children)
		goto out;
	/*
	 * Now we are ready to prepare for relocating the nodes under
	 * the parent.
	 */

	corner[0] = node->corner[1];
	corner[1] = node->corner[0];
	if (debug) {
		printf("\nInitial Search rectangle (%f %f) (%f %f), (%f %f)\n",
			corner[0].x, corner[0].y,
			corner[1].x, corner[1].y,
			node->pos.x, node->pos.y);
		fflush(stdout);
	}
	moved = optimally_move_tree(node, parent, corner, ops);

	if (debug) {
		if (moved != children) {
			printf("Got %d children but %d were moved\n",
				children, moved);
			printf("nearest children left:\n");
			for (i = 0 ; i < 4; i++)
				if (node->child[i])
					printf("   node %d %p, (%f %f)\n",
						i, node->child[i],
						node->child[i]->pos.x,
						node->child[i]->pos.y);
			fflush(stdout);
			trap();
		}
		printf("Delete done, returning parent %p\n", parent);
		fflush(stdout);
	}

out:
	validate_tree(parent);
	return quadtree_find_parent(parent);
}

static int check_for_crossed_subnodes(struct quadtree *node,
				struct quadtree *skip,
				struct vector *limit, struct quadtree_ops *ops)
{
	int direction = 0, i;
	int up = 0, left = 0, right = 0, down = 0;
	int cross = 0;

	for (i = 0; i < 2; i++) {
		if (limit[i].x < node->pos.x)
			left = 1;
		else
			right = 1;
		if (limit[i].y < node->pos.y)
			up = 1;
		else
			down = 1;
	}

	if (left || up)
		direction |= QUADTREE_UPLEFT;
	if (right || up)
		direction |= QUADTREE_UPRIGHT;
	if (left || down)
		direction |= QUADTREE_DOWNLEFT;
	if (right || down)
		direction |= QUADTREE_DOWNRIGHT;
	if ((left && right) || (up && down))
		direction |= QUADTREE_SELF;


	/*
	 * We need to skip the topmost node (the one that was actually
	 * moved), otherwise we would trigger rebalance every time
	 */
	if (node == skip)
		goto child_check;

	if (direction & QUADTREE_SELF) {
		struct quadtree *parent;

		if (debug)
			printf("Rebalanced because crossed child %p: "
				"node (%f %f) limits (%f %f) (%f %f)\n",
				node,
				node->pos.x, node->pos.y,
				limit[0].x, limit[0].y,
				limit[1].x, limit[1].y);
		return 1;
		parent = quadtree_del(node, ops);
		quadtree_add(parent, node, ops);
	}

child_check:
	if ((direction & QUADTREE_UPLEFT) && node->child[0])
		cross += check_for_crossed_subnodes(node->child[0], skip,
						limit, ops);

	if (cross)
		goto out;

	if ((direction & QUADTREE_UPRIGHT) && node->child[1])
		cross += check_for_crossed_subnodes(node->child[1], skip,
						limit, ops);

	if (cross)
		goto out;

	if ((direction & QUADTREE_DOWNLEFT) && node->child[2])
		cross += check_for_crossed_subnodes(node->child[2], skip,
						limit, ops);

	if (cross)
		goto out;

	if ((direction & QUADTREE_DOWNRIGHT) && node->child[3])
		cross += check_for_crossed_subnodes(node->child[3], skip,
						limit, ops);
out:
	return cross;
}

struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
			struct quadtree_ops *ops)
{
	struct quadtree *parent, *tree_parent;
	int modify = 0;
	int parents = 0, all_parents = 0;

	if (debug) {
		parent = node->parent;
		while (parent) {
			parent = parent->parent;
			all_parents++;
		}
	}

	/* Check if we have crossed any of the parents */
	parent = node->parent;
	while (parent) {
		parents++;
		if (node->pos.x < parent->pos.x && new_pos.x > parent->pos.x)
			modify |= 1;
		if (node->pos.x > parent->pos.x && new_pos.x < parent->pos.x)
			modify |= 2;
		if (node->pos.y < parent->pos.y && new_pos.y > parent->pos.y)
			modify |= 4;
		if (node->pos.y > parent->pos.y && new_pos.y < parent->pos.y)
			modify |= 8;

		if (!modify) {
			parent = parent->parent;
			continue;
		}

		if (debug)
			printf("Rebalanced because crossed parent: node %p, "
				"%d/%d %x "
				"old (%f %f) new (%f %f) parent (%f %f)\n",
				node, parents, all_parents, modify,
				node->pos.x, node->pos.y,
				new_pos.x, new_pos.y,
				parent->pos.x, parent->pos.y);
		/*
		 * If the node has crossed the boundaries, remove it
		 * from the tree and add it again to it. It is then
		 * guaranteed to be in the correct position of the
		 * tree.
		 */
		validate_tree(node);
		quadtree_rebalanced_nodes += node->children;
		tree_parent = quadtree_del(node, ops);
		node->pos = new_pos;
		quadtree_add(tree_parent, node, ops);
		quadtree_rebalance_events++;
		validate_tree(node);

		return tree_parent;
	}

	if (node->children) {
		/*
		 * Now, search the subtree for any children that are
		 * located in wrong place and move them into correct
		 * place within the tree.
		 */
		struct vector limit[2];

		limit[0] = node->pos;
		limit[1] = new_pos;
		modify = check_for_crossed_subnodes(node, node, limit, ops);
	}

	/* Move the node into its new location */

	validate_tree(node);
	if (modify)
		tree_parent = quadtree_del(node, ops);
	node->pos = new_pos;
	if (!modify)
		recalculate_parent_area_stats(node);
	if (modify)
		quadtree_add(tree_parent, node, ops);
	validate_tree(node);
	return quadtree_find_parent(node);

}

static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
{
	int direction, count = 0;

	direction = it->direction(head, (struct quadtree_iterator *)it);

	if ((direction & QUADTREE_UPLEFT) && head->child[0])
		count += _walk_tree(head->child[0], it);

	if ((direction & QUADTREE_UPRIGHT) && head->child[1])
		count += _walk_tree(head->child[1], it);

	if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
		count += _walk_tree(head->child[2], it);

	if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
		count += _walk_tree(head->child[3], it);

	if ((direction & QUADTREE_SELF) && it->callback) {
		it->callback(head, (struct quadtree_iterator *)it);
		count++;
	}

	return count;
}

int walk_quadtree(const struct quadtree_iterator *it)
{
	return _walk_tree(it->head, it);
}