14 link(const T& t): item(t), prev(0), next(0)
16 link(const T& t, link<T> *p, link<T> *n): item(t), prev(p), next(n)
24 List_DL(const List_DL&);
27 void append(const T& item);
28 void prepend(const T& item);
29 void insert(const T& item, Pix x, bool before);
32 { T tmp; remove(x, tmp); }
33 void remove(Pix& x, T& item);
37 unsigned length() const
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; }
60 List_DL<T>::List_DL():
66 List_DL<T>::List_DL(const List_DL& other):
70 for (Pix x=other.first(); 0 != x; other.next(x))
75 List_DL<T>::~List_DL()
82 List_DL<T>::append(const T& item)
86 head = new link<T>(item);
89 tail->next = new link<T>(item, tail, 0);
96 List_DL<T>::prepend(const T& item)
100 head = new link<T>(item);
103 head = new link<T>(item, 0, head);
111 List_DL<T>::insert(const T& item, Pix x, bool before = TRUE) // { dg-error "default arguments" }
113 link<T> *l = (link<T> *) x;
116 if (0 == l || l == head) {
119 link<T> *n = new link<T>(item, l->prev, l);
124 if (0 == l || l == tail) {
127 link<T> *n = new link<T>(item, l, l->next);
136 List_DL<T>::remove(Pix& x, T& item)
138 link<T> *l = (link<T> *) x;
149 // more than one item in the list
155 } else if (l == tail) {
161 l->next->prev = l->prev;
162 l->prev->next = l->next;
173 for (l=head; 0 != l; l=succ) {
182 class List_DLS: public List_DL<T> {
184 List_DLS(): List_DL<T>()
186 List_DLS(const List_DLS& other): List_DL<T>(other)
189 bool contains(const T& item) const
190 { return search(item) != 0 ? TRUE: FALSE; }
191 Pix search(const T&) const;
196 List_DLS<T>::search(const T& item) const
198 for (Pix x=this->first(); 0 != x; this->next(x)) {
199 if (item == this->operator()(x)) // { dg-error "qualifiers" } const subversion
206 class List_DLSp: public List_DL<T> {
208 List_DLSp(): List_DL<T>()
210 List_DLSp(const List_DLSp& other): List_DL<T>(other)
213 bool contains(const T& item) const
214 #ifndef INTERNAL_ERROR
217 { return search(item) != 0 ? TRUE: FALSE; }
219 Pix search(const T&) const;
224 List_DLSp<T>::contains(const T& item) const
226 for (Pix x=this->first(); 0 != x; this->next(x)) {
227 if (*item == *(this->operator()(x)))
237 Set(const Set& other);
239 virtual void add(const T& item);
241 void remove(const T& item)
242 { Pix x = search(item); remove(x); }
244 { T tmp; remove(x, tmp); }
245 virtual void remove(Pix& x, T& item);
247 virtual void clear();
249 virtual bool contains(const T&) const;
250 virtual Pix search(const T&) const;
252 virtual unsigned length() const;
254 virtual Pix first() const;
255 virtual void next(Pix& x) const;
256 virtual T& operator()(Pix x) const;
264 Set<T>::Set(const Set& other)
269 class Set_DL: public List_DLS<T> {
272 Set_DL(const Set_DL& other);
274 void add(const T& item)
275 { list.append(item); }
276 void remove(Pix& x, T& item)
277 { list.remove(x, item); }
282 bool contains(const T& item) const
283 { return list.contains(item); }
284 Pix search(const T& item) const
285 { return list.search(item); }
287 unsigned length() const
288 { return list.length(); }
291 { return list.first(); }
292 void next(Pix& x) const
294 T& operator()(Pix x) const
301 class Set_DLp: public List_DLSp<T> {
304 Set_DLp(const Set_DLp& other);
306 void add(const T& item)
307 { list.append(item); }
308 void remove(Pix& x, T& item)
309 { list.remove(x, item); }
314 bool contains(const T& item) const
315 { return list.contains(item); }
316 Pix search(const T& item) const
317 { return list.search(item); }
319 unsigned length() const
320 { return list.length(); }
323 { return list.first(); }
324 void next(Pix& x) const
326 T& operator()(Pix x) const
335 List_DL<vertex<T> *> fanout;
337 vertex(): item(), fanout() // { dg-bogus "" }
339 vertex(const T& i): item(), fanout() // { dg-bogus "" }
350 void add(const T& from, const T& to);
351 bool contains(const T& from, const T& to) const;
354 { vertices.clear(); }
356 unsigned lengthV() const
357 { return vertices.length(); }
360 { return vertices.first(); }
361 void nextV(Pix& x) const
362 { vertices.next(x); }
364 { return vertices(x).item; }
366 Pix firstV1(Pix vx) const;
367 void nextV1(Pix vx, Pix& x) const;
368 T& V1(Pix vx, Pix x) const;
370 vertex<T> *lookup(const T& from) const;
371 vertex<T> *lookup_new(const T& from);
373 List_DLS<vertex<T> > vertices;
382 Graph<T>::Graph(const Graph& other):
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));
400 Graph<T>::add(const T& from, const T& to)
402 vertex<T> *fromv = lookup_new(from);
405 vertex<T> *tov = lookup_new(to);
406 fromv->fanout.append(tov);
411 Graph<T>::contains(const T& from, const T& to) const
413 vertex<T> *fromv = lookup(from);
417 for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
418 if (fromv->fanout(x)->item == to)
427 Graph<T>::lookup(const T& from) const
429 for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
430 if (vertices(x).item == from)
438 Graph<T>::lookup_new(const T& from)
440 vertex<T> *v = lookup(from);
442 vertices.append(from);
443 return &vertices(vertices.last());
450 Graph<T>::firstV1(Pix vx) const
452 vertex<T> *v = (vertex<T> *) vx;
453 return v->fanout.first();
458 Graph<T>::nextV1(Pix vx, Pix& x) const
460 vertex<T> *v = (vertex<T> *) vx;
461 return v->fanout.next(x);
466 Graph<T>::V1(Pix vx, Pix x) const
468 vertex<T> *v = (vertex<T> *) vx;
473 class STRLIdentifier;
475 extern int x(List_DL<STRLIdentifier *>);
476 extern int x(List_DLS<STRLIdentifier *>);
478 extern int x(Set<STRLIdentifier *>);
479 extern int x(Set_DL<STRLIdentifier *>);
480 extern int x(Set_DLp<STRLIdentifier *>);
482 extern int x(Graph<STRLIdentifier *>);
484 class STRLIdentifier {
488 extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "argument 1" } const subversion
489 extern int operator==(STRLIdentifier&, STRLIdentifier&);
491 extern int x(List_DLSp<STRLIdentifier *>);
493 template class Graph<STRLIdentifier *>;
494 template class List_DLS<vertex<STRLIdentifier *> >;