Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

# Tools/List.h

Go to the documentation of this file.

    00001 /**
    00002  * @file List.h
    00003  *
    00004  * Declaration of template class List.
    00005  *
    00006  * @author <A href=mailto:roefer@tzi.de>Thomas Röfer</A>
    00007  */
    00008
    00009 #ifndef __LIST_H__
    00010 #define __LIST_H__
    00011
    00012 #ifdef _WIN32
    00013 #pragma warning(disable:4786)
    00014 // The VC6 compiler produced the uncritical warning 4786 (too long debug identifier)
    00015 #endif
    00016
    00017 #include "Tools/Streams/InOut.h"
    00018
    00019 template <class T> class List;
    00020
    00021 template <class T> Out& operator<<(Out&,const List<T>&);
    00022 template <class T> In& operator>>(In&,List<T>&);
    00023
    00024 /**
    00025  * The class implements double linked lists for arbitrary data types.
    00026  */
    00027 template <class T> class List
    00028 {
    00029   private:
    00030     /**
    00031      * A struct for list nodes.
    00032      */
    00033     struct Data
    00034     {
    00035       T* data; /**< A pointer to a list entry. */
    00036       Data* next; /**< A pointer to the next list node. */
    00037       Data* prev; /**< A pointer to the previous list node. */
    00038     };
    00039
    00040     Data* first; /**< A pointer to the first list node. */
    00041     Data* last; /**< A pointer to the last list node. */
    00042     int size; /**< The number of entries in the list. */
    00043
    00044   public:
    00045     /**
    00046      * The local class implements a list iterator.
    00047      */
    00048     class Pos
    00049     {
    00050       private:
    00051         Data* entry; /**< A pointer to the current list entry. */
    00052
    00053       public:
    00054         /**
    00055          * Empty constructor.
    00056          * The iterator points nowhere.
    00057          */
    00058         Pos() {entry = 0;}
    00059
    00060         /**
    00061          * Constructor.
    00062          * The iterator points to the given list node.
    00063          * @param p The list node.
    00064          */
    00065         Pos(Data* p) {entry = p;}
    00066
    00067         /**
    00068          * The pre-increment operator moves the iterator to the successor in the list.
    00069          * If the iterator is moved behind the end of the list, it will point nowhere.
    00070          * Note that the iterator must point to a list element before
    00071          * this operation.
    00072          * @return A reference to the new state of the iterator.
    00073          */
    00074         Pos& operator++() {entry = entry->next; return *this;}
    00075
    00076         /**
    00077          * The pre-decrement operator moves the iterator to the predecessor in the list.
    00078          * If the iterator is moved before the beginning of the list, it will point nowhere.
    00079          * Note that the iterator must point to a list element before
    00080          * this operation.
    00081          * @return A reference to the new state of the iterator.
    00082          */
    00083         Pos& operator--() {entry = entry->prev; return *this;}
    00084
    00085         /**
    00086          * The post-increment operator moves the iterator to the successor in the list.
    00087          * If the iterator is moved behind the end of the list, it will point nowhere.
    00088          * Note that the iterator must point to a list element before
    00089          * this operation.
    00090          * @return The state of the iterator before the operation.
    00091          */
    00092         Pos operator++(int) {Pos old(entry); entry = entry->next; return old;}
    00093
    00094         /**
    00095          * The post-decrement operator moves the iterator to the predecessor in the list.
    00096          * If the iterator is moved before the beginning of the list, it will point nowhere.
    00097          * Note that the iterator must point to a list element before
    00098          * this operation.
    00099          * @return The state of the iterator before the operation.
    00100          */
    00101         Pos operator--(int) {Pos old(entry); entry = entry->prev; return old;}
    00102
    00103         /**
    00104          * The operator returns whether the iterator points to a list entry.
    00105          * If it does not point to a list entry, it points "nowhere".
    00106          * @return Does it point to a list entry?
    00107          */
    00108         operator bool() const {return entry != 0;}
    00109
    00110         /**
    00111          * The operator determines whether two iterators point to the same list element.
    00112          * @param pos The other iterator.
    00113          * @return Are they equal?
    00114          */
    00115         bool operator==(const Pos& pos) const {return entry == pos.entry;}
    00116
    00117         /**
    00118          * The operator determines whether two iterators point to different list elements.
    00119          * @param pos The other iterator.
    00120          * @return Are they unequal?
    00121          */
    00122         bool operator!=(const Pos& pos) const {return entry != pos.entry;}
    00123
    00124       friend class List<T>;
    00125     };
    00126
    00127     /**
    00128      * The functions empties the list.
    00129      * All list elements are destructed.
    00130      */
    00131     void clear()
    00132     {
    00133       Pos p = getFirst();
    00134       while(p)
    00135         remove(p);
    00136     }
    00137
    00138     /**
    00139      * Constructor of an empty list.
    00140      */
    00141     List() {first = 0; last = 0; size = 0;}
    00142
    00143     /**
    00144      * The operator copies another list into this list.
    00145      * The previous entries in this list are destroyed.
    00146      * @param l The other list.
    00147      * @return A reference to this list after the operation took place.
    00148      */
    00149     List& operator=(const List& l)
    00150     {
    00151       clear();
    00152       Pos p = l.getFirst();
    00153       while(p)
    00154       {
    00155         insert(new T(l[p]));
    00156         ++p;
    00157       }
    00158       return *this;
    00159     }
    00160
    00161     /**
    00162      * Copy constuctor.
    00163      * @param l The list from which this list will be copied.
    00164      */
    00165     List(const List& l) {first = 0; last = 0; size = 0; *this = l;}
    00166
    00167     /**
    00168      * Destructor.
    00169      * All list elements are destructed.
    00170      */
    00171     ~List() {clear();}
    00172
    00173     /**
    00174      * The function returns an iterator pointing to the first element of the list.
    00175      * @return The iterator.
    00176      */
    00177     Pos getFirst() const {return Pos(first);}
    00178
    00179     /**
    00180      * The function returns an iterator pointing to the last element of the list.
    00181      * @return The iterator.
    00182      */
    00183     Pos getLast() const {return Pos(last);}
    00184
    00185     /**
    00186      * The operator implements read-only access to individual elements of the list.
    00187      * @param p The iterator pointing to the element to be accessed.
    00188      * @return A reference to the selected list element.
    00189      */
    00190     const T& operator[](Pos p) const {return *p.entry->data;}
    00191
    00192     /**
    00193      * The operator implements read/write access to individual elements of the list.
    00194      * @param p The iterator pointing to the element to be accessed.
    00195      * @return A reference to the selected list element.
    00196      */
    00197     T& operator[](Pos p) {return *p.entry->data;}
    00198
    00199     /**
    00200      * The operator concatenates another list to this list.
    00201      * @param l The other list.
    00202      * @return A reference to this list after the operation took place.
    00203      */
    00204     List<T>& operator+=(const List<T>& l)
    00205     {
    00206       for(List<T>::Pos pos = l.getFirst(); pos; ++pos)
    00207         insert(l[pos]);
    00208       return *this;
    00209     }
    00210
    00211     /**
    00212      * The operator concatenates two lists.
    00213      * @param l The other list.
    00214      * @return The concatenation of this list and the other list.
    00215      */
    00216     List<T> operator+(const List<T>& l) const {List<T> temp(*this); return temp += l;}
    00217
    00218     /**
    00219      * The function returns the number of elements in the list.
    00220      * @return The length of the list.
    00221      */
    00222     int getSize() const {return size;}
    00223
    00224     /**
    00225      * The function inserts a new element into the list.
    00226      * @param t The new element. It will not be copied, and it will be destructed
    00227      *          when it is removed from the list.
    00228      * @param p An iterator pointing to the element after which the new one is
    00229      *          inserted. If the operator points nowhere, the element will be
    00230      *          appended to the list. This is also the default case.
    00231      * @return An iterator pointing to the new list element.
    00232      */
    00233   /**
    00234    * Wrong description, the new entry is not inserted AFTER, but BEFORE the iterator p
    00235    */
    00236     Pos insert(T* t,Pos p = Pos())
    00237     {
    00238       Data* data = new Data;
    00239       data->data = t;
    00240       if(p.entry)
    00241       {
    00242         data->prev = p.entry->prev;
    00243         p.entry->prev = data;
    00244         if(data->prev)
    00245         {
    00246           data->next = data->prev->next;
    00247           data->prev->next = data;
    00248         }
    00249         else
    00250         {
    00251           data->next = first;
    00252           first = data;
    00253         }
    00254       }
    00255       else
    00256       {
    00257         data->prev = last;
    00258         last = data;
    00259         data->next = 0;
    00260         if(data->prev)
    00261           data->prev->next = data;
    00262         else
    00263           first = data;
    00264       }
    00265       ++size;
    00266       return Pos(data);
    00267     }
    00268
    00269     /**
    00270      * The function inserts a new element into the list.
    00271      * @param t The new element. A copy will be inserted into the list. Therefore,
    00272      *          the class of the element must provide a copy constuctor.
    00273      * @param p An iterator pointing to the element after which the new one is
    00274      *          inserted. If the operator points nowhere, the element will be
    00275      *          appended to the list. This is also the default case.
    00276      * @return An iterator pointing to the new list element.
    00277      */
    00278     Pos insert(const T& t,Pos p = Pos()) {T* t2 = new T(t); return insert(t2,p);}
    00279
    00280     /**
    00281      * The function inserts a new element into the list.
    00282      * @param t The new element. It will not be copied, and it will be destructed
    00283      *          when it is removed from the list.
    00284      * @param p An iterator pointing to the element after which the new one is
    00285      *          inserted. If the operator points nowhere, the element will be
    00286      *          appended to the list. This is also the default case.
    00287      * @return An iterator pointing to the new list element.
    00288    *
    00289    * UNTESTED
    00290      */
    00291     Pos insertAfter(T* t,Pos p = Pos())
    00292     {
    00293       Data* data = new Data;
    00294       data->data = t;
    00295       if(p.entry)
    00296       {
    00297       data->next = p.entry->next;
    00298       data->prev = p.entry;
    00299
    00300       if (p.entry->next)
    00301       {
    00302         p.entry->next->prev = data;
    00303       }
    00304       else
    00305       {
    00306         last = data;
    00307       }
    00308
    00309         p.entry->next = data;
    00310     }
    00311       else
    00312       {
    00313       //insert as first
    00314       if (first)
    00315         first->prev = data;
    00316       data->next = first;
    00317       first = data;
    00318       data->prev = 0;
    00319       }
    00320       ++size;
    00321       return Pos(data);
    00322     }
    00323
    00324     /**
    00325      * The function inserts a new element into the list.
    00326      * @param t The new element. A copy will be inserted into the list. Therefore,
    00327      *          the class of the element must provide a copy constuctor.
    00328      * @param p An iterator pointing to the element after which the new one is
    00329      *          inserted. If the operator points nowhere, the element will be
    00330      *          appended to the list. This is also the default case.
    00331      * @return An iterator pointing to the new list element.
    00332      */
    00333     Pos insertAfter(const T& t,Pos p = Pos()) {T* t2 = new T(t); return insertAfter(t2,p);}
    00334
    00335     /**
    00336      * The function removes an element from the list.
    00337      * The element will be destructed.
    00338      * @param p An iterator pointing to the element that shall be removed.
    00339      */
    00340     void remove(Pos& p)
    00341     {
    00342       Data* data = p.entry;
    00343       if(!data)
    00344         return;
    00345       if(data->prev)
    00346         data->prev->next = data->next;
    00347       else
    00348         first = data->next;
    00349       if(data->next)
    00350         data->next->prev = data->prev;
    00351       else
    00352         last = data->prev;
    00353       p.entry = data->next;
    00354 //without if (data->data): HEAP[RobotControl.exe]: HEAP: Free Heap block 9807e38 modified at 9807e64 after it was freed
    00355       if (data->data)
    00356         delete data->data;
    00357       delete data;
    00358       data = 0;                                                //oo7 : as suggested by *zensored* for stability reasons
    00359       --size;
    00360     }
    00361 };
    00362
    00363 /**
    00364  * The operator writes a list into a stream.
    00365  * @param stream The stream.
    00366  * @param list The list that is written.
    00367  * @return The stream.
    00368  */
    00369 template <class T> Out& operator<<(Out& stream,const List<T>& list)
    00370 {
    00371   stream << list.getSize();
    00372   for(typename List<T>::Pos pos = list.getFirst(); pos; ++pos)
    00373     stream << list[pos];
    00374   return stream;
    00375 }
    00376
    00377 /**
    00378  * The operator reads a list from a stream.
    00379  * The original list elements are removed from the list.
    00380  * @param stream The stream.
    00381  * @param list The list that is read.
    00382  * @return The stream.
    00383  */
    00384 template <class T> In& operator>>(In& stream,List<T>& list)
    00385 {
    00386   list.clear();
    00387   int size;
    00388   for(stream >> size; size; size--)
    00389   {
    00390     T* p = new T;
    00391     stream >> *p;
    00392     list.insert(p);
    00393   }
    00394   return stream;
    00395 }
    00396
    00397 #endif