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

linkedlist.cpp

/**********************************************************************
 ** LinkedList class: object that maintains a linked list of mudobjects, 
 **                   usually used for inventories of mudobjects
 **
 ** Last reviewed: version 0.14
 **
 **
 ** 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. 
 **
 **********************************************************************/

#include "config.h"
#include "sysdep.h"
#include "strings.h"
#include "mudobject.h"
#include "linkedlist.h"
#include "timespan.h"
#include "merger.h"
#include "player.h"
#include "newfuncts.h"
#include "global.h"
#include "utils.h"
#include "btree.h"
#include "code.h"

template<class TYPE>
cur_ptr<TYPE>::cur_ptr()
{
   current = NULL;
   next = NULL; 
}

template<class TYPE>
cur_ptr<TYPE>::~cur_ptr()
{
}


/* these all were embedded functions in the header, but since these type
   have been misbehaving, I took these out.  Documentation later. */
template<class TYPE>
LinkedNode<TYPE>::LinkedNode(TYPE *the_data)
{
   data = the_data; 
   next = prev = NULL; 
}

template<class TYPE>
void LinkedNode<TYPE>::set_data(TYPE *the_data) 
{ 
   data = the_data; 
}

template<class TYPE>
TYPE *LinkedNode<TYPE>::get_data() 
{ 
   return data; 
}

template<class TYPE>
void LinkedNode<TYPE>::del_data() 
{ 
   delete data; 
   data = NULL;
}

template<class TYPE>
void LinkedNode<TYPE>::set_next(LinkedNode<TYPE> *nextnode) 
{ 
   next = nextnode; 
}

template<class TYPE>
void LinkedNode<TYPE>::set_prev(LinkedNode<TYPE> *prevnode) 
{ 
   prev = prevnode; 
}

template<class TYPE>
LinkedNode<TYPE> *LinkedNode<TYPE>::get_next() 
{ 
   return next; 
}

template<class TYPE>
LinkedNode<TYPE> *LinkedNode<TYPE>::get_prev() 
{ 
   return prev; 
}


/*********************************************************************
 * CONSTRUCTOR - initializes the linked list
 *********************************************************************/
template<class TYPE>
LinkedList<TYPE>::LinkedList()
{
   root = NULL;
   cur_list = NULL;
   del_data = 0;
}

/*********************************************************************
 * DESTRUCTOR - Cleans up the linked list and clears all allocated
 *              memory.
 *********************************************************************/
template<class TYPE>
LinkedList<TYPE>::~LinkedList()
{
  clr_list();
}


/*********************************************************************
 * clr_list - clears all entry in the list, deleting the entry data if
 *            del_data is set
 *********************************************************************/

template<class TYPE>
void LinkedList<TYPE>::clr_list()
{
   LinkedNode<TYPE> *theNode;
   cur_ptr<TYPE> *del_ptr;

   while (root != NULL)
   {  
     theNode = root;
     root = root->get_next();

     if (del_data)
       theNode->del_data();

     delete theNode;
   }
   root = NULL;

   del_ptr = cur_list;
   while (cur_list != NULL)
   {
     cur_list = cur_list->next;
     delete del_ptr;
       del_ptr = cur_list;
   }
   cur_list = NULL;
}

/*********************************************************************
 * add_entry - Adds an entry to the list. It doesnt check if the 
 *             object to be added is already in the list.
 *
 * Parameters:
 * INPUT - pointer to a mudobject that needs to be added to the list
 * OUTPUT- 1 if succesful, 0 if not.
 *********************************************************************/
template<class TYPE>
int LinkedList<TYPE>::add_entry(TYPE *new_entry)
{   LinkedNode<TYPE> *newNode;

    newNode = new LinkedNode<TYPE>(new_entry);
    if (newNode == NULL)
    {
       fault("Error in linkedlist, node is null.\n");
       return 0;
    }

    if (root != NULL)
    {  newNode->set_next(root);
       newNode->set_prev(NULL);
       newNode->set_data(new_entry);
       root->set_prev(newNode);
       root = newNode;
       return 1;
    }
    else
    {  newNode->set_next(NULL);
       newNode->set_prev(NULL);
       root = newNode;
       return 1;
    }
    fault("Error in linked list, unreachable code reached!\n");
    return 0;
}


