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

/*!
 * @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 addAtIteratorPosition(T* entity, tIterator<T>* itereator);
    void remove(const T* entity);
    void removeFromLast(const T* entity);
    void removeLast();
    void flush();
    T* firstElement() const;
    T* lastElement() const;
    bool isEmpty() const;
    unsigned int getSize() const;
    bool inList(T* entity) const;
    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->currentEl = NULL;
  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 remain
 */
template<class T>
    inline tList<T>::~tList ()
{
  this->currentEl = this->first;
  listElement<T>* le;
  while(this->currentEl != NULL)
  {
    le = this->currentEl->next;
    delete this->currentEl;
    this->currentEl = le;
  }
  this->first = NULL;
  this->last = NULL;
  this->currentEl = 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->last = el; /* if first element */
  else el->next->prev = el;
  this->size++;
}

/**
 * add an entity at an iterators position
 * @param entity the entity to add
 * @param iterator the iterator get the Positional from
 *
 * this works best with an iterator walking with
 * firstElement() ; nextStep();
 * or
 * lastElement(); prevStep();
 */
template<class T>
    inline void tList<T>::addAtIteratorPosition(T* entity, tIterator<T>* iterator)
{
  // rule out unusable
  if (unlikely(entity == NULL))
    return;
  // on any error (or next == NULL) add using default add-function
  if (unlikely(iterator == NULL || iterator->getList() == NULL) ||
      iterator->tmpEl == NULL || iterator->tmpEl->next == NULL)
    return this->add(entity);
  // on prev == NULL add with addAtBeginning-function
  if (unlikely(iterator->tmpEl->prev == NULL))
    return addAtBeginning(entity);
  else
  {
    listElement<T>* el = new listElement<T>;
    el->next = iterator->tmpEl->next;
    el->curr = entity;
    el->prev = iterator->tmpEl->prev;

    el->next->prev = el;
    el->prev->next = el;
  }
}

/**
 * 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))
    {
      // erstes element?
      if( unlikely(this->currentEl->prev == NULL)) this->first = this->currentEl->next;
      else this->currentEl->prev->next = this->currentEl->next;

      // letztes element?
      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;
  }
}

/**
 * remove an entity from the list
 * @param entity: the entity to be removed
 *
 * this algorithm starts at the end of the List, working its way to the front
 * for finding the right entity.
 */
template<class T>
    inline void tList<T>::removeFromLast(const T* entity)
{
  this->currentEl = this->last;
  while( this->currentEl != NULL)
  {
    if( unlikely(this->currentEl->curr == entity))
    {
      // erstes element?
      if( unlikely(this->currentEl->prev == NULL)) this->first = this->currentEl->next;
      else this->currentEl->prev->next = this->currentEl->next;

      // letztes element?
      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->prev;
  }
}


/**
 * removes the Last Element of the List
 */
 template<class T>
     inline void tList<T>::removeLast()
{
  if( unlikely(this->last == NULL))
    return;

  // only one element in the list (and its not NULL :D )
  if( unlikely(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 delete all objects from the list, this can be very dangerous if there are ghost objects in the list.
 */
template<class T>
    inline void tList<T>::flush()
{
  this->currentEl = this->first;

  listElement<T>* le;
  while( this->currentEl != NULL)
  {
    le = this->currentEl->next;
    delete this->currentEl->curr;
    delete this->currentEl;
    this->currentEl = le;
  }
  this->first = NULL;
  this->last = NULL;
  this->currentEl = 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) const
{
  // pre checks
  if( unlikely(entity == NULL)) return false;

  // search in the List
  listElement<T>* el = this->first;
  while( this->currentEl != NULL)
  {
    if( this->currentEl->curr == entity)
      return true;

    el = this->currentEl->next;
  }
}


/**
 *  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
{
  friend class tList<T>;
  public:
    tIterator(const tList<T>* list);
    ~tIterator();

    T* firstElement();
    T* lastElement();
    T* nextElement();
    T* prevElement();
    T* seekElement(const T* element);
    T* iteratorElement(const tIterator<T>* iterator);
    bool compareListPointer(const tList<T>* list) const;
    inline const tList<T>* getList() const { return this->list; };
    /** another way to iterate through the list
     * !! THIS IS NOT MEANT FOR DELETION
     */
    T* prevStep();
    T* nextStep();
    T* getCurrent();

  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 ()
{
  this->currentEl = NULL;
  this->tmpEl = NULL;
  this->list = NULL;
}

/**
 * this returns the first element of the iterator list
 * @returns first element
 */
template<class T>
    inline T* tIterator<T>::firstElement ()
{
  this->tmpEl = this->list->first;
  if( likely(this->tmpEl != NULL))
  {
    this->currentEl = this->tmpEl->next;
    return this->tmpEl->curr;
  }
  else
    return NULL;
}

/**
 * this returns the last element of the iterator list
 * @returns last element
 */
template<class T>
    inline T* tIterator<T>::lastElement ()
{
  this->tmpEl = this->list->last;
  if( likely(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( unlikely(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( unlikely(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 (const T* element)
{
  if( unlikely(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( unlikely(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;
  }
}

template<class T>
    bool tIterator<T>::compareListPointer(const tList<T>* list) const
{
  return (this->list == list)?true:false;
}


/**
 *  use it to move through the list without interfering with the iteration
 * @returns previous list element
 *
 * this stepping mode will !not! step beyond the boundraries of the List!
 */
template<class T>
    inline T* tIterator<T>::nextStep ()
{
  if( unlikely(this->tmpEl == NULL || this->tmpEl->next == NULL))
    return NULL;
  else
  {
    this->tmpEl = this->tmpEl->next;
    return tmpEl->curr;
  }
}

/**
 *  use it to move backwards through the list without interfering with the itereation
 * @returns next list element
 *
 * this stepping mode will !not! step beyond the boundraries of the List!
 */
template<class T>
    inline T* tIterator<T>::prevStep ()
{
  if( unlikely(this->tmpEl == NULL || this->tmpEl->prev == NULL))
    return NULL;
  else
  {
    this->tmpEl = this->tmpEl->prev;
    return tmpEl->curr;
  }
}

/**
 * @returns the current Element
 */
template<class T>
    inline T* tIterator<T>::getCurrent()
{
  if (likely(this->tmpEl != NULL))
    return this->tmpEl->curr;
  else
    return NULL;
}

#endif /* _LIST_H */