|
|
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&) { fI = NULL; }
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 int abort(...);
96:
97: #define lnnk(type) name2(type,lnnk)
98: #define list(type) name2(type,_list)
99: #define ListHead(type) name2(type,ListHead)
100: #define listiterator(type) name2(type,_list_iterator)
101: #define listsubitem(type) name2(type,listsubitem)
102: #define plist(type) name2(type,P_list)
103: #define plistiterator(type) name2(type,P_list_iterator)
104: #define plistsubitem(type) name2(type,Plistsubitem)
105: #define CMPF(type) name2(type,CMPFN)
106: #define CMPFP(type) name2(type,CMPFNP)
107:
108: #define listdeclare(type) \
109: extern GPT errorhandler(list,type); \
110: extern GPT set_handler(list,type,GPT); \
111: extern GPT errorhandler(listiterator,type); \
112: extern GPT set_handler(listiterator,type,GPT); \
113: class list(type); \
114: class lnnk(type); \
115: class ListHead(type); \
116: class listiterator(type); \
117: class listsubitem(type); \
118: typedef int (*CMPF(type))(type&, type&); \
119: ostream& operator<<(ostream&, list(type)&); \
120: class lnnk(type) : public lnk { \
121: friend ListHead(type); \
122: friend list(type); \
123: friend listsubitem(type); \
124: friend listiterator(type); \
125: friend ostream& operator<<(ostream&, list(type)&); \
126: friend void voidP_list_sort_internal(voidP_list&, CMPF(voidP)); \
127: type val; \
128: lnnk(type)(type& pp) : val(pp) {} \
129: ~lnnk(type)() {} \
130: }; \
131: class ListHead(type) : public LstHead { \
132: friend list(type); \
133: ListHead(type)() {} \
134: ~ListHead(type)(); \
135: lnnk(type) *tail() { return (lnnk(type)*)t; } \
136: lnnk(type) *head() { return (lnnk(type)*)h(); } \
137: bit firstX(type&); \
138: bit lastX(type&); \
139: }; \
140: class list(type) : public List { \
141: lnnk(type) *tail() { return (lnnk(type)*)List::tail(); } \
142: lnnk(type) *head() { return (lnnk(type)*)List::head(); } \
143: void init() { it = new ListHead(type); it->refCount = 1; } \
144: void sepWork(); \
145: public: \
146: friend ostream& operator<<(ostream&, list(type)&); \
147: friend void voidP_list_sort_internal(voidP_list&, CMPF(voidP)); \
148: list(type)() { init(); } \
149: list(type)(list(type)& x) : (x) { it = x.it; it->refCount++; } \
150: ~list(type)() {} \
151: operator void*() { return length() ? this : 0; } \
152: bit operator==(list(type)&); \
153: bit operator!=(list(type)& x) { return !(*this == x); } \
154: list(type)& operator=(list(type)& ll) { return *(list(type)*) \
155: &(*(List*)this = *(List*)&ll); } \
156: list(type)& put(type &x) { return (list(type)&) \
157: List::put(new lnnk(type)(x)); } \
158: list(type)& put(list(type)&); /* append */ \
159: list(type)& operator+=(list(type)& oo) { return put(oo); } \
160: list(type)& operator+=(type& t) { return put(t); } \
161: list(type) operator+(list(type)& ll) { list(type) ans = *this; \
162: ans += ll; return ans; } \
163: list(type) operator+(type& t) { list(type) ans = *this; \
164: ans += t; return ans; } \
165: bit unputX(type &t); \
166: bit unput(); \
167: bit getX(type&); /* get */ \
168: bit get(); /* get */ \
169: list(type)& unget(type &x) { return (list(type)&) \
170: List::unget(new lnnk(type)(x)); } \
171: list(type)& unget(list(type)&); /* prepend */ \
172: bit firstX(type& t) { return \
173: ((ListHead(type)*)it)->firstX(t); } \
174: bit lastX(type& t) { return \
175: ((ListHead(type)*)it)->lastX(t); } \
176: /* getAt(0) returns the head of the list */ \
177: type getAt(int ii) { return ((lnnk(type)*)it->getAt(ii))->val; } \
178: inline listsubitem(type)& operator[](int ii); \
179: list(type)(type& x) { init(); put(x); } \
180: list(type)(type& x, type& y) { init(); put(x); put(y); } \
181: list(type)(type& x, type& y, type& z) { init(); put(x); put(y); \
182: put(z); } \
183: list(type)(type& x, type& y, type& z, type& w) { init(); \
184: put(x); put(y); put(z); put(w); } \
185: void sort(CMPF(type)); \
186: }; \
187: class listiterator(type) : public lstiter { \
188: friend listsubitem(type); \
189: friend list(type); \
190: public: \
191: listiterator(type)(list(type)& a, int i=0) : (*(List*)&a, i) {} \
192: listiterator(type)(listiterator(type)& a) : (*(lstiter*)&a) {} \
193: ~listiterator(type)() {} \
194: listiterator(type)& operator=(listiterator(type)& a) { return \
195: *(listiterator(type)*) \
196: &(*(lstiter*)this = *(lstiter*)&a); } \
197: bit nextX(type&); \
198: bit nextX(type*&); \
199: bit next() { return lstiter::next() != 0; } \
200: bit r_nextX(type&); \
201: bit r_nextX(type*&); \
202: bit r_next() { return lstiter::r_next() != 0; } \
203: bit peekX(type&); \
204: bit peekX(type*&); \
205: bit peek() { return !atEnd(); } \
206: bit r_peekX(type&); \
207: bit r_peekX(type*&); \
208: bit r_peek() { return !r_atEnd(); } \
209: /* remove -- deletes current from list */ \
210: bit remove(); \
211: bit r_remove(); \
212: bit removeX(type&); \
213: bit r_removeX(type&); \
214: /* insert -- put it at the left of the pointer */ \
215: void insert(type& x) { lstiter::insert(new lnnk(type)(x)); } \
216: void r_insert(type& x) { lstiter::r_insert(new lnnk(type)(x)); } \
217: bit replace(type&); \
218: bit r_replace(type&); \
219: }; \
220: class listsubitem(type) : public listiterator(type) { \
221: public: \
222: listsubitem(type)(list(type)& t, int i) : (t, i) {} \
223: listsubitem(type)(listsubitem(type)& a) : (*(listiterator(type)*)&a) {} \
224: ~listsubitem(type)() {} \
225: type& operator=(type& x) { r_replace(x); return x; } \
226: operator type(); \
227: }; \
228: inline listsubitem(type)& \
229: list(type)::operator[](unsigned ii) \
230: { \
231: return *new listsubitem(type)(*this, ii); \
232: }
233:
234: typedef void* voidP;
235: listdeclare(voidP)
236:
237: #define plistdeclare(type) \
238: extern GPT errorhandler(Plist,type); \
239: extern GPT set_handler(Plist,type,GPT); \
240: extern GPT errorhandler(Plistiterator,type); \
241: extern GPT set_handler(Plistiterator,type,GPT); \
242: class plist(type); \
243: typedef int (*CMPFP(type))(type*&, type*&); \
244: ostream& operator<<(ostream&, plist(type)&); \
245: class plistiterator(type); \
246: class plistsubitem(type); \
247: class plist(type) : public voidP_list { \
248: public: \
249: friend ostream& operator<<(ostream&, plist(type)&); \
250: plist(type)() {} \
251: plist(type)(type* x) : ((voidP) x) {} \
252: plist(type)(type* x, type* y) : ((voidP) x, (voidP) y) {} \
253: plist(type)(type* x, type* y, type* z) : \
254: ((voidP) x, (voidP) y, (voidP) z) {} \
255: plist(type)(type* x, type* y, type* z, type* w) : \
256: ((voidP) x, (voidP) y, (voidP) z, (voidP) w) {} \
257: plist(type)(plist(type)& ll) : ((voidP_list&) ll) {} \
258: ~plist(type)() {} \
259: operator void*() { return voidP_list::operator void*(); } \
260: bit operator==(plist(type)& ll) { return ((voidP_list&)*this == \
261: (voidP_list&)ll); } \
262: plist(type)& operator=(plist(type)& ll) { return (plist(type)&) \
263: ((voidP_list&)*this = (voidP_list&)ll); } \
264: plist(type) operator+(plist(type)& ll) { \
265: return (plist(type)&)((voidP_list&)*this + (voidP_list&)ll); } \
266: plist(type) operator+(type* t) { \
267: return (plist(type)&) ((voidP_list&)*this + (voidP)t); } \
268: plist(type)& put(type *t) { return (plist(type)&) \
269: voidP_list::put((voidP)t); } \
270: plist(type)& put(plist(type)& ll) { return (plist(type)&) \
271: voidP_list::put((voidP_list&)ll); } \
272: plist(type)& operator+=(plist(type)& oo) { return put(oo); } \
273: plist(type)& operator+=(type* t) { return put(t); } \
274: bit unputX(type *&t) { return voidP_list::unputX((voidP&)t); } \
275: bit unput() { return voidP_list::unput(); } \
276: bit getX(type *&t) { return voidP_list::getX((voidP&)t); } \
277: bit get() { return voidP_list::get(); } \
278: plist(type)& unget(type *x) { return (plist(type)&) \
279: voidP_list::unget((voidP)x); } \
280: plist(type)& unget(plist(type)& ll) { return (plist(type)&) \
281: voidP_list::unget((voidP_list&)ll); } \
282: bit firstX(type *&t) { return voidP_list::firstX((voidP&)t); } \
283: bit lastX(type *&t) { return voidP_list::lastX((voidP&)t); } \
284: /* getAt(0) returns the head of the list */ \
285: type* getAt(int ii) { return (type *) voidP_list::getAt(ii); } \
286: inline plistsubitem(type)& operator[](int ii); \
287: void sort(CMPFP(type) pf) { voidP_list::sort((CMPF(voidP))pf); } \
288: }; \
289: class plistiterator(type) : public voidP_list_iterator { \
290: public: \
291: plistiterator(type)(plist(type)& a, int i=0) : \
292: ((voidP_list&)a, i) {} \
293: plistiterator(type)(plistiterator(type)& a) : \
294: ((voidP_list_iterator&)a) {} \
295: ~plistiterator(type)() {} \
296: plistiterator(type)& operator=(plistiterator(type)& a) { return \
297: (plistiterator(type)&)((voidP_list_iterator&)*this = \
298: (voidP_list_iterator&)a); } \
299: bit nextX(type *&t) { return \
300: voidP_list_iterator::nextX((voidP&)t); } \
301: bit nextX(type **&t) { return \
302: voidP_list_iterator::nextX((voidP*&)t); } \
303: bit next() { return voidP_list_iterator::next(); } \
304: bit r_nextX(type *&t) { return \
305: voidP_list_iterator::r_nextX((voidP&)t); } \
306: bit r_nextX(type **&t) { return \
307: voidP_list_iterator::r_nextX((voidP*&)t); } \
308: bit r_next() { return voidP_list_iterator::r_next(); } \
309: bit peekX(type *&t) { return \
310: voidP_list_iterator::peekX((voidP&)t); } \
311: bit peekX(type **&t) { return \
312: voidP_list_iterator::peekX((voidP*&)t); } \
313: bit peek() { return voidP_list_iterator::peek(); } \
314: bit r_peekX(type *&t) { return \
315: voidP_list_iterator::r_peekX((voidP&)t); } \
316: bit r_peekX(type **&t) { return \
317: voidP_list_iterator::r_peekX((voidP*&)t); } \
318: bit r_peek() { return voidP_list_iterator::r_peek(); } \
319: bit remove() { return voidP_list_iterator::remove(); } \
320: bit r_remove() { return voidP_list_iterator::r_remove(); } \
321: bit removeX(type *&x) { return \
322: voidP_list_iterator::removeX((voidP&)x); } \
323: bit r_removeX(type *&x) { return \
324: voidP_list_iterator::r_removeX((voidP&)x); } \
325: void insert(type *&x) { voidP_list_iterator::insert((voidP&)x); } \
326: void r_insert(type *&x) { \
327: voidP_list_iterator::r_insert((voidP&)x); } \
328: void replace(type *x) { voidP_list_iterator::replace((voidP)x); } \
329: void r_replace(type *x) { \
330: voidP_list_iterator::r_replace((voidP)x); } \
331: }; \
332: class plistsubitem(type) : public voidPlistsubitem { \
333: public: \
334: plistsubitem(type)(plist(type)& t, int i) : ((voidP_list&)t, i) {} \
335: plistsubitem(type)(plistsubitem(type)&ll) : ((voidPlistsubitem&)ll){} \
336: ~plistsubitem(type)() {} \
337: type*& operator=(type *&t) { return \
338: (type*&) ((voidPlistsubitem&)*this =(voidP&)t); } \
339: operator type*() { return (type*) voidPlistsubitem::operator voidP(); } \
340: }; \
341: inline \
342: plistsubitem(type)& \
343: plist(type)::operator[](int ii) \
344: { \
345: return (plistsubitem(type)&)voidP_list::operator[](ii); \
346: }
347:
348:
349: #define listimplement(type) \
350: GPT errorhandler(list,type) = genericerror; \
351: GPT errorhandler(listiterator,type) = genericerror; \
352: bit \
353: ListHead(type)::firstX(type& v) \
354: { \
355: lnnk(type) *aLink = (lnnk(type) *)LstHead::h(); \
356: return aLink ? (v = aLink->val, TRUE) : FALSE; \
357: } \
358: bit \
359: ListHead(type)::lastX(type& v) \
360: { \
361: lnnk(type) *aLink = (lnnk(type) *)LstHead::t; \
362: return aLink ? (v = aLink->val, TRUE) : FALSE; \
363: } \
364: ListHead(type)::~ListHead(type)() \
365: { \
366: lnnk(type) *temp; \
367: while (temp = (lnnk(type) *)LstHead::get()) \
368: delete temp; \
369: } \
370: bit \
371: listiterator(type)::remove() \
372: { \
373: lnnk(type) *aLink = (lnnk(type) *)lstiter::remove(); \
374: return aLink ? (delete aLink, TRUE) : FALSE; \
375: } \
376: bit \
377: listiterator(type)::removeX(type &x) \
378: { \
379: lnnk(type) *aLink = (lnnk(type) *)lstiter::remove(); \
380: return aLink ? (x = aLink->val, delete aLink, TRUE) : FALSE; \
381: } \
382: bit \
383: listiterator(type)::r_remove() \
384: { \
385: lnnk(type) *aLink = (lnnk(type) *)lstiter::r_remove(); \
386: return aLink ? (delete aLink, TRUE) : FALSE; \
387: } \
388: bit \
389: listiterator(type)::r_removeX(type &x) \
390: { \
391: lnnk(type) *aLink = (lnnk(type) *)lstiter::r_remove(); \
392: return aLink ? (x = aLink->val, delete aLink, TRUE) : FALSE; \
393: } \
394: bit \
395: listiterator(type)::nextX(type& t) \
396: { \
397: return atEnd() ? FALSE : \
398: (t = ((lnnk(type)*)lstiter::next())->val, TRUE); \
399: } \
400: bit \
401: listiterator(type)::nextX(type*& t) \
402: { \
403: return atEnd() ? FALSE : \
404: (theList()->separate(), t = &((lnnk(type)*)lstiter::next())->val, \
405: TRUE); \
406: } \
407: bit \
408: listiterator(type)::r_nextX(type& t) \
409: { \
410: return r_atEnd() ? FALSE : \
411: (t = ((lnnk(type)*)lstiter::r_next())->val, TRUE); \
412: } \
413: bit \
414: listiterator(type)::r_nextX(type*& t) \
415: { \
416: return r_atEnd() ? FALSE : \
417: (theList()->separate(), t = &((lnnk(type)*)lstiter::r_next())->val, \
418: TRUE); \
419: } \
420: bit \
421: listiterator(type)::r_peekX(type& t) \
422: { \
423: return r_atEnd() ? FALSE : \
424: (t = ((lnnk(type)*)lstiter::r_peek())->val, TRUE); \
425: } \
426: bit \
427: listiterator(type)::r_peekX(type*& t) \
428: { \
429: return r_atEnd() ? FALSE : \
430: (theList()->separate(), t = &((lnnk(type)*)lstiter::r_peek())->val, \
431: TRUE); \
432: } \
433: bit \
434: listiterator(type)::peekX(type& t) \
435: { \
436: return atEnd() ? FALSE : \
437: (t = ((lnnk(type)*)lstiter::peek())->val, TRUE); \
438: } \
439: bit \
440: listiterator(type)::peekX(type*& t) \
441: { \
442: return atEnd() ? FALSE : \
443: (theList()->separate(), t = &((lnnk(type)*)lstiter::peek())->val, \
444: TRUE); \
445: } \
446: bit \
447: listiterator(type)::replace(type& x) \
448: { \
449: return r_atEnd() ? FALSE : \
450: (theList()->separate(), ((lnnk(type)*)lstiter::r_peek())->val = x, \
451: TRUE); \
452: } \
453: bit \
454: listiterator(type)::r_replace(type& x) \
455: { \
456: return atEnd() ? FALSE : \
457: (theList()->separate(), ((lnnk(type)*)lstiter::peek())->val = x, \
458: TRUE); \
459: } \
460: bit \
461: list(type)::operator==(list(type)& x) \
462: { \
463: if ( length() != x.length() ) \
464: return FALSE; \
465: if ( length() == 0 ) \
466: return TRUE; \
467: lnnk(type) *mine = (lnnk(type) *)head(); \
468: lnnk(type) *yours = (lnnk(type) *)x.head(); \
469: for ( int i = length(); i--; ) \
470: if ( mine->val == yours->val ) { \
471: mine = (lnnk(type) *)mine->nxt; \
472: yours = (lnnk(type) *)yours->nxt; \
473: } else \
474: return FALSE; \
475: return TRUE; \
476: } \
477: bit \
478: list(type)::getX(type& t) \
479: { \
480: lnnk(type) *aLink = (lnnk(type) *)List::get(); \
481: return aLink ? (t = aLink->val, delete aLink, TRUE) : FALSE; \
482: } \
483: bit \
484: list(type)::get() \
485: { \
486: lnnk(type) *aLink = (lnnk(type) *)List::get(); \
487: return aLink ? (delete aLink, TRUE) : FALSE; \
488: } \
489: bit \
490: list(type)::unputX(type& t) \
491: { \
492: lnnk(type) *aLink = (lnnk(type) *)List::unput(); \
493: return aLink ? (t = aLink->val, delete aLink, TRUE) : FALSE; \
494: } \
495: bit \
496: list(type)::unput() \
497: { \
498: lnnk(type) *aLink = (lnnk(type) *)List::unput(); \
499: return aLink ? (delete aLink, TRUE) : FALSE; \
500: } \
501: list(type)& \
502: list(type)::put(list(type)& a) \
503: { \
504: if (a.length()) { \
505: type t; \
506: listiterator(type) ita(a); \
507: while (ita.nextX(t)) \
508: put(t); \
509: } \
510: return *this; \
511: } \
512: list(type)& \
513: list(type)::unget(list(type)& a) \
514: { \
515: if (a.length()) { \
516: type t; \
517: listiterator(type) ita(a); \
518: ita.r_reset(); \
519: while (ita.r_nextX(t)) \
520: unget(t); \
521: } \
522: return *this; \
523: } \
524: type \
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.