1 # 1 "SetLS.cc"
2 // GROUPS passed templates nested-classes
3 // Special g++ Options:
4 //
5 // The SetLS template test
6 //
7 // Wendell Baker, Berkeley CAD Group, 1993 (wbaker@ic.Berkeley.EDU)
8 //
9
10 #pragma implementation "ListS.h"
11 #pragma implementation "SetLS.h"
12
13 #include <cstdlib>
14 #include <iostream>
15 using namespace std;
16
17 # 1 "../../templates/SetLS.h" 1
18 // -*- C++ -*-
19
20
21
22 //
23 // A Set Template - implemented with an ListS
24 //
25 // Wendell Baker, Berkeley CAD Group, 1993 (wbaker@ic.Berkeley.EDU)
26 //
27
28
29
30
31
32 #pragma interface
33
34
35
36
37
38 #define XTRUE true
39 #define XFALSE false
40
41 # 37 "../../templates/SetLS.h"
42
43
44 # 1 "../../templates/ListS.h" 1
45 // -*- C++ -*-
46
47
48
49 //
50 // A List Template - providing a singly linked capability
51 //
52 // Wendell Baker, Berkeley CAD Group, 1993 (wbaker@ic.Berkeley.EDU)
53 //
54
55
56
57
58
59 #pragma interface
60
61
62
63
64
65
66 # 1 "/projects/gnu-cygnus/gnu-cygnus-14/mips/lib/gcc-lib/decstation/cygnus-reno-1/g++-include/bool.h" 1 3
67 // Defining XTRUE and XFALSE is usually a Bad Idea,
68 // because you will probably be inconsistent with anyone
69 // else who had the same clever idea.
70 // Therefore: DON'T USE THIS FILE.
71
72
73
74
75
76
77
78
79
80 # 23 "../../templates/ListS.h" 2
81
82 # 37 "../../templates/ListS.h"
83
84
85
86 // g++ reno-1 is not yet capable of creating templates with nested
87 // classes which instantiate the template arguments.
88 template<class T>
89 struct ListS_link {
90 T item;
91 ListS_link<T> *next;
92
itemListS_link93 ListS_link(const T& i, ListS_link<T> *n = 0): item(i), next(n)
94 { }
95 };
96
97
98 //
99 // For now, errors are raised by ::abort() because exceptions
100 // are not well implemented in cxx or at all in CC 3.0.1
101 //
102 template<class T>
103 class ListS {
104 public:
105 ListS();
106 ListS(const ListS<T>&);
107 ~ListS();
108
109 void operator=(const ListS<T>&);
110
length()111 unsigned length() const
112 { return count; }
113
114 void prepend(const T& item);
115 void append(const T& item);
116 void clear();
117
head()118 const T& head() const
119 { ensure_1();
120 return head_link->item; }
head()121 T& head()
122 { ensure_1();
123 return head_link->item; }
head(T & fill)124 void head(T& fill) const
125 { ensure_1();
126 fill = head_link->item; }
remove_head()127 void remove_head()
128 { remove_head_filling(0); }
remove_head(T & fill)129 void remove_head(T& fill)
130 { remove_head_filling(&fill); }
131
tail()132 const T& tail() const
133 { ensure_1();
134 return tail_link->item; }
tail()135 T& tail()
136 { ensure_1();
137 return tail_link->item; }
tail(T & fill)138 void tail(T& fill) const
139 { ensure_1();
140 fill = tail_link->item; }
141
142 class Vix {
143 public:
Vix()144 Vix(): owner(0), index(0)
145 { }
146
147 // These are friend functions so that v == x is the same as x == v
148 friend int operator==(void *v, const Vix& x)
149 { return v == x.index; }
150 friend int operator==(const Vix& x, void *v)
151 { return v == x.index; }
152 friend int operator!=(void *v, const Vix& x)
153 { return v != x.index; }
154 friend int operator!=(const Vix& x, void *v)
155 { return v != x.index; }
156 friend int operator==(const Vix& x1, const Vix& x2)
157 { return x1.owner == x2.owner && x1.index == x2.index; }
158 friend int operator!=(const Vix& x1, const Vix& x2)
159 { return x1.owner != x2.owner || x1.index != x2.index; }
160 private:
161 friend class ListS<T>;
162
163
Vix(const ListS<T> * o,ListS_link<T> * i)164 Vix(const ListS<T> *o, ListS_link<T> *i): owner(o), index(i)
165 { }
166
167
168
169
170
171 const ListS<T> *owner;
172
173 ListS_link<T> *index;
174
175
176
177 };
178
first()179 Vix first() const
180 { return Vix(this, head_link); }
next(Vix & x)181 void next(Vix& x) const
182 { check(x);
183 if (x.index != 0)
184 x.index = x.index->next; }
operator()185 T& operator()(const Vix& x)
186 { check(x);
187 return x.index->item; }
operator()188 const T& operator()(const Vix& x) const
189 { check(x);
190 return x.index->item; }
191 protected:
192 # 154 "../../templates/ListS.h"
193
194
195 unsigned count;
196
197 ListS_link<T> *head_link; // 0 for a zero-length list
198 ListS_link<T> *tail_link; // 0 for a zero-length list
199
200
201
202
203
204 private:
205 // fill may be 0 (then don't fill)
206 void remove_head_filling(T *fill);
207
ensure_1()208 void ensure_1() const
209 { if (0 == head_link)
210 ::abort(); }
check(const Vix & x)211 void check(const Vix& x) const
212 { if (this != x.owner)
213 ::abort();
214 if (0 == x.index)
215 ::abort(); }
216 };
217
218 template<class T>
ListS()219 ListS<T>::ListS():
220 count(0),
221 head_link(0),
222 tail_link(0)
223 { }
224
225 template<class T>
ListS(const ListS<T> & other)226 ListS<T>::ListS(const ListS<T>& other):
227 count(0),
228 head_link(0),
229 tail_link(0)
230 {
231 for (Vix x=other.first(); 0 != x; other.next(x))
232 append(other(x));
233 }
234
235 template<class T>
~ListS()236 ListS<T>::~ListS()
237 {
238 clear();
239 }
240
241 template<class T>
242 void
243 ListS<T>::operator=(const ListS<T>& other)
244 {
245 clear();
246 for (Vix x=other.first(); 0 != x; other.next(x))
247 append(other(x));
248 }
249
250 template<class T>
251 void
prepend(const T & item)252 ListS<T>::prepend(const T& item)
253 {
254
255 head_link = new ListS_link<T>(item, head_link);
256
257
258
259 if (0 == tail_link)
260 tail_link = head_link;
261 count++;
262 }
263
264 template<class T>
265 void
append(const T & item)266 ListS<T>::append(const T& item)
267 {
268
269 ListS_link<T> *new_link = new ListS_link<T>(item);
270
271
272
273 if (0 == tail_link) {
274 head_link = new_link;
275 tail_link = new_link;
276 } else {
277 tail_link->next = new_link;
278 tail_link = tail_link->next;
279 }
280 count++;
281 }
282
283 template<class T>
284 void
clear()285 ListS<T>::clear()
286 {
287
288 ListS_link<T> *next, *l;
289
290
291
292 for (l=head_link; 0 != l; l=next) {
293 next = l->next;
294 delete l;
295 }
296
297 count = 0;
298 head_link = 0;
299 tail_link = 0;
300 }
301
302 template<class T>
303 void
remove_head_filling(T * fill)304 ListS<T>::remove_head_filling(T* fill)
305 // fill may be 0 in which case don't assign into it
306 {
307 ensure_1();
308
309 ListS_link<T> *ohead = head_link;
310
311
312
313 if (0 != fill)
314 *fill = ohead->item;
315 head_link = ohead->next;
316 if (0 == head_link)
317 tail_link = 0;
318 count--;
319 delete ohead;
320 }
321
322
323 # 40 "../../templates/SetLS.h" 2
324
325
326 # 62 "../../templates/SetLS.h"
327
328 template<class T>
329 class SetLS {
330 public:
331 SetLS();
332
333 void add(const T& item);
334 // There is no remove(const T& item) for this set
335 bool contains(const T& item) const;
336
length()337 unsigned length() const
338 { return list.length(); }
339
clear()340 void clear()
341 { list.clear(); }
342
343 class Vix {
344 public:
Vix()345 Vix(): owner(0), vix()
346 { }
347
348 // These are friend functions so that v == x is the same as x == v
349 friend int operator==(void *v, const Vix& x)
350 { return v == x.vix; }
351 friend int operator==(const Vix& x, void *v)
352 { return v == x.vix; }
353 friend int operator!=(void *v, const Vix& x)
354 { return v != x.vix; }
355 friend int operator!=(const Vix& x, void *v)
356 { return v != x.vix; }
357 friend int operator==(const Vix& x1, const Vix& x2)
358 { return x1.owner == x2.owner && x1.vix == x2.vix; }
359 friend int operator!=(const Vix& x1, const Vix& x2)
360 { return x1.owner != x2.owner || x1.vix != x2.vix; }
361 private:
362 friend class SetLS<T>;
363
Vix(const SetLS<T> * o,const typename ListS<T>::Vix & x)364 Vix(const SetLS<T> *o, const typename ListS<T>::Vix& x): owner(o), vix(x)
365 { }
366
367 const SetLS<T> *owner;
368 typename ListS<T>::Vix vix;
369 };
370 friend class Vix;
371
first()372 Vix first() const
373 { return Vix(this, list.first()); }
next(Vix & x)374 void next(Vix& x) const
375 { check(x);
376 list.next(x.vix); }
operator()377 const T& operator()(const Vix& x) const
378 { check(x);
379 return list(x.vix); }
380 // There is item no remove(const Vix&) for this set
381 protected:
382 ListS<T> list;
383
384 private:
check(const Vix & x)385 void check(const Vix& x) const
386 { if (this != x.owner)
387 ::abort(); }
388 };
389
390
391 template<class T>
SetLS()392 SetLS<T>::SetLS():
393
394
395
396 list()
397
398 { }
399
400 template<class T>
401 void
add(const T & item)402 SetLS<T>::add(const T& item)
403 {
404 if ( ! contains(item) ) {
405
406
407
408 list.append(item);
409
410 }
411 }
412
413 template<class T>
414 bool
contains(const T & item)415 SetLS<T>::contains(const T& item) const
416 {
417 for (Vix x=first(); 0 != x; next(x)) {
418 if (operator()(x) == item)
419 return XTRUE;
420 }
421 return XFALSE;
422 }
423
424
425 # 17 "SetLS.cc" 2
426
427
428
429 // In (most versions of) g++ 2.X, this use of typedefs has the effect
430 // of causing the instantiation of the templates, thereby testing the
431 // templates
432
433 class test {
434 public:
test()435 test(): value(0)
436 { }
test(int v)437 test(int v): value(v)
438 { }
439
print(ostream & out)440 void print(ostream& out) const
441 { out << value; }
442
443 friend int operator==(const test& a, const test& b);
444 private:
445 int value;
446 };
447
448 int
449 operator==(const test& a, const test& b)
450 {
451 return a.value == b.value;
452 }
453
454 ostream&
455 operator<<(ostream& o, const test& t)
456 {
457 t.print(o);
458 return o;
459 }
460
461 typedef SetLS<test> SLS;
462
463 static ostream&
464 operator<<(ostream& o, const SLS& s)
465 {
466 o << "set of " << s.length() << " = {";
467
468 bool first;
469 SetLS<test>::Vix x;
470 for (first=XTRUE, x=s.first(); 0 != x; s.next(x), first=XFALSE) {
471 if ( ! first )
472 o << ',';
473 o << ' ';
474 s(x).print(o);
475 }
476 o << '}';
477
478 return o;
479 }
480
481 SLS gsls;
482 const SLS gcsls;
483
foo()484 void foo()
485 {
486 const unsigned SIZE = 20;
487
488 //
489 // SetLS()
490 // SetLS(const SetLS<T>&)
491 //
492 SLS sls;
493 {
494 // Fill sls with some interesting values
495 for (unsigned i=0; i<SIZE; i++) {
496 test t = i;
497 sls.add(t);
498 }
499 }
500
501 const SLS csls(sls);
502
503 //
504 // void operator=(const SetLS<T>&);
505 //
506 sls = csls;
507
508 //
509 // bool contains(const T& item) const
510 //
511 for (unsigned i=0; i<SIZE; i++) {
512 test t = i;
513
514 int contains = sls.contains(t);
515 }
516
517 //
518 // void clear()
519 //
520 sls.clear();
521 if (sls.length() != 0)
522 ::abort();
523
524 sls = csls;
525
526 //
527 // Vix first() const
528 // void next(Vix& x) const
529 // T& operator()(const Vix& x)
530 // const T& operator()(const Vix& x) const
531 //
532 SetLS<test>::Vix cx;
533 for (cx=csls.first(); 0 != cx; sls.next(cx)) {
534 if ( ! sls.contains(csls(cx)) )
535 ::abort();
536 }
537
538 cout << "gsls:\t" << gsls << '\n';
539 cout << "gcsls:\t" << gcsls << '\n';
540 cout << "sls:\t" << sls << '\n';
541 cout << "csls:\t" << csls << '\n';
542 }
543
544 // Dummy function so it'll run
main()545 int main()
546 {
547 cout << "PASS" << endl;
548 }
549
550 template class ListS<test>;
551