Logo Search packages:      
Sourcecode: aime version File versions  Download package

btree.cpp

/**********************************************************************
 ** btree - a template binary tree class.  
 ** 
 ** Last reviewed:
 **
 ** Copyright (C) 2001 George Noel (Slate)
 **
 **   This program 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 2 of the 
 **   License, or any later version. 
 **
 **   This program 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 this program (in the docs dir); if not, write to the Free
 **   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
 **
 **********************************************************************/

#ifndef BTREE_C
#define BTREE_C

#include "config.h"
#include "sysdep.h"
#include "strings.h"
#include "mudtypes.h"
#include "entity.h"
#include "btree.h"
#include "global.h"
#include "newfuncts.h"
#include "mudobject.h"
#include "door.h"
#include "objtype.h"
#include "object_list.h"
#include "area_dbase.h"
#include "utils.h"

/***********************************************************************
 ** btree (Constructor) - Initializes a binary tree
 **
 ***********************************************************************/

template<class TYPE>
btree<TYPE>::btree()
{
   root = NULL;
   del_data = 0;
}


/***********************************************************************
 ** add - add a node to the binary tree given a key character string
 **
 ** Parameters: key - the key to add this element as
 **             data - the data for this element
 **
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::add(char *key,TYPE *data)
{   b_node<TYPE> *newnode;
    int      result;

    if ((key == NULL) || (data == NULL))
       return -1;

    // First lets create a new b_node record for it, and copy the key in it,
    // so we will be able to identify it later. The pointers in the newnode
    // record are cleared by the constructor of b_node.

    newnode = new b_node<TYPE>;
    newnode->key = NULL;
    newnode->data = NULL;    
    newnode->left = NULL;    
    newnode->right = NULL;

    newnode->key = new char[strlen(key) + 1];
    strcpy(newnode->key,key);
    newnode->data = data;

    // Then we try adding it to the tree
    result = add_node(&root,newnode);

    // if the add to tree was successful, add it to the linked list
    if (result > 0)
    {
       the_list.add_entry(newnode);
    }
    return result;
}


/***********************************************************************
 ** show - display all the btree entries in a tree format
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::show()
{   show(root,0);
}


/***********************************************************************
 ** add_node - for recursively adding a node to the binary tree
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::add_node(b_node<TYPE> **baseptr,b_node<TYPE> *newnode)
{   int cmpres = 0;      // result of the string compare

    if (newnode == NULL)
       return -1;

    // First see if we hit rock bottom. If so, we can safely add our new
    // node here.
    if ((*baseptr) == NULL)  
    {  *baseptr = newnode;
       return 1;
    }
    else if ((cmpres = STRCASECMP((*baseptr)->key,newnode->key)) < 0)
    {   // Key is smaller than current one, so lets try inserting it on
        // the left branch.
        return add_node(&(*baseptr)->left,newnode);
    }
    else if (cmpres > 0)
    {   // The other option is that it is greater than the current key, then
        // we traverse down the right branch.
        return add_node(&(*baseptr)->right,newnode);
    }
    // Last but not least, it may already be in there, in which case the
    // cmpres will be zero, so lets tell the user he's being foolish.
    return 0;
}


/***********************************************************************
 ** show - Shows a nice dump of the tree on the screen
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::show(b_node<TYPE> *baseptr, int level)
{   int i;

    if (baseptr != NULL)
    {  show(baseptr->left, level + 1);
       
       for (i = 0; i < level; i++)        // Indent to form a tree
         printf("   ");
       printf("%s\n",baseptr->key);

       show(baseptr->right, level + 1); 
    }
}


/***********************************************************************
 ** del - delete a node, deleting the data as well
 **
 ** Parameters: key - the key string of the node to delete
 **
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::del(char *key)
{
  b_node<TYPE> *tmpnode;

  tmpnode = the_list.get_first();
  while (tmpnode != NULL)
  {
    if (!STRCASECMP(tmpnode->key, key))
    {
      the_list.del_entry(tmpnode);
      break;
    }
    tmpnode = the_list.get_next();
  }
  return del_node(&root,key, 1);
}


/***********************************************************************
 ** rem - delete a node without deleting the data
 **
 ** Parameters: key - the key string of the node to delete
 **
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::rem(char *key)
{
  b_node<TYPE> *tmpnode;

  tmpnode = the_list.get_first();
  while (tmpnode != NULL)
  {
    if (!STRCASECMP(tmpnode->key, key))
    {
      the_list.del_entry(tmpnode);
      break;
    }
    tmpnode = the_list.get_next();
  }
  return del_node(&root,key, 0);
}


/***********************************************************************
 ** del_node - for recursively deleting the nodes in the tree
 **
 ** Parameters: baseptr - the base ptr of the subtree to search
 **             key - the key of the element to delete
 **             del_data - should we delete the data as well?
 **
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::del_node(b_node<TYPE> **baseptr,char *key, int del_data)
{  
   int res = 0;

   if ((*baseptr) == NULL)
      return 0;                                          // Not Found
   else if ((res = STRCASECMP((*baseptr)->key,key)) == 0)    // This node is the one
   {   b_node<TYPE> *tempptr, *delptr;
 
       // Store current pointer  so we can free up memory when it is removed.
       delptr = (*baseptr);

       if ((*baseptr)->right == NULL)
           *baseptr = (*baseptr)->left;
       else 
       {   tempptr = (*baseptr)->left;
           *baseptr = (*baseptr)->right;
           (void)add_node(baseptr,tempptr);        // insert the remainder
       }

       if ((del_data) && (delptr->data != NULL))
           delete delptr->data;

       delete delptr->key;
       delete delptr;
       return 1;     
   }
   else if (res < 0)
       return del_node(&(*baseptr)->left,key, del_data);
   else
       return del_node(&(*baseptr)->right,key, del_data);
   return 0;
}


/***********************************************************************
 ** find - finds an element based on a given key
 **
 ** Parameters: key - the key string of the node to find
 **
 ***********************************************************************/

