Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

List.H

Go to the documentation of this file.
00001 /* _______              __
00002   / ___/ /  ___  __ _  / /  ___
00003  / /__/ _ \/ _ \/  ' \/ _ \/ _ \
00004  \___/_//_/\___/_/_/_/_.__/\___/ 
00005 */
00006 //
00007 // This software is copyright (C) by the Lawrence Berkeley
00008 // National Laboratory.  Permission is granted to reproduce
00009 // this software for non-commercial purposes provided that
00010 // this notice is left intact.
00011 // 
00012 // It is acknowledged that the U.S. Government has rights to
00013 // this software under Contract DE-AC03-765F00098 between
00014 // the U.S.  Department of Energy and the University of
00015 // California.
00016 //
00017 // This software is provided as a professional and academic
00018 // contribution for joint exchange. Thus it is experimental,
00019 // is provided ``as is'', with no warranties of any kind
00020 // whatsoever, no support, no promise of updates, or printed
00021 // documentation. By using this software, you acknowledge
00022 // that the Lawrence Berkeley National Laboratory and
00023 // Regents of the University of California shall have no
00024 // liability with respect to the infringement of other
00025 // copyrights by any part of this software.
00026 //
00027 
00028 
00029 #ifndef _LIST_H_
00030 #define _LIST_H_
00031 
00032 #include "MayDay.H"
00033 
00034 
00035 template <class T> class ListLink;
00036 template <class T> class ListIterator;
00037 template <class T> class List;
00038 
00039 template <class T>
00040 class ListLink
00041 {
00042 private:
00043     friend class List<T>;
00044     friend class ListIterator<T>;
00045 
00046     ListLink (const T&     _val,
00047               ListLink<T>* _pre,
00048               ListLink<T>* _suc)
00049         : val(_val),
00050           pre(_pre),
00051           suc(_suc)
00052     {}
00053 
00054 private:
00055     T            val;
00056     ListLink<T>* pre;
00057     ListLink<T>* suc;
00058 };
00059 
00060 //
00061 //@Man:
00062 //@Memo: Iterate over a List
00063 /*@Doc:
00064 
00065   The class ListIterator<T> is an iterator over class List<T>.
00066   
00067   This class does NOT provide a default constructor or an assignment operator.
00068 */
00069 
00070 template <class T>
00071 class ListIterator
00072 {
00073 public:
00074     //
00075     //@ManDoc: Construct a ListIterator<T> to first element of aList.
00076     //
00077     inline ListIterator (const List<T>& aList);
00078     //
00079     //@ManDoc: The copy constructor.
00080     //
00081     inline ListIterator (const ListIterator<T>& rhs);
00082 
00083     /*@ManDoc: Reset this ListIterator<T> to point to the first element
00084                in the List<T>.
00085     */
00086     inline void rewind ();
00087 
00088     /*@ManDoc: Return a constant reference to the object in the List<T>
00089                currently pointed to by this ListIterator<T>.
00090     */
00091     inline const T& operator() () const;
00092 
00093     /*@ManDoc: Return a constant reference to the object in the List<T>
00094                currently pointed to by this ListIterator<T>.
00095     */
00096     inline const T& operator* () const;
00097 
00098     /*@ManDoc: This is a conversion operator that makes the iterator look
00099                like a pointer.  This operator makes it easy to check if the
00100                iterator is pointing to an element on the List<T>.  If the
00101                iterator has been moved off the List<T> or if the List<T> is
00102                empty, this conversion returns the NULL pointer.
00103     */
00104     inline operator bool () const;
00105 
00106     /*@ManDoc: Returns true if ListIterator<T> doesn't point to any
00107                element on the List<T>.
00108     */
00109     inline bool operator! () const;
00110 
00111     /*@ManDoc: Return a constant reference to the object in the List<T>
00112                currently pointed to by the iterator.
00113     */
00114     inline const T& value () const;
00115 
00116     /*@ManDoc: This is the prefix auto-increment operator.  It advances the
00117                ListIterator<T> to point to the next element on the List<T>.
00118                It then returns a reference to itself to allow for chaining
00119                with other operators.
00120     */
00121     inline ListIterator<T>& operator++ ();
00122 
00123     /*@ManDoc: This is the prefix auto-decrement operator.  It moves the
00124                ListIterator<T> to point to the previous element on the
00125                List<T>.  It then returns a reference to itself to allow for
00126                chaining with other operators.
00127     */
00128     inline ListIterator<T>& operator-- ();
00129 
00130     /*@ManDoc: This is the postfix auto-decrement operator.  It moves the
00131                ListIterator<T> to point to the previous element on the
00132                List<T>.  It then returns a ListIterator<T> that points to
00133                the old element to allow for chaining with other operators.
00134 
00135     */
00136     inline ListIterator<T> operator-- (int);
00137 
00138     /*@ManDoc: This is the postfix auto-increment operator.  It advances the
00139                ListIterator<T> to point to the next element on the List<T>.
00140                It then returns a ListIterator<T> that points to the old
00141                element to allow for chaining with other operators.
00142     */
00143     inline ListIterator<T> operator++ (int);
00144 
00145     /*@ManDoc: Do the two ListIterator<T>s point to the same List<T> and
00146                the same element within the List<T>?
00147     */
00148     inline bool operator== (const ListIterator<T>&) const;
00149     //
00150     //@ManDoc: Are the ListIterator<T>s not equal?
00151     //
00152     inline bool operator!= (const ListIterator<T>&) const;
00153 
00154 protected:
00155     //
00156     // Construct a ListIterator<T> to a List<T> and object in that List<T>.
00157     //
00158     inline ListIterator (const List<T>& _list,
00159                          ListLink<T>*   _p);
00160     //
00161     // A reference to the List<T> to which we point.
00162     //
00163     const List<T>& list;
00164     //
00165     // A pointer to the element in the List<T> to which we point.
00166     //
00167     ListLink<T>* p;
00168 
00169 private:
00170     friend class List<T>;
00171     //
00172     // These are disallowed.
00173     //
00174     ListIterator ();
00175     ListIterator<T>& operator= (const ListIterator<T>&);
00176 };
00177 
00178 //
00179 //@Man:
00180 //@Memo: A Doubly-Linked List
00181 /*@Doc:
00182 
00183   The List<T> class is a template class that implements a doubly-linked list
00184   of objects.  A List<T> is a useful container class when the number of
00185   objects in the collection is not known ahead of time.   A List<T> can
00186   contain an arbitrary number of elements; operations such as insertion,
00187   deletion, and catenation are easily implemented and inexpensive.
00188 
00189   The only difficulty when defining a list class is devising a mechanism to
00190   access the elements.  In an array, an element is accessed using an
00191   integer index.  Since the elements in a List<T> are ordered by position,
00192   we could define an integer indexing operation that walks along the
00193   List<T> links from the beginning until the numbered element is found.
00194   Unfortunately, this would be very inefficient when accessing elements near
00195   the  end of a long list.  Another solution is to allow user access to the
00196   individual link objects that contain the element as well as the forward and
00197   backward pointers.  This is not a satisfactory solution since it allows
00198   user access to the internal representation of the class.  The solution
00199   chosen is to define a ListIterator<T> template class.
00200   
00201   Think of a ListIterator<T> as a pointer to an object in the List<T>.  You
00202   can access the element currently pointed to by the iterator, move the
00203   iterator forward and backward through the List<T>, and use it as a
00204   mechanism to define where elements should be inserted and deleted.  If the
00205   iterator is moved off the end of the list it behaves as a null pointer.
00206 
00207   This is a concrete class, not a polymorphic one.
00208 */
00209 
00210 template <class T>
00211 class List
00212 {
00213 public:
00214     //
00215     //@ManDoc: Construct an empty List<T>.
00216     //
00217     inline List ();
00218     //
00219     //@ManDoc: The copy constructor.
00220     //
00221     List (const List<T>& rhs);
00222     //
00223     //@ManDoc: The assignment operator.
00224     //
00225     List<T>& operator= (const List<T>& rhs);
00226     //
00227     //@ManDoc: The destructor.
00228     //
00229     inline ~List();
00230     //
00231     //@ManDoc: Adds a copy of the value to the beginning of the List<T>.
00232     //
00233     inline void prepend (const T& value);
00234     //
00235     //@ManDoc: Adds a copy of the value to the end of the List<T>.
00236     //
00237     inline void append (const T& value);
00238     //
00239     //@ManDoc: Adds a copy of the value to the end of the List<T>.
00240     //
00241     void add (const T& value);
00242     //
00243     //@ManDoc: Appends a copy of all items in List<T> src to this List<T>.
00244     //
00245     void join (const List<T>& src);
00246 
00247     /*@ManDoc: Appends a copy of all items in List<T> src to this List<T>.
00248                This differs from join() in that it unlinks the objects from
00249                the List<T> src and glues them to the end of this List<T>,
00250                leaving List<T> src empty.  This is more efficient that
00251                join() if src is no longer needed.
00252     */
00253     void catenate (List<T>& src);
00254     //
00255     //@ManDoc: Removes all objects from the List<T>.
00256     //
00257     void clear ();
00258 
00259     /*@ManDoc: Returns a copy of this List<T> on the heap.  It is the user's
00260                responsibility to delete this when no longer needed.
00261     */
00262     inline List<T>* copy () const;
00263     //
00264     //@ManDoc: Returns a reference to the first element in the List<T>.
00265     //
00266     inline T& firstElement () const;
00267     //
00268     //@ManDoc: Returns a reference to the last element in the List<T>.
00269     //
00270     inline T& lastElement () const;
00271 
00272     /*@ManDoc: Returns true if the List<T> contains an object identical
00273                to value.  Type T must have an operator==() defined, or
00274                be an intrinsic type.
00275     */
00276     bool includes (const T& value) const;
00277 
00278     /*@ManDoc: Returns true if the this and rhs are memberwise equal;
00279                i.e. the two lists are the same size and each of the
00280                elements in the list compare equal. Type T must have an
00281                operator==() defined, or be an intrinsic type.
00282     */
00283     bool operator== (const List<T>& rhs) const;
00284     //
00285     //@ManDoc: Returns true if the this and rhs are not equal.
00286     //
00287     bool operator!= (const List<T>& rhs) const;
00288     //
00289     //@ManDoc: Returns true if the List<T> is empty.
00290     //
00291     inline bool isEmpty () const;
00292     //
00293     //@ManDoc: Returns true if the List<T> is not empty.
00294     //
00295     inline bool isNotEmpty () const;
00296     //
00297     //@ManDoc: Returns the number of objects in the List<T>.
00298     //
00299     int length () const;
00300     //
00301     //@ManDoc: Removes the first element in the List<T>.
00302     //
00303     inline void removeFirst ();
00304     //
00305     //@ManDoc: Removes the last element in the List<T>.
00306     //
00307     inline void removeLast ();
00308     //
00309     //@ManDoc: Returns reference to object pointed to by the ListIterator<T>.
00310     //
00311     inline const T& operator[] (const ListIterator<T>& li) const;
00312     //
00313     //@ManDoc: Returns reference to object pointed to by the ListIterator<T>.
00314     //
00315     inline T& operator[] (const ListIterator<T>& li);
00316     //
00317     //@ManDoc: Removes all objects in the List<T> equal to value.
00318     //
00319     void remove (const T& value);
00320 
00321     /*@ManDoc: Removes all objects in the List<T> equal to any of the
00322                values in lst.
00323     */
00324     void remove (const List<T>& lst);
00325     //
00326     //@ManDoc: Removes the object pointed to by the ListIterator<T>.
00327     //
00328     void remove (ListIterator<T>& lit);
00329     //
00330     //@ManDoc: Replace the value pointed to by the ListIterator<T> by val.
00331     //
00332     inline void replace (ListIterator<T>& li,
00333                          const T&         val);
00334 
00335     /*@ManDoc: Insert val into List<T> after the object pointed to by
00336                ListIterator<T>.
00337     */
00338     inline void addAfter (ListIterator<T>& lit,
00339                           const T&         val);
00340 
00341     /*@ManDoc: Insert val into List<T> before the object pointed to by
00342                ListIterator<T>.
00343     */
00344     inline void addBefore (ListIterator<T>& lit,
00345                            const T&         val);
00346     //
00347     //@ManDoc: Returns a ListIterator<T> to the first object in this List<T>.
00348     //
00349     inline ListIterator<T> first () const;
00350     //
00351     //@ManDoc: Returns a ListIterator<T> to the last object in this List<T>.
00352     //
00353     inline ListIterator<T> last () const;
00354 
00355 protected:
00356     //
00357     // A helper function for removing nodes.
00358     //
00359     void remove (ListLink<T> *ln);
00360     //
00361     // A helper function for adding nodes.
00362     //
00363     ListLink<T>* addBefore (ListLink<T>* ln,
00364                             const T&     val);
00365     //
00366     // A helper function for adding nodes.
00367     //
00368     ListLink<T>* addAfter (ListLink<T>* ln,
00369                            const T&     val);
00370     //
00371     // The head of the list.
00372     //
00373     ListLink<T>* head;
00374     //
00375     // The tail of the list.
00376     //
00377     ListLink<T>* tail;
00378     //
00379     // Our good and trusted friend.
00380     //
00381     friend class ListIterator<T>;
00382 };
00383 
00384 //
00385 // Inlines.
00386 //
00387 
00388 //
00389 // The ListIterator stuff.
00390 //
00391 
00392 template <class T>
00393 inline
00394 ListIterator<T>::ListIterator (const List<T>& _list,
00395                                ListLink<T>*   _p)
00396     : list(_list),
00397       p(_p)
00398 {}
00399 
00400 template <class T>
00401 inline
00402 ListIterator<T>::ListIterator (const List<T>& aList)
00403     : list(aList)
00404 {
00405     p = list.head;
00406 }
00407 
00408 template <class T>
00409 inline
00410 ListIterator<T>::ListIterator (const ListIterator<T>& li)
00411     : list(li.list),
00412       p(li.p)
00413 {}
00414 
00415 template <class T>
00416 inline
00417 void
00418 ListIterator<T>::rewind ()
00419 {
00420     p = list.head;
00421 }
00422 
00423 template <class T>
00424 inline
00425 const T&
00426 ListIterator<T>::operator() () const
00427 {
00428     assert(p != 0);
00429     return p->val;
00430 }
00431 
00432 template <class T>
00433 inline
00434 const T&
00435 ListIterator<T>::operator* () const
00436 {
00437     assert(p != 0);
00438     return p->val;
00439 }
00440 
00441 template <class T>
00442 inline
00443 ListIterator<T>::operator bool () const
00444 {
00445     return p != 0 ? true : false;
00446 }
00447 
00448 template <class T>
00449 inline
00450 bool
00451 ListIterator<T>::operator! () const
00452 {
00453     return p == 0 ? true : false;
00454 }
00455 
00456 template <class T>
00457 inline
00458 const T&
00459 ListIterator<T>::value () const
00460 {
00461     assert(p != 0);
00462     return p->val;
00463 }
00464 
00465 template <class T>
00466 inline
00467 ListIterator<T>&
00468 ListIterator<T>::operator++ ()
00469 {
00470     if (p)
00471         p = p->suc;
00472     return *this;
00473 }
00474 
00475 template <class T>
00476 inline
00477 ListIterator<T>&
00478 ListIterator<T>::operator-- ()
00479 {
00480     if (p)
00481         p = p->pre;
00482     return *this;
00483 }
00484 
00485 template <class T>
00486 inline
00487 ListIterator<T>
00488 ListIterator<T>::operator++ (int)
00489 {
00490     const ListIterator<T> li = *this;
00491     ++(*this);
00492     return li;
00493 }
00494 
00495 template <class T>
00496 inline
00497 ListIterator<T>
00498 ListIterator<T>::operator-- (int)
00499 {
00500     const ListIterator<T> li = *this;
00501     --(*this);
00502     return li;
00503 }
00504 
00505 template <class T>
00506 inline
00507 bool
00508 ListIterator<T>::operator== (const ListIterator<T>& _li) const
00509 {
00510     return (&list == &_li.list && p == _li.p) ? true : false;
00511 }
00512 
00513 template <class T>
00514 inline
00515 bool
00516 ListIterator<T>::operator!= (const ListIterator<T>& _li) const
00517 {
00518     return ! ListIterator<T>::operator==(_li);
00519 }
00520 
00521 //
00522 // List stuff.
00523 //
00524 
00525 template <class T>
00526 inline
00527 List<T>::List ()
00528     : head(0),
00529       tail(0)
00530 {}
00531 
00532 template <class T>
00533 inline
00534 List<T>::~List ()
00535 {
00536     clear();
00537 }
00538 
00539 template <class T>
00540 inline
00541 void
00542 List<T>::prepend (const T& value)
00543 {
00544     addBefore(head, value);
00545 }
00546 
00547 template <class T>
00548 inline
00549 void
00550 List<T>::append (const T& value)
00551 {
00552     addAfter(tail, value);
00553 }
00554 
00555 template <class T>
00556 inline
00557 List<T>*
00558 List<T>::copy () const
00559 {
00560     List<T>* newlist = new List<T>(*this);
00561     if (newlist == 0)
00562       MayDay::Error("Out of memory in List::copy ");
00563     return newlist;
00564 }
00565 
00566 template <class T>
00567 inline
00568 T&
00569 List<T>::firstElement () const
00570 {
00571     assert(head != 0);
00572     return head->val;
00573 }
00574 
00575 template <class T>
00576 inline
00577 T&
00578 List<T>::lastElement () const
00579 {
00580     assert(tail != 0);
00581     return tail->val;
00582 }
00583 
00584 template <class T>
00585 inline
00586 bool
00587 List<T>::isEmpty () const
00588 {
00589     return head == 0 && tail == 0;
00590 }
00591 
00592 template <class T>
00593 inline
00594 bool
00595 List<T>::isNotEmpty () const
00596 {
00597     return !isEmpty();
00598 }
00599 
00600 template <class T>
00601 inline
00602 void
00603 List<T>::removeFirst ()
00604 {
00605     remove(head);
00606 }
00607 
00608 template <class T>
00609 inline
00610 void
00611 List<T>::removeLast ()
00612 {
00613     remove(tail);
00614 }
00615 
00616 template <class T>
00617 inline
00618 const T&
00619 List<T>::operator[] (const ListIterator<T>& li) const
00620 {
00621     assert(li.p != 0);
00622     return li.p->val;
00623 }
00624 
00625 template <class T>
00626 inline
00627 T&
00628 List<T>::operator[] (const ListIterator<T>& li)
00629 {
00630     assert(li.p != 0);
00631     return li.p->val;
00632 }
00633 
00634 template <class T>
00635 inline
00636 void
00637 List<T>::replace (ListIterator<T>& li,
00638                   const T&         _val)
00639 {
00640     assert(li.p != 0);
00641     li.p->val = _val;
00642 }
00643 
00644 template <class T>
00645 inline
00646 void
00647 List<T>::addAfter (ListIterator<T>& lit,
00648                    const T&         val)
00649 {
00650     addAfter(lit.p, val);
00651 }
00652 
00653 template <class T>
00654 inline
00655 void
00656 List<T>::addBefore (ListIterator<T>& lit,
00657                     const T&         val)
00658 {
00659     addBefore(lit.p, val);
00660 }
00661 
00662 template <class T>
00663 inline
00664 ListIterator<T>
00665 List<T>::first () const
00666 {
00667     return ListIterator<T>(*this,head);
00668 }
00669 
00670 template <class T>
00671 inline
00672 ListIterator<T>
00673 List<T>::last () const
00674 {
00675     return ListIterator<T>(*this,tail);
00676 }
00677 
00678 #include "ListImplem.H"
00679 
00680 #endif /*_LIST_H_*/

Generated on Tue Jul 2 10:42:20 2002 for Chombo by doxygen1.2.16