casa  $Rev:20696$
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Link.h
Go to the documentation of this file.
00001 //# Link.h: Doubly linked list primitive
00002 //# Copyright (C) 1993,1994,1995,1999,2000,2001
00003 //# Associated Universities, Inc. Washington DC, USA.
00004 //#
00005 //# This library is free software; you can redistribute it and/or modify it
00006 //# under the terms of the GNU Library General Public License as published by
00007 //# the Free Software Foundation; either version 2 of the License, or (at your
00008 //# option) any later version.
00009 //#
00010 //# This library is distributed in the hope that it will be useful, but WITHOUT
00011 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00012 //# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
00013 //# License for more details.
00014 //#
00015 //# You should have received a copy of the GNU Library General Public License
00016 //# along with this library; if not, write to the Free Software Foundation,
00017 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
00018 //#
00019 //# Correspondence concerning AIPS++ should be addressed as follows:
00020 //#        Internet email: aips2-request@nrao.edu.
00021 //#        Postal address: AIPS++ Project Office
00022 //#                        National Radio Astronomy Observatory
00023 //#                        520 Edgemont Road
00024 //#                        Charlottesville, VA 22903-2475 USA
00025 //#
00026 //# $Id: Link.h 20551 2009-03-25 00:11:33Z Malte.Marquarding $
00027 
00028 #ifndef CASA_LINK_H
00029 #define CASA_LINK_H
00030 
00031 #include <casa/aips.h>
00032 
00033 namespace casa { //# NAMESPACE CASA - BEGIN
00034 
00035 // <summary>doubly linked list primitive</summary>
00036 // <use visibility=export>
00037 //
00038 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
00039 // </reviewed>
00040 //
00041 // <etymology>
00042 //    This class provides the primitives for creating a class of linked
00043 //    data structures. Thus it is called <src>Link</src>.
00044 // </etymology>
00045 //
00046 // <synopsis>
00047 //  This class provides a minimal doubly linked list implementation. All of
00048 //  the work is performed by the constructor. This class does not keep
00049 //  track of the head of the list; this is left to the user of the class.
00050 //  This class can be thought of as the "nodes" of a linked list, but
00051 //  conceptually each of the nodes is a list itself. This class will
00052 //  typically not be used by the average user because although it is
00053 //  a functional doubly linked list implementation, <src>List<t></src>
00054 //  provides a higher level of abstraction.
00055 // </synopsis>
00056 //
00057 // <example>
00058 //     This example makes <src>Link</src> behave like a stack:
00059 //     <srcblock>
00060 // #include <iostream>
00061 //     #include <casa/Containers/Link.h>
00062 //
00063 //     main() {
00064 //         Link<int> *hed = new Link<int>(23);
00065 //
00066 //         hed = new Link<int>(12,0,hed);
00067 //         hed = new Link<int>(19,0,hed);
00068 //         hed = new Link<int>(10,0,hed);
00069 //
00070 //         while (hed) {
00071 //             Link<int> *cur = hed;
00072 //             hed = hed->unlink();
00073 //             cout << cur->val() << " ";
00074 //             delete cur;
00075 //         }
00076 //         cout << endl;
00077 //     }
00078 //     </srcblock>
00079 //     The output from the previous example would be:
00080 //     <pre>
00081 //           10 19 12 23
00082 //     </pre>
00083 //     As each new link is being created, the new element goes at the
00084 //     beginning of the list because the previous head of the list,
00085 //     <src>hed</src>, is being passed in as the <em>next</em> list
00086 //     element.
00087 //
00088 //     This next example demonstrates how a queue could be created
00089 //     instead of a stack:
00090 //     <srcblock>
00091 // #include <iostream>
00092 //     #include <casa/Containers/Link.h>
00093 //
00094 //     main() {
00095 //         Link<int> *hed = new Link<int>(23);
00096 //         Link<int> *cur = hed;
00097 //
00098 //         cur = new Link<int>(12,cur);
00099 //         cur = new Link<int>(19,cur);
00100 //         cur = new Link<int>(10,cur);
00101 //
00102 //         while (hed) {
00103 //             cur = hed;
00104 //             hed = hed->unlink();
00105 //             cout << cur->val() << " ";
00106 //             delete cur;
00107 //         }
00108 //         cout << endl;
00109 //     }
00110 //     </srcblock>
00111 //     The output here would be:
00112 //     <pre>
00113 //           23 12 19 10
00114 //     </pre>
00115 // </example>
00116 template<class t> class Link {
00117 protected:
00118     t store;
00119     Link<t> *Next;
00120     Link<t> *Prev;
00121 public:
00122     //  The <src>val()</src> member function will return a reference to the
00123     //  contents of the current node.
00124     // <group>
00125     t &val() {return store;}
00126     const t &val() const {return store;}
00127     // </group>
00128   
00129     //  These member functions allow traversal of the list. the <src>next()</src>
00130     //  functions retrieve the next element in the list, and <src>prev()</src>
00131     //  retrieves the previous element.
00132     //
00133     //  <note role=tip> The <em>non-const</em> versions of these functions
00134     //      return a reference to the pointer to the next element in the list.
00135     //      This allows for modification of the list if necessary, e.g. for
00136     //      removal of elements.
00137     //  </note>
00138     // <group>
00139     Link<t> *&next() {return Next;}
00140     const Link<t> *next() const {return Next;}
00141     Link<t> *&prev() {return Prev;}
00142     const Link<t> *prev() const {return Prev;}
00143     // </group>
00144 
00145     //
00146     // This is where the maintenance of the list happens. The parameters are:
00147     // <ul>
00148     //    <li> <b>e</b> -- the element to be added
00149     //    <li> <b>p</b> -- the previous element of the list
00150     //    <li> <b>n</b> -- the next element of the list
00151     // </ul>
00152     // If the previous element is non-null it is used to get all of the 
00153     // information necessary to add this new element to the list. If 
00154     // the previous element is null and the next element is non-null
00155     // it is assumed that the new element is being added to the 
00156     // beginning of the list, i.e. before the next element but with
00157     // no previous element.
00158     //
00159     Link(t e,Link<t> *p=0,Link<t> *n=0) : store(e), Prev(p) {
00160         if (Prev) {
00161             Next = (*Prev).Next;
00162             (*Prev).Next = this;
00163             if (Next) (*Next).Prev = this;
00164         } else {
00165             Next = n;
00166             if (Next) {
00167                 //
00168                 // Clean up previous list if inserting in the middle
00169                 // of a list with "p==0".
00170                 //
00171                 if ((*Next).Prev) (*(*Next).Prev).Next = 0;
00172                 (*Next).Prev = this;
00173             }
00174         }
00175     }
00176 
00177     //
00178     // This destructor destroys the rest of the list, i.e. this object and all
00179     // that follow.
00180     // <note role=warning> If the destructor is called for a <src>Link<t></src> in
00181     //        the middle of a list the elements which occur before the object will
00182     //        be left dangling, and the objects which follow the deleted object
00183     //        will also be deleted.
00184     // </note>
00185     ~Link();
00186 
00187     //
00188     // This function unlinks a given element of the list. It requires
00189     // no parameters because the node has links to the previous and 
00190     // next elements in the list. This is useful when removing a 
00191     // single element from the list because the destructor, 
00192     // <src>Link::~Link</src>, will delete the rest of the list elements
00193     // if they are linked in with <src>this</src>. This function returns
00194     // the next element in the list.
00195     // <note role=tip> The <src>Link<t>*</src> parameter is unused. It is a
00196     //    historical artifact which <b>will</b> be removed.
00197     // </note>
00198     Link<t> *unlink(Link<t> * = 0);
00199 
00200 };
00201 
00202 typedef Link<int> Link_int;
00203 
00204 
00205 } //# NAMESPACE CASA - END
00206 
00207 #ifndef CASACORE_NO_AUTO_TEMPLATES
00208 #include <casa/Containers/Link.tcc>
00209 #endif //# CASACORE_NO_AUTO_TEMPLATES
00210 #endif