template<class TYPE>
TYPE *btree<TYPE>::find(char *key)
{ 
   return find_node(root,key);
}


/***********************************************************************
 ** can_find - is the given node in the tree?
 **
 ** Parameters: key - the key string of the node to look for
 **
 ***********************************************************************/

template<class TYPE> 
bool btree<TYPE>::can_find(char *key)
{  if (find_node(root,key) == NULL)
      return false;
   return true;
}


/***********************************************************************
 ** find_node - recursively find the node we are looking for
 **
 ** Parameters: baseptr - the ptr to the subtree to search in
 **             key - the key string of the node we are looking for
 **
 ***********************************************************************/

template<class TYPE>
TYPE *btree<TYPE>::find_node(b_node<TYPE> *baseptr, char *key)
{   int cmpres;

    if (baseptr == NULL)
       return NULL;
    else if ((cmpres = STRCASECMP(baseptr->key,key)) == 0)
       return baseptr->data;
    else if (cmpres < 0)
       return find_node(baseptr->left,key);

    return find_node(baseptr->right,key);
}


/***********************************************************************
 ** reset_current - reset the linked list current entry, wrapper function
 **
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::reset_current(void)
{
  the_list.reset_current();
}


/***********************************************************************
 ** get_next - gets the next element in the linked list, wrapper function
 **
 ***********************************************************************/

template<class TYPE>
TYPE *btree<TYPE>::get_next(void)
{
  b_node<TYPE> *tmp_node;

  if ((tmp_node = the_list.get_next()) == NULL)
    return NULL;
  return tmp_node->data;
}


/***********************************************************************
 ** clr_tree - remove all nodes
 ***********************************************************************/

template<class TYPE>
int btree<TYPE>::clr_tree()
{
  b_node<TYPE> *del_node;
  TYPE *del_ptr;

  del_node = the_list.get_first();
  while (del_node != NULL)
  {
    the_list.del_entry(del_node);
    delete del_node->key;

      if (del_data)
      {
            del_ptr = del_node->data;
            delete del_ptr;
      }
    delete del_node;
    del_node = the_list.get_first();
  }
  root = NULL;
  return 1;
}


/***********************************************************************
 ** btree (destructor) - free the binary tree
 ***********************************************************************/

template<class TYPE>
btree<TYPE>::~btree(void)
{
   clr_tree();
}


/***********************************************************************
 ** push_current - wrapper that saves the old current pointer by pushing
 **                a new current on the stack
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::push_current()
{
  the_list.push_current();
}


/***********************************************************************
 ** pop_current - wrapper that removes the current pointer for the linked
 **               list to return to the old pointer
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::pop_current()
{
  the_list.pop_current();
}


/***********************************************************************
 ** set_del_data - sets the btree to delete the data as well when clearing
 ***********************************************************************/

template<class TYPE>
void btree<TYPE>::set_del_data()
{
  del_data = 1;
}


// This stuff is here to make templates work in g++ as they appear to be
// slightly broken.  It must be done for all possible uses.


template class btree<Entity>;
template class btree<Area_Dbase>;
template class b_node<Entity>;
template class b_node<Area_Dbase>;

#endif


Generated by  Doxygen 1.6.0   Back to index