SMAUG: "Binary Search Tree" snippet by Zeno
=======================================

Description
-----------
This snippet is used to install a binary search tree into Smaug. It is
not intended to change gameplay, but to provide a template to use the
BST or an example of how a BST works. If you do not know what a Binary
Search Tree is, I do not recommend using this. This was going to be
used in the hate system, but I am not sure if I will use a BST for it.

Support
-------
All support for this snippet (and any of my snippets) must be posted on
MudBytes (mudbytes.net) under the appropriate code. Find this snippet
on MudBytes, post a new comment, and I will reply as soon as possible.

Sharing
-------
All of my released code can be distributed anywhere as long as credit
is given when due. Please do not claim my code as your own. If you
do distribute my code to other places, I'd like it if you notify me.
My email address is zenomcdohl-AT-gmail-DOT-com, but please do not
use this for support.

Background
----------
This code was originally released at MudBytes (mudbytes.net). Most
(if not all) of my released code originated from the MUD I run
(InuYasha Galaxy: iyg.arthmoor.com) which is a modified version of
SmaugFUSS. Therefor all code I release has been tested and is currently
running on a MUD open to the public. Everything should work as intended,
but since I wrote most of this code years ago, improvements can probably
be made to the code to make it more efficient. I'd appreciate it if you
improve any of the code, that you would post the changes on MudBytes. You
can find contact information and details about myself at the following URL:
http://en.wikipedia.org/wiki/User:Zeno_McDohl


Installation
------------
1.) Copy the following code to a .c file (I used handler.c):

 /* Hate System  -Zeno */
 search_tree tree_make_empty( search_tree tree )
 {
   if ( tree != NULL )
   {
       tree_make_empty( tree->left );
       tree_make_empty( tree->right );
       free( tree );
   }
   return NULL;
 }

 tree_position tree_find( CHAR_DATA *target, search_tree tree )
 {
     if ( tree == NULL )
       return NULL;

     if ( target < tree->hatedata->target_char )
       return tree_find( target, tree->left );
     else if ( target > tree->hatedata->target_char )
       return tree_find( target, tree->right );
     else
       return tree;
 }

 search_tree tree_insert( HATE_DATA *hatedata, search_tree tree )
 {
     if ( tree == NULL )
     {
       tree = (HATE_NODE * ) malloc( sizeof( HATE_NODE ) );

       if ( tree == NULL )
          bug( "tree_insert: out of space!" );
       else
       {
          tree->hatedata = hatedata;
          tree->left = tree->right = NULL;
       }
     }
     else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_insert( hatedata, tree->left );
     else if ( hatedata->target_char > tree->hatedata->target_char )
          tree->right = tree_insert( hatedata, tree->right );

     return tree;
 }

 tree_position tree_find_min( search_tree tree )
 {
    if ( tree == NULL )
       return NULL;
    else if ( tree->left == NULL )
       return tree;
    else
       return tree_find_min( tree->left );
 }

 search_tree tree_delete( HATE_DATA *hatedata, search_tree tree )
 {
    tree_position pos;

    if ( tree == NULL )
       bug( "tree_delete: not found" );
    else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_delete( hatedata, tree->left );
    else if ( hatedata->target_char > tree->hatedata->target_char )
         tree->right = tree_delete( hatedata, tree->right );
    else if ( tree->left && tree->right )
    {
       pos = tree_find_min( tree->right );
       tree->hatedata = pos->hatedata;
       tree->right = tree_delete( tree->hatedata, tree->right );
    }
    else
    {
       pos = tree;
       if ( tree->left == NULL )
         tree = tree->right;
       else if ( tree->right == NULL )
         tree = tree->left;
       free( pos );
    }

    return tree;
 }

 HATE_DATA *tree_retrieve( tree_position pos )
 {
    return pos->hatedata;
 }


2.) In db.c, in create_mobile add this line:
 mob->hatedata = tree_make_empty( NULL );

3.) In mud.h, under the other typedef structs add these lines:
 typedef struct hate_data HATE_DATA;
 typedef struct hate_node *tree_position;
 typedef struct hate_node *search_tree;
 typedef struct hate_node HATE_NODE;

4.) In mud.h near the other structs, add these lines:
 /* Hate System  -Zeno */
 struct hate_data
 {
    CHAR_DATA *target_char;
    int hate_amount;
 };

 struct hate_node
 {
    HATE_DATA *hatedata;
    search_tree left;
    search_tree right;
 };

5.) In mud.h with the other fn prototypes, add these lines:
 search_tree tree_make_empty( search_tree tree );
 tree_position tree_find( CHAR_DATA *target, search_tree tree );
 search_tree tree_insert( HATE_DATA *hatedata, search_tree tree );
 tree_position tree_find_min( search_tree tree );
 search_tree tree_delete( HATE_DATA *hatedata, search_tree tree );
 HATE_DATA *tree_retrieve( tree_position pos );

6.) In mud.h under the char_data struct, add this:
   search_tree hatedata; //Hate System  -Zeno


7.) To test the BST, I added this in do_consider:
    /* Hate System test  -Zeno */
    if ( IS_NPC(victim) )
    {
         HATE_DATA *hatedata;
       tree_position P;

       if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )
       {
         int test;
         hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );
         hatedata->target_char = ch;
         test = number_range( 1, 50 );
         hatedata->hate_amount = test;
         victim->hatedata = tree_insert( hatedata, victim->hatedata );
         ch_printf( ch, "It should now hate you for %d.\n\r", test );
       }
       else
       {
         hatedata = tree_retrieve(tree_find( ch, victim->hatedata ));
         ch_printf(ch, "You are already hated for %d!\n\r", hatedata->hate_amount );
       }

    }

8.) Make clean, make and hotboot/reboot the MUD.