← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/tcm/intrepid

« back to all changes in this revision

Viewing changes to src/gl/llist.c

  • Committer: Bazaar Package Importer
  • Author(s): Otavio Salvador
  • Date: 2003-07-03 20:08:21 UTC
  • Revision ID: james.westby@ubuntu.com-20030703200821-se4xtqx25e5miczi
Tags: upstream-2.20
Import upstream version 2.20

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gl/llist.c
 
1
////////////////////////////////////////////////////////////////////////////////
 
2
//
 
3
// This file is part of Toolkit for Conceptual Modeling (TCM).
 
4
// (c) copyright 1995, Vrije Universiteit Amsterdam.
 
5
// Author: Frank Dehne (frank@cs.vu.nl).
 
6
//
 
7
// TCM is free software; you can redistribute it and/or modify
 
8
// it under the terms of the GNU General Public License as published by
 
9
// the Free Software Foundation; either version 2 of the License, or
 
10
// (at your option) any later version.
 
11
//
 
12
// TCM is distributed in the hope that it will be useful,
 
13
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
// GNU General Public License for more details.
 
16
//
 
17
// You should have received a copy of the GNU General Public License
 
18
// along with TCM; if not, write to the Free Software
 
19
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 
20
// 02111-1307, USA.
 
21
////////////////////////////////////////////////////////////////////////////////
 
22
#ifndef __LIST_C
 
23
#define __LIST_C
 
24
 
 
25
#include "llist.h"
 
26
 
 
27
#if defined(__SUNPRO_CC)
 
28
#include "lstring.h"
 
29
#if __SUNPRO_CC >= 0x500
 
30
template<> inline void List<string>::clear() { empty(); }
 
31
template<> inline void List<unsigned>::clear() { empty(); }
 
32
template<> inline void List<int>::clear() { empty(); }
 
33
#else
 
34
inline void List<string>::clear() { empty(); }
 
35
inline void List<unsigned>::clear() { empty(); }
 
36
inline void List<int>::clear() { empty(); }
 
37
#endif
 
38
#endif
 
39
 
 
40
template <class T> List<T>::List() {
 
41
        head = 0;
 
42
        tail = 0;
 
43
        current = 0;
 
44
        length = 0;
 
45
}
 
46
 
 
47
template <class T> List<T>::~List() {
 
48
        Element<T> *p = head, *q;
 
49
        while (p != 0) {
 
50
                q = p->next;
 
51
                delete p;
 
52
                p = q;
 
53
        }
 
54
}
 
55
 
 
56
template <class T> List<T>::List(const List<T> &l) {
 
57
        head = 0;
 
58
        tail = 0;
 
59
        length = 0;
 
60
        current = 0;
 
61
        unsigned s = l.count();
 
62
        for (unsigned i = 0; i < s; i++)
 
63
                add(l[i]);
 
64
        current = head;
 
65
}
 
66
 
 
67
template <class T> List<T> &List<T>::operator=(const List<T> &l) {
 
68
        if (this == &l) 
 
69
                return *this;
 
70
        empty();
 
71
        unsigned s = l.count();
 
72
        for (unsigned i = 0; i < s; i++)
 
73
                add(l[i]);
 
74
        current = head;
 
75
        return *this;   
 
76
}
 
77
 
 
78
template <class T> List<T> *List<T>::add(const T &e) {
 
79
        Element<T> *p = new Element<T>;
 
80
        p->item = e;
 
81
        p->prev = tail;
 
82
        p->next = 0;
 
83
        if (tail != 0) 
 
84
                tail->next = p;
 
85
        if (head == 0) 
 
86
                head = p;
 
87
        tail = p;
 
88
        if (current == 0)
 
89
                current = head;
 
90
        length++;
 
91
        return this;
 
92
}
 
93
 
 
94
template <class T> void List<T>::insert(const T &e, const unsigned i) {
 
95
        if (i >= length) {
 
96
                add(e); 
 
97
                return;
 
98
        }
 
99
        Element<T> *p = new Element<T>;
 
100
        Element<T> *q = head;
 
101
        unsigned j = 0;
 
102
        p->item = e;
 
103
        while (j++ < i) 
 
104
                q = q->next;
 
105
        p->next = q;
 
106
        if (q != 0) {
 
107
                p->prev = q->prev;
 
108
                q->prev = p;
 
109
        } 
 
110
        else {
 
111
                p->prev = tail;
 
112
                tail = p;
 
113
        }
 
114
        if (p->prev != 0)
 
115
                p->prev->next = p;
 
116
        else
 
117
                head = p;
 
118
        length++;
 
119
}
 
120
 
 
121
template <class T> int List<T>::find(const T &e) const {
 
122
        Element<T> *q = head;
 
123
        int i = 0;
 
124
        while (q != 0) {
 
125
                if (q->item == e) 
 
126
                        return i;
 
127
                i++;
 
128
                q = q->next;
 
129
        }
 
130
        return -1;
 
131
}
 
132
 
 
133
template <class T> void List<T>::remove(const T &e) {
 
134
        int i;
 
135
        while ((i = find(e)) >= 0)
 
136
                removei((unsigned) i);
 
137
}
 
138
 
 
139
template <class T> void List<T>::removei(const unsigned i) {
 
140
        unsigned j = 0;
 
141
        Element<T> *q = head;
 
142
        if (i >= length) 
 
143
                return;
 
144
        while (j++ < i) 
 
145
                q = q->next;
 
146
        if (q->prev != 0)
 
147
                q->prev->next = q->next;
 
148
        else 
 
149
                head = q->next;
 
150
        if (q->next != 0)
 
151
                q->next->prev = q->prev;
 
152
        else 
 
153
                tail = q->prev;
 
154
        if (current == q)
 
155
                current = q->next;
 
156
        delete q;
 
157
        length--;
 
158
}
 
