source: branches/stable/NALIGNER/ali_tlist.hxx

Last change on this file was 16766, checked in by westram, 8 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.4 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 = NULp; }
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 = NULp;
82        cardinal = 0;
83    }
84    ALI_TLIST(T &a) {
85        marked_elem = NULp;
86        first_elem = last_elem = current_elem = new ALI_TLIST_ELEM<T>(a);
87        cardinal = 1;
88    }
89    ~ALI_TLIST() {
90        while (first_elem) {
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) {
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 = NULp;
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)
151            ali_fatal_error("No marked element in list", "ALI_TLIST<T>::marked()");
152        current_elem = marked_elem;
153        marked_elem = NULp;
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;
167    }
168    int has_next() {
169        return current_elem && current_elem->next_elem;
170    }
171    int has_prev() {
172        return current_elem && current_elem->prev_elem;
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)
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    ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
200
201    if (last_elem) {
202        last_elem->next_elem = elem;
203        elem->prev_elem = last_elem;
204        last_elem = elem;
205    }
206
207    else {
208        last_elem = first_elem = current_elem = elem;
209    }
210    cardinal++;
211}
212
213template <class T>
214void ALI_TLIST<T>::append_end(ALI_TLIST<T> &a) {
215    ALI_TLIST_ELEM<T> *elem, *akt_elem;
216
217    for (akt_elem = a.first_elem; akt_elem != 0;
218         akt_elem = akt_elem->next_elem) {
219        elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
220        if (last_elem != 0) {
221            last_elem->next_elem = elem;
222            elem->prev_elem = last_elem;
223            last_elem = elem;
224        }
225        else {
226            last_elem = first_elem = current_elem = elem;
227        }
228        cardinal++;
229    }
230}
231
232template <class T>
233void ALI_TLIST<T>::append_front(T &a) {
234    ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
235
236    if (first_elem != 0) {
237        first_elem->prev_elem = elem;
238        elem->next_elem = first_elem;
239        first_elem = elem;
240    }
241    else {
242        last_elem = first_elem = current_elem = elem;
243    }
244    cardinal++;
245}
246
247template <class T>
248void ALI_TLIST<T>::append_front(ALI_TLIST<T> &a) {
249    ALI_TLIST_ELEM<T> *elem, *akt_elem;
250
251    for (akt_elem = a.last_elem; akt_elem != 0;
252         akt_elem = akt_elem->prev_elem) {
253        elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
254        if (first_elem != 0) {
255            first_elem->prev_elem = elem;
256            elem->next_elem = first_elem;
257            first_elem = elem;
258        }
259        else {
260            last_elem = first_elem = current_elem = elem;
261        }
262        cardinal++;
263    }
264}
265
266template <class T>
267void ALI_TLIST<T>::insert_after(T &a) {
268    ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
269
270    if (current_elem != 0) {
271        if (current_elem->next_elem != 0) {
272            elem->next_elem = current_elem->next_elem;
273            current_elem->next_elem->prev_elem = elem;
274        }
275        current_elem->next_elem = elem;
276        elem->prev_elem = current_elem;
277        if (current_elem == last_elem)
278            last_elem = elem;
279    }
280    else {
281        last_elem = first_elem = current_elem = elem;
282    }
283    cardinal++;
284}
285
286template <class T>
287void ALI_TLIST<T>::insert_after(ALI_TLIST<T> &a) {
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    ALI_TLIST_ELEM<T> *elem = new ALI_TLIST_ELEM<T>(a);
313
314    if (current_elem) {
315        if (current_elem->prev_elem) {
316            elem->prev_elem = current_elem->prev_elem;
317            current_elem->prev_elem->next_elem = elem;
318        }
319        current_elem->prev_elem = elem;
320        elem->next_elem = current_elem;
321        if (current_elem == first_elem)
322            first_elem = elem;
323    }
324    else {
325        last_elem = first_elem = current_elem = elem;
326    }
327    cardinal++;
328}
329
330template <class T>
331void ALI_TLIST<T>::insert_bevor(ALI_TLIST<T> &a) {
332    ALI_TLIST_ELEM<T> *elem, *akt_elem;
333
334    for (akt_elem = a.last_elem; akt_elem != 0;
335         akt_elem = akt_elem->prev_elem) {
336        elem = new ALI_TLIST_ELEM<T>(akt_elem->info);
337        if (current_elem != 0) {
338            if (current_elem->prev_elem != 0) {
339                elem->prev_elem = current_elem->prev_elem;
340                current_elem->prev_elem->next_elem = elem;
341            }
342            current_elem->prev_elem = elem;
343            elem->next_elem = current_elem;
344            if (current_elem == first_elem)
345                first_elem = elem;
346        }
347        else {
348            last_elem = first_elem = current_elem = elem;
349        }
350        cardinal++;
351    }
352}
353
354template<class T>
355void ALI_TLIST<T>::delete_element() {
356    if (current_elem) {
357        if (current_elem == marked_elem) {
358            ali_warning("Delete marked element");
359            marked_elem = NULp;
360        }
361        //   prev_elem <--> current <--> next_elem
362        if (current_elem->prev_elem && current_elem->next_elem) {
363            ALI_TLIST_ELEM<T> *elem = current_elem;
364            current_elem->prev_elem->next_elem = current_elem->next_elem;
365            current_elem->next_elem->prev_elem = current_elem->prev_elem;
366            current_elem = current_elem->next_elem;
367            delete elem;
368        }
369        else {
370            //   prev_elem <--> current -|
371            if (current_elem->prev_elem) {
372                ALI_TLIST_ELEM<T> *elem = current_elem;
373                current_elem->prev_elem->next_elem = NULp;
374                current_elem = current_elem->prev_elem;
375                last_elem = current_elem;
376                delete elem;
377            }
378            else {
379                //   |- current <--> next_elem
380                if (current_elem->next_elem) {
381                    ALI_TLIST_ELEM<T> *elem = current_elem;
382                    current_elem->next_elem->prev_elem = NULp;
383                    current_elem = current_elem->next_elem;
384                    first_elem = current_elem;
385                    delete elem;
386                }
387                else {
388                    //   |- current -|
389                    ALI_TLIST_ELEM<T> *elem = current_elem;
390                    delete elem;
391                    first_elem = last_elem = current_elem = NULp;
392                }
393            }
394        }
395        cardinal--;
396    }
397}
398
399#else
400#error ali_tlist.hxx included twice
401#endif // ALI_TLIST_HXX
Note: See TracBrowser for help on using the repository browser.