#include <stdio.h>

#include "quadtree.h"

/**
 * quadtree_add - add a node to a quadtree
 * @parent: parent node
 * @new: the new node to be added
 * @compare: pointer to a comparison function
 *
 * Add a node to a quadtree. The tree is kept in order, the new node
 * is placed in the end of appropriate branch. The compare function is
 * used to compare the new node against a branch in the tree. The
 * comparison function must have following return value depending on
 * the position of node a compared to the position of node b:
 *
 * 0: upper left
 * 1: upper right
 * 2: lower left
 * 3: lower right
 *
 * The case of nodes sharing identical coordinates is not taken into
 * account at all.
 */

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

	ret = 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, compare);

	parent->child[ret] = new;
	new->parent = parent;

	return new;
}

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

	direction = it->direction(head, it->ptr);

	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, it->ptr);
		count++;
	}

	return count;
}


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