source: tags/initial/NALIGNER/ali_tlist.hxx

Last change on this file was 2, checked in by oldcode, 23 years ago

Initial revision
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.0 KB
Line 
1
2
3#ifndef _ALI_TLIST_INC_
4#define _ALI_TLIST_INC_
5
6#include "ali_misc.hxx"
7
8#include <stdio.h>
9
10template<class T>
11struct ALI_TLIST_ELEM {
12        T info;
13        ALI_TLIST_ELEM<T> *next_elem, *prev_elem;
14
15        ALI_TLIST_ELEM<T>(T &a) : info(a)
16                { prev_elem = next_elem = 0; }
17        void print(void) {
18                printf("<%8p (%8p) %8p> = %lx", prev_elem,this,next_elem,info);
19        }
20};
21
22template<class T>
23class ALI_TLIST {
24        ALI_TLIST_ELEM<T> *first_elem, *last_elem;
25        ALI_TLIST_ELEM<T> *current_elem;
26        ALI_TLIST_ELEM<T> *marked_elem;
27        unsigned long cardinal;
28
29public:
30   int is_consistent(void) {
31                int current_inside_flag = 0;
32                int marked_inside_flag = 0;
33      ALI_TLIST_ELEM<T> *akt, *pre;
34
35                if (!((current_elem == 0 && first_elem == 0 && last_elem == 0) ||
36                          (current_elem != 0 && first_elem != 0 && last_elem != 0))) {
37                        printf("List is inconsistent (1)\n");
38                        return 0;
39                }
40                if (first_elem != 0) {
41                        pre = first_elem;
42                        if (current_elem == pre)
43                                current_inside_flag = 1;
44                        if (marked_elem == pre)
45                                marked_inside_flag = 1;
46                        akt = pre->next_elem;
47                        while (akt) {
48                                if (current_elem == akt)
49                                        current_inside_flag = 1;
50                                if (marked_elem == akt)
51                                        marked_inside_flag = 1;
52                                if (akt->prev_elem != pre) {
53                                        printf("List is inconsistent (2)\n");
54                                        return 0;
55                                }
56            pre = akt;
57                                akt = akt->next_elem;
58                        }
59         if (pre != last_elem) {
60                                printf("List is inconsistent (3)\n");
61                                return 0;
62                        }
63                        if (current_inside_flag == 0) {
64                                printf("List is inconsistent (4)\n");
65                                return 0;
66                        }
67                        if (marked_elem && marked_inside_flag == 0) {
68                                printf("List is inconsistent (5)\n");
69                                return 0;
70                        }
71                }
72                return 1;
73        }
74
75        ALI_TLIST(void) { 
76                first_elem = last_elem = current_elem = marked_elem = 0; 
77                cardinal = 0;
78        }
79        ALI_TLIST(T &a) { 
80                marked_elem = 0;
81                first_elem = last_elem = current_elem = new ALI_TLIST_ELEM<T>(a); 
82                cardinal = 1;
83        }
84        ~ALI_TLIST(void) {
85                while (first_elem != 0) {
86                   current_elem = first_elem;
87                        first_elem = current_elem->next_elem;
88                        delete current_elem;
89                }
90        }
91
92        void print(void) {
93                unsigned long l;
94                ALI_TLIST_ELEM<T> *akt;
95
96      printf("List (%ld):\n", cardinal);
97                printf("first = %p  last = %p  current = %p  marked = %p\n",
98                                 first_elem, last_elem, current_elem, marked_elem);
99                for (akt = first_elem, l = 0; akt != 0 && akt != last_elem; 
100                                                                                                                                  l++, akt = akt->next_elem) {
101                        printf("%2ld ",l);
102                        akt->print();
103                        printf("\n");
104                }
105                if (akt != 0)
106                        akt->print();
107                printf("\n\n");
108        }
109        /* clear the list */
110
111        void make_empty(void) {
112                while (first_elem != 0) {
113                        current_elem = first_elem;
114                        first_elem = current_elem->next_elem;
115                        delete current_elem;
116                }
117                first_elem = last_elem = current_elem = marked_elem = 0;
118                cardinal = 0;
119        }
120
121   /* append at end or front of _list_ */
122
123   void append_end(T &a);
124        void append_end(ALI_TLIST<T> &a);
125        void append_front(T &a);
126        void append_front(ALI_TLIST<T> &a);
127
128        /* insert after or bevore _current_ element */
129
130        void insert_after(T &a);
131        void insert_after(ALI_TLIST<T> &a);
132        void insert_bevor(T &a);
133        void insert_bevor(ALI_TLIST<T> &a);
134
135   /* delete _current_ element and goto _next_ element */
136
137        void delete_element(void);
138
139   /* Mark a unique element */
140
141        void mark_element(void) {
142                marked_elem = current_elem;
143        }
144        void marked(void) {
145                if (marked_elem == 0)
146                        ali_fatal_error("No marked element in list","ALI_TLIST<T>::marked()");
147                current_elem = marked_elem;
148                marked_elem = 0;
149        }
150
151   /* Overwrite */
152        void overwrite_element(T new_elem) {
153                if (current_elem != 0)
154                        (current_elem->info) = new_elem;
155        }
156        /* For navigation through the list */
157   const int cardinality() {
158                return cardinal;
159        }
160   int is_empty() { 
161                return (current_elem == 0); 
162        }
163        int is_next() { 
164                return (current_elem != 0 && current_elem->next_elem != 0); 
165        }
166        int is_prev() { 
167           return (current_elem != 0 && current_elem->prev_elem != 0); 
168        }
169        T current() { 
170                return current_elem->info; 
171        }
172        T first() { 
173                current_elem = first_elem; 
174                return current_elem->info; 
175        }
176        T last() { 
177                current_elem = last_elem; 
178                return current_elem->info; 
179        }
180        T next() { 
181                if (current_elem->next_elem != 0)
182              current_elem = current_elem->next_elem;
183           return current_elem->info; 
184        }
185        T prev() { 
186                if (current_elem->prev_elem != 0)
187              current_elem = current_elem->prev_elem;
188           return current_elem->info; 
189        }
190};
191
192template <class T>
193void ALI_TLIST<T>::append_end(T &a)
194{
195        ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
196
197   if (last_elem != 0) {
198                last_elem->next_elem = elem;
199                elem->prev_elem = last_elem;
200                last_elem = elem;
201        }
202        else {
203                last_elem = first_elem = current_elem = elem;
204        }
205        cardinal++;
206}
207
208template <class T>
209void ALI_TLIST<T>::append_end(ALI_TLIST<T> &a)
210{
211        ALI_TLIST_ELEM<T> *elem, *akt_elem;
212
213        for (akt_elem = a.first_elem; akt_elem != 0; 
214                                                                                                 akt_elem = akt_elem->next_elem) {
215                elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
216                if (last_elem != 0) {
217                        last_elem->next_elem = elem;
218                        elem->prev_elem = last_elem;
219                        last_elem = elem;
220                }
221                else {
222                        last_elem = first_elem = current_elem = elem;
223                }
224                cardinal++;
225        }
226}
227
228template <class T>
229void ALI_TLIST<T>::append_front(T &a)
230{
231        ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
232
233   if (first_elem != 0) {
234                first_elem->prev_elem = elem;
235                elem->next_elem = first_elem;
236                first_elem = elem;
237        }
238        else {
239                last_elem = first_elem = current_elem = elem;
240        }
241        cardinal++;
242}
243
244template <class T>
245void ALI_TLIST<T>::append_front(ALI_TLIST<T> &a)
246{
247        ALI_TLIST_ELEM<T> *elem, *akt_elem;
248
249        for (akt_elem = a.last_elem; akt_elem != 0; 
250                                                                                                akt_elem = akt_elem->prev_elem) {
251                elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
252                if (first_elem != 0) {
253                        first_elem->prev_elem = elem;
254                        elem->next_elem = first_elem;
255                        first_elem = elem;
256                }
257                else {
258                        last_elem = first_elem = current_elem = elem;
259                }
260                cardinal++;
261        }
262}
263
264template <class T>
265void ALI_TLIST<T>::insert_after(T &a)
266{
267        ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
268
269   if (current_elem != 0) {
270                if (current_elem->next_elem != 0) {
271                        elem->next_elem = current_elem->next_elem;
272                        current_elem->next_elem->prev_elem = elem;
273                }
274                current_elem->next_elem = elem;
275                elem->prev_elem = current_elem;
276                if (current_elem == last_elem)
277                        last_elem = elem;
278        }
279        else {
280                last_elem = first_elem = current_elem = elem;
281        }
282        cardinal++;
283}
284
285template <class T>
286void ALI_TLIST<T>::insert_after(ALI_TLIST<T> &a)
287{
288        ALI_TLIST_ELEM<T> *elem, *akt_elem;
289
290        for (akt_elem = a.first_elem; akt_elem != 0; 
291                                                                                                 akt_elem = akt_elem->next_elem) {
292                elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
293                if (current_elem != 0) {
294                        if (current_elem->next_elem != 0) {
295                           elem->next_elem = current_elem->next_elem;
296                                current_elem->next_elem->prev_elem = elem;
297                        }
298                        current_elem->next_elem = elem;
299                        elem->prev_elem = current_elem;
300                        if (current_elem == last_elem)
301                                last_elem = elem;
302                }
303                else {
304                        last_elem = first_elem = current_elem = elem;
305                }
306                cardinal++;
307        }
308}
309
310template <class T>
311void ALI_TLIST<T>::insert_bevor(T &a)
312{
313        ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
314
315   if (current_elem != 0) {
316                if (current_elem->prev_elem != 0) {
317                        elem->prev_elem = current_elem->prev_elem;
318                        current_elem->prev_elem->next_elem = elem;
319                }
320                current_elem->prev_elem = elem;
321                elem->next_elem = current_elem;
322                if (current_elem == first_elem)
323                        first_elem = elem;
324        }
325        else {
326                last_elem = first_elem = current_elem = elem;
327        }
328        cardinal++;
329}
330
331template <class T>
332void ALI_TLIST<T>::insert_bevor(ALI_TLIST<T> &a)
333{
334        ALI_TLIST_ELEM<T> *elem, *akt_elem;
335
336        for (akt_elem = a.last_elem; akt_elem != 0; 
337                                                                                                akt_elem = akt_elem->prev_elem) {
338                elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
339                if (current_elem != 0) {
340                        if (current_elem->prev_elem != 0) {
341                                elem->prev_elem = current_elem->prev_elem;
342                                current_elem->prev_elem->next_elem = elem;
343                        }
344                        current_elem->prev_elem = elem;
345                        elem->next_elem = current_elem;
346                        if (current_elem == first_elem)
347                                first_elem = elem;
348                }
349                else {
350                        last_elem = first_elem = current_elem = elem;
351                }
352                cardinal++;
353        }
354}
355
356template<class T>
357void ALI_TLIST<T>::delete_element(void)
358{
359   ALI_TLIST_ELEM<T> *elem;
360
361        if (current_elem != 0) {
362                if (current_elem == marked_elem) {
363                        ali_warning("Delete marked element");
364                        marked_elem = 0;
365                }
366                /*   prev_elem <--> current <--> next_elem   */
367                if (current_elem->prev_elem != 0 && current_elem->next_elem != 0) {
368                        elem = current_elem;
369                        current_elem->prev_elem->next_elem = current_elem->next_elem;
370                        current_elem->next_elem->prev_elem = current_elem->prev_elem;
371                        current_elem = current_elem->next_elem;
372                        delete elem;
373                }
374                else {
375                /*   prev_elem <--> current -|   */
376                        if (current_elem->prev_elem != 0) {
377                                elem = current_elem;
378                                current_elem->prev_elem->next_elem = 0;
379                                current_elem = current_elem->prev_elem;
380                                last_elem = current_elem;
381                                delete elem;
382                        }
383                        else {
384                /*   |- current <--> next_elem   */
385                                if (current_elem->next_elem != 0) {
386                                        elem = current_elem;
387                                        current_elem->next_elem->prev_elem = 0;
388                                        current_elem = current_elem->next_elem;
389                                        first_elem = current_elem;
390                                        delete elem;
391                                }
392                                else {
393                /*   |- current -|   */
394                                        elem = current_elem;
395                                        delete elem;
396                                        first_elem = last_elem = current_elem = 0;
397                                }
398                        }
399                }
400                cardinal--;
401        }
402}
403
404
405#endif
406
Note: See TracBrowser for help on using the repository browser.