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