source: orxonox.OLD/trunk/src/lib/util/list.h @ 5099

/*!
 * @file list.h
 * a File that includes a List-template
 */

#ifndef _LIST_H
#define _LIST_H

#include "compiler.h"
#ifndef NULL
#define NULL 0                                       //!< this will define NULL
#endif



//! a list element of the tList,
template<class T> struct listElement
{
  listElement*        prev;                          //!< pointer to the previous listElement in the list
  T*                  curr;                          //!< pointer to the list payload/container
  listElement*        next;                          //!< pointer to the next listElement
};

/**
 *  an iterator class

   this enables the user to iterate through a list very easely
*/
template<class T> class tIterator
{
 public:
  tIterator(listElement<T>* startElement);
  ~tIterator();

  T* nextElement();
  T* seekElement(T* element);

 private:
  listElement<T>*    currentEl;                      //!< pointer to the current list element in the iterator
  listElement<T>*    tmpEl;                          //!< temp listElemnt pointer
  listElement<T>*    startElement;                   //!< pointer to the start of the list
};


/**
 *  iterator constructor
 * @param startElement:  the first list element from the tList

   normaly you will use it like this:

   tIterator<char>* nameIterator = nameList->getIterator();
   char name* = nameIterator->nextElement();
   while( name != NULL)
   {
     PRINTF(3)("found name: %s in list\n", name);
     name = nameIterator->nextElement();
   }
   delete nameIterator;
*/
template<class T>
inline tIterator<T>::tIterator (listElement<T>* startElement)
{
  this->currentEl = startElement;
  this->tmpEl = NULL;
  this->startElement = startElement;
}


/**
 *  the destructor
*/
template<class T>
inline tIterator<T>::~tIterator ()
{
  this->currentEl = NULL;
}


/**
 *  use it to iterate through the list
 * @returns next list element
*/
template<class T>
inline T* tIterator<T>::nextElement ()
{
  if( this->currentEl == NULL)
    return NULL;

  this->tmpEl = this->currentEl;
  this->currentEl = this->currentEl->next;
  return this->tmpEl->curr;
}

/**
 *  gets the element after the selected one, sets the iterator to this point in the list
 * @param element the element to seek
 * @returns next list element

  Attention: if you seek an element, the iterator pointer will point to the NEXT listelement after the argument!
 */
template<class T>
inline T* tIterator<T>::seekElement (T* element)
{
  for(this->tmpEl = this->startElement; this->tmpEl != NULL; this->tmpEl = this->tmpEl->next)
  {
    if( unlikely(this->tmpEl->curr == element))
    {
      if( this->tmpEl->next != NULL)
      {
        this->currentEl = this->tmpEl->next->next;
        return this->tmpEl->next->curr;
      }
      return NULL;
    }
  }
  return NULL;
}



/**
 *  the list template class

   you will use this as a generic list for all type of objects
*/
template<class T> class tList
{
 public:
  tList ();
  ~tList ();

  void add(T* entity);
  void addAtBeginning(T* entity); //!< @todo This should be made with an ENUM
  void remove(T* entity);
  void removeLast();
  void flush();
  T* firstElement();
  T* lastElement();
  bool isEmpty();
  unsigned int getSize();
  bool inList(T* entity);
  tIterator<T>* getIterator();
  T* nextElement(T* toEntity);
  T* toArray();

 private:
  unsigned int       size;             //!< the size (lenght) of the list
  listElement<T>*    first;            //!< pointer to the first element
  listElement<T>*    last;             //!< pointer to the last element
  listElement<T>*    currentEl;        //!< pointer to the current element
};


/**
 *  the constructor
*/
template<class T>
inline tList<T>::tList ()
{
  this->first = NULL;
  this->last = NULL;
  this->size = 0;
}


/**
 *  the deconstructor

   this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will
   not be deleted
*/
template<class T>
inline tList<T>::~tList ()
{
  this->currentEl = this->first;
  while(this->currentEl != NULL)
    {
      listElement<T>* le = this->currentEl->next;
      //delete this->currentEl->curr;
      delete this->currentEl;
      this->currentEl = le;
    }
  this->first = NULL;
  this->last = NULL;
  this->size = 0;
}


/**
 *  add an entity to the list
 * @param entity: the entity to add
*/
template<class T>
inline void tList<T>::add(T* entity)
{
  if( unlikely(entity == NULL)) return;
  listElement<T>* el = new listElement<T>;
  el->prev = this->last;
  el->curr = entity;
  el->next = NULL;

  this->last = el;

  if( unlikely(el->prev == NULL)) this->first = el; /* if first element */
  else el->prev->next = el;
  this->size++;
}

