casacore
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
33namespace 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>
116template<class t> class Link {
117protected:
121public:
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>
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>
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
const Double e
e and functions thereof:
this file contains all the compiler specific defines
Definition: mainpage.dox:28
Link< int > Link_int
Definition: Link.h:202