|
|
1.1 root 1: #ifndef listdeclare
2: #ifndef GENERICH
3: #include <generic.h>
4: #endif
5: #include <stream.h>
6:
7: #ifndef TRUE
8: #define FALSE 0
9: #define TRUE (!FALSE)
10: #endif
11:
12: #ifndef NULL
13: #define NULL 0
14: #endif
15:
16: #ifndef BIT_DEFINED
17: #define BIT_DEFINED
18: typedef int bit;
19: #endif
20:
21: struct lnk {
22: lnk* nxt;
23: lnk* prv;
24: void init(lnk* p, lnk* s) { prv = p; nxt = s; }
25: lnk() {}
26: ~lnk() {}
27: };
28: struct LstHead {
29: lnk *t; // tail
30: lnk *h() { return t ? t->nxt : 0; }
31: int sz;
32: lnk *cache; // a recently retrieved link
33: int cacheNo; // its index or garbage if cache == NULL
34: int refCount;
35: LstHead() { sz = 0; cache = t = NULL; }
36: virtual ~LstHead();
37: void insert(lnk*); // used by put() and unget()
38: void unget(lnk* nl) { insert(nl); cacheNo++; }
39: void put(lnk* nl) { insert(nl); t = nl; }
40: lnk* get();
41: lnk* unput();
42: lnk* getAt(int);
43: };
44: struct lstiter;
45: struct List {
46: friend lstiter;
47: lstiter *fI;
48: LstHead *it;
49: virtual void sepWork();
50: void separate() { if (it->refCount > 1) sepWork(); }
51: int length() { return it->sz; }
52: List() { fI = NULL; }
53: List(List& x) { fI = NULL; it = x.it; it->refCount++; }
54: ~List();
55: lnk* tail() { return it->t; }
56: lnk* head() { return it->h(); }
57: lstiter* firstIt() { return fI; }
58: void newIt(lstiter*, int=0);
59: void removeIt(lstiter*);
60: operator void*() { return length() ? this : 0; }
61: List& operator=(List&);
62: List& unget(lnk*);
63: List& put(lnk*);
64: lnk* get();
65: lnk* unput();
66: };
67: struct lstiter {
68: friend List;
69: lnk *pred;
70: List *aList;
71: lstiter *nextIt;
72: int index;
73: lstiter(List&, int =0);
74: lstiter(lstiter&);
75: ~lstiter();
76: List *theList() { return aList; }
77: lstiter& operator=(lstiter&);
78: bit operator==(lstiter& oo) {
79: return aList == oo.aList &&
80: index == oo.index; }
81: bit atEnd() { return index == aList->length(); }
82: bit r_atEnd() { return index == 0 ; }
83: lnk* next();
84: lnk* r_next();
85: lnk* peek();
86: lnk* r_peek();
87: void insert(lnk*);
88: void r_insert(lnk*);
89: lnk* remove();
90: lnk* r_remove();
91: void reset(int =0);
92: void r_reset(int i=0) { reset(aList->length() - i); }
93: };
94:
95: extern "C" {
96: extern int abort();
97: }
98:
99: #define lnnk(type) name2(type,lnnk)
100: #define list(type) name2(type,_list)
101: #define ListHead(type) name2(type,ListHead)
102: #define listiterator(type) name2(type,_list_iterator)
103: #define listsubitem(type) name2(type,listsubitem)
104: #define plist(type) name2(type,P_list)
105: #define plistiterator(type) name2(type,P_list_iterator)
106: #define plistsubitem(type) name2(type,Plistsubitem)
107: #define CMPF(type) name2(type,CMPFN)
108: #define CMPFP(type) name2(type,CMPFNP)
109:
110: #define listdeclare(type) \
111: extern GPT errorhandler(list,type); \
112: extern GPT set_handler(list,type,GPT); \
113: extern GPT errorhandler(listiterator,type); \
114: extern GPT set_handler(listiterator,type,GPT); \
115: class list(type); \
116: class lnnk(type); \
117: class ListHead(type); \
118: class listiterator(type); \
119: class listsubitem(type); \
120: typedef int (*CMPF(type))(type&, type&); \
121: ostream& operator<<(ostream&, list(type)&); \
122: class lnnk(type) : public lnk { \
123: friend ListHead(type); \
124: friend list(type); \
125: friend listsubitem(type); \
126: friend listiterator(type); \
127: friend ostream& operator<<(ostream&, list(type)&); \
128: friend void voidP_list_sort_internal(voidP_list&, CMPF(voidP)); \
129: type val; \
130: lnnk(type)(type& pp) : val(pp) {} \
131: ~lnnk(type)() {} \
132: }; \
133: class ListHead(type) : public LstHead { \
134: friend list(type); \
135: ListHead(type)() {} \
136: ~ListHead(type)(); \
137: lnnk(type) *tail() { return (lnnk(type)*)t; } \
138: lnnk(type) *head() { return (lnnk(type)*)h(); } \
139: bit firstX(type&); \
140: bit lastX(type&); \
141: }; \
142: class list(type) : public List { \
143: lnnk(type) *tail() { return (lnnk(type)*)List::tail(); } \
144: lnnk(type) *head() { return (lnnk(type)*)List::head(); } \
145: void init() { it = new ListHead(type); it->refCount = 1; } \
146: void sepWork(); \
147: public: \
148: friend ostream& operator<<(ostream&, list(type)&); \
149: friend void voidP_list_sort_internal(voidP_list&, CMPF(voidP)); \
150: list(type)() { init(); } \
151: list(type)(list(type)& x) : (x) {} \
152: ~list(type)() {} \
153: operator void*() { return length() ? this : 0; } \
154: bit operator==(list(type)&); \
155: bit operator!=(list(type)& x) { return !(*this == x); } \
156: list(type)& operator=(list(type)& ll) { return (list(type)&) \
157: (*(List*)this = (List&)ll); } \
158: list(type)& put(type &x) { return (list(type)&) \
159: List::put(new lnnk(type)(x)); } \
160: list(type)& put(list(type)&); /* append */ \
161: list(type)& operator+=(list(type)& oo) { return put(oo); } \
162: list(type)& operator+=(type& t) { return put(t); } \
163: list(type) operator+(list(type)& ll) { list(type) ans = *this; \
164: ans += ll; return ans; } \
165: list(type) operator+(type& t) { list(type) ans = *this; \
166: ans += t; return ans; } \
167: bit unputX(type &t); \
168: bit unput(); \
169: bit getX(type&); /* get */ \
170: bit get(); /* get */ \
171: list(type)& unget(type &x) { return (list(type)&) \
172: List::unget(new lnnk(type)(x)); } \
173: list(type)& unget(list(type)&); /* prepend */ \
174: bit firstX(type& t) { return \
175: ((ListHead(type)*)it)->firstX(t); } \
176: bit lastX(type& t) { return \
177: ((ListHead(type)*)it)->lastX(t); } \
178: /* getAt(0) returns the head of the list */ \
179: type getAt(int ii) { return ((lnnk(type)*)it->getAt(ii))->val; } \
180: inline listsubitem(type) operator[](unsigned ii); \
181: list(type)(type& x) { init(); put(x); } \
182: list(type)(type& x, type& y) { init(); put(x); put(y); } \
183: list(type)(type& x, type& y, type& z) { init(); put(x); put(y); \
184: put(z); } \
185: list(type)(type& x, type& y, type& z, type& w) { init(); \
186: put(x); put(y); put(z); put(w); } \
187: void sort(CMPF(type)); \
188: }; \
189: class listiterator(type) : public lstiter { \
190: friend listsubitem(type); \
191: friend list(type); \
192: public: \
193: listiterator(type)(list(type)& a, int i=0) : (*(List*)&a, i) {} \
194: listiterator(type)(listiterator(type)& a) : (*(lstiter*)&a) {} \
195: ~listiterator(type)() {} \
196: listiterator(type)& operator=(listiterator(type)& a) { return \
197: (listiterator(type)&)(*(lstiter*)this = (lstiter&)a); } \
198: bit nextX(type&); \
199: bit nextX(type*&); \
200: bit next() { return lstiter::next() != 0; } \
201: bit r_nextX(type&); \
202: bit r_nextX(type*&); \
203: bit r_next() { return lstiter::r_next() != 0; } \
204: bit peekX(type&); \
205: bit peekX(type*&); \
206: bit peek() { return !atEnd(); } \
207: bit r_peekX(type&); \
208: bit r_peekX(type*&); \
209: bit r_peek() { return !r_atEnd(); } \
210: /* remove -- deletes current from list */ \
211: bit remove(); \
212: bit r_remove(); \
213: bit removeX(type&); \
214: bit r_removeX(type&); \
215: /* insert -- put it at the left of the pointer */ \
216: void insert(type& x) { lstiter::insert(new lnnk(type)(x)); } \
217: void r_insert(type& x) { lstiter::r_insert(new lnnk(type)(x)); } \
218: bit replace(type&); \
219: bit r_replace(type&); \
220: }; \
221: class listsubitem(type) : public listiterator(type) { \
222: public: \
223: listsubitem(type)(list(type)& t, unsigned i) : (t, i) {} \
224: listsubitem(type)(listsubitem(type)& a) : ((listiterator(type)&)a) {} \
225: ~listsubitem(type)() {} \
226: type& operator=(type& x) { r_replace(x); return x; } \
227: operator type(); \
228: }; \
229: inline listsubitem(type) \
230: list(type)::operator[](unsigned ii) \
231: { \
232: return listsubitem(type)(*this, ii); \
233: }
234:
235: typedef void* voidP;
236: listdeclare(voidP)
237:
238: #define plistdeclare(type) \
239: extern GPT errorhandler(Plist,type); \
240: extern GPT set_handler(Plist,type,GPT); \
241: extern GPT errorhandler(Plistiterator,type); \
242: extern GPT set_handler(Plistiterator,type,GPT); \
243: class plist(type); \
244: typedef int (*CMPFP(type))(type*&, type*&); \
245: ostream& operator<<(ostream&, plist(type)&); \
246: class plistiterator(type); \
247: class plistsubitem(type); \
248: class plist(type) : public voidP_list { \
249: public: \
250: friend ostream& operator<<(ostream&, plist(type)&); \
251: plist(type)() {} \
252: plist(type)(type* x) : ((voidP) x) {} \
253: plist(type)(type* x, type* y) : ((voidP) x, (voidP) y) {} \
254: plist(type)(type* x, type* y, type* z) : \
255: ((voidP) x, (voidP) y, (voidP) z) {} \
256: plist(type)(type* x, type* y, type* z, type* w) : \
257: ((voidP) x, (voidP) y, (voidP) z, (voidP) w) {} \
258: plist(type)(plist(type)& ll) : ((voidP_list&) ll) {} \
259: ~plist(type)() {} \
260: operator void*() { return voidP_list::operator void*(); } \
261: bit operator==(plist(type)& ll) { return ((voidP_list&)*this == \
262: (voidP_list&)ll); } \
263: plist(type)& operator=(plist(type)& ll) { return (plist(type)&) \
264: ((voidP_list&)*this = (voidP_list&)ll); } \
265: plist(type) operator+(plist(type)& ll) { \
266: return (plist(type)&)((voidP_list&)*this + (voidP_list&)ll); } \
267: plist(type) operator+(type* t) { \
268: return (plist(type)&) ((voidP_list&)*this + (voidP)t); } \
269: plist(type)& put(type *t) { return (plist(type)&) \
270: voidP_list::put((voidP)t); } \
271: plist(type)& put(plist(type)& ll) { return (plist(type)&) \
272: voidP_list::put((voidP_list&)ll); } \
273: plist(type)& operator+=(plist(type)& oo) { return put(oo); } \
274: plist(type)& operator+=(type* t) { return put(t); } \
275: bit unputX(type *&t) { return voidP_list::unputX((voidP&)t); } \
276: bit unput() { return voidP_list::unput(); } \
277: bit getX(type *&t) { return voidP_list::getX((voidP&)t); } \
278: bit get() { return voidP_list::get(); } \
279: plist(type)& unget(type *x) { return (plist(type)&) \
280: voidP_list::unget((voidP)x); } \
281: plist(type)& unget(plist(type)& ll) { return (plist(type)&) \
282: voidP_list::unget((voidP_list&)ll); } \
283: bit firstX(type *&t) { return voidP_list::firstX((voidP&)t); } \
284: bit lastX(type *&t) { return voidP_list::lastX((voidP&)t); } \
285: /* getAt(0) returns the head of the list */ \
286: type* getAt(int ii) { return (type *) voidP_list::getAt(ii); } \
287: inline plistsubitem(type) operator[](unsigned ii); \
288: void sort(CMPFP(type) pf) { voidP_list::sort((CMPF(voidP))pf); } \
289: }; \
290: class plistiterator(type) : public voidP_list_iterator { \
291: public: \
292: plistiterator(type)(plist(type)& a, int i=0) : \
293: ((voidP_list&)a, i) {} \
294: plistiterator(type)(plistiterator(type)& a) : \
295: ((voidP_list_iterator&)a) {} \
296: ~plistiterator(type)() {} \
297: plistiterator(type)& operator=(plistiterator(type)& a) { return \
298: (plistiterator(type)&)((voidP_list_iterator&)*this = \
299: (voidP_list_iterator&)a); } \
300: bit nextX(type *&t) { return \
301: voidP_list_iterator::nextX((voidP&)t); } \
302: bit nextX(type **&t) { return \
303: voidP_list_iterator::nextX((voidP*&)t); } \
304: bit next() { return voidP_list_iterator::next(); } \
305: bit r_nextX(type *&t) { return \
306: voidP_list_iterator::r_nextX((voidP&)t); } \
307: bit r_nextX(type **&t) { return \
308: voidP_list_iterator::r_nextX((voidP*&)t); } \
309: bit r_next() { return voidP_list_iterator::r_next(); } \
310: bit peekX(type *&t) { return \
311: voidP_list_iterator::peekX((voidP&)t); } \
312: bit peekX(type **&t) { return \
313: voidP_list_iterator::peekX((voidP*&)t); } \
314: bit peek() { return voidP_list_iterator::peek(); } \
315: bit r_peekX(type *&t) { return \
316: voidP_list_iterator::r_peekX((voidP&)t); } \
317: bit r_peekX(type **&t) { return \
318: voidP_list_iterator::r_peekX((voidP*&)t); } \
319: bit r_peek() { return voidP_list_iterator::r_peek(); } \
320: bit remove() { return voidP_list_iterator::remove(); } \
321: bit r_remove() { return voidP_list_iterator::r_remove(); } \
322: bit removeX(type *&x) { return \
323: voidP_list_iterator::removeX((voidP&)x); } \
324: bit r_removeX(type *&x) { return \
325: voidP_list_iterator::r_removeX((voidP&)x); } \
326: void insert(type *&x) { voidP_list_iterator::insert((voidP&)x); } \
327: void r_insert(type *&x) { \
328: voidP_list_iterator::r_insert((voidP&)x); } \
329: void replace(type *x) { voidP_list_iterator::replace((voidP)x); } \
330: void r_replace(type *x) { \
331: voidP_list_iterator::r_replace((voidP)x); } \
332: }; \
333: class plistsubitem(type) : public voidPlistsubitem { \
334: public: \
335: plistsubitem(type)(plist(type)& t, int i) : ((voidP_list&)t, i) {} \
336: plistsubitem(type)(plistsubitem(type)&ll) : ((voidPlistsubitem&)ll){} \
337: ~plistsubitem(type)() {} \
338: type*& operator=(type *&t) { return \
339: (type*&) ((voidPlistsubitem&)*this =(voidP&)t); } \
340: operator type*() { return (type*) voidPlistsubitem::operator voidP(); } \
341: }; \
342: inline \
343: plistsubitem(type) \
344: plist(type)::operator[](unsigned ii) \
345: { \
346: return plistsubitem(type)(*this, ii); \
347: }
348:
349:
350: #define listimplement(type) \
351: GPT errorhandler(list,type) = genericerror; \
352: GPT errorhandler(listiterator,type) = genericerror; \
353: bit \
354: ListHead(type)::firstX(type& v) \
355: { \
356: lnnk(type) *aLink = (lnnk(type) *)LstHead::h(); \
357: return aLink ? (v = aLink->val, TRUE) : FALSE; \
358: } \
359: bit \
360: ListHead(type)::lastX(type& v) \
361: { \
362: lnnk(type) *aLink = (lnnk(type) *)LstHead::t; \
363: return aLink ? (v = aLink->val, TRUE) : FALSE; \
364: } \
365: ListHead(type)::~ListHead(type)() \
366: { \
367: lnnk(type) *temp; \
368: while (temp = (lnnk(type) *)LstHead::get()) \
369: delete temp; \
370: } \
371: bit \
372: listiterator(type)::remove() \
373: { \
374: lnnk(type) *aLink = (lnnk(type) *)lstiter::remove(); \
375: return aLink ? (delete aLink, TRUE) : FALSE; \
376: } \
377: bit \
378: listiterator(type)::removeX(type &x) \
379: { \
380: lnnk(type) *aLink = (lnnk(type) *)lstiter::remove(); \
381: return aLink ? (x = aLink->val, delete aLink, TRUE) : FALSE; \
382: } \
383: bit \
384: listiterator(type)::r_remove() \
385: { \
386: lnnk(type) *aLink = (lnnk(type) *)lstiter::r_remove(); \
387: return aLink ? (delete aLink, TRUE) : FALSE; \
388: } \
389: bit \
390: listiterator(type)::r_removeX(type &x) \
391: { \
392: lnnk(type) *aLink = (lnnk(type) *)lstiter::r_remove(); \
393: return aLink ? (x = aLink->val, delete aLink, TRUE) : FALSE; \
394: } \
395: bit \
396: listiterator(type)::nextX(type& t) \
397: { \
398: return atEnd() ? FALSE : \
399: (t = ((lnnk(type)*)lstiter::next())->val, TRUE); \
400: } \
401: bit \
402: listiterator(type)::nextX(type*& t) \
403: { \
404: return atEnd() ? FALSE : \
405: (theList()->separate(), t = &((lnnk(type)*)lstiter::next())->val, \
406: TRUE); \
407: } \
408: bit \
409: listiterator(type)::r_nextX(type& t) \
410: { \
411: return r_atEnd() ? FALSE : \
412: (t = ((lnnk(type)*)lstiter::r_next())->val, TRUE); \
413: } \
414: bit \
415: listiterator(type)::r_nextX(type*& t) \
416: { \
417: return r_atEnd() ? FALSE : \
418: (theList()->separate(), t = &((lnnk(type)*)lstiter::r_next())->val, \
419: TRUE); \
420: } \
421: bit \
422: listiterator(type)::r_peekX(type& t) \
423: { \
424: return r_atEnd() ? FALSE : \
425: (t = ((lnnk(type)*)lstiter::r_peek())->val, TRUE); \
426: } \
427: bit \
428: listiterator(type)::r_peekX(type*& t) \
429: { \
430: return r_atEnd() ? FALSE : \
431: (theList()->separate(), t = &((lnnk(type)*)lstiter::r_peek())->val, \
432: TRUE); \
433: } \
434: bit \
435: listiterator(type)::peekX(type& t) \
436: { \
437: return atEnd() ? FALSE : \
438: (t = ((lnnk(type)*)lstiter::peek())->val, TRUE); \
439: } \
440: bit \
441: listiterator(type)::peekX(type*& t) \
442: { \
443: return atEnd() ? FALSE : \
444: (theList()->separate(), t = &((lnnk(type)*)lstiter::peek())->val, \
445: TRUE); \
446: } \
447: bit \
448: listiterator(type)::replace(type& x) \
449: { \
450: return r_atEnd() ? FALSE : \
451: (theList()->separate(), ((lnnk(type)*)lstiter::r_peek())->val = x, \
452: TRUE); \
453: } \
454: bit \
455: listiterator(type)::r_replace(type& x) \
456: { \
457: return atEnd() ? FALSE : \
458: (theList()->separate(), ((lnnk(type)*)lstiter::peek())->val = x, \
459: TRUE); \
460: } \
461: bit \
462: list(type)::operator==(list(type)& x) \
463: { \
464: if ( length() != x.length() ) \
465: return FALSE; \
466: if ( length() == 0 ) \
467: return TRUE; \
468: lnnk(type) *mine = (lnnk(type) *)head(); \
469: lnnk(type) *yours = (lnnk(type) *)x.head(); \
470: for ( int i = length(); i--; ) \
471: if ( mine->val == yours->val ) { \
472: mine = (lnnk(type) *)mine->nxt; \
473: yours = (lnnk(type) *)yours->nxt; \
474: } else \
475: return FALSE; \
476: return TRUE; \
477: } \
478: bit \
479: list(type)::getX(type& t) \
480: { \
481: lnnk(type) *aLink = (lnnk(type) *)List::get(); \
482: return aLink ? (t = aLink->val, delete aLink, TRUE) : FALSE; \
483: } \
484: bit \
485: list(type)::get() \
486: { \
487: lnnk(type) *aLink = (lnnk(type) *)List::get(); \
488: return aLink ? (delete aLink, TRUE) : FALSE; \
489: } \
490: bit \
491: list(type)::unputX(type& t) \
492: { \
493: lnnk(type) *aLink = (lnnk(type) *)List::unput(); \
494: return aLink ? (t = aLink->val, delete aLink, TRUE) : FALSE; \
495: } \
496: bit \
497: list(type)::unput() \
498: { \
499: lnnk(type) *aLink = (lnnk(type) *)List::unput(); \
500: return aLink ? (delete aLink, TRUE) : FALSE; \
501: } \
502: list(type)& \
503: list(type)::put(list(type)& a) \
504: { \
505: if (a.length()) { \
506: type t; \
507: listiterator(type) ita(a); \
508: while (ita.nextX(t)) \
509: put(t); \
510: } \
511: return *this; \
512: } \
513: list(type)& \
514: list(type)::unget(list(type)& a) \
515: { \
516: if (a.length()) { \
517: type t; \
518: listiterator(type) ita(a); \
519: ita.r_reset(); \
520: while (ita.r_nextX(t)) \
521: unget(t); \
522: } \
523: return *this; \
524: } \
525: listsubitem(type)::operator type() \
526: { \
527: type t; \
528: peekX(t); \
529: return t; \
530: } \
531: void \
532: list(type)::sepWork() \
533: { \
534: it->refCount--; \
535: ListHead(type) *newLst = new ListHead(type); \
536: if (tail()) { \
537: for (lnnk(type) *oldLnk = (lnnk(type) *)head();; \
538: oldLnk = (lnnk(type) *)oldLnk->nxt) { \
539: lnnk(type) *newLnk; \
540: newLst->put(newLnk = new lnnk(type)(oldLnk->val)); \
541: /* only be one or two listiterators (I hope) */ \
542: for (listiterator(type) *anIt = \
543: (listiterator(type) *)firstIt(); anIt; \
544: anIt = (listiterator(type) *)anIt->nextIt) { \
545: if (anIt->pred == oldLnk) { \
546: anIt->pred = newLnk; \
547: } \
548: } \
549: if ( oldLnk == tail() ) \
550: break; \
551: } \
552: } \
553: it = newLst; \
554: it->refCount = 1; \
555: } \
556: void \
557: list(type)::sort(CMPF(type) cmp) \
558: { \
559: if (length() < 2) return; \
560: separate(); \
561: voidP_list_sort_internal(*(voidP_list*)this, (CMPF(voidP))cmp); \
562: for (listiterator(type) *anIt = \
563: (listiterator(type) *)firstIt(); anIt; \
564: anIt = (listiterator(type) *)anIt->nextIt) \
565: anIt->reset(); \
566: }
567:
568: #define listoutimplement(type) \
569: ostream& \
570: operator<<(ostream& oo, list(type)& ll) \
571: { \
572: oo<<"("; \
573: if ( ll.length() ) { \
574: listiterator(type) it(ll); \
575: type t; \
576: it.nextX(t); \
577: oo<<t; \
578: while (it.nextX(t)) \
579: oo << " " << t; \
580: } else \
581: oo<<"EMPTYLIST"; \
582: oo<<")"; \
583: return oo; \
584: }
585:
586: #endif
587:
588: #define plistimplement(type) \
589: GPT errorhandler(Plist,type) = genericerror; \
590: GPT errorhandler(Plistiterator,type) = genericerror;
591:
592: #define plistoutimplement(type) \
593: ostream& operator<<(ostream& oo, plist(type)& ll) \
594: { \
595: oo<<"("; \
596: if ( ll.length() ) { \
597: plistiterator(type) it(ll); \
598: type *t; \
599: it.nextX(t); \
600: oo<<t; \
601: while (it.nextX(t)) \
602: oo << " " << t; \
603: } else \
604: oo<<"EMPTYLIST"; \
605: oo<<")"; \
606: return oo; \
607: }
608:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.