source: branches/port5/NALIGNER/ali_tlist.hxx

Last change on this file was 5442, checked in by westram, 17 years ago
  • removed const modifier from value return type
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.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    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.