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

lextree.cpp

/**********************************************************************
 ** Lextree - A lexical analysis tree used to store verbs and provide a
 **           quick lookup while still allowing for abbreviation of verbs.
 **           It is a modified lexical analysis tree in that it uses only
 **           one node for each word, rather than one node for each
 **           letter as you descend the tree.  This means more efficient
 **           use of memory and faster lookup, but slower adds and 
 **           deletes.  That is ok since we rarely add or delete, only
 **           lookup.
 **
 ** Reviewed through:
 **
 **
 ** Copyright (C) 2000 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 LEXTREE_C
#define LEXTREE_C

#include "config.h"
#include "sysdep.h"
#include "strings.h"
#include "mudtypes.h"
#include "entity.h"
#include "lextree.h"
#include "global.h"
#include "newfuncts.h"

lextree::lextree()
{
   root = NULL; 
   last_added = NULL; 
   next_in_list = NULL;

   current_node = NULL;
   list_root = NULL;
}

int lextree::add(char *key,Entity *data)
{   lex_holder *newnode;
    int      result;
    int      i;

    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_lex_holder();
    newnode->key = NULL;
    newnode->data = NULL;    
    for (i=0; i<27; i++)
       newnode->letters[i] = NULL;
    newnode->next = NULL;

    newnode->key = new char[strlen(key) + 1];
    strcpy(newnode->key,key);
    newnode->data = data;
    newnode->next = NULL;
    
    // Then we try adding it to the tree
    if ((result = add_node(&root,newnode, 0)) > 0)
    {
       if (last_added == NULL)
       {
          list_root = newnode;
          last_added = list_root;
       }
       else
       {
          last_added->next = newnode;
          last_added = newnode;
       }
    }

    return result;
}

int lextree::clr_list()
{
   
   return 1;
}

int lextree::get_slot(char the_char)
{
   if (((int)the_char < 97) || ((int)the_char > 122))
      return 26;
   return (((int) the_char) - 97);  
}

 
int lextree::add_node(lex_holder **baseptr,lex_holder *newnode, 
                                                       int cur_offset)
{ 
   char keyltrptr;
   char nodeltrptr;

   int  new_offset;
   int  slot = -1;
   int  i;

   new_offset = cur_offset;
   keyltrptr = *(newnode->key + new_offset);
   keyltrptr = (char) tolower((int) keyltrptr);   

   /* if this is the first addition, set the cur_letter pointer and create
      the root node */
   if ((*baseptr) == NULL)
   {
      root = new_lex_holder();
      root->key = NULL;
      root->data = NULL;

      for (i=0; i<27; i++)
         root->letters[i] = NULL;
      root->indexltr = 0;
      root->next = NULL;
      (*baseptr) = root;
   }
  
   /* if this is not the root node, check the key in this node */
   if ((*baseptr)->key != NULL)
   {
      nodeltrptr = (*((*baseptr)->key + new_offset));
      nodeltrptr = (char) tolower((int) nodeltrptr);   

      /* advance till we find a difference */
      while ((nodeltrptr != '\0') && (keyltrptr != '\0') && 
             ((nodeltrptr == keyltrptr) && 
              (new_offset < (*baseptr)->indexltr)))
      {
         new_offset++;
         nodeltrptr = (*((*baseptr)->key + new_offset));
         keyltrptr = (*(newnode->key + new_offset));
      } 
      
      /* if theyre both equal to null, then we have a duplicate */
      if ((nodeltrptr == '\0') && (keyltrptr == '\0'))
      {
         delete newnode->key;
         delete_lex_holder(newnode);
         return 0;   
      }

      /* if the node pointer is null, then the key to be added is longer,
         so we index on the next letter. */
      if (nodeltrptr == '\0') 
      {
         slot = get_slot(keyltrptr);
      }

      /* else if the key ends up being smaller, we replace the data
         and then place the old data */
      else if (keyltrptr == '\0')
      {
         Entity *tmp_entity;
         char   *tmp_key;
         lex_holder *tmp_lex;


         if ((*baseptr)->indexltr != new_offset)
       {
            tmp_lex = *baseptr;
            *baseptr = newnode;
            newnode = tmp_lex;
            keyltrptr = (*(newnode->key + new_offset));
            slot = get_slot(keyltrptr);
            (*baseptr)->indexltr = new_offset;
         }
         else
       {
            tmp_key = newnode->key;
            tmp_entity = newnode->data;
            newnode->key = (*baseptr)->key;
            newnode->data = (*baseptr)->data;
            (*baseptr)->key = tmp_key;
            (*baseptr)->data = tmp_entity;   

            slot = get_slot(nodeltrptr);
         }

      }

      /* they must both be letters and not equal */
      else
      {
      /* if we are indexing the wrong letter for this node, then replace 
           the one here since that means that the new key is indexing 
           a letter before the key at this node now */
         if ((*baseptr)->indexltr != new_offset)
       {
            lex_holder tmp_lex;
                               
            /* switch newnode with the current node and work on finding
               a spot for the current node now */
            tmp_lex.data = newnode->data;
            tmp_lex.key = newnode->key;
            for (i=0; i<27; i++)
               tmp_lex.letters[i] = newnode->letters[i];

            newnode->data = (*baseptr)->data;
            newnode->key = (*baseptr)->key;
            for (i=0; i<27; i++)
               newnode->letters[i] = (*baseptr)->letters[i];
            newnode->indexltr = (*baseptr)->indexltr;
          
            (*baseptr)->data = tmp_lex.data;
            (*baseptr)->key = tmp_lex.key;
            for (i=0; i<27; i++)
               (*baseptr)->letters[i] = tmp_lex.letters[i];
            (*baseptr)->indexltr = cur_offset;

            slot = get_slot(nodeltrptr);

       }
         else
            slot = get_slot(keyltrptr);
      }
   }
   else
   {
      slot = get_slot(*newnode->key);
   }

   if ((*baseptr)->letters[slot] == NULL)
   {
      (*baseptr)->letters[slot] = newnode;
      (*baseptr)->indexltr = new_offset;
      return 1;
   }
   else
   {
      if (slot != 26)
         new_offset++;
      return add_node(&((*baseptr)->letters[slot]), newnode, new_offset);
   }
}

