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

/*!
 * @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

template<class T> class tIterator;

//! 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
};

/**
 *  the list template class

   you will use this as a generic list for all type of objects
*/
template<class T> class tList
{
  friend class tIterator<T>;

 public:
  tList ();
  ~tList ();

  void add(T* entity);
  void addAtBeginning(T* entity); //!< @todo This should be made with an ENUM
  void remove(const T* entity);
  void removeLast();
  void flush();
  T* firstElement() const;
  T* lastElement() const;
  bool isEmpty() const;
  unsigned int getSize() const;
  bool inList(T* entity);
  tIterator<T>* getIterator() const;
  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;  //! THIS IS EXTREMELY UNSAFE (the list only stores pointers not instances) //
      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(const 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() const
{
  return this->first->curr;
}


/**
 *  function returns the last element of the list
 * @returns the last element
*/
template<class T>
inline T* tList<T>::lastElement() const
{
  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() const
{
  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() const
{
  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() const
{
  return new tIterator<T>(this);
}



/**
 *  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;
}




/**
 *  an iterator class

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

    T* firstElement();
    T* lastElement();
    T* nextElement();
    T* prevElement();
    T* seekElement(T* element);
    T* iteratorElement(const tIterator<T>* iterator);

  private:
    listElement<T>*    currentEl;                      //!< pointer to the current list element in the iterator
    listElement<T>*    tmpEl;                          //!< temp listElemnt pointer
    const tList<T>*    list;                           //!< The List, that we want to iterate through
};


/**
 *  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->firstElement();
 * while( name != NULL)
 *  {
 *   PRINTF(3)("found name: %s in list\n", name);
 *   name = nameIterator->nextElement();
 *  }
 * delete nameIterator;
 * ********************************************************
 */
template<class T>
  inline tIterator<T>::tIterator (const tList<T>* list)
{
  this->currentEl = NULL;
  this->tmpEl = NULL;
  this->list = list;
}


/**
 *  the destructor
 */
template<class T>
    inline tIterator<T>::~tIterator ()
{
}

template<class T>
    inline T* tIterator<T>::firstElement ()
{
  this->tmpEl = this->list->first;
  if (this->tmpEl != NULL)
  {
    this->currentEl = this->tmpEl->next;
    return this->tmpEl->curr;
  }
  else
    return NULL;
}

template<class T>
    inline T* tIterator<T>::lastElement ()
{
  this->tmpEl = this->list->last;
  if (this->tmpEl != NULL)
  {
    this->currentEl = tmpEl->prev;
    return this->tmpEl->curr;
  }
  else
    return 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;
}

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

  this->tmpEl = this->currentEl;
  this->currentEl = this->currentEl->prev;

  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 current list element
 */
template<class T>
    inline T* tIterator<T>::seekElement (T* element)
{
  if (element == NULL)
  {
    this->currentEl = NULL;
    return NULL;
  }
  this->tmpEl = this->list->first;
  while( this->tmpEl != NULL)
  {
    if( unlikely(this->tmpEl->curr == element))
    {
      this->currentEl = this->tmpEl;
      return this->currentEl->curr;
    }
    this->tmpEl = this->tmpEl->next;
  }
  this->currentEl = NULL;
  return NULL;
}

/**
 * grabs the iterator entity from another iterator
 * @param iterator the iterator to grab the local currentEl from
 * @returns the grabbed element (current). NULL if not found, or not defined
 *
 * Both iterators must be from the same List!
 */
template<class T>
    T* tIterator<T>::iteratorElement(const tIterator<T>* iterator)
{
  if (iterator != NULL && iterator->list == this->list)
  {
    this->currentEl = iterator->currentEl;
    if (this->currentEl != NULL)
      return this->currentEl->curr;
    else
      return NULL;
  }
  else
  {
    this->currentEl = NULL;
    return NULL;
  }
}


#endif /* _LIST_H */