Tools/List.h

Go to the documentation of this file.

/**
 * @file List.h
 * 
 * Declaration of template class List.
 * 
 * @author <A href=mailto:roefer@tzi.de>Thomas Röfer</A>
 */

#ifndef __LIST_H__
#define __LIST_H__

#ifdef _WIN32
#pragma warning(disable:4786) 
// The VC6 compiler produced the uncritical warning 4786 (too long debug identifier)
#endif

#include "Tools/Streams/InOut.h"

template <class T> class List;

template <class T> Out& operator<<(Out&,const List<T>&);
template <class T> In& operator>>(In&,List<T>&);

/**
 * The class implements double linked lists for arbitrary data types.
 */
template <class T> class List
{
  private:
    /**
     * A struct for list nodes.
     */
    struct Data
    {
      T* data; /**< A pointer to a list entry. */
      Data* next; /**< A pointer to the next list node. */
      Data* prev; /**< A pointer to the previous list node. */
    };

    Data* first; /**< A pointer to the first list node. */
    Data* last; /**< A pointer to the last list node. */
    int size; /**< The number of entries in the list. */

  public:
    /**
     * The local class implements a list iterator.
     */
    class Pos
    {
      private:
        Data* entry; /**< A pointer to the current list entry. */

      public:
        /**
         * Empty constructor.
         * The iterator points nowhere.
         */
        Pos() {entry = 0;}

        /**
         * Constructor.
         * The iterator points to the given list node.
         * @param p The list node.
         */
        Pos(Data* p) {entry = p;}

        /**
         * The pre-increment operator moves the iterator to the successor in the list.
         * If the iterator is moved behind the end of the list, it will point nowhere.
         * Note that the iterator must point to a list element before
         * this operation.
         * @return A reference to the new state of the iterator.
         */
        Pos& operator++() {entry = entry->next; return *this;}

        /**
         * The pre-decrement operator moves the iterator to the predecessor in the list.
         * If the iterator is moved before the beginning of the list, it will point nowhere.
         * Note that the iterator must point to a list element before
         * this operation.
         * @return A reference to the new state of the iterator.
         */
        Pos& operator--() {entry = entry->prev; return *this;}

        /**
         * The post-increment operator moves the iterator to the successor in the list.
         * If the iterator is moved behind the end of the list, it will point nowhere.
         * Note that the iterator must point to a list element before
         * this operation.
         * @return The state of the iterator before the operation.
         */
        Pos operator++(int) {Pos old(entry); entry = entry->next; return old;}

        /**
         * The post-decrement operator moves the iterator to the predecessor in the list.
         * If the iterator is moved before the beginning of the list, it will point nowhere.
         * Note that the iterator must point to a list element before
         * this operation.
         * @return The state of the iterator before the operation.
         */
        Pos operator--(int) {Pos old(entry); entry = entry->prev; return old;}

        /**
         * The operator returns whether the iterator points to a list entry.
         * If it does not point to a list entry, it points "nowhere".
         * @return Does it point to a list entry?
         */
        operator bool() const {return entry != 0;}

        /**
         * The operator determines whether two iterators point to the same list element.
         * @param pos The other iterator.
         * @return Are they equal?
         */
        bool operator==(const Pos& pos) const {return entry == pos.entry;}

        /**
         * The operator determines whether two iterators point to different list elements.
         * @param pos The other iterator.
         * @return Are they unequal?
         */
        bool operator!=(const Pos& pos) const {return entry != pos.entry;}

      friend class List<T>;
    };

    /**
     * The functions empties the list. 
     * All list elements are destructed.
     */
    void clear()
    {
      Pos p = getFirst();
      while(p)
        remove(p);
    }

    /**
     * Constructor of an empty list.
     */
    List() {first = 0; last = 0; size = 0;}

    /**
     * The operator copies another list into this list.
     * The previous entries in this list are destroyed.
     * @param l The other list.
     * @return A reference to this list after the operation took place.
     */
    List& operator=(const List& l)
    {
      clear();
      Pos p = l.getFirst();
      while(p)
      {
        insert(new T(l[p]));
        ++p;
      }
      return *this;
    }

    /**
     * Copy constuctor.
     * @param l The list from which this list will be copied.
     */
    List(const List& l) {first = 0; last = 0; size = 0; *this = l;}

    /**
     * Destructor.
     * All list elements are destructed.
     */
    ~List() {clear();}

    /**
     * The function returns an iterator pointing to the first element of the list.
     * @return The iterator.
     */
    Pos getFirst() const {return Pos(first);}

    /**
     * The function returns an iterator pointing to the last element of the list.
     * @return The iterator.
     */
    Pos getLast() const {return Pos(last);}

    /**
     * The operator implements read-only access to individual elements of the list.
     * @param p The iterator pointing to the element to be accessed.
     * @return A reference to the selected list element.
     */
    const T& operator[](Pos p) const {return *p.entry->data;}

    /**
     * The operator implements read/write access to individual elements of the list.
     * @param p The iterator pointing to the element to be accessed.
     * @return A reference to the selected list element.
     */
    T& operator[](Pos p) {return *p.entry->data;}

    /**
     * The operator concatenates another list to this list.
     * @param l The other list.
     * @return A reference to this list after the operation took place.
     */
    List<T>& operator+=(const List<T>& l)
    {
      for(List<T>::Pos pos = l.getFirst(); pos; ++pos)
        insert(l[pos]);
      return *this;
    }

    /**
     * The operator concatenates two lists.
     * @param l The other list.
     * @return The concatenation of this list and the other list.
     */
    List<T> operator+(const List<T>& l) const {List<T> temp(*this); return temp += l;}

    /**
     * The function returns the number of elements in the list.
     * @return The length of the list.
     */
    int getSize() const {return size;}

    /**
     * The function inserts a new element into the list.
     * @param t The new element. It will not be copied, and it will be destructed
     *          when it is removed from the list.
     * @param p An iterator pointing to the element after which the new one is
     *          inserted. If the operator points nowhere, the element will be
     *          appended to the list. This is also the default case.
     * @return An iterator pointing to the new list element.
     */
  /**
   * Wrong description, the new entry is not inserted AFTER, but BEFORE the iterator p
   */
    Pos insert(T* t,Pos p = Pos())
    {
      Data* data = new Data;
      data->data = t;
      if(p.entry)
      {
        data->prev = p.entry->prev;
        p.entry->prev = data;
        if(data->prev)
        {
          data->next = data->prev->next;
          data->prev->next = data;
        }
        else
        {
          data->next = first;
          first = data;
        }
      }
      else
      {
        data->prev = last;
        last = data;
        data->next = 0;
        if(data->prev)
          data->prev->next = data;
        else
          first = data;
      }
      ++size;
      return Pos(data);
    }

    /**
     * The function inserts a new element into the list.
     * @param t The new element. A copy will be inserted into the list. Therefore,
     *          the class of the element must provide a copy constuctor.
     * @param p An iterator pointing to the element after which the new one is
     *          inserted. If the operator points nowhere, the element will be
     *          appended to the list. This is also the default case.
     * @return An iterator pointing to the new list element.
     */
    Pos insert(const T& t,Pos p = Pos()) {T* t2 = new T(t); return insert(t2,p);}

    /**
     * The function inserts a new element into the list.
     * @param t The new element. It will not be copied, and it will be destructed
     *          when it is removed from the list.
     * @param p An iterator pointing to the element after which the new one is
     *          inserted. If the operator points nowhere, the element will be
     *          appended to the list. This is also the default case.
     * @return An iterator pointing to the new list element.
   *
   * UNTESTED
     */
    Pos insertAfter(T* t,Pos p = Pos())
    {
      Data* data = new Data;
      data->data = t;
      if(p.entry)
      {
      data->next = p.entry->next;
      data->prev = p.entry;

      if (p.entry->next)
      {
        p.entry->next->prev = data;
      }
      else
      {
        last = data;
      }

        p.entry->next = data;
    }
      else
      {
      //insert as first
      if (first)
        first->prev = data;
      data->next = first;
      first = data;
      data->prev = 0;
      }
      ++size;
      return Pos(data);
    }

    /**
     * The function inserts a new element into the list.
     * @param t The new element. A copy will be inserted into the list. Therefore,
     *          the class of the element must provide a copy constuctor.
     * @param p An iterator pointing to the element after which the new one is
     *          inserted. If the operator points nowhere, the element will be
     *          appended to the list. This is also the default case.
     * @return An iterator pointing to the new list element.
     */
    Pos insertAfter(const T& t,Pos p = Pos()) {T* t2 = new T(t); return insertAfter(t2,p);}

    /**
     * The function removes an element from the list.
     * The element will be destructed.
     * @param p An iterator pointing to the element that shall be removed.
     */
    void remove(Pos& p)
    {
      Data* data = p.entry;
      if(!data)
        return;
      if(data->prev)
        data->prev->next = data->next;
      else
        first = data->next;
      if(data->next)
        data->next->prev = data->prev;
      else
        last = data->prev;
      p.entry = data->next;
//without if (data->data): HEAP[RobotControl.exe]: HEAP: Free Heap block 9807e38 modified at 9807e64 after it was freed
      if (data->data)
        delete data->data;
      delete data;
      data = 0;                                                //oo7 : as suggested by *zensored* for stability reasons
      --size;
    }
};

/**
 * The operator writes a list into a stream.
 * @param stream The stream.
 * @param list The list that is written.
 * @return The stream.
 */
template <class T> Out& operator<<(Out& stream,const List<T>& list)
{
  stream << list.getSize();
  for(typename List<T>::Pos pos = list.getFirst(); pos; ++pos)
    stream << list[pos];
  return stream;
}

/**
 * The operator reads a list from a stream.
 * The original list elements are removed from the list.
 * @param stream The stream.
 * @param list The list that is read.
 * @return The stream.
 */
template <class T> In& operator>>(In& stream,List<T>& list)
{
  list.clear();
  int size;
  for(stream >> size; size; size--)
  {
    T* p = new T;
    stream >> *p;
    list.insert(p);
  }
  return stream;
}

#endif

---