filters

list.h

00001 /* This file is part of the LibMSWrite Library
00002    Copyright (C) 2001-2003 Clarence Dang <clarencedang@users.sourceforge.net>
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License Version 2 as published by the Free Software Foundation.
00007 
00008    This library is distributed in the hope that it will be useful,
00009    but WITHOUT ANY WARRANTY; without even the implied warranty of
00010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00011    Library General Public License Version 2 for more details.
00012 
00013    You should have received a copy of the GNU Library General Public License
00014    Version 2 along with this library; see the file COPYING.LIB.  If not,
00015    write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00016  * Boston, MA 02110-1301, USA.
00017 
00018    LibMSWrite Project Website:
00019    http://sourceforge.net/projects/libmswrite/
00020 */
00021 
00022 /* 
00023  * list.h - linked list implementation
00024  * This file ensures that we do not have to depend on STL but don't waste
00025  * time and memory trying to reallocate arrays.
00026  *
00027  * An implementation without C++-style iterators would have taken half
00028  * as many lines and would probably be twice as efficient...
00029  *
00030  */
00031 
00032 #ifndef __MSWRITE_LIST_H__
00033 #define __MSWRITE_LIST_H__
00034 
00035 #ifndef NULL
00036     #define NULL 0
00037 #endif
00038 
00039 #include <assert.h>
00040 // TODO: _desperately_ need to implement ConstIterator so that all the List<dtype>::end (void) const's can have the const etc.
00041 namespace MSWrite
00042 {
00043     template <class dtype>  class List;
00044     template <class dtype>  class ListIterator;
00045     template <class dtype>
00046     class ListElement
00047     {
00048     private:
00049         dtype m_data;
00050         ListElement *m_prev, *m_next;
00051 
00052     public:
00053         ListElement ()
00054         {
00055             m_prev = m_next = NULL;
00056         }
00057 
00058         ListElement (dtype &data)
00059         {
00060             m_prev = m_next = NULL;
00061             m_data = data;
00062         }
00063 
00064         ~ListElement ()
00065         {
00066         }
00067 
00068         dtype &getData (void) const
00069         {
00070             return m_data;
00071         }
00072         dtype &operator* (void) const
00073         {
00074             return m_data;
00075         }
00076         bool operator== (const dtype &rhs)
00077         {
00078             return this->data == rhs.data;
00079         }
00080 
00081         void setData (const dtype &data)
00082         {
00083             m_data = data;
00084         }
00085         dtype &operator= (const dtype &rhs)
00086         {
00087             if (this == &rhs)
00088                 return *this;
00089 
00090             this->data = rhs.data;
00091             return this->data;
00092         }
00093 
00094         friend class List <dtype>;
00095         friend class ListIterator <dtype>;
00096     };
00097 
00098     template <class dtype>  class List;
00099     template <class dtype>
00100     class ListIterator
00101     {
00102     private:
00103         bool m_forward;
00104         ListElement <dtype> *m_upto;
00105 
00106         void setPtr (ListElement <dtype> *ptr)
00107         {
00108             m_upto = ptr;
00109         }
00110 
00111     public:
00112         ListIterator (const bool forward = true)
00113         {
00114             m_forward = forward;
00115         }
00116 
00117         ListIterator <dtype> &prev (void)
00118         {
00119             if (m_forward)
00120                 m_upto = m_upto->m_prev;
00121             else
00122                 m_upto = m_upto->m_next;
00123 
00124             return *this;
00125         }
00126 
00127         ~ListIterator ()
00128         {
00129         }
00130         
00131         ListIterator <dtype> &operator-- (void)
00132         {
00133             return prev ();
00134         }
00135 
00136         ListIterator <dtype> &operator-- (int)
00137         {
00138             return prev ();
00139         }
00140 
00141         ListIterator <dtype> &next (void)
00142         {
00143             if (m_forward)
00144                 m_upto = m_upto->m_next;
00145             else
00146                 m_upto = m_upto->m_prev;
00147 
00148             return *this;
00149         }
00150 
00151         ListIterator <dtype> &operator++ (void)
00152         {
00153             return next ();
00154         }
00155 
00156         ListIterator <dtype> &operator++ (int)
00157         {
00158             return next ();
00159         }
00160 
00161         bool operator== (const ListIterator <dtype> &rhs)
00162         {
00163             return this->m_upto == rhs.m_upto;
00164         }
00165 
00166         bool operator!= (const ListIterator <dtype> &rhs)
00167         {
00168             return this->m_upto != rhs.m_upto;
00169         }
00170 
00171         dtype &operator* (void)
00172         {
00173             //return *(*m_upto);    // why doesn't this work?
00174             return m_upto->m_data;
00175         }
00176 
00177         friend class List <dtype>;
00178     };
00179 
00180     template <class dtype>
00181     class List
00182     {
00183     private:
00184         ListElement <dtype> *m_head, *m_tail;
00185         int m_num;
00186         bool m_good;
00187 
00188     public:
00189         List ()
00190         {
00191             m_head = m_tail = (ListElement <dtype> *) NULL;
00192             m_num = 0;
00193             m_good = true;
00194         }
00195 
00196         virtual ~List ()
00197         {
00198             killself ();
00199         }
00200 
00201         void killself (void)
00202         {
00203             ListElement <dtype> *e = m_head;
00204             ListElement <dtype> *nexte;
00205             while (e)
00206             {
00207                 nexte = e->m_next;
00208                 delete e;
00209                 e = nexte;
00210             }
00211             m_head = m_tail = NULL;
00212             m_num = 0;
00213             m_good = true;
00214         }
00215 
00216         bool empty (void) const
00217         {
00218             return m_head;
00219         }
00220 
00221         bool good (void) const
00222         {
00223             return m_good;
00224         }
00225 
00226         bool bad (void) const
00227         {
00228             return !good ();
00229         }
00230 
00231         bool addToFront (dtype &data)
00232         {
00233             ListElement <dtype> *e = new ListElement <dtype> (data);
00234             if (!e)
00235             {
00236                 m_good = false;
00237                 return false;
00238             }
00239 
00240             if (m_head)
00241             {
00242                 e->next = m_head;
00243                 m_head->prev = e;
00244                 m_head = e;
00245             }
00246             // empty
00247             else
00248             {
00249                 m_head = m_tail = e;
00250             }
00251 
00252             m_num++;
00253             return true;
00254         }
00255 
00256         bool addToBack (void)
00257         {
00258             ListElement <dtype> *e = new ListElement <dtype> ();
00259             if (!e)
00260             {
00261                 m_good = false;
00262                 return false;
00263             }
00264 
00265             if (m_tail)
00266             {
00267                 e->m_prev = m_tail;
00268                 m_tail->m_next = e;
00269                 m_tail = e;
00270             }
00271             // empty
00272             else
00273             {
00274                 m_head = m_tail = e;
00275             }
00276 
00277             m_num++;
00278             return true;
00279         }
00280 
00281         // for efficiency, you can call the above void argument list version
00282         // and initialise the data within the list yourself (avoiding a copy)
00283         bool addToBack (const dtype &data)
00284         {
00285             if (!addToBack ())
00286                 return false;
00287             m_tail->setData (data);
00288             return true;
00289         }
00290 
00291         int getNumElements (void) const
00292         {
00293             return m_num;
00294         }
00295 
00296         List <dtype> &operator= (const List <dtype> &rhs)
00297         {
00298             if (this == &rhs)
00299                 return *this;
00300 
00301             killself ();
00302 
00303             m_num = rhs.m_num;
00304             m_good = rhs.m_good;
00305 
00306             ListElement <dtype> *e = rhs.m_head;
00307             while (e)
00308             {
00309                 if (!addToBack (e->m_data)) break;
00310                 e = e->m_next;
00311             }
00312 
00313             return *this;
00314         }
00315 
00316         typedef ListIterator <dtype> Iterator;
00317         friend class ListIterator <dtype>;
00318 
00319         ListIterator <dtype> begin (const bool forward = true) const
00320         {
00321             ListIterator <dtype> ret (forward);
00322             if (forward)
00323                 ret.setPtr (m_head);
00324             else
00325                 ret.setPtr (m_tail);
00326             return ret; // not a reference
00327         }
00328 
00329         ListIterator <dtype> end (void) const
00330         {
00331             ListIterator <dtype> ret;
00332             ret.setPtr (NULL);  // true regardless of which direction
00333             return ret; // not a reference
00334         }
00335 
00336         ListIterator <dtype> erase (ListIterator <dtype> &it)
00337         {
00338             // regardless of iterator direction
00339             ListElement <dtype> *eat = it.m_upto;
00340             ListElement <dtype> *prevElement = it.m_upto->m_prev;
00341             ListElement <dtype> *nextElement = it.m_upto->m_next;
00342             it++;
00343             delete (eat);
00344 
00345             if (prevElement)
00346                 prevElement->m_next = nextElement;
00347             else
00348                 m_head = nextElement;
00349 
00350             if (nextElement)
00351                 nextElement->m_prev = prevElement;
00352             else
00353                 m_tail = prevElement;
00354 
00355             m_num--;
00356             return it;
00357         }
00358         
00359         ListIterator <dtype> search (const dtype &value) const
00360         {
00361             ListIterator <dtype> it;
00362             for (it = begin (); it != end (); it++)
00363             {
00364                 if ((*it) == value)
00365                     break;
00366             }
00367 
00368             // not reference
00369             return it;
00370         }
00371     };
00372 }   // namespace MSWrite    {
00373 
00374 #endif  // #ifndef __MSWRITE_LIST_H__
00375 
00376 // end of list.h
KDE Home | KDE Accessibility Home | Description of Access Keys