/*********************************************************************
 * add_tail_entry - Adds an entry to the tail of the list. It doesnt 
 *                  check if the object to be added is already in the list.
 *
 * Parameters:
 * INPUT - pointer to a mudobject that needs to be added to the list
 * OUTPUT- 1 if succesful, 0 if not.
 *********************************************************************/
template<class TYPE>
int LinkedList<TYPE>::add_tail_entry(TYPE *new_entry)
{   LinkedNode<TYPE> *newNode;
    LinkedNode<TYPE> *tmpNode;

    newNode = new LinkedNode<TYPE>(new_entry);
    if (newNode == NULL)
    {
       fault("Error in linkedlist, node is null.\n");
       return 0;
    }

    if (root == NULL)
    {
      root = newNode;
      newNode->set_prev(NULL);
      newNode->set_next(NULL);
      return 1;
    }

    tmpNode = root;
    while (tmpNode->get_next() != NULL)
       tmpNode = tmpNode->get_next();

    tmpNode->set_next(newNode);
    newNode->set_prev(tmpNode);
    return 1;
 }



/*********************************************************************
 * del_entry - Deletes an entry from the linked list
 *
 * Parameters:
 * INPUT - The type that needs to be deleted from the linked list
 *         the type will remain in memory, the node it is in will
 *         be deleted.
 * OUTPUT- 1 if succesful, 0 if not found.
 *********************************************************************/
template<class TYPE>
int LinkedList<TYPE>::del_entry(TYPE *entry)
{   
   LinkedNode<TYPE> *tmpNode = root;
   LinkedNode<TYPE> *nxtNode;
   LinkedNode<TYPE> *prvNode;

   while (tmpNode != NULL)
   {   
      if (tmpNode->get_data() == entry)
      {   
         if (tmpNode == root)
         {   
          nxtNode = root->get_next();
            if (nxtNode != NULL)
            {  
             nxtNode->set_prev(NULL);
            }
            root = nxtNode;
         }
       else
         {  
          nxtNode = tmpNode->get_next();
            prvNode = tmpNode->get_prev();

            if (nxtNode != NULL)
             nxtNode->set_prev(prvNode);
          if (prvNode != NULL)
            prvNode->set_next(nxtNode);
         }
      
       if (cur_list == NULL)
         push_current();

       if (cur_list->current == tmpNode)
         cur_list->current = nxtNode;

       // If this is set to delete data when deleting an element, do it
       if (del_data)
         tmpNode->del_data();

       // Now kill the element
       delete tmpNode;
       return 1;
      }
      tmpNode = tmpNode->get_next();
   }
   return 0;
}

/*********************************************************************
 * del_cur_entry - Deletes the entry that was requested by get_next,
 *                 get_first or get_prev.
 * Parameters:
 * OUTPUT- 0 if there is no current entry or the entry could not be
 *         found, 1 if there is.
 *********************************************************************/
template<class TYPE>
int  LinkedList<TYPE>::del_cur_entry()
{  LinkedNode<TYPE> *prvNode, *theNode, *nxtNode;
 
   if (cur_list == NULL)
      push_current();
   
   // If we are past the end, find the last node again
   if (cur_list->current == NULL)
   {
     prvNode = root;
     theNode = root;
     while (theNode != NULL)
     {
       prvNode = theNode;
       theNode = theNode->get_next();
     }
     theNode = prvNode;
   }
   else
   {
     theNode = cur_list->current->get_prev();
     if (theNode == NULL)
       theNode = root;
   }

   if (theNode != NULL)
   {   prvNode = theNode->get_prev();
       nxtNode = theNode->get_next();
       
       if (prvNode != NULL)
       prvNode->set_next(nxtNode);
       else if (theNode == root)
       root = root->get_next();

       if (nxtNode != NULL)
       nxtNode->set_prev(prvNode);

       if (del_data)
       theNode->del_data();

       delete theNode;
       cur_list->current = nxtNode;
       return 1;
   }
   printf("Current was null!\n");
   return 0;
}

/*********************************************************************
 * get_next - get the next entry in the linked list
 * 
 * Parameters:
 * OUTPUT- returns the next object in the linked list, NULL if the
 *         end is reached.
 *********************************************************************/
