btree.h

用Borland C写的B-Tree算法

/******************************************************************************
 * btree-mem-C/btree.h
 *
 * COPYRIGHT (c) 1995, 1997 by David Van Wagner ALL RIGHTS RESERVED
 * This source may be distributed under the terms of the GNU General Public
 * License version 2, see the file COPYING for details.
 *
 * [e-mail]
 * http://alumni.cse.ucsc.edu/~davevw/
 *****************************************************************************/

#ifndef BTREE_H
#define BTREE_H

#include <iostream.h>
#include <strstream.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include "my_assert.h"

typedef signed char BTREE_POS;

template <class KEY>
class BTREE_ITERATOR;

template <class KEY>
class BTREE {
  protected:
	BTREE_POS count;		/* number of keys which are valid */
	BTREE *parent;
	BTREE **ptr;
	KEY *key;

  private:
   BTREE(const BTREE&) { assert(0); } // copy constructor disabled
   BTREE& operator=(const BTREE&) { assert(0); // assignment disabled
     return *this; }

  public:
	BTREE(BTREE_POS order);	// constructor
	~BTREE();	// destructor
	BTREE* find(const KEY& key, BTREE_POS& pos);
	BTREE* add(const KEY& key, BTREE_POS& pos, BTREE_POS order) {
		return add_internal(NULL, NULL, key, pos, order, -1);
	}
	void empty();	// empty out a node leaving allocation of ptr & key
	void check(BTREE_POS order);
	void print();
	void display(int only_level);
	long get_count() const;
	int levels();
	void display2(int level);
	void remove(BTREE_POS pos, BTREE_POS order);
	void fix_root_add(BTREE*& tree) const {
		if (tree->parent != NULL)
			tree = tree->parent;
	}
	void fix_root_remove(BTREE*& tree) const;
   void traverse(int (*operation)(const KEY& key));
   BTREE* find_first(BTREE_POS& pos);
	BTREE* find_next(const BTREE_POS pos, BTREE_POS &next_pos);
  protected:
	BTREE* add_internal(BTREE* left, BTREE* right,
		const KEY& key, BTREE_POS& pos, BTREE_POS order, BTREE_POS split_pos);
	BTREE* find_insert_position(const KEY& key);
	void remove_internal(BTREE_POS pos, BTREE_POS order);
	void underflow(BTREE_POS order);
   friend BTREE_ITERATOR<KEY>;
};

template <class KEY>
class BTREE_ROOT {
	protected:
		/* MUST BE ODD, greater than 1, less than 32 */
		BTREE_POS order;
		BTREE<KEY> *root;

	public:
		inline BTREE_ROOT(BTREE_POS o) {
			order = o;
			assertf(o>1 && o%2==1, "%d", o);
			root = new BTREE<KEY>(order);
		}
      inline BTREE_ROOT(BTREE_ROOT& source) {
        order = source.order;
        root = new BTREE<KEY>(order);
        add_tree(source);
      }
   	inline BTREE_ROOT& operator=(BTREE_ROOT& source) {
        delete root;
        order = source.order;
        root = new BTREE<KEY>(order);
        add_tree(source);
        return *this;
      }
		inline ~BTREE_ROOT() { delete root; }
		inline BTREE<KEY>* find(const KEY& key, BTREE_POS& pos) {
			return root->find(key, pos); }
		BTREE<KEY>* add(const KEY& key, BTREE_POS& pos) {
			BTREE<KEY>* new_node = root->add(key, pos, order);
			root->fix_root_add(root);
			return new_node;
		}
	   int add_tree(BTREE_ROOT& source);
		inline BTREE<KEY>* find_first(BTREE_POS& pos) const {
        return root->find_first(pos);
      }
		inline void empty() { root->empty(); }
		inline void check() { root->check(order); }
		inline void print() { root->print(); }
		inline void display(int only_level) { root->display(only_level); }
		inline long get_count() const { return root->get_count(); }
		inline int levels() { return root->levels(); }
		inline void display2(int level) { root->display2(level); }
		inline void remove(const KEY& key) {
			BTREE<KEY> *node;
			BTREE_POS pos;
			node = root->find(key, pos);
			if (pos >= 0 && node != NULL) {
				node->remove(pos, order);
				root->fix_root_remove(root);
			}
		}
      inline void traverse(int (*operation)(const KEY& key)) const {
         root->traverse(operation);
      }
		inline BTREE_POS get_order() const { return order; }