int lextree::del(char *key)
{
   lex_holder *prev_node;
   int        prev_ltr = 0;
   lex_holder *del_node;
   int        offset = 0;
   char       key_char;
   char       node_char;
   int        pullup_slot;
   int        i;

   lex_holder *tmp_letters[27];

   /* first find the node */
   prev_node = root;
   del_node = prev_node;
   key_char = *key;
   node_char = *(del_node->key);
   
   while ((key_char != '\0') && (node_char != '\0'))
   {
      if (key_char != node_char)
      {
         if (offset != del_node->indexltr)
          return -1;
         prev_node = del_node;
         del_node = prev_node->letters[(prev_ltr = get_slot(key_char))];
         
         offset++;
         node_char = *(prev_node->key + offset);
         key_char = *(key+offset);
      }
      else
      {
         offset++; 
         node_char = *(prev_node->key + offset);
         key_char = *(key+offset);
      }
   }

   /* we found no match, can't delete */
   if ((key_char != '\0') || (node_char != '\0'))
   {
      return 0;
   }

   /* we are at the element to delete, perform the steps */

   /* get the letter that matches the letter compared against in the
      word to be deleted, so if we're comparing the third letter in the
      word look, we would pull up the o pointer */

   /* if we don't have anything on that pointer, take the far left pointer */
   if (del_node->letters[(pullup_slot = 
                            get_slot(*(key+del_node->indexltr)))] == NULL)
   {
      int counter = 0;
      
      while ((del_node->letters[counter] == NULL) && (counter < 27))
         counter++;

      /* if there is nothing attached to this node, just delete it */
      if (counter == 27)
      {
         prev_node->letters[prev_ltr] = NULL;
         if (del_node->data != NULL)
            mainstruct->delete_entity(del_node->data);
         delete del_node->key;
         delete_lex_holder(del_node);
         return 1;
      }
     
      pullup_slot = counter;
   }

   prev_node->letters[prev_ltr] = del_node->letters[pullup_slot];
   /* copy all pointers in the one to be moved up to this temp array */
   for (i=0; i<27; i++)
      tmp_letters[i] = prev_node->letters[prev_ltr]->letters[i];

   for (i=0; i<27; i++)
      prev_node->letters[prev_ltr]->letters[i] = del_node->letters[i];

   if (del_node->data != NULL)
      mainstruct->delete_entity(del_node->data);

   delete del_node->key;
   delete_lex_holder(del_node);

   /* now re-add the saved nodes to the list and we should be done */
   for (i=0; i<27; i++)
   {
      if (tmp_letters[i] != NULL)
         add_node(&root,tmp_letters[i], 0);      
   }
   return 1;

}


Entity *lextree::find(char *key)
{
   return find_node(root,key, 0);
}

Entity *lextree::find_abbrev(char *key)
{
   return find_node_abbrev(root,key, 0);
}

 
bool lextree::can_find(char *key)
{  if (find_node(root,key, 0) == NULL)
      return false;
   return true;
}