template<class TYPE>
TYPE *LinkedList<TYPE>::get_next()
{
   TYPE *the_data;
   
   if (cur_list == NULL)
     push_current();

   if (cur_list->current == NULL)
   {
      return NULL;
   }

   the_data = cur_list->current->get_data();
   cur_list->current = cur_list->current->get_next();
   return the_data;
}

/*********************************************************************
 * get_prev - returns the previous entry in the linked list.
 * 
 * Parameters:
 * OUTPUT- Pointer to the previous mudobject or NULL if the beginning
 *         of the list was reached.
 *********************************************************************/
template<class TYPE>
TYPE *LinkedList<TYPE>::get_prev()
{
    if (cur_list == NULL)
      push_current();

    if (cur_list->current == NULL)
    {
       return NULL;
    }
    else
    {   cur_list->current = cur_list->current->get_prev();
        if (cur_list->current != NULL)
      {
           return cur_list->current->get_data();
      }
    }
    return NULL;
}

/*********************************************************************
 * get_first - gets the first entry in the linked list
 * 
 * Parameters:
 * OUTPUT: returns NULL if the list is empty or a pointer to the
 *         first mudobject.
 *********************************************************************/
template<class TYPE>
TYPE *LinkedList<TYPE>::get_first()
{
   TYPE *the_data = NULL;

   if (cur_list == NULL)
     push_current();

   cur_list->current = root;
   if (cur_list->current != NULL)
   {
      the_data = cur_list->current->get_data();
      cur_list->current = cur_list->current->get_next();
      return the_data;
   }
   return NULL;
}

/***********************************************************************
 ** reset_current - resets the current linked list to the beginning
 **
 ** Parameters: None
 **
 ** Returns: Nothing
 **
 ***********************************************************************/

template<class TYPE>
void LinkedList<TYPE>::reset_current()
{
   if (cur_list == NULL)
     push_current();
   else
     cur_list->current = root;
}


/***********************************************************************
 ** push_current - pushes a new current pointer onto the stack
 **
 ** Parameters: None
 **
 ** Returns: 1 for success, -1 for failure
 ** 
 ***********************************************************************/

template<class TYPE>
int LinkedList<TYPE>::push_current()
{
  cur_ptr<TYPE> *new_current;

  new_current = new cur_ptr<TYPE>;
  new_current->current = root;
  new_current->next = cur_list;
  cur_list = new_current;
  return 1;
}


/***********************************************************************
 ** pop_current - pops the current pointer from the stack
 **
 ** Parameters: None
 **
 ** Returns: 1 for success, -1 for failure
 ** 
 ***********************************************************************/

template<class TYPE>
int LinkedList<TYPE>::pop_current()
{
  cur_ptr<TYPE> *old_ptr;

  if (cur_list == NULL)
    return -1;

  old_ptr = cur_list;
  cur_list = cur_list->next;
  delete old_ptr;

  return 1;
}

/***********************************************************************
 ** set_del_data - sets this linked list to delete data when deleting an
 **                entry
 ***********************************************************************/

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


/***********************************************************************
 ** get_mem_size - gets how much memory this special is taking up
 **
 ** Returns: mem size in bytes
 **
 ***********************************************************************/

template<class TYPE>
int LinkedList<TYPE>::get_mem_size()
{
   int size = 0;

   size = sizeof(this);
   size += get_mem_size_dynamic();
   return size;
}

/***********************************************************************
 ** get_mem_size_dynamic    - gets how much memory is taken up by pointers
 ** get_mem_size_linkedlist - pointing to other objects, not including the
 **                           sizeof(this)
 **
 ** Returns: mem size in bytes
 **
 ***********************************************************************/

template<class TYPE>
int LinkedList<TYPE>::get_mem_size_dynamic()
{
   return get_mem_size_linkedlist();
}

template<class TYPE>
int LinkedList<TYPE>::get_mem_size_linkedlist()
{
   int  size = 0;
   LinkedNode<TYPE> *tmp_node;

   tmp_node = root;
   while (tmp_node != NULL)
   {
      size += sizeof(*tmp_node);
      tmp_node = tmp_node->get_next();
   }
   return size;
}

// 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 LinkedList<MudObject>;
template class LinkedList<Strings>;
template class LinkedList< b_node<Entity> >;
template class LinkedList< b_node<Area_Dbase> >;
template class LinkedList<params>;
template class cur_ptr<params>;





Generated by  Doxygen 1.6.0   Back to index