1// { dg-do assemble  }
2// prms-id: 1989
3
4#define TRUE true
5#define FALSE false
6typedef void *Pix;
7
8template<class T>
9struct link {
10    T item;
11    link *next;
12    link *prev;
13
14    link(const T& t): item(t), prev(0), next(0)
15	{ }
16    link(const T& t, link<T> *p, link<T> *n): item(t), prev(p), next(n)
17	{ }
18};
19
20template<class T>
21class List_DL {
22public:
23    List_DL();
24    List_DL(const List_DL&);
25    ~List_DL();
26
27    void append(const T& item);
28    void prepend(const T& item);
29    void insert(const T& item, Pix x, bool before);
30
31    void remove(Pix& x)
32	{ T tmp; remove(x, tmp); }
33    void remove(Pix& x, T& item);
34
35    void clear();
36
37    unsigned length() const
38	{ return count; }
39
40private:
41
42    unsigned count;
43    link<T> *head;
44    link<T> *tail;
45
46public:
47    Pix first() const
48	{ return Pix(head); }
49    Pix last() const
50	{ return Pix(tail); }
51    void next(Pix& x) const
52	{ if (0 != x) x = ((link<T> *) x)->next; }
53    void prev(Pix& x) const
54	{ if (0 != x) x = ((link<T> *) x)->prev; }
55    T& operator()(Pix x) const
56	{ return ((link<T> *) x)->item; }
57};
58
59template<class T>
60List_DL<T>::List_DL():
61count(0),
62head(0)
63{ }
64
65template<class T>
66List_DL<T>::List_DL(const List_DL& other):
67count(0),
68head(0)
69{
70    for (Pix x=other.first(); 0 != x; other.next(x))
71	append(other(x));
72}
73
74template<class T>
75List_DL<T>::~List_DL()
76{
77    clear();
78}
79
80template<class T>
81void
82List_DL<T>::append(const T& item)
83{
84    count++;
85    if (0 == head) {
86	head = new link<T>(item);
87	tail = head;
88    } else {
89	tail->next = new link<T>(item, tail, 0);
90	tail = tail->next;
91    }
92}
93
94template<class T>
95void
96List_DL<T>::prepend(const T& item)
97{
98    count++;
99    if (0 == head) {
100	head = new link<T>(item);
101	tail = head;
102    } else {
103	head = new link<T>(item, 0, head);
104	if (tail == head)
105	    tail = tail->next;
106    }
107}
108
109template<class T>
110void
111List_DL<T>::insert(const T& item, Pix x, bool before = TRUE)
112{
113    link<T> *l = (link<T> *) x;
114
115    if (before) {
116	if (0 == l || l == head) {
117	    prepend(item);
118	} else {
119	    link<T> *n = new link<T>(item, l->prev, l);
120	    l->prev->next = n;
121	    l->prev = n;
122	}
123    } else {
124	if (0 == l || l == tail) {
125	    append(item);
126	} else {
127	    link<T> *n = new link<T>(item, l, l->next);
128	    l->next->prev = n;
129	    l->prev = n;
130	}
131    }
132}
133
134template<class T>
135void
136List_DL<T>::remove(Pix& x, T& item)
137{
138    link<T> *l = (link<T> *) x;
139
140    if (0 == l)
141	return;
142
143    item = l->item;
144    if (1 == count) {
145	delete head;
146	head = 0;
147	tail = 0;
148    } else {
149	// more than one item in the list
150	if (l == head) {
151	    link<T> *old = head;
152	    head = head->next;
153	    head->prev = 0;
154	    delete old;
155	} else if (l == tail) {
156	    link<T> *old = tail;
157	    tail = tail->prev;
158	    tail->next = 0;
159	    delete old;
160	} else {
161	    l->next->prev = l->prev;
162	    l->prev->next = l->next;
163	    delete l;
164	}
165    }
166}
167
168template<class T>
169void
170List_DL<T>::clear()
171{
172    link<T> *l, *succ;
173    for (l=head; 0 != l; l=succ) {
174	succ = l->next;
175	delete l;
176    }
177    head = 0;
178    tail = 0;
179}
180
181template<class T>
182class List_DLS: public List_DL<T> {
183public:
184    List_DLS(): List_DL<T>()
185	{ }
186    List_DLS(const List_DLS& other): List_DL<T>(other)
187	{ }
188
189    bool contains(const T& item) const
190	{ return search(item) != 0 ? TRUE: FALSE; }
191    Pix search(const T&) const;
192};
193
194template<class T>
195Pix
196List_DLS<T>::search(const T& item) const
197{
198    for (Pix x=this->first(); 0 != x; this->next(x)) {
199	if (item == this->operator()(x)) // { dg-error "match" } const subversion
200	    return x;
201    }
202    return 0;
203}
204
205template<class T>
206class List_DLSp: public List_DL<T> {
207public:
208    List_DLSp(): List_DL<T>()
209	{ }
210    List_DLSp(const List_DLSp& other): List_DL<T>(other)
211	{ }
212
213    bool contains(const T& item) const
214#ifndef INTERNAL_ERROR
215	;
216#else
217	{ return search(item) != 0 ? TRUE: FALSE; }
218#endif
219    Pix search(const T&) const;
220};
221
222template<class T>
223bool
224List_DLSp<T>::contains(const T& item) const
225{
226    for (Pix x=this->first(); 0 != x; this->next(x)) {
227        if (*item == *(this->operator()(x)))
228	    return TRUE;
229    }
230    return FALSE;
231}
232
233template<class T>
234class Set {
235public:
236    Set();
237    Set(const Set& other);
238
239    virtual void add(const T& item);
240
241    void remove(const T& item)
242	{ Pix x = search(item); remove(x); }
243    void remove(Pix& x)
244	{ T tmp; remove(x, tmp); }
245    virtual void remove(Pix& x, T& item);
246
247    virtual void clear();
248
249    virtual bool contains(const T&) const;
250    virtual Pix search(const T&) const;
251
252    virtual unsigned length() const;
253
254    virtual Pix first() const;
255    virtual void next(Pix& x) const;
256    virtual T& operator()(Pix x) const;
257};
258
259template<class T>
260Set<T>::Set()
261{ }
262
263template<class T>
264Set<T>::Set(const Set& other)
265{ }
266
267
268template<class T>
269class Set_DL: public List_DLS<T> {
270public:
271    Set_DL();
272    Set_DL(const Set_DL& other);
273
274    void add(const T& item)
275	{ list.append(item); }
276    void remove(Pix& x, T& item)
277	{ list.remove(x, item); }
278
279    void clear()
280	{ list.clear(); }
281
282    bool contains(const T& item) const
283	{ return list.contains(item); }
284    Pix search(const T& item) const
285	{ return list.search(item); }
286
287    unsigned length() const
288	{ return list.length(); }
289
290    Pix first() const
291	{ return list.first(); }
292    void next(Pix& x) const
293	{ list.next(x); }
294    T& operator()(Pix x) const
295	{ return list(x); }
296private:
297    List_DLS<T> list;
298};
299
300template<class T>
301class Set_DLp: public List_DLSp<T> {
302public:
303    Set_DLp();
304    Set_DLp(const Set_DLp& other);
305
306    void add(const T& item)
307	{ list.append(item); }
308    void remove(Pix& x, T& item)
309	{ list.remove(x, item); }
310
311    void clear()
312	{ list.clear(); }
313
314    bool contains(const T& item) const
315	{ return list.contains(item); }
316    Pix search(const T& item) const
317	{ return list.search(item); }
318
319    unsigned length() const
320	{ return list.length(); }
321
322    Pix first() const
323	{ return list.first(); }
324    void next(Pix& x) const
325	{ list.next(x); }
326    T& operator()(Pix x) const
327	{ return list(x); }
328private:
329    List_DLSp<T> list;
330};
331
332template<class T>
333struct vertex {
334    T item;
335    List_DL<vertex<T> *> fanout;
336
337    vertex(): item(), fanout()	// { dg-bogus "" }
338      { }
339    vertex(const T& i): item(), fanout() // { dg-bogus "" }
340      { }
341};
342
343template<class T>
344class Graph {
345public:
346    Graph();
347    Graph(const Graph&);
348    ~Graph();
349
350    void add(const T& from, const T& to);
351    bool contains(const T& from, const T& to) const;
352
353    void clear()
354	{ vertices.clear(); }
355
356    unsigned lengthV() const
357	{ return vertices.length(); }
358
359    Pix firstV() const
360	{ return vertices.first(); }
361    void nextV(Pix& x) const
362	{ vertices.next(x); }
363    T& V(Pix x) const
364	{ return vertices(x).item; }
365
366    Pix firstV1(Pix vx) const;
367    void nextV1(Pix vx, Pix& x) const;
368    T& V1(Pix vx, Pix x) const;
369private:
370    vertex<T> *lookup(const T& from) const;
371    vertex<T> *lookup_new(const T& from);
372
373    List_DLS<vertex<T> > vertices;
374};
375
376template<class T>
377Graph<T>::Graph():
378vertices()
379{ }
380
381template<class T>
382Graph<T>::Graph(const Graph& other):
383vertices()
384{
385    for (Pix vx=firstV(); 0 != vx; nextV(vx)) {
386	for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) {
387	    add(V(vx), V1(vx, vx1));
388	}
389    }
390}
391
392template<class T>
393Graph<T>::~Graph()
394{
395    clear();
396}
397
398template<class T>
399void
400Graph<T>::add(const T& from, const T& to)
401{
402    vertex<T> *fromv = lookup_new(from);
403    if (from == to)
404	return;
405    vertex<T> *tov = lookup_new(to);
406    fromv->fanout.append(tov);
407}
408
409template<class T>
410bool
411Graph<T>::contains(const T& from, const T& to) const
412{
413    vertex<T> *fromv = lookup(from);
414    if (0 == fromv)
415	return FALSE;
416
417    for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
418	if (fromv->fanout(x)->item == to)
419	    return TRUE;
420    }
421
422    return FALSE;
423}
424
425template<class T>
426vertex<T> *
427Graph<T>::lookup(const T& from) const
428{
429    for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
430	if (vertices(x).item == from)
431	    return &vertices(x);
432    }
433    return 0;
434}
435
436template<class T>
437vertex<T> *
438Graph<T>::lookup_new(const T& from)
439{
440    vertex<T> *v = lookup(from);
441    if (0 == v) {
442	vertices.append(from);
443	return &vertices(vertices.last());
444    }
445    return v;
446}
447
448template<class T>
449Pix
450Graph<T>::firstV1(Pix vx) const
451{
452    vertex<T> *v = (vertex<T> *) vx;
453    return v->fanout.first();
454}
455
456template<class T>
457void
458Graph<T>::nextV1(Pix vx, Pix& x) const
459{
460    vertex<T> *v = (vertex<T> *) vx;
461    return v->fanout.next(x);
462}
463
464template<class T>
465T&
466Graph<T>::V1(Pix vx, Pix x) const
467{
468    vertex<T> *v = (vertex<T> *) vx;
469    static T x1;
470    return x1;
471}
472
473class STRLIdentifier;
474
475extern int x(List_DL<STRLIdentifier *>);
476extern int x(List_DLS<STRLIdentifier *>);
477
478extern int x(Set<STRLIdentifier *>);
479extern int x(Set_DL<STRLIdentifier *>);
480extern int x(Set_DLp<STRLIdentifier *>);
481
482extern int x(Graph<STRLIdentifier *>);
483
484class STRLIdentifier {
485    char buf[10];
486};
487
488extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "candidates" } const subversion
489extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-message "note" } fn ref in err msg
490
491extern int x(List_DLSp<STRLIdentifier *>);
492
493template class Graph<STRLIdentifier *>;
494template class List_DLS<vertex<STRLIdentifier *> >;
495