source: branches/stable/NALIGNER/ali_tlist.hxx

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