source: orxonox.OLD/orxonox/trunk/src/list.h @ 2758

/* 
   orxonox - the future of 3D-vertical-scrollers

   Copyright (C) 2004 orx

   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, or (at your option)
   any later version.

   ### File Specific:
   main-programmer: Christian Meyer

   ADDONS/FIXES:
  
   Patrick Boenzli     :          Implemented getSize() function
*/


/*!
  \file list.h
  \brief Contains a template for a doubly linked list
*/

#ifndef LIST_H
#define LIST_H

#include "stdlib.h"

//! An enum to list all the modes available when adding an object to a List
enum ADDMODE {LIST_ADD_NEXT, LIST_ADD_PREV, LIST_ADD_FIRST, LIST_ADD_LAST};
//! An enum to list the two searching directions available when removing an object from a List
enum FINDMODE {LIST_FIND_BW, LIST_FIND_FW};

//! A generic doubly linked list
template<class T> class List 
{
  T* object;
  List<T>* next;
  List<T>* prev;
  bool bReference;
  int size;
  
 public:
  List (T* obj, List<T>* n, List<T>* p, bool bRef);
  ~List ();
  
  int add (T* obj, ADDMODE mode, bool bRef);
  T* get_object();
  List<T>* get_next ();
  List<T>* get_previous ();
  List<T>* get_last ();
  List<T>* get_first ();
  void set_next (List<T>* ptr);
  void set_prev (List<T>* ptr);
  int remove (T* obj, FINDMODE mode);
  int getSize();
};


/**
  \brief Standard constructor
  
  Call this without any parameters to generate a new List which can be filled with content.
  DO NOT create a List element that contains an object on your own, you'll lose the data
  contained in that object and will have trouble removing the list from your memory.
*/
template<class T>
List<T>::List (T* obj = NULL, List<T>* n = NULL, List<T>* p = NULL, bool bRef = false)
{
  object = obj;
  next = n;
  prev = p;
  bReference = bRef;
  if(obj != NULL)
    ++size;
}

/**
  \brief Standard destructor
  
  Call this on the initially generated base List element to remove the whole List from the memory.
  You can safely do this to any List element you want without messing up the rest of the List, but keep in mind
  that the contained object will be deleted as well when bRef had been set to false.
*/
template<class T>
List<T>::~List ()
{
  if (object == NULL) // deleted foot node => disband the list
  {
    while( next != NULL)
    {
      delete next;
    }
    while( prev != NULL)
    {
      delete prev;
    }
  }
  else
  {
    if (prev != NULL) prev->set_next (next);
    if (next != NULL) next->set_prev (prev);
    if (!bReference) delete object;
  }
}
 
/**
  \brief Add an object to the List
  \param obj: A pointer to an allocated object
  \param mode: A Value of ADDMODE (default: LIST_ADD_NEXT)
  \param bRef: Sets whether the element is serving as a storage point or a simple listing (default: false)
  \return 0 if the operation succeded, -1 if the element could not be added
  
  This adds a new List element to the chain. The mode parameter can be used to specify
  the location where the element should be added. LIST_ADD_NEXT will add the new element directly
  after the base element. LIST_ADD_PREV will add the new element directly before the base element.
  LIST_ADD_FIRST will add the element at the beginning of the List whereas LIST_ADD_LAST will add
  it to the end of the chain. If the bRef parameter is set to true, the object pointer will not be deleted
  when the element containing that object is deleted, thus the List can be used for temporary listings as
  well as permanent data storage.
*/
template<class T> 
int List<T>::add (T* obj, ADDMODE mode = LIST_ADD_NEXT, bool bRef = false)
{
  List<T>* p;
  if( obj == NULL) return -1;
  switch (mode)
  {
    case LIST_ADD_NEXT:
      p = new List<T>( obj, next, this, bRef);
      if( next != NULL) next->set_prev (p);
      next = p;
      break;
    case LIST_ADD_PREV:
      p = new List<T>( obj, this, prev, bRef);
      if( prev != NULL) prev->set_next (p);
      prev = p;
      break;
    case LIST_ADD_FIRST:
      if (prev == NULL) prev = new List<T> (obj, this, NULL, bRef);
      else return prev->add (obj, mode, bRef);
      break;
    case LIST_ADD_LAST:
      if (next == NULL) next = new List<T> (obj, NULL, this, bRef);
      else return next->add (obj, mode, bRef);
      break;
    default:
        return -1;
      break;
  }
  ++size;
  return 0;
}

/**
  \brief Get the next element of the List
  \return The List element after the current List element
*/
template<class T>
List<T>* List<T>::get_next ()
{
  return next;
}
 
/**
  \brief Get the previous element of the List
  \return The List element before the current List element
*/
template<class T>
List<T>* List<T>::get_previous ()
{
  return prev;
}

/**
  \brief Get the last element of the List
  \return The last List element
*/
template<class T>
List<T>* List<T>::get_last ()
{
  if (next == NULL) return this;
  else return next->get_last();
}

/**
  \brief Get the first element of the List
  \return The first List element
*/
template<class T>
List<T>* List<T>::get_first ()
{
  if (prev == NULL) return this;
  else return prev->get_first();
}

/**
  \brief Removes a certain element from the List
  \param obj: A pointer to the object that should be removed
  \param mode: A value of FINDMODE
  \return 0 if the element was found and removed, -1 if the element was not found
  
  This searches the part of the List specified with mode for the object in question.
  When the object is found it is deleted and the List element is removed from the chain.
  If mode is LIST_FIND_FW all elements AFTER the base element are searched, if mode is
  LIST_FIND_BW all elements BEFORE the base element are searched. Note that the object
  contained within the List element is NOT deleted when bRef was set to true.
*/
template<class T>
int List<T>::remove (T* obj, FINDMODE mode = LIST_FIND_FW)
{
  if (obj == NULL) return -1;
  else
  {
    switch (mode)
    {
      case LIST_FIND_BW:
        if (prev == NULL) return -1;
        else
        {
          if( prev->get_object() == obj)
          {
            delete prev;
          }
          else
          {
            return prev->remove( obj, mode);
          }
        }
        break;
      case LIST_FIND_FW:
        if (next == NULL) return -1;
        else
        {
          if( next->get_object() == obj)
          {
            delete next;
          }
          else
          {
            return next->remove( obj, mode);
          }
        }
        break;
      default:
        return -1;
    }
  }
  --size;
  return 0;
}

/**
  \brief Set the next element of a List element
  \param ptr: A pointer to the new next element
    
  Sets the next element of a List element... Better not touch this, it can really mess up a List.
*/
template<class T>
void List<T>::set_next (List<T>* ptr)
{
  next = ptr;
}

/**
  \brief Set the prev element of a List element
  \param ptr: A pointer to the new previous element
    
  Sets the previous element of a List element... Better not touch this, it can really mess up a List.
*/
template<class T>
void List<T>::set_prev (List<T>* ptr)
{
  prev = ptr;
}

/**
  \brief Get the pointer to the object the element is containing
  \return The contained object (will be NULL if called on the base element).
*/
template<class T>
T* List<T>::get_object()
{
  return object;
}


/**
  \brief Returns the current size of the List
  \return Size of List
*/
template<class T>
int List<T>::getSize()
{
  return this->size;
}

#endif