/**
 *  add an entity to the list
 * @param entity: the entity to add
 */
template<class T>
    inline void tList<T>::addAtBeginning(T* entity)
{
  if( unlikely(entity == NULL)) return;
  listElement<T>* el = new listElement<T>;
  el->next = this->first;
  el->curr = entity;
  el->prev = NULL;

  this->first = el;

  if( unlikely(el->next == NULL)) this->first = el; /* if first element */
  else el->next->prev = el;
  this->size++;
}


/**
 *  remove an entity from the list
 * @param entity: the entity to be removed
*/
template<class T>
inline void tList<T>::remove(T* entity)
{
  this->currentEl = this->first;
  while( this->currentEl != NULL)
    {
      if( unlikely(this->currentEl->curr == entity))
        {
          if( unlikely(this->currentEl->prev  == NULL)) this->first = this->currentEl->next;
          else this->currentEl->prev->next = this->currentEl->next;

          if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
          else this->currentEl->next->prev = this->currentEl->prev;

          delete this->currentEl;
          this->size--;
          return;
        }
      this->currentEl = this->currentEl->next;
    }
}

/**
 * removes the Last Element of the List
 */
 template<class T>
     inline void tList<T>::removeLast()
{
  if (this->last == NULL)
    return;
  else if (this->last == this->first)
  {
    delete this->first;
    this->first = NULL;
    this->last = NULL;
    this->size--;
  }
  else
  {
    listElement<T>* delLast = this->last;
    this->last->prev->next = NULL;
    this->last = this->last->prev;
    delete delLast;
  }
}

/**
 *  this will deletes the objects from the list
*/
template<class T>
inline void tList<T>::flush()
{
  this->currentEl = this->first;
  while(this->currentEl != NULL)
    {
      listElement<T>* le = this->currentEl->next;
      delete this->currentEl->curr;
      delete this->currentEl;
      this->currentEl = le;
    }
  this->first = NULL;
  this->last = NULL;
  this->size = 0;
}


/**
 *  returns the first element of the list
 * @returns first element
*/
template<class T>
inline T* tList<T>::firstElement()
{
  return this->first->curr;
}


/**
 *  function returns the last element of the list
 * @returns the last element
*/
template<class T>
inline T* tList<T>::lastElement()
{
  return this->last->curr;
}


/**
 *  returns true if the list is empty
 * @returns true if the list is empty
*/
template<class T>
inline bool tList<T>::isEmpty()
{
  return (this->size==0)?true:false;
}

/**
 *  checks if an entity is in the List
 * @param entity The entity to check for in the entire List.
 * @returns true if it is, false otherwise
*/
template<class T>
inline bool tList<T>::inList(T* entity)
{
  // pre checks
  if(this->size == 0) return false;
  if( entity == NULL) return false;

  // search in the List
  this->currentEl = this->first;
  while(this->currentEl->curr != entity && this->currentEl != NULL)
    this->currentEl = this->currentEl->next;

  // post checks
  if(this->currentEl == NULL)
    return false;
  else
    return true;
}

/**
 *  this returns the number of elements in the list
 * @returns number of elements
*/
template<class T>
inline unsigned int tList<T>::getSize()
{
  return this->size;
}


/**
 *  creates an itereator object and returns it
 * @returns the iterator object to this list

   You will use this, if you want to iterate through the list
*/
template<class T>
inline tIterator<T>* tList<T>::getIterator()
{
  tIterator<T>* iterator = new tIterator<T>(this->first);
  return iterator;
}



/**
 *  this returns the next element after toEntity or the first if toEntity is last
 * @param toEntity: the entity after which is an entity, that has to be returned, sorry, terrible phrase
 * @returns the element after toEntity
*/
template<class T>
inline T* tList<T>::nextElement(T* toEntity)
{
  //if( this->last == this->first == NULL) return NULL;
  if(this->size == 0) return NULL;
  if( toEntity == NULL) return this->first->curr;
  if( toEntity == this->last->curr ) return this->first->curr;
  this->currentEl = this->first;
  while(this->currentEl->curr != toEntity && this->currentEl->next != NULL)
    {
      this->currentEl = this->currentEl->next;
    }
  if(this->currentEl == NULL) return NULL;
  return this->currentEl->next->curr;
}


/**
 *  creates an array out of the list (ATTENTION: not implemented)
 * @returns pointer to the array beginning

   ATTENTION: function is not implemented and wont do anything
*/
template<class T>
T* tList<T>::toArray()
{
  return NULL;
}

#endif /* _LIST_H */