159
 
 
160
// added by David N. Jansen <dnjansen@cs.utwente.nl>
 
161
template <class T> bool List<T>::removecur() {
 
162
        if ( 0 == current )
 
163
                return False;
 
164
        Element<T> *q = current;
 
165
        current = q->next;
 
166
        if ( 0 != q->prev )
 
167
                q->prev->next = current;
 
168
        else
 
169
                head = current;
 
170
        if ( 0 != current )
 
171
                current->prev = q->prev;
 
172
        else
 
173
                tail = q->prev;
 
174
        delete q;
 
175
        length--;
 
176
        return True;
 
177
}
 
178
 
 
179
// added by Rik Eshuis <eshuis@cs.utwente.nl>
 
180
template <class T> bool List<T>::isSet(void) const {
 
181
        Element<T> *q = head;
 
182
        while (q != 0) {
 
183
                if (count(q->item)>1) 
 
184
                        return False;     
 
185
                q = q->next;
 
186
        }
 
187
        return True;
 
188
}
 
189
 
 
190
// added by Rik Eshuis <eshuis@cs.utwente.nl>
 
191
template <class T> int List<T>::count(const T &e) const {
 
192
        int c=0;
 
193
        Element<T> *q = head;
 
194
        while (q != 0) {
 
195
                if (q->item == e) {
 
196
                        c++;
 
197
                }
 
198
                q = q->next;
 
199
        }
 
200
        return c;
 
201
}
 
202
 
 
203
// added by Rik Eshuis <eshuis@cs.utwente.nl>
 
204
// The following procedure is a bit inefficient since multiple
 
205
// elements are counted every time they occur in list l
 
206
//template <class T> bool List<T>::contains(List<T> *l) const {
 
207
//      for (l->first();!l->done();l->next()){
 
208
//              if (l->count(l->cur()) > this->count(l->cur())) 
 
209
//                      return False;
 
210
//      }
 
211
//      return True;
 
212
//}
 
213
 
 
214
template <class T> T &List<T>::operator[] (const unsigned i) const {
 
215
        Element<T> *q = head;
 
216
        unsigned j = 0;
 
217
        while (j++ < i) 
 
218
                q = q->next;
 
219
        return q->item;
 
220
}
 
221
 
 
222
template <class T> T &List<T>::elem(const unsigned i) const {
 
223
        Element<T> *q = head;
 
224
        unsigned j = 0;
 
225
        while(j++ < i) 
 
226
                q = q->next;
 
227
        return q->item;
 
228
}
 
229
 
 
230
template <class T> void List<T>::replace(const T &old, const T &fresh) {
 
231
        Element<T> *q = head;
 
232
        while(q != 0)
 
233
                if(q->item == old)      
 
234
                        q->item = fresh;
 
235
}
 
236
 
 
237
template <class T> void List<T>::sort(int (*cmp)(T, T)) {
 
238
        Element<T> *p, *q;
 
239
        if (head == 0)
 
240
                return;
 
241
        for (p=head; p->next!=0; p=p->next) {
 
242
                for(q=tail;(p!=q && p!=q->next); q=q->prev) {
 
243
                        if ((*cmp) (q->item, q->prev->item) < 0) {
 
244
                                T temp = q->item;
 
245
                                q->item = q->prev->item;
 
246
                                q->prev->item = temp;
 
247
                        }
 
248
                }
 
249
        }
 
250
}
 
251
 
 
252
template <class T> void List<T>::reverse() {
 
253
        Element<T> *p, *q;
 
254
        if (head == 0)
 
255
                return;
 
256
        for (p=head,q=tail; (p!=q && p!=q->next);p=p->next,q=q->prev) {
 
257
                T temp = p->item;
 
258
                p->item = q->item;
 
259
                q->item = temp;
 
260
        }
 
261
}
 
262
 
 
263
template <class T> void List<T>::empty() {
 
264
        Element<T> *p = head, *q;
 
265
        // delete all nodes.
 
266
        while (p != 0) {
 
267
                q = p->next;
 
268
                delete p;
 
269
                p = q;
 
270
        }
 
271
        head = 0;
 
272
        tail = 0;
 
273
        length = 0;
 
274
}
 
275
 
 
276
template <class T> void List<T>::clear() { 
 
277
        Element<T> *p = head, *q;
 
278
        // delete all items.
 
279
        while (p != 0) {
 
280
                // dangerous when p is not a pointer.
 
281
                if (p->item) 
 
282
                        delete p->item;
 
283
                p = p->next;
 
284
        }
 
285
        // delete all nodes.
 
286
        p = head;
 
287
        while (p != 0) {
 
288
                q = p->next;
 
289
                delete p;
 
290
                p = q;
 
291
        }
 
292
        head = 0;
 
293
        tail = 0;
 
294
        length = 0;
 
295
        current = 0;
 
296
}
 
297
 
 
298
template <class T> int List<T>::setcur(const T &e) {
 
299
        Element<T> *q = head;
 
300
        while (q != 0) {
 
301
                if (q->item == e) {
 
302
                        current = q;
 
303
                        return 1;
 
304
                }
 
305
                q = q->next;
 
306
        }
 
307
        return 0;
 
308
}
 
309
 
 
310
//
 
311
// template <class T> ostream &operator<<(ostream &o, const List<T> &l) {
 
312
//      Element<T> *q = l.head;
 
313
//      while(q++ != 0)
 
314
//              o << q->item;
 
315
// }
 
316
 
 
317
 
 
318
#ifdef __GNUC__
 
319
#include "instances.h"
 
320
#endif
 
321
 
 
322
#ifdef XLC
 
323
#include "xlcinstances.h"
 
324
#endif
 
325
 
 
326
#endif