ARB
ali_tlist.hxx
Go to the documentation of this file.
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 
19 template<class T>
23 
25  { prev_elem = next_elem = NULp; }
26  void print() {
27  printf("<%8p (%8p) %8p> = %lx", prev_elem, this, next_elem, info);
28  }
29 };
30 
31 template<class T>
32 class 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 
38 public:
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 
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  }
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 
197 template <class T>
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 
213 template <class T>
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 
232 template <class T>
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 
247 template <class T>
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 
266 template <class T>
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 
286 template <class T>
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 
310 template <class T>
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 
330 template <class T>
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 
354 template<class T>
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
int is_consistent()
Definition: ali_tlist.hxx:39
int has_next()
Definition: ali_tlist.hxx:168
void make_empty()
Definition: ali_tlist.hxx:116
ALI_TLIST(T &a)
Definition: ali_tlist.hxx:84
int cardinality()
Definition: ali_tlist.hxx:162
void delete_element()
Definition: ali_tlist.hxx:355
ALI_TLIST_ELEM< T > * prev_elem
Definition: ali_tlist.hxx:22
ALI_TLIST_ELEM< T > * next_elem
Definition: ali_tlist.hxx:22
void mark_element()
Definition: ali_tlist.hxx:146
int is_empty()
Definition: ali_tlist.hxx:165
void marked()
Definition: ali_tlist.hxx:149
void append_front(T &a)
Definition: ali_tlist.hxx:233
void print()
Definition: ali_tlist.hxx:97
int has_prev()
Definition: ali_tlist.hxx:171
void overwrite_element(T new_elem)
Definition: ali_tlist.hxx:157
void ali_fatal_error(const char *message, const char *func)
Definition: ali_main.cxx:85
void ali_warning(const char *message)
Definition: ali_misc.hxx:47
#define NULp
Definition: cxxforward.h:97
void insert_bevor(T &a)
Definition: ali_tlist.hxx:311
Definition: trnsprob.h:20
void append_end(T &a)
Definition: ali_tlist.hxx:198
void insert_after(T &a)
Definition: ali_tlist.hxx:267