Entity *lextree::find_node_abbrev(lex_holder *baseptr, char *key, 
                                                         int cur_offset)
{  
    int new_offset;
    char key_char;
    char node_char = '\0';
    int  check_slot;
    Entity *found_node;

    key_char = *(key + cur_offset);
    new_offset = cur_offset;

    if (baseptr == NULL)
       return NULL;

    if (baseptr->key != NULL)
    {
       node_char = *(baseptr->key + cur_offset);
       while ((key_char != '\0') && (node_char != '\0') && 
              (key_char == node_char) && (new_offset != baseptr->indexltr))
       {
          new_offset++;
          key_char = *(key + new_offset);
          node_char = *(baseptr->key + new_offset);
       }

       /* matches this verb by abbreviation */
       if (key_char == '\0')
       {
          return baseptr->data;
       }
    }

    check_slot = get_slot(key_char);

    if (((baseptr->indexltr != new_offset) || (node_char == '\0')) && 
                             (baseptr->letters[check_slot] == NULL))
    {
       return NULL;
    }

    if (check_slot != 26)
       new_offset++;

    /* if we dont find a solution by travelling this path, we make sure
       this word wasnt the one */
    if (((found_node = find_node_abbrev(baseptr->letters[check_slot], 
         key, new_offset)) == NULL) && (baseptr->key != NULL))
    {
       key_char = *(key + new_offset);
       node_char = *(baseptr->key + new_offset);   
       while ((key_char != '\0') && (node_char != '\0') && 
              (key_char == node_char))
       {
          new_offset++;
          key_char = *(key + new_offset);
          node_char = *(baseptr->key + new_offset);
       }

       /* matches this verb by abbreviation */
       if (key_char == '\0')
       {
          return baseptr->data;
       }       
    }
    else
       return found_node;

    return NULL;
}


Entity *lextree::find_node(lex_holder *baseptr, char *key, int cur_offset)
{  
    int new_offset;
    char key_char;
    char node_char;
    int  check_slot;

    key_char = *(key + cur_offset);
    new_offset = cur_offset;

    if (baseptr->key != NULL)
    {
       node_char = *(baseptr->key + cur_offset);
       while ((key_char != '\0') && (node_char != '\0') && 
              (key_char == node_char))
       {
          new_offset++;
          key_char = *(key + new_offset);
          node_char = *(baseptr->key + new_offset);
       }

       if ((key_char == '\0') && (node_char == '\0'))
          return baseptr->data;

       if (key_char == '\0')
       {
          return NULL;
       }
    }
  
    if (baseptr->letters[(check_slot = get_slot(key_char))] == NULL)
    {
       return NULL;
    }

    if (((baseptr->indexltr != new_offset) || (node_char == '\0')) && 
                             (baseptr->letters[check_slot] == NULL))
    {
       return NULL;
    }

    new_offset++;
    return find_node(baseptr->letters[check_slot], key, new_offset);
}

int lextree::free_node(lex_holder *the_node)
{
   int i;

   if (the_node == NULL)
      return 1;

   for (i=0; i<27; i++)
      if (the_node->letters[i] != NULL)
         free_node(the_node->letters[i]);

   delete the_node->key;
   if (the_node->data != NULL)
   {
         mainstruct->delete_entity(the_node->data);
   }
   delete_lex_holder(the_node);
   return 1;
}

int lextree::show(void)
{
   return show_node(root, 0);
}

int lextree::show_node(lex_holder *baseptr, int level)
{
   int i, j;   

   if (baseptr == NULL)
      return -1;

   for (i=0; i<level; i++)
      printf("   ");

   if (baseptr->data == NULL)
      printf("Root Node\n");
   else
   {
      printf("Node: \t%s\n", baseptr->key);
      for (i=0; i<level; i++)
         printf("   ");
      printf("Checking ltr: \t%d\n", baseptr->indexltr); 
   }

   for (i=0; i<27; i++)
   {
      if (baseptr->letters[i] != NULL)
      {
         for (j=0; j<level; j++)
            printf("   ");
         printf("Pointer '%c':\n", (char) (i+97));
         show_node(baseptr->letters[i], level + 1);
      }
   }  
   return 1;
}


lextree::~lextree(void)
{
   free_node(root);
}

void lextree::reset_current()
{
   current_node = list_root;
}


Entity *lextree::get_next()
{
   Entity *ret_holder;

   if (current_node == NULL)
      return NULL;

   ret_holder = current_node->data;
   current_node = current_node->next;
   return ret_holder;
}

#endif


Generated by  Doxygen 1.6.0   Back to index