/* Bit-based binary search tree code V1.00 2/11/03
   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_H
#define _BBBSEARCH_H

typedef struct {
	int mask,twiddle,pos;
	void *zero,*one;
} bbbsnode;

typedef struct {
	int cutoff; /* Cutoff value for tree */
	bbbsnode *tree;
} bbbstree;

extern bbbstree *bbbs_new(int cutoff);
/* Create a new bbbstree
   Cutoff is the smallest difference in values you want the tree to notice (Which must be a power of 2).
   E.g. a cutoff of 1 will allow the tree to store data items with any value, while a value of 8 will cause items with values 1, 2, 3, 4, 5, 6 and 7 to be treated as if they were value 0
   Specifically, all values passed to the bbbs functions are treated as if they were:
     val & ~(cutoff-1)
   Returns NULL on failure
*/

extern void bbbs_free(bbbstree *t);
/* Delete the entire tree structure
   Any memory allocated to the items in the tree must be freed seperately
*/

extern int bbbs_add(bbbstree *t,int val,void *item);
/* Add item 'item' with value 'val' to the tree.
   Returns 1 on failure (e.g. if an item with that value already exists)
*/

extern void *bbbs_find(bbbstree *t,int val);
/* Searches the tree for an item with value 'val'
   Returns a pointer to it on success, or NULL on failure
*/

extern void bbbs_remove(bbbstree *t,int val);
/* Searches the tree for an item with value 'val', then removes it
   Any memory allocated to the object must be freed seperately
   Note that this function is very simple, in that it won't shrink any of the internal tree structure
*/

#endif
