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> 15using 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. 88template<class T> 89struct ListS_link { 90 T item; 91 ListS_link<T> *next; 92 93 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// 102template<class T> 103class ListS { 104public: 105 ListS(); 106 ListS(const ListS<T>&); 107 ~ListS(); 108 109 void operator=(const ListS<T>&); 110 111 unsigned length() const 112 { return count; } 113 114 void prepend(const T& item); 115 void append(const T& item); 116 void clear(); 117 118 const T& head() const 119 { ensure_1(); 120 return head_link->item; } 121 T& head() 122 { ensure_1(); 123 return head_link->item; } 124 void head(T& fill) const 125 { ensure_1(); 126 fill = head_link->item; } 127 void remove_head() 128 { remove_head_filling(0); } 129 void remove_head(T& fill) 130 { remove_head_filling(&fill); } 131 132 const T& tail() const 133 { ensure_1(); 134 return tail_link->item; } 135 T& tail() 136 { ensure_1(); 137 return tail_link->item; } 138 void tail(T& fill) const 139 { ensure_1(); 140 fill = tail_link->item; } 141 142 class Vix { 143 public: 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 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 179 Vix first() const 180 { return Vix(this, head_link); } 181 void next(Vix& x) const 182 { check(x); 183 if (x.index != 0) 184 x.index = x.index->next; } 185 T& operator()(const Vix& x) 186 { check(x); 187 return x.index->item; } 188 const T& operator()(const Vix& x) const 189 { check(x); 190 return x.index->item; } 191protected: 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 204private: 205 // fill may be 0 (then don't fill) 206 void remove_head_filling(T *fill); 207 208 void ensure_1() const 209 { if (0 == head_link) 210 ::abort(); } 211 void check(const Vix& x) const 212 { if (this != x.owner) 213 ::abort(); 214 if (0 == x.index) 215 ::abort(); } 216}; 217 218template<class T> 219ListS<T>::ListS(): 220count(0), 221head_link(0), 222tail_link(0) 223{ } 224 225template<class T> 226ListS<T>::ListS(const ListS<T>& other): 227count(0), 228head_link(0), 229tail_link(0) 230{ 231 for (Vix x=other.first(); 0 != x; other.next(x)) 232 append(other(x)); 233} 234 235template<class T> 236ListS<T>::~ListS() 237{ 238 clear(); 239} 240 241template<class T> 242void 243ListS<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 250template<class T> 251void 252ListS<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 264template<class T> 265void 266ListS<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 283template<class T> 284void 285ListS<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 302template<class T> 303void 304ListS<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 328template<class T> 329class SetLS { 330public: 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 337 unsigned length() const 338 { return list.length(); } 339 340 void clear() 341 { list.clear(); } 342 343 class Vix { 344 public: 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 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 372 Vix first() const 373 { return Vix(this, list.first()); } 374 void next(Vix& x) const 375 { check(x); 376 list.next(x.vix); } 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 381protected: 382 ListS<T> list; 383 384private: 385 void check(const Vix& x) const 386 { if (this != x.owner) 387 ::abort(); } 388}; 389 390 391template<class T> 392SetLS<T>::SetLS(): 393 394 395 396list() 397 398{ } 399 400template<class T> 401void 402SetLS<T>::add(const T& item) 403{ 404 if ( ! contains(item) ) { 405 406 407 408 list.append(item); 409 410 } 411} 412 413template<class T> 414bool 415SetLS<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 433class test { 434public: 435 test(): value(0) 436 { } 437 test(int v): value(v) 438 { } 439 440 void print(ostream& out) const 441 { out << value; } 442 443 friend int operator==(const test& a, const test& b); 444private: 445 int value; 446}; 447 448int 449operator==(const test& a, const test& b) 450{ 451 return a.value == b.value; 452} 453 454ostream& 455operator<<(ostream& o, const test& t) 456{ 457 t.print(o); 458 return o; 459} 460 461typedef SetLS<test> SLS; 462 463static ostream& 464operator<<(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 481SLS gsls; 482const SLS gcsls; 483 484void 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 545int main() 546{ 547 cout << "PASS" << endl; 548} 549 550template class ListS<test>; 551