/* Bit-based binary search tree code V1.00 2/11/03
   See bbbsearch.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM 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.
   WOUM is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY 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 WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _BBBSEARCH_C
#define _BBBSEARCH_C

#include <stdlib.h>
#include "bbbsearch.h"

bbbstree *bbbs_new(int cutoff)
{
	bbbstree *t;
	bbbsnode *n;
	t = (bbbstree *) malloc(sizeof(bbbstree));
	if (t == NULL)
		return NULL;
	t->cutoff = cutoff;
	n = (bbbsnode *) malloc(sizeof(bbbsnode));
	if (n == NULL)
	{
		free(t);
		return NULL;
	}
	t->tree = n;
	n->twiddle = cutoff;
	n->pos = 0;
	n->mask = ~((cutoff*2)-1);
	return t;
}

static void bbbs_free_rec(bbbstree *t,bbbsnode *n)
{
	if (n == NULL)
		return; /* No node */
	if (n->twiddle == t->cutoff)
		return; /* Leaves */
	bbbs_free_rec(t,(bbbsnode *) n->zero);
	bbbs_free_rec(t,(bbbsnode *) n->one);
	free(n);
}

void bbbs_free(bbbstree *t)
{
	bbbs_free_rec(t,t->tree);
	free(t);
}

int bbbs_add(bbbstree *t,int val,void *item)
{
	bbbsnode *branch,*newb;
	branch = t->tree;
	val = val & ~(t->cutoff-1);
	newb = 0;
	do {
		if ((val & branch->mask) != branch->pos)
		{
			/* Insert new branch */
			/* Need to identify the first bit which differs from the mask */
			newb = malloc(sizeof(bbbsnode));
			newb->mask = branch->mask; /* Make copy of 'branch' so 'branch' can become new branch (to avoid modifying 'branch's parent to point to the new node) */
			newb->twiddle = branch->twiddle;
			newb->pos = branch->pos;
			newb->zero = branch->zero;
			newb->one = branch->one;
			while ((val & branch->mask) != (branch->pos & branch->mask))
			{ /* while masked check value doesn't matck masked position of node */
				branch->twiddle *= 2; /* Increase twiddle bit */
				branch->mask ^= branch->twiddle; /* Clear twiddle bit from mask */
			}
			branch->pos = branch->pos & branch->mask; /* Forget lower bits of position */
			/* Now relink */
			if (val & branch->twiddle)
			{
				/* Storing in branch one */
				branch->zero = newb; /* Original branch */
				branch->one = newb = malloc(sizeof(bbbsnode));
			}
			else
			{
				branch->one = newb;
				branch->zero = newb = malloc(sizeof(bbbsnode));
			}
			/* Code at end of function will fill in the new leaves */
		}
		else if (val & branch->twiddle) /* Else go down a branch */
		{
			/* Go down 'one'*/
			if (branch->twiddle == t->cutoff)
			{
				if (branch->one)
					return 1; /* Already got value */
				branch->one = item;
				return 0;
			}
			branch = (bbbsnode *) branch->one;
		}
		else
		{
			/* Go down 'zero' */
			if (branch->twiddle == t->cutoff)
			{
				if (branch->zero)
					return 1; /* Already got value */
				branch->zero = item;
				return 0;
			}
			branch = (bbbsnode *) branch->zero;
		}
	} while (!newb);
	/* Fill in newb with terminating branch */
	newb->mask = ~((t->cutoff*2)-1);
	newb->twiddle = t->cutoff;
	newb->pos = val & newb->mask;
	if (val & newb->twiddle)
	{
		newb->zero = 0;
		newb->one = item;
	}
	else
	{
		newb->one = 0;
		newb->zero = item;
	}
	return 0;
}

void *bbbs_find(bbbstree *t,int val)
{
	bbbsnode *branch;
	branch = t->tree;
	val = val & ~(t->cutoff-1);
	do {
		if ((val & branch->mask) != branch->pos)
			return NULL; /* No such branch */
		if (val & branch->twiddle)
		{
			if (branch->twiddle == t->cutoff)
				return branch->one;
			branch = (bbbsnode *) branch->one;
		}
		else
		{
			if (branch->twiddle == t->cutoff)
				return branch->zero;
			branch = (bbbsnode *) branch->zero;
		}
	} while (branch);
	return NULL; /* Shouldn't happen (I think) */
}

void bbbs_remove(bbbstree *t,int val)
{
	/* Simple removal system
	   I.e. don't bother deleting any of the tree, just the data item */
	bbbsnode *branch;
	branch = t->tree;
	val = val & ~(t->cutoff-1);
	do {
		if ((val & branch->mask) != branch->pos)
			return;
		if (val & branch->twiddle)
		{
			if (branch->twiddle == t->cutoff)
				branch->one = NULL;
			branch = (bbbsnode *) branch->one;
		}
		else
		{
			if (branch->twiddle == t->cutoff)
				branch->zero = NULL;
			branch = (bbbsnode *) branch->zero;
		}
	} while (branch);
	return;
}

#endif
