Back
1 //------------------------------------------------------------------------------
2 // module: stdList.h //
3 // //
4 // Simple but time efficient single linked list template //
5 // //
6 // copyright 2000-2003 by Lars Haendel //
7 // home: www.newty.de //
8 // //
9 // This program is free software; you can redistribute it and/or modify //
10 // it under the terms of the GNU General Public License as published by //
11 // the Free Software Foundation as version 2 of the License. //
12 // //
13 // This program is distributed in the hope that it will be useful, //
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of //
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
16 // GNU General Public License for more details. //
17 // //
18 // You should have received a copy of the GNU General Public License //
19 // along with this program; if not, write to the Free Software //
20 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. //
21 // //
22 //------------------------------------------------------------------------------
23
24 #ifndef STDLIST_H
25 #define STDLIST_H
26
27
28 // Note: Positions are counted up from 0
29
30 //--------------------------------------------------------------------------------------------------------
31 // note: do not(!) include <string> to prevent dozens of warnings "...not expanded inline"
32 #include <stdio> // sprintf()
33 #include "defines.h" // STS
34
35 //--------------------------------------------------------------------------------------------------------
36 // exception handling
37 #define NO_EXCEPTIONS // switch to disable exceptions
38
39 #ifdef NO_EXCEPTIONS // define empty function for IfTrueThrowTypeB() if exceptions are diabled
40 inline void IfTrueThrowTypeB(const bool, const char*, const char*, const char*){};
41 #else
42 #include "exception.h" // else: header file used for exception handling
43 #endif
44
45
46 //----------------------------------------------------------------------------------------------------------------------
47 // utility function: iterates list and calls 'delete' for each element; however this will only compile if <TEntry>
48 // is a pointer
49 template <class TList> void DeleteEntries(TList* list)
50 {
51 if(list->Size() > 0) // if list is not empty ...
52 {
53 list->Reset(); // ... position to top, ...
54 for(int i=0;i<list->Size();i++) // ... iterate the list and ...
55 {
56 list->Next();
57 delete list->Get(); // ... call 'delete' for each element
58 }
59 }
60 };
61
62
63 //----------------------------------------------------------------------------------------------------------------------
64 // template definition of list element
65 template <class TEntry> class TListElement
66 {
67 public:
68 TListElement* next; // pointer to next element
69 TEntry entry; // element itself
70 };
71
72
73 //----------------------------------------------------------------------------------------------------------------------
74 // class template for simple but efficient single linked list
75 // Attention: If the list elements are pointers you(!) must release the memory the pointer point to. You may use the
76 // utility function DeleteEntries() to do this. If elements are inserted into the list they will be copied.
77 // Take care if the list element is a class which has pointers. You may have to implement a copy constructor!
78 // Attention: If you call Reset() you have to call Next() before you can access the first list element!
79 template <class TEntry> class TStdList
80 {
81 private:
82
83 // pointers to list elements
84 TListElement<TEntry>* start; // first
85 mutable TListElement<TEntry>* act; // actual
86 mutable TListElement<TEntry>* prev; // previous
87
88 int size; // # list elements
89 mutable int _pos; // index of actual list position
90
91 char szName[STS]; // name of the list, useful in debug mode
92
93 public:
94
95 // constructor/destructor
96 TStdList();
97 ~TStdList();
98
99 void Clear(); // clear all list elements
100 void SetName(const char* _szName) { strcpy(szName, _szName); }; // set the list's name
101
102 // functions to position in list
103 inline void Reset() const; // position to first element
104 inline void Next() const; // position to next element
105 void Pos(const int& __pos) const; // position to element with specified index
106 const int& Pos() const { return _pos; }; // return current position index
107
108
109 // functions to get and set list elements
110 inline TEntry& Get(); // return element at actual position
111 inline const TEntry& Get() const; // const version
112 inline TEntry& Get(const int& i) { Pos(i); return Get(); }; // return i-th element in list
113 inline const TEntry& Get(const int& i) const { Pos(i); return Get(); }; // const version
114 inline TEntry& Ins(); // insert new empty element after(!) actual position
115
116 // overwrite(!) element at actual position with given element
117 inline void Put(const TEntry& entry) { (*act).entry = entry; };
118 inline void Ins(const TEntry& entry) { Ins() = entry; }; // insert given element after(!) actual position
119 inline void Del(); // delete element at actual position from list
120 inline void Del(const int& i) { Pos(i); Del(); } ; // delete element at position i
121
122 void Cat(TStdList<TEntry>* list); // concatenate/append given list at the end of this list
123
124 inline const int& Size() const { return size; }; // return # elements in list
125 };
126
127
128 //----------------------------------------------------------------------------------------------------------------------
129 // constructor
130 template <class TEntry> TStdList<TEntry>::TStdList()
131 {
132 strcpy(szName, "TStdList<TEntry>");
133
134 // create dummy element at begin of list
135 prev = new TListElement<TEntry>;
136 (*prev).next = NULL;
137
138 act = prev;
139 start = prev;
140
141 size = 0;
142 _pos = -1;
143 }
144
145
146 //----------------------------------------------------------------------------------------------------------------------
147 // destructor
148 template <class TEntry> TStdList<TEntry>::~TStdList()
149 {
150 Clear(); // clear all list elements
151 delete start; // delete the dummy element at top of list
152 }
153
154
155 //----------------------------------------------------------------------------------------------------------------------
156 // clear all list elements
157 template <class TEntry> void TStdList<TEntry>::Clear()
158 {
159 if(size > 0) // if list is not empty ...
160 {
161 Reset(); // position to top of list
162 Next();
163
164 int t = size; // remember # list elements ...
165
166 for(int i=0;i<t;i++)
167 Del(); // and delete them
168 }
169
170 // note: reset() is called automatically when deleting the last element
171 }
172
173
174
175 //----------------------------------------------------------------------------------------------------------------------
176 // position to first list element
177 template <class TEntry> void TStdList<TEntry>::Reset() const
178 {
179 prev = start; // set previous and actual element
180 act = start; //
181
182 _pos = -1;
183 }
184
185
186 //----------------------------------------------------------------------------------------------------------------------
187 // position forward to next element
188 template <class TEntry> inline void TStdList<TEntry>::Next() const
189 {
190 // throw exception if actual element is NULL, i.e. not existing
191 IfTrueThrowTypeB(!act, "Function Next() called after last element in list!", szName, "stdList.h");
192
193
194 prev = act;
195 act = (*act).next; // position forward
196
197 _pos++; // increment position index
198 }
199
200
201 //----------------------------------------------------------------------------------------------------------------------
202 // position to element at specified position
203 template <class TEntry> void TStdList<TEntry>::Pos(const int& __pos) const
204 {
205 // throw exception if index is 'out of range'
206 IfTrueThrowTypeB(__pos<-1 || __pos>=size, "Function Pos() called with illegal value!", szName, "stdList.h");
207
208 // if specified position is before(!) actual position
209 if(_pos > __pos)
210 {
211 Reset(); // reset to top
212 Pos(__pos); // ... and call again
213
214 return;
215 }
216
217 int k=__pos-_pos; // estimate # of elements from actual to desired position
218
219 // ... and call Next() as many times
220 for(int i=0;i<k;i++)
221 Next();
222 }
223
224
225 //----------------------------------------------------------------------------------------------------------------------
226 // return element at actual list position
227 template <class TEntry> TEntry& TStdList<TEntry>::Get()
228 {
229 // throw exception if actual element is NULL, i.e. not existing
230 IfTrueThrowTypeB(!act, "Function Get() called on NULL-pointer!", szName, "stdList.h");
231 IfTrueThrowTypeB(_pos==-1,"Function Get() called while list was positioned before first element! Call Next() before!"
232 , szName, "stdList.h");
233
234 return (*act).entry; // return element
235 }
236
237
238 template <class TEntry> const TEntry& TStdList<TEntry>::Get() const
239 {
240 // throw exception if actual element is NULL, i.e. not existing
241 IfTrueThrowTypeB(!act, "Function Get() called on NULL-pointer!", szName, "stdList.h");
242
243 return (*act).entry; // return element
244 }
245
246
247 //----------------------------------------------------------------------------------------------------------------------
248 // insert new (and un-initialized) element after(!) the actual position
249 template <class TEntry> TEntry& TStdList<TEntry>::Ins()
250 {
251 // throw exception if actual element is NULL, i.e. not existing
252 IfTrueThrowTypeB(!act, "Function Ins() called on NULL-pointer!", szName, "stdList.h");
253
254
255 TListElement<TEntry>* old = (*act).next; // remember pointer to next element
256 (*act).next = new TListElement<TEntry>; // insert element
257 prev = act;
258 act = (*act).next; // position forward
259 (*act).next = old; // connect to next element (set stored pointer)
260
261 size++; // increment # element counter and ...
262 _pos++; // position index
263
264 return (*act).entry; // return new element
265 }
266
267
268 //----------------------------------------------------------------------------------------------------------------------
269 // concatenate/append another list to the end of this one
270 template <class TEntry> void TStdList<TEntry>::Cat(TStdList<TEntry>* list)
271 {
272 list->Reset(); // position on first entry of other list
273 list->Next();
274
275 Pos(Size()-1); // position to end of this list
276 act->next = list->act; // append other list
277
278
279 size+=list->size; // manipulate sizes
280 list->size=0;
281 }
282
283
284 //----------------------------------------------------------------------------------------------------------------------
285 // delete list element at actual list position
286 template <class TEntry> void TStdList<TEntry>::Del()
287 {
288 // throw exception if element at actual position is NULL, i.e. not existing
289 IfTrueThrowTypeB( !act || _pos == -1, "Function Del() called on NULL-pointer!", szName, "stdList.h");
290
291
292 (*prev).next = (*act).next; // connect previous element to next element
293 delete act; // delete element at actual list position
294 act = (*prev).next; // position forward, note: reset() is called below if element does not exist
295
296 size--; // decrement element counter
297
298 if(!act) // reset if actual element does not exist (see above)
299 Reset();
300 }
301 #endif
Top |