libBLOC

/*
 * Copyright (C) 2023 Barry
 *
 * This file is part of Barry's Little Objects in C Library (libBLOC).
 *
 * libBLOC is free software: you can redistribute it and/or modify it under the
 * terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * libBLOC is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTIBILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * libBLOC.  If not, see <https://www.gnu.org/licenses/>.
 */

/*
 * This file implements object Trees.  Object Trees work similarly to lists
 * except trees store ordered data and are organised such that inserting,
 * removing, and searching are more efficient.  Trees can also be created with
 * a specific Object Type, and will only accept objects of that type.  If no
 * type is specified, the tree can accept any object.
 */

#include <BLOC/object.h>
#include <BLOC/tree.h>
#include "../assert.h"
#include "tree.h"

static void _tree_new(void *);
static void _tree_delete(void *);

/* Tree object type */
struct ObjectType treeType = {
	.name = "Tree",
	.size = sizeof(Tree),
	.new = _tree_new,
	.delete = _tree_delete,
};

/* Create a Tree object */
static void
_tree_new(void *obj)
{
	Tree *tree = obj;
	iterable_init(&tree->header);
}

/* Destroy a Tree object */
static void
_tree_delete(void *obj)
{
	Tree *tree = obj;
	struct TreeNode *node, *next;
	for (node = (void *) tree->header.start; node; node = next) {
		next = (struct TreeNode *) node->header.next;
		obj_put(node->header.obj);
		free(node);
	}
}

/* Count the number of nodes in a (sub-)tree recursively */
unsigned int
_tree_count(struct TreeNode *root)
{
	if (!root)
		return 0;
	unsigned int n = 0;
	n += _tree_count(root->left);
	n += _tree_count(root->right);
	return n + 1;
}

/* Rotate an entire tree left */
struct TreeNode *
_tree_rotate_left(struct TreeNode *root)
{
	struct TreeNode *tmp = root->right;
	root->right = tmp->left;
	tmp->left = root;
	return tmp;
}

/* Rotate an entire tree right */
struct TreeNode *
_tree_rotate_right(struct TreeNode *root)
{
	struct TreeNode *tmp = root->left;
	root->left = tmp->right;
	tmp->right = root;
	return tmp;
}

/* Create an object tree */
Tree *
tree_create(struct ObjectType *type, int (*compare)(void *, void *))
{
	if (!compare)
		return NULL;
	Tree *tree = obj_new(&treeType);
	tree->type = type;
	tree->compare = compare;
	return tree;
}

/* Count the nodes in a tree */
unsigned int
tree_count(Tree *tree)
{
	return tree->header.entries;
}