#include <stdlib.h>
#include "tree23.h"
tree23_t *tree23_alloc(int (* compar)(const void *, const void *))
{
tree23_t *t;
tree23_node_t *r;
t = malloc(sizeof(tree23_t));
t->n = 0;
t->min_item = NULL;
t->compar = compar;
t->stack = malloc(TREE23_STACK_SIZE * sizeof(tree23_node_t *));
t->path_info = malloc(TREE23_STACK_SIZE * sizeof(signed char));
r = t->root = malloc(sizeof(tree23_node_t));
r->key_item1 = r->key_item2 = NULL;
r->link_kind = LEAF_LINK;
r->left.item = r->middle.item = r->right.item = NULL;
return t;
}
void tree23_free(tree23_t *t)
{
int tos;
tree23_node_t *p, **stack;
stack = malloc(2 * TREE23_STACK_SIZE * sizeof(tree23_node_t *));
stack[0] = t->root;
tos = 1;
while(tos) {
p = stack[--tos];
if(p->link_kind == INTERNAL_LINK) {
stack[tos++] = p->left.node;
stack[tos++] = p->middle.node;
if(p->right.node) stack[tos++] = p->right.node;
}
free(p);
}
free(stack);
free(t->stack);
free(t->path_info);
free(t);
}
void *tree23_insert(tree23_t *t, void *item)
{
int (* compar)(const void *, const void *);
int cmp_result;
void *key_item1, *key_item2, *temp_item, *x_min, *return_item;
tree23_node_t *new_node, *x, *p;
tree23_node_t **stack;
int tos;
signed char *path_info;
p = t->root;
compar = t->compar;
if(t->n <= 1) {
if(t->n == 0) {
t->min_item = p->left.item = item;
}
else {
cmp_result = compar(item, p->left.item);
if(cmp_result == 0) return p->left.item;
if(cmp_result > 0) {
p->key_item1 = p->middle.item = item;
}
else {
p->key_item1 = p->middle.item = p->left.item;
t->min_item = p->left.item = item;
}
}
t->n++;
return NULL;
}
stack = t->stack;
path_info = t->path_info;
tos = 0;
while(p->link_kind != LEAF_LINK) {
stack[tos] = p;
if(p->key_item2 && compar(item, p->key_item2) >= 0) {
p = p->right.node;
path_info[tos] = 1;
}
else if(compar(item, p->key_item1) >= 0) {
p = p->middle.node;
path_info[tos] = 0;
}
else {
p = p->left.node;
path_info[tos] = -1;
}
tos++;
}
key_item1 = p->key_item1;
key_item2 = p->key_item2;
if(key_item2 && (cmp_result = compar(item, key_item2)) >= 0) {
if(cmp_result == 0) {
return key_item2;
}
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = LEAF_LINK;
new_node->left.item = p->right.item;
new_node->key_item1 = new_node->middle.item = item;
new_node->key_item2 = new_node->right.item = NULL;
p->key_item2 = p->right.item = NULL;
}
else if((cmp_result = compar(item, key_item1)) >= 0) {
if(cmp_result == 0) {
return key_item1;
}
if(key_item2) {
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = LEAF_LINK;
new_node->left.item = item;
new_node->key_item1 = new_node->middle.item = p->right.item;
new_node->key_item2 = new_node->right.item = NULL;
p->key_item2 = p->right.item = NULL;
}
else {
p->key_item2 = p->right.item = item;
t->n++;
return NULL;
}
}
else {
if((cmp_result = compar(item, p->left.item)) <= 0) {
if(cmp_result == 0) {
return p->left.item;
}
temp_item = item;
item = p->left.item;
t->min_item = p->left.item = temp_item;
}
if(key_item2) {
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = LEAF_LINK;
new_node->left.item = p->middle.item;
new_node->key_item1 = new_node->middle.item = p->right.item;
new_node->key_item2 = new_node->right.item = NULL;
p->key_item1 = p->middle.item = item;
p->key_item2 = p->right.item = NULL;
}
else {
p->key_item2 = p->right.item = p->middle.item;
p->key_item1 = p->middle.item = item;
t->n++;
return NULL;
}
}
return_item = NULL;
t->n++;
x = new_node;
x_min = new_node->left.item;
while(tos) {
p = stack[--tos];
if(path_info[tos] > 0) {
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = INTERNAL_LINK;
new_node->left.node = p->right.node;
new_node->middle.node = x;
new_node->key_item1 = x_min;
new_node->right.node = NULL;
new_node->key_item2 = NULL;
x_min = p->key_item2;
p->right.node = NULL;
p->key_item2 = NULL;
}
else if(path_info[tos] == 0) {
if(p->key_item2) {
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = INTERNAL_LINK;
new_node->left.node = x;
new_node->middle.node = p->right.node;
new_node->key_item1 = p->key_item2;
new_node->right.node = NULL;
new_node->key_item2 = NULL;
p->right.node = NULL;
p->key_item2 = NULL;
}
else {
p->right.node = x;
p->key_item2 = x_min;
return return_item;
}
}
else {
if(p->key_item2) {
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = INTERNAL_LINK;
new_node->left.node = p->middle.node;
new_node->middle.node = p->right.node;
new_node->key_item1 = p->key_item2;
new_node->right.node = NULL;
new_node->key_item2 = NULL;
p->middle.node = x;
temp_item = p->key_item1;
p->key_item1 = x_min;
x_min = temp_item;
p->right.node = NULL;
p->key_item2 = NULL;
}
else {
p->right.node = p->middle.node;
p->key_item2 = p->key_item1;
p->middle.node = x;
p->key_item1 = x_min;
return return_item;
}
}
x = new_node;
}
new_node = malloc(sizeof(tree23_node_t));
new_node->link_kind = INTERNAL_LINK;
new_node->left.node = p;
new_node->middle.node = x;
new_node->key_item1 = x_min;
new_node->right.node = NULL;
new_node->key_item2 = NULL;
t->root = new_node;
return return_item;
}
void *tree23_find(tree23_t *t, void *key_item)
{
int (* compar)(const void *, const void *);
int cmp_result;
tree23_node_t *p;
void *key_item1, *key_item2;
p = t->root;
compar = t->compar;
if(t->n <= 1) {
if(t->n && (compar(key_item, p->left.item) == 0)) return p->left.item;
return NULL;
}
while(p->link_kind != LEAF_LINK) {
if(p->key_item2 && compar(key_item, p->key_item2) >= 0) {
p = p->right.node;
}
else if(compar(key_item, p->key_item1) >= 0) {
p = p->middle.node;
}
else {
p = p->left.node;
}
}
key_item1 = p->key_item1;
key_item2 = p->key_item2;
if(key_item2 && (cmp_result = compar(key_item, key_item2)) >= 0) {
if(cmp_result) {
return NULL;
}
return key_item2;
}
else if((cmp_result = compar(key_item, key_item1)) >= 0) {
if(cmp_result) {
return NULL;
}
return key_item1;
}
else {
if(compar(key_item, p->left.item)) {
return NULL;
}
return p->left.item;
}
}
void *tree23_find_min(tree23_t *t)
{
return t->min_item;
}
void *tree23_delete(tree23_t *t, void *key_item)
{
int (* compar)(const void *, const void *);
int cmp_result;
void *key_item1, *key_item2, *return_item, *merge_item;
void **min_key_ptr;
tree23_node_t *p, *q, *parent, *merge_node;
tree23_node_t **stack;
int tos;
signed char *path_info;
p = t->root;
compar = t->compar;
if(t->n <= 2) {
if(t->n <= 1) {
if(t->n == 0) {
return NULL;
}
if(compar(key_item, p->left.item) == 0) {
return_item = p->left.item;
t->min_item = p->left.item = NULL;
t->n--;
return return_item;
}
return NULL;
}
if((cmp_result = compar(key_item, p->middle.item)) >= 0) {
if(cmp_result == 0) {
return_item = p->middle.item;
p->key_item1 = p->middle.item = NULL;
t->n--;
return return_item;
}
return NULL;
}
if(compar(key_item, p->left.item) == 0) {
return_item = p->left.item;
t->min_item = p->left.item = p->key_item1;
p->key_item1 = p->middle.item = NULL;
t->n--;
return return_item;
}
return NULL;
}
stack = t->stack;
path_info = t->path_info;
tos = 0;
min_key_ptr = NULL;
while(p->link_kind != LEAF_LINK) {
stack[tos] = p;
if(p->key_item2 && compar(key_item, p->key_item2) >= 0) {
min_key_ptr = &p->key_item2;
p = p->right.node;
path_info[tos] = 1;
}
else if(compar(key_item, p->key_item1) >= 0) {
min_key_ptr = &p->key_item1;
p = p->middle.node;
path_info[tos] = 0;
}
else {
p = p->left.node;
path_info[tos] = -1;
}
tos++;
}
key_item1 = p->key_item1;
key_item2 = p->key_item2;
if(key_item2 && (cmp_result = compar(key_item, key_item2)) >= 0) {
if(cmp_result) {
return_item = NULL;
}
else {
return_item = key_item2;
t->n--;
p->key_item2 = p->right.item = NULL;
}
return return_item;
}
else if((cmp_result = compar(key_item, key_item1)) >= 0) {
if(cmp_result) {
return NULL;
}
return_item = key_item1;
t->n--;
if(key_item2) {
p->key_item1 = p->middle.item = key_item2;
p->key_item2 = p->right.item = NULL;
return return_item;
}
merge_item = p->left.item;
}
else {
if(compar(key_item, p->left.item)) {
return NULL;
}
return_item = p->left.item;
t->n--;
if(min_key_ptr) {
*min_key_ptr = p->middle.item;
}
else {
t->min_item = key_item1;
}
if(key_item2) {
p->left.item = key_item1;
p->key_item1 = p->middle.item = key_item2;
p->key_item2 = p->right.item = NULL;
return return_item;
}
merge_item = p->middle.item;
}
parent = stack[--tos];
if(path_info[tos] > 0) {
q = parent->middle.node;
if(q->key_item2) {
parent->key_item2 = p->left.item = q->key_item2;
p->key_item1 = p->middle.item = merge_item;
q->key_item2 = q->right.item = NULL;
return return_item;
}
else {
q->key_item2 = q->right.item = merge_item;
parent->right.node = NULL;
parent->key_item2 = NULL;
free(p);
return return_item;
}
}
else if(path_info[tos] == 0) {
q = parent->left.node;
if(q->key_item2) {
parent->key_item1 = p->left.item = q->key_item2;
p->key_item1 = p->middle.item = merge_item;
q->key_item2 = q->right.item = NULL;
return return_item;
}
else {
q->key_item2 = q->right.item = merge_item;
free(p);
if(parent->key_item2) {
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
return return_item;
}
merge_node = q;
p = parent;
}
}
else {
q = parent->middle.node;
if(q->key_item2) {
p->left.item = merge_item;
p->key_item1 = p->middle.item = q->left.item;
parent->key_item1 = q->left.item = q->key_item1;
q->key_item1 = q->middle.item = q->key_item2;
q->key_item2 = q->right.item = NULL;
return return_item;
}
else {
q->key_item2 = q->right.item = q->key_item1;
q->key_item1 = q->middle.item = q->left.item;
q->left.item = merge_item;
free(p);
if(parent->key_item2) {
parent->left.node = q;
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
return return_item;
}
merge_node = q;
p = parent;
}
}
while(tos) {
parent = stack[--tos];
if(path_info[tos] > 0) {
q = parent->middle.node;
if(q->key_item2) {
p->left.node = q->right.node;
p->middle.node = merge_node;
p->key_item1 = parent->key_item2;
parent->key_item2 = q->key_item2;
q->right.node = NULL;
q->key_item2 = NULL;
return return_item;
}
else {
q->right.node = merge_node;
q->key_item2 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
free(p);
return return_item;
}
}
else if(path_info[tos] == 0) {
q = parent->left.node;
if(q->key_item2) {
p->left.node = q->right.node;
p->middle.node = merge_node;
p->key_item1 = parent->key_item1;
parent->key_item1 = q->key_item2;
q->right.node = NULL;
q->key_item2 = NULL;
return return_item;
}
else {
q->right.node = merge_node;
q->key_item2 = parent->key_item1;
free(p);
if(parent->key_item2) {
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
return return_item;
}
merge_node = q;
p = parent;
}
}
else {
q = parent->middle.node;
if(q->key_item2) {
p->left.node = merge_node;
p->middle.node = q->left.node;
p->key_item1 = parent->key_item1;
q->left.node = q->middle.node;
parent->key_item1 = q->key_item1;
q->middle.node = q->right.node;
q->key_item1 = q->key_item2;
q->right.node = NULL;
q->key_item2 = NULL;
return return_item;
}
else {
q->right.node = q->middle.node;
q->key_item2 = q->key_item1;
q->middle.node = q->left.node;
q->key_item1 = parent->key_item1;
q->left.node = merge_node;
free(p);
if(parent->key_item2) {
parent->left.node = q;
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
return return_item;
}
merge_node = q;
p = parent;
}
}
}
free(p);
t->root = merge_node;
return return_item;
}
void *tree23_delete_min(tree23_t *t)
{
void *return_item, *merge_item;
tree23_node_t *p, *q, *parent, *merge_node;
tree23_node_t **stack;
int tos;
p = t->root;
if(t->n <= 2) {
if(t->n <= 1) {
if(t->n == 0) {
return NULL;
}
return_item = p->left.item;
t->min_item = p->left.item = NULL;
}
else {
return_item = p->left.item;
t->min_item = p->left.item = p->key_item1;
p->key_item1 = p->middle.item = NULL;
}
t->n--;
return return_item;
}
stack = t->stack;
tos = 0;
while(p->link_kind != LEAF_LINK) {
stack[tos] = p;
p = p->left.node;
tos++;
}
return_item = p->left.item;
t->n--;
t->min_item = p->key_item1;
if(p->key_item2) {
p->left.item = p->key_item1;
p->key_item1 = p->middle.item = p->key_item2;
p->key_item2 = p->right.item = NULL;
return return_item;
}
merge_item = p->middle.item;
parent = stack[--tos];
q = parent->middle.node;
if(q->key_item2) {
p->left.item = merge_item;
p->key_item1 = p->middle.item = q->left.item;
parent->key_item1 = q->left.item = q->key_item1;
q->key_item1 = q->middle.item = q->key_item2;
q->key_item2 = q->right.item = NULL;
return return_item;
}
else {
q->key_item2 = q->right.item = q->key_item1;
q->key_item1 = q->middle.item = q->left.item;
q->left.item = merge_item;
free(p);
if(parent->key_item2) {
parent->left.node = q;
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
merge_node = q;
p = parent;
return return_item;
}
merge_node = q;
p = parent;
}
while(tos) {
parent = stack[--tos];
q = parent->middle.node;
if(q->key_item2) {
p->left.node = merge_node;
p->middle.node = q->left.node;
p->key_item1 = parent->key_item1;
q->left.node = q->middle.node;
parent->key_item1 = q->key_item1;
q->middle.node = q->right.node;
q->key_item1 = q->key_item2;
q->right.node = NULL;
q->key_item2 = NULL;
return return_item;
}
else {
q->right.node = q->middle.node;
q->key_item2 = q->key_item1;
q->middle.node = q->left.node;
q->key_item1 = parent->key_item1;
q->left.node = merge_node;
free(p);
if(parent->key_item2) {
parent->left.node = q;
parent->middle.node = parent->right.node;
parent->key_item1 = parent->key_item2;
parent->right.node = NULL;
parent->key_item2 = NULL;
return return_item;
}
merge_node = q;
p = parent;
}
}
free(p);
t->root = merge_node;
return return_item;
}
void *_tree23_alloc(int (* compar)(const void *, const void *),
unsigned int (* getval)(const void *)) {
return tree23_alloc(compar);
}
void _tree23_free(void *t) {
tree23_free((tree23_t *)t);
}
void *_tree23_insert(void *t, void *item) {
return tree23_insert((tree23_t *)t, item);
}
void *_tree23_delete(void *t, void *key_item) {
return tree23_delete((tree23_t *)t, key_item);
}
void *_tree23_delete_min(void *t) {
return tree23_delete_min((tree23_t *)t);
}
void *_tree23_find(void *t, void *key_item) {
return tree23_find((tree23_t *)t, key_item);
}
void *_tree23_find_min(void *t) {
return tree23_find_min((tree23_t *)t);
}
const dict_info_t TREE23_info = {
_tree23_alloc,
_tree23_free,
_tree23_insert,
_tree23_delete,
_tree23_delete_min,
_tree23_find,
_tree23_find_min
};