casa  5.7.0-16
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Link.h
Go to the documentation of this file.
1 //# Link.h: Doubly linked list primitive
2 //# Copyright (C) 1993,1994,1995,1999,2000,2001
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 //#
26 //# $Id$
27 
28 #ifndef CASA_LINK_H
29 #define CASA_LINK_H
30 
31 #include <casacore/casa/aips.h>
32 
33 namespace casacore { //# NAMESPACE CASACORE - BEGIN
34 
35 // <summary>doubly linked list primitive</summary>
36 // <use visibility=export>
37 //
38 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
39 // </reviewed>
40 //
41 // <etymology>
42 // This class provides the primitives for creating a class of linked
43 // data structures. Thus it is called <src>Link</src>.
44 // </etymology>
45 //
46 // <synopsis>
47 // This class provides a minimal doubly linked list implementation. All of
48 // the work is performed by the constructor. This class does not keep
49 // track of the head of the list; this is left to the user of the class.
50 // This class can be thought of as the "nodes" of a linked list, but
51 // conceptually each of the nodes is a list itself. This class will
52 // typically not be used by the average user because although it is
53 // a functional doubly linked list implementation, <src>List<t></src>
54 // provides a higher level of abstraction.
55 // </synopsis>
56 //
57 // <example>
58 // This example makes <src>Link</src> behave like a stack:
59 // <srcblock>
60 // #include <iostream>
61 // #include <casacore/casa/Containers/Link.h>
62 //
63 // main() {
64 // Link<int> *hed = new Link<int>(23);
65 //
66 // hed = new Link<int>(12,0,hed);
67 // hed = new Link<int>(19,0,hed);
68 // hed = new Link<int>(10,0,hed);
69 //
70 // while (hed) {
71 // Link<int> *cur = hed;
72 // hed = hed->unlink();
73 // cout << cur->val() << " ";
74 // delete cur;
75 // }
76 // cout << endl;
77 // }
78 // </srcblock>
79 // The output from the previous example would be:
80 // <pre>
81 // 10 19 12 23
82 // </pre>
83 // As each new link is being created, the new element goes at the
84 // beginning of the list because the previous head of the list,
85 // <src>hed</src>, is being passed in as the <em>next</em> list
86 // element.
87 //
88 // This next example demonstrates how a queue could be created
89 // instead of a stack:
90 // <srcblock>
91 // #include <iostream>
92 // #include <casacore/casa/Containers/Link.h>
93 //
94 // main() {
95 // Link<int> *hed = new Link<int>(23);
96 // Link<int> *cur = hed;
97 //
98 // cur = new Link<int>(12,cur);
99 // cur = new Link<int>(19,cur);
100 // cur = new Link<int>(10,cur);
101 //
102 // while (hed) {
103 // cur = hed;
104 // hed = hed->unlink();
105 // cout << cur->val() << " ";
106 // delete cur;
107 // }
108 // cout << endl;
109 // }
110 // </srcblock>
111 // The output here would be:
112 // <pre>
113 // 23 12 19 10
114 // </pre>
115 // </example>
116 template<class t> class Link {
117 protected:
118  t store;
121 public:
122  // The <src>val()</src> member function will return a reference to the
123  // contents of the current node.
124  // <group>
125  t &val() {return store;}
126  const t &val() const {return store;}
127  // </group>
128 
129  // These member functions allow traversal of the list. the <src>next()</src>
130  // functions retrieve the next element in the list, and <src>prev()</src>
131  // retrieves the previous element.
132  //
133  // <note role=tip> The <em>non-const</em> versions of these functions
134  // return a reference to the pointer to the next element in the list.
135  // This allows for modification of the list if necessary, e.g. for
136  // removal of elements.
137  // </note>
138  // <group>
139  Link<t> *&next() {return Next;}
140  const Link<t> *next() const {return Next;}
141  Link<t> *&prev() {return Prev;}
142  const Link<t> *prev() const {return Prev;}
143  // </group>
144 
145  //
146  // This is where the maintenance of the list happens. The parameters are:
147  // <ul>
148  // <li> <b>e</b> -- the element to be added
149  // <li> <b>p</b> -- the previous element of the list
150  // <li> <b>n</b> -- the next element of the list
151  // </ul>
152  // If the previous element is non-null it is used to get all of the
153  // information necessary to add this new element to the list. If
154  // the previous element is null and the next element is non-null
155  // it is assumed that the new element is being added to the
156  // beginning of the list, i.e. before the next element but with
157  // no previous element.
158  //
159  Link(t e,Link<t> *p=0,Link<t> *n=0) : store(e), Prev(p) {
160  if (Prev) {
161  Next = (*Prev).Next;
162  (*Prev).Next = this;
163  if (Next) (*Next).Prev = this;
164  } else {
165  Next = n;
166  if (Next) {
167  //
168  // Clean up previous list if inserting in the middle
169  // of a list with "p==0".
170  //
171  if ((*Next).Prev) (*(*Next).Prev).Next = 0;
172  (*Next).Prev = this;
173  }
174  }
175  }
176 
177  //
178  // This destructor destroys the rest of the list, i.e. this object and all
179  // that follow.
180  // <note role=warning> If the destructor is called for a <src>Link<t></src> in
181  // the middle of a list the elements which occur before the object will
182  // be left dangling, and the objects which follow the deleted object
183  // will also be deleted.
184  // </note>
185  ~Link();
186 
187  //
188  // This function unlinks a given element of the list. It requires
189  // no parameters because the node has links to the previous and
190  // next elements in the list. This is useful when removing a
191  // single element from the list because the destructor,
192  // <src>Link::~Link</src>, will delete the rest of the list elements
193  // if they are linked in with <src>this</src>. This function returns
194  // the next element in the list.
195  // <note role=tip> The <src>Link<t>*</src> parameter is unused. It is a
196  // historical artifact which <b>will</b> be removed.
197  // </note>
198  Link<t> *unlink(Link<t> * = 0);
199 
200 };
201 
203 
204 
205 } //# NAMESPACE CASACORE - END
206 
207 #ifndef CASACORE_NO_AUTO_TEMPLATES
208 #include <casacore/casa/Containers/Link.tcc>
209 #endif //# CASACORE_NO_AUTO_TEMPLATES
210 #endif
Link< int > Link_int
Definition: Link.h:202
const Double e
e and functions thereof:
#define casacore
&lt;X11/Intrinsic.h&gt; #defines true, false, casacore::Bool, and String.
Definition: X11Intrinsic.h:42