      friend BTREE_ITERATOR<KEY>;
};

/******************************************************************************
 * BTREE() constructor                                                        *
 *                                                                            *
 * INPUTS:	none															  *
 * OUTPUTS:	warning errors to stderr                                          *
 *				with allocated and initialized ptr and key members			  *
 *****************************************************************************/
template <class KEY>
BTREE<KEY>::BTREE(BTREE_POS order)
{
	int i;

	assertf(order>1 && order%2 == 1, "%d", order);
	count = 0;
	parent = NULL;
	typedef BTREE<KEY>* PTR_BTREE;
	ptr = new PTR_BTREE[order];
//	ptr = new (BTREE<KEY> *)[order];
	for (i=0; i<order; ++i)
		ptr[i] = NULL;
	key = new KEY[order-1];
}

template <class KEY>
void BTREE<KEY>::fix_root_remove(BTREE<KEY>*& tree) const
{
   if (tree->count == 0 && tree->ptr[0] != NULL) {
      BTREE_POS i;
      tree = tree->ptr[0];
      delete tree->parent;
      tree->parent = NULL;
      for (i=0; i<=tree->count; ++i) {
         if (tree->ptr[i] != NULL)
            tree->ptr[i]->parent = tree;
      }
   }
}

/*****************************************************************************
 * find()
 *
 * INPUTS: 	key value to search for (or find insertion point)
 *			pointer to int for returning position
 * OUTPUTS:	modifies contents of pos pointer to int to position of matched key
 *			(-1 if not found, 0 based into key array)
 * RETURNS:	BTREE node of leaf where key is found or should be inserted  
 *****************************************************************************/
template <class KEY>
BTREE<KEY>* BTREE<KEY>::find(const KEY& key, BTREE_POS& pos)
{
	BTREE_POS i;
	BTREE<KEY> *prev=NULL;
	BTREE<KEY> *node=this;

	pos = -1;

	while (node != NULL) {
		prev = node;
		for (i=0; i < node->count; ++i) {
			if (key < node->key[i]) {
				node = node->ptr[i];
				break;
			} else if (key == node->key[i]) {
				pos = i;
				node = NULL;
				break;
			}
		}
		if (node == prev && i == node->count)
			node = node->ptr[i];
	}

	return prev;
}

/*****************************************************************************
 * find_insert_position()
 *
 * INPUTS: 	key value to search for (or find insertion point)
 *			pointer to int for returning position
 * OUTPUTS:	modifies contents of pos pointer to int to position of matched key
 *			(-1 if not found, 0 based into key array)
 *
  RETURNS:	BTREE node of leaf where key is found or should be inserted
 *****************************************************************************/
template <class KEY>
BTREE<KEY>* BTREE<KEY>::find_insert_position(const KEY& key)
{
	BTREE_POS i;
	BTREE<KEY> *prev=NULL;
	BTREE<KEY> *node=this;

	while (node != NULL) {
		prev = node;
		for (i=0; i < node->count; ++i) {
			if (key <= node->key[i]) {
				node = node->ptr[i];
				break;
			}
		}
		if (node == prev && i == node->count)
			node = node->ptr[i];
	}

	return prev;
}

template <class KEY>
BTREE<KEY>* BTREE<KEY>::find_first(BTREE_POS& pos)
{
  BTREE<KEY>* ptr = this;
  while(ptr->ptr[0] != 0)
    ptr = ptr->ptr[0];
  pos = 0;
  return ptr;
}

/*****************************************************************************
 * find_next()
 *
 * INPUTS: 	starting position
 * OUTPUTS:	none
 * RETURNS:	BTREE node where next key is found
 *
 * WARNING: because of actions of add_internal, BTREE may not be "well-formed"
 *          in other words, some children may be NULL, some may not...
 *****************************************************************************/
template <class KEY>
BTREE<KEY>* BTREE<KEY>::find_next(const BTREE_POS pos, BTREE_POS &next_pos)
{
	BTREE<KEY> *node;
	assert(pos >= 0);
	assert(pos < count);
	if (ptr[pos + 1] == NULL) {
		// THIS IS A LEAF, OR AT LEAST CAN'T DESCEND INTO RIGHT CHILD
		if (pos < count-1) {
			// NEXT IS NEXT ELEMENT IN LEAF
			next_pos = (BTREE_POS)(pos + 1);
			node = this;
		} else {
			if (parent == NULL) {
				next_pos = -1;
				return NULL;	// FAILED, WAS LAST KEY
			} else {
				// NEXT IS PARENT KEY WHOSE LEFT POINTER POINTS TO THIS
				node=parent;
				next_pos=0;
				while (next_pos < node->count && node->ptr[next_pos] != this)
					++next_pos;
				assert(node->ptr[next_pos] == this);
            while (next_pos == node->count)
            {
              // NO RIGHT POINTER, GO UP UNTIL FIND A RIGHT POINTER
              if (node->parent == 0)
              {
                next_pos = -1;
                return NULL;	// FAILED, WAS LAST KEY
              }
              next_pos=0;
              while (next_pos < node->parent->count
                && node->parent->ptr[next_pos] != node)
                ++next_pos;
              assert(node->parent->ptr[next_pos] == node);
              node = node->parent;
            }
			}
		}
	} else {
		// FROM INTERIOR, NEXT IS LEFTMOST GRAND*-CHILD OF RIGHT POINTER
		assert(ptr[pos+1] != NULL);
		node = ptr[pos+1];
		while (node->ptr[0] != NULL) {
			assert(key[pos] <= node->key[0]);
			node = node->ptr[0];
		}
		next_pos = 0;
	}
	assert(node != this || pos < next_pos);
	assert(next_pos < node->count);
	assert(key[pos] <= node->key[next_pos]);
	return node;
}

/*****************************************************************************
 * underflow()
 *
 * INPUTS: 	nothing
 * OUTPUTS:	resolves underflow caused by remove
 * RETURNS:	nothing
 *****************************************************************************/
template <class KEY>
void BTREE<KEY>::underflow(BTREE_POS order)
{
	assertf(count == 0, "%d", count);

	/* UNDERFLOW: CHECK IF CAN BORROW FROM BROTHERS */

	BTREE_POS i;

	if (parent == NULL) {
		// TREE SHOULD SHRINK IN SIZE (IF MORE THAN ONE LEVEL
		// BUT WILL ACTUALL HAPPEN IN BTREE_ROOT::remove
	} else {
		// SOLVE UNDERFLOW
		// FIND PTR IN PARENT

		for (i=0; i <= parent->count && parent->ptr[i] != this; ++i)
			; // KEEP LOOKING

		assert(i <= parent->count);
		assert(parent->ptr[i] == this);

		if (i>0 && parent->ptr[i-1]->count > 1) {
			/* BORROW FROM LEFT BROTHER */
			BTREE<KEY> *brother = parent->ptr[i-1];
			key[0] = parent->key[i-1];
			ptr[1] = ptr[0];
			ptr[0] = brother->ptr[brother->count];
			if (ptr[0] != NULL)
				ptr[0]->parent = this;
			count=1;
			parent->key[i-1] = brother->key[brother->count-1];
			--brother->count;
		} else if (i < parent->count && parent->ptr[i+1]->count > 1) {
			/* BORROW FROM RIGHT BROTHER */
			BTREE<KEY> *brother = parent->ptr[i+1];
			key[0] = parent->key[i];
			ptr[1] = brother->ptr[0];
			if (ptr[1] != NULL)
				ptr[1]->parent = this;
			count=1;
			parent->key[i] = brother->key[0];
			brother->ptr[0] = brother->ptr[1]; // REMOVE_INTERNAL WON'T DO THIS!
			brother->remove_internal(0, order);
		} else {
			// CAN'T BORROW FROM IMMEDIATE BROTHERS
			// COLLAPSE A BROTHER AND KEY FROM PARENT INSTEAD
			if (i>0) {
				/* COLLAPSE WITH LEFT BROTHER */
				BTREE<KEY> *brother = parent->ptr[i-1];
				assert(brother->count == 1);
				brother->key[1] = parent->key[i-1];
				brother->ptr[2] = ptr[0];
				if (brother->ptr[2] != NULL)
					brother->ptr[2]->parent = brother;
assert((brother->ptr[0]==NULL && brother->ptr[1]==NULL && brother->ptr[2]==NULL)
  || (brother->ptr[0]!=NULL && brother->ptr[1]!=NULL && brother->ptr[2]!=NULL));
				++brother->count;
				assert(brother->count == 2);
				parent->remove_internal(i-1, order);
				assert(count == 0);
				delete this;
			} else {
				/* COLLAPSE WITH RIGHT BROTHER */
				BTREE<KEY> *brother = parent->ptr[i+1];
				assert(brother->count == 1);
				key[0] = parent->key[i];
				key[1] = brother->key[0];
				ptr[1] = brother->ptr[0];
				if (ptr[1] != NULL)
					ptr[1]->parent = this;
				ptr[2] = brother->ptr[1];
				if (ptr[2] != NULL)
					ptr[2]->parent = this;
				assert((ptr[0]==NULL && ptr[1]==NULL && ptr[2]==NULL)
					|| (ptr[0]!=NULL && ptr[1]!=NULL && ptr[2]!=NULL));
				count=2;
				parent->remove_internal(i, order);
				brother->count = 0; // KEEP CHILDREN FROM BEING DELETED
				delete brother;
			}
		}
	}
}

/******************************************************************************
 * add_internal()
 *
 * INPUTS: 	split left & right trees of node (for recursive use only,
 *				should be NULL by normal callers)
 *			key value to add
 *			pointer to int for returning position where added
 * OUTPUTS:	modifies contents of B-Tree, assertion errors to stderr
 *          modifies contents of pos pointer to int to added position
 *			(-1 for failure, 0 based into key array)
 * RETURNS:	pointer to node where added
 *
 * NOTE:	currently never returns -1 as failed assert() will terminate program
 *			and _not_ return
 *****************************************************************************/
template <class KEY>
BTREE<KEY>* BTREE<KEY>::add_internal(BTREE<KEY> *left, BTREE<KEY> *right,
	const KEY& key, BTREE_POS& pos, BTREE_POS order, BTREE_POS split_pos)
{
	BTREE<KEY> *node = this;
	BTREE_POS i, j;

	/* verify parameters */
	assert((left==NULL && right==NULL) || (left!=NULL && right!=NULL));
	assertf(order>1 && order%2 == 1, "%d", order);

	pos = -1;

	if (split_pos < 0) {
		/* find key and position, or simply node where it should be inserted */
		node = node->find_insert_position(key);
		assert(node != NULL);
		for (i=0; i < node->count && node->key[i] <= key; ++i)
			; // find position
	} else
		i = split_pos;

// MAY NOT BE A LEAF NODE:  because B-tree may temp. not be well formed
//	assert (node->ptr[0] == NULL);	// must be a leaf node

	assert ((i < node->count && key <= node->key[i]) || (i == node->count));

	if (node->count < order-1) {
		/* fits, so insert it... */
		if (i < node->count) {
			// MUST SHIFT EXISTING KEYS OVER TO INSERT
			for (j=node->count-1; j>=i; --j) {
				/* move right pointer and key to right */
				node->ptr[j+2] = node->ptr[j+1];
				node->key[j+1] = node->key[j];
			}
			/* move last right pointer to right */
			node->ptr[j+2] = node->ptr[j+1];
		}

		node->key[i] = key;
		pos = i;
		++node->count;

		if (left == NULL) {
			assert(right == NULL);
		} else {
			assert(right != NULL);
			/* both left and right not NULL */
			node->ptr[pos] = left;
			left->parent = node;
			node->ptr[pos+1] = right;
			right->parent = node;
		}
	} else {