// { dg-do assemble }
|
// { dg-do assemble }
|
// prms-id: 1989
|
// prms-id: 1989
|
|
|
#define TRUE true
|
#define TRUE true
|
#define FALSE false
|
#define FALSE false
|
typedef void *Pix;
|
typedef void *Pix;
|
|
|
template
|
template
|
struct link {
|
struct link {
|
T item;
|
T item;
|
link *next;
|
link *next;
|
link *prev;
|
link *prev;
|
|
|
link(const T& t): item(t), prev(0), next(0)
|
link(const T& t): item(t), prev(0), next(0)
|
{ };
|
{ };
|
link(const T& t, link *p, link *n): item(t), prev(p), next(n)
|
link(const T& t, link *p, link *n): item(t), prev(p), next(n)
|
{ };
|
{ };
|
};
|
};
|
|
|
template
|
template
|
class List_DL {
|
class List_DL {
|
public:
|
public:
|
List_DL();
|
List_DL();
|
List_DL(const List_DL&);
|
List_DL(const List_DL&);
|
~List_DL();
|
~List_DL();
|
|
|
void append(const T& item);
|
void append(const T& item);
|
void prepend(const T& item);
|
void prepend(const T& item);
|
void insert(const T& item, Pix x, bool before);
|
void insert(const T& item, Pix x, bool before);
|
|
|
void remove(Pix& x)
|
void remove(Pix& x)
|
{ T tmp; remove(x, tmp); }
|
{ T tmp; remove(x, tmp); }
|
void remove(Pix& x, T& item);
|
void remove(Pix& x, T& item);
|
|
|
void clear();
|
void clear();
|
|
|
unsigned length() const
|
unsigned length() const
|
{ return count; }
|
{ return count; }
|
|
|
private:
|
private:
|
|
|
unsigned count;
|
unsigned count;
|
link *head;
|
link *head;
|
link *tail;
|
link *tail;
|
|
|
public:
|
public:
|
Pix first() const
|
Pix first() const
|
{ return Pix(head); }
|
{ return Pix(head); }
|
Pix last() const
|
Pix last() const
|
{ return Pix(tail); }
|
{ return Pix(tail); }
|
void next(Pix& x) const
|
void next(Pix& x) const
|
{ if (0 != x) x = ((link *) x)->next; }
|
{ if (0 != x) x = ((link *) x)->next; }
|
void prev(Pix& x) const
|
void prev(Pix& x) const
|
{ if (0 != x) x = ((link *) x)->prev; }
|
{ if (0 != x) x = ((link *) x)->prev; }
|
T& operator()(Pix x) const
|
T& operator()(Pix x) const
|
{ return ((link *) x)->item; }
|
{ return ((link *) x)->item; }
|
};
|
};
|
|
|
template
|
template
|
List_DL::List_DL():
|
List_DL::List_DL():
|
count(0),
|
count(0),
|
head(0)
|
head(0)
|
{ }
|
{ }
|
|
|
template
|
template
|
List_DL::List_DL(const List_DL& other):
|
List_DL::List_DL(const List_DL& other):
|
count(0),
|
count(0),
|
head(0)
|
head(0)
|
{
|
{
|
for (Pix x=other.first(); 0 != x; other.next(x))
|
for (Pix x=other.first(); 0 != x; other.next(x))
|
append(other(x));
|
append(other(x));
|
}
|
}
|
|
|
template
|
template
|
List_DL::~List_DL()
|
List_DL::~List_DL()
|
{
|
{
|
clear();
|
clear();
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
List_DL::append(const T& item)
|
List_DL::append(const T& item)
|
{
|
{
|
count++;
|
count++;
|
if (0 == head) {
|
if (0 == head) {
|
head = new link(item);
|
head = new link(item);
|
tail = head;
|
tail = head;
|
} else {
|
} else {
|
tail->next = new link(item, tail, 0);
|
tail->next = new link(item, tail, 0);
|
tail = tail->next;
|
tail = tail->next;
|
}
|
}
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
List_DL::prepend(const T& item)
|
List_DL::prepend(const T& item)
|
{
|
{
|
count++;
|
count++;
|
if (0 == head) {
|
if (0 == head) {
|
head = new link(item);
|
head = new link(item);
|
tail = head;
|
tail = head;
|
} else {
|
} else {
|
head = new link(item, 0, head);
|
head = new link(item, 0, head);
|
if (tail == head)
|
if (tail == head)
|
tail = tail->next;
|
tail = tail->next;
|
}
|
}
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
List_DL::insert(const T& item, Pix x, bool before = TRUE)
|
List_DL::insert(const T& item, Pix x, bool before = TRUE)
|
{
|
{
|
link *l = (link *) x;
|
link *l = (link *) x;
|
|
|
if (before) {
|
if (before) {
|
if (0 == l || l == head) {
|
if (0 == l || l == head) {
|
prepend(item);
|
prepend(item);
|
} else {
|
} else {
|
link *n = new link(item, l->prev, l);
|
link *n = new link(item, l->prev, l);
|
l->prev->next = n;
|
l->prev->next = n;
|
l->prev = n;
|
l->prev = n;
|
}
|
}
|
} else {
|
} else {
|
if (0 == l || l == tail) {
|
if (0 == l || l == tail) {
|
append(item);
|
append(item);
|
} else {
|
} else {
|
link *n = new link(item, l, l->next);
|
link *n = new link(item, l, l->next);
|
l->next->prev = n;
|
l->next->prev = n;
|
l->prev = n;
|
l->prev = n;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
List_DL::remove(Pix& x, T& item)
|
List_DL::remove(Pix& x, T& item)
|
{
|
{
|
link *l = (link *) x;
|
link *l = (link *) x;
|
|
|
if (0 == l)
|
if (0 == l)
|
return;
|
return;
|
|
|
item = l->item;
|
item = l->item;
|
if (1 == count) {
|
if (1 == count) {
|
delete head;
|
delete head;
|
head = 0;
|
head = 0;
|
tail = 0;
|
tail = 0;
|
} else {
|
} else {
|
// more than one item in the list
|
// more than one item in the list
|
if (l == head) {
|
if (l == head) {
|
link *old = head;
|
link *old = head;
|
head = head->next;
|
head = head->next;
|
head->prev = 0;
|
head->prev = 0;
|
delete old;
|
delete old;
|
} else if (l == tail) {
|
} else if (l == tail) {
|
link *old = tail;
|
link *old = tail;
|
tail = tail->prev;
|
tail = tail->prev;
|
tail->next = 0;
|
tail->next = 0;
|
delete old;
|
delete old;
|
} else {
|
} else {
|
l->next->prev = l->prev;
|
l->next->prev = l->prev;
|
l->prev->next = l->next;
|
l->prev->next = l->next;
|
delete l;
|
delete l;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
List_DL::clear()
|
List_DL::clear()
|
{
|
{
|
link *l, *succ;
|
link *l, *succ;
|
for (l=head; 0 != l; l=succ) {
|
for (l=head; 0 != l; l=succ) {
|
succ = l->next;
|
succ = l->next;
|
delete l;
|
delete l;
|
}
|
}
|
head = 0;
|
head = 0;
|
tail = 0;
|
tail = 0;
|
}
|
}
|
|
|
template
|
template
|
class List_DLS: public List_DL {
|
class List_DLS: public List_DL {
|
public:
|
public:
|
List_DLS(): List_DL()
|
List_DLS(): List_DL()
|
{ };
|
{ };
|
List_DLS(const List_DLS& other): List_DL(other)
|
List_DLS(const List_DLS& other): List_DL(other)
|
{ };
|
{ };
|
|
|
bool contains(const T& item) const
|
bool contains(const T& item) const
|
{ return search(item) != 0 ? TRUE: FALSE; }
|
{ return search(item) != 0 ? TRUE: FALSE; }
|
Pix search(const T&) const;
|
Pix search(const T&) const;
|
};
|
};
|
|
|
template
|
template
|
Pix
|
Pix
|
List_DLS::search(const T& item) const
|
List_DLS::search(const T& item) const
|
{
|
{
|
for (Pix x=this->first(); 0 != x; this->next(x)) {
|
for (Pix x=this->first(); 0 != x; this->next(x)) {
|
if (item == this->operator()(x)) // { dg-error "" } const subversion
|
if (item == this->operator()(x)) // { dg-error "" } const subversion
|
return x;
|
return x;
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
|
|
template
|
template
|
class List_DLSp: public List_DL {
|
class List_DLSp: public List_DL {
|
public:
|
public:
|
List_DLSp(): List_DL()
|
List_DLSp(): List_DL()
|
{ };
|
{ };
|
List_DLSp(const List_DLSp& other): List_DL(other)
|
List_DLSp(const List_DLSp& other): List_DL(other)
|
{ };
|
{ };
|
|
|
bool contains(const T& item) const
|
bool contains(const T& item) const
|
#ifndef INTERNAL_ERROR
|
#ifndef INTERNAL_ERROR
|
;
|
;
|
#else
|
#else
|
{ return search(item) != 0 ? TRUE: FALSE; }
|
{ return search(item) != 0 ? TRUE: FALSE; }
|
#endif
|
#endif
|
Pix search(const T&) const;
|
Pix search(const T&) const;
|
};
|
};
|
|
|
template
|
template
|
bool
|
bool
|
List_DLSp::contains(const T& item) const
|
List_DLSp::contains(const T& item) const
|
{
|
{
|
for (Pix x=this->first(); 0 != x; this->next(x)) {
|
for (Pix x=this->first(); 0 != x; this->next(x)) {
|
if (*item == *(this->operator()(x)))
|
if (*item == *(this->operator()(x)))
|
return TRUE;
|
return TRUE;
|
}
|
}
|
return FALSE;
|
return FALSE;
|
}
|
}
|
|
|
template
|
template
|
class Set {
|
class Set {
|
public:
|
public:
|
Set();
|
Set();
|
Set(const Set& other);
|
Set(const Set& other);
|
|
|
virtual void add(const T& item);
|
virtual void add(const T& item);
|
|
|
void remove(const T& item)
|
void remove(const T& item)
|
{ Pix x = search(item); remove(x); }
|
{ Pix x = search(item); remove(x); }
|
void remove(Pix& x)
|
void remove(Pix& x)
|
{ T tmp; remove(x, tmp); }
|
{ T tmp; remove(x, tmp); }
|
virtual void remove(Pix& x, T& item);
|
virtual void remove(Pix& x, T& item);
|
|
|
virtual void clear();
|
virtual void clear();
|
|
|
virtual bool contains(const T&) const;
|
virtual bool contains(const T&) const;
|
virtual Pix search(const T&) const;
|
virtual Pix search(const T&) const;
|
|
|
virtual unsigned length() const;
|
virtual unsigned length() const;
|
|
|
virtual Pix first() const;
|
virtual Pix first() const;
|
virtual void next(Pix& x) const;
|
virtual void next(Pix& x) const;
|
virtual T& operator()(Pix x) const;
|
virtual T& operator()(Pix x) const;
|
};
|
};
|
|
|
template
|
template
|
Set::Set()
|
Set::Set()
|
{ }
|
{ }
|
|
|
template
|
template
|
Set::Set(const Set& other)
|
Set::Set(const Set& other)
|
{ }
|
{ }
|
|
|
|
|
template
|
template
|
class Set_DL: public List_DLS {
|
class Set_DL: public List_DLS {
|
public:
|
public:
|
Set_DL();
|
Set_DL();
|
Set_DL(const Set_DL& other);
|
Set_DL(const Set_DL& other);
|
|
|
void add(const T& item)
|
void add(const T& item)
|
{ list.append(item); }
|
{ list.append(item); }
|
void remove(Pix& x, T& item)
|
void remove(Pix& x, T& item)
|
{ list.remove(x, item); }
|
{ list.remove(x, item); }
|
|
|
void clear()
|
void clear()
|
{ list.clear(); }
|
{ list.clear(); }
|
|
|
bool contains(const T& item) const
|
bool contains(const T& item) const
|
{ return list.contains(item); }
|
{ return list.contains(item); }
|
Pix search(const T& item) const
|
Pix search(const T& item) const
|
{ return list.search(item); }
|
{ return list.search(item); }
|
|
|
unsigned length() const
|
unsigned length() const
|
{ return list.length(); }
|
{ return list.length(); }
|
|
|
Pix first() const
|
Pix first() const
|
{ return list.first(); }
|
{ return list.first(); }
|
void next(Pix& x) const
|
void next(Pix& x) const
|
{ list.next(x); }
|
{ list.next(x); }
|
T& operator()(Pix x) const
|
T& operator()(Pix x) const
|
{ return list(x); }
|
{ return list(x); }
|
private:
|
private:
|
List_DLS list;
|
List_DLS list;
|
};
|
};
|
|
|
template
|
template
|
class Set_DLp: public List_DLSp {
|
class Set_DLp: public List_DLSp {
|
public:
|
public:
|
Set_DLp();
|
Set_DLp();
|
Set_DLp(const Set_DLp& other);
|
Set_DLp(const Set_DLp& other);
|
|
|
void add(const T& item)
|
void add(const T& item)
|
{ list.append(item); }
|
{ list.append(item); }
|
void remove(Pix& x, T& item)
|
void remove(Pix& x, T& item)
|
{ list.remove(x, item); }
|
{ list.remove(x, item); }
|
|
|
void clear()
|
void clear()
|
{ list.clear(); }
|
{ list.clear(); }
|
|
|
bool contains(const T& item) const
|
bool contains(const T& item) const
|
{ return list.contains(item); }
|
{ return list.contains(item); }
|
Pix search(const T& item) const
|
Pix search(const T& item) const
|
{ return list.search(item); }
|
{ return list.search(item); }
|
|
|
unsigned length() const
|
unsigned length() const
|
{ return list.length(); }
|
{ return list.length(); }
|
|
|
Pix first() const
|
Pix first() const
|
{ return list.first(); }
|
{ return list.first(); }
|
void next(Pix& x) const
|
void next(Pix& x) const
|
{ list.next(x); }
|
{ list.next(x); }
|
T& operator()(Pix x) const
|
T& operator()(Pix x) const
|
{ return list(x); }
|
{ return list(x); }
|
private:
|
private:
|
List_DLSp list;
|
List_DLSp list;
|
};
|
};
|
|
|
template
|
template
|
struct vertex {
|
struct vertex {
|
T item;
|
T item;
|
List_DL *> fanout;
|
List_DL *> fanout;
|
|
|
vertex(): item(), fanout() // { dg-bogus "" }
|
vertex(): item(), fanout() // { dg-bogus "" }
|
{ };
|
{ };
|
vertex(const T& i): item(), fanout() // { dg-bogus "" }
|
vertex(const T& i): item(), fanout() // { dg-bogus "" }
|
{ };
|
{ };
|
};
|
};
|
|
|
template
|
template
|
class Graph {
|
class Graph {
|
public:
|
public:
|
Graph();
|
Graph();
|
Graph(const Graph&);
|
Graph(const Graph&);
|
~Graph();
|
~Graph();
|
|
|
void add(const T& from, const T& to);
|
void add(const T& from, const T& to);
|
bool contains(const T& from, const T& to) const;
|
bool contains(const T& from, const T& to) const;
|
|
|
void clear()
|
void clear()
|
{ vertices.clear(); }
|
{ vertices.clear(); }
|
|
|
unsigned lengthV() const
|
unsigned lengthV() const
|
{ return vertices.length(); }
|
{ return vertices.length(); }
|
|
|
Pix firstV() const
|
Pix firstV() const
|
{ return vertices.first(); }
|
{ return vertices.first(); }
|
void nextV(Pix& x) const
|
void nextV(Pix& x) const
|
{ vertices.next(x); }
|
{ vertices.next(x); }
|
T& V(Pix x) const
|
T& V(Pix x) const
|
{ return vertices(x).item; }
|
{ return vertices(x).item; }
|
|
|
Pix firstV1(Pix vx) const;
|
Pix firstV1(Pix vx) const;
|
void nextV1(Pix vx, Pix& x) const;
|
void nextV1(Pix vx, Pix& x) const;
|
T& V1(Pix vx, Pix x) const;
|
T& V1(Pix vx, Pix x) const;
|
private:
|
private:
|
vertex *lookup(const T& from) const;
|
vertex *lookup(const T& from) const;
|
vertex *lookup_new(const T& from);
|
vertex *lookup_new(const T& from);
|
|
|
List_DLS > vertices;
|
List_DLS > vertices;
|
};
|
};
|
|
|
template
|
template
|
Graph::Graph():
|
Graph::Graph():
|
vertices()
|
vertices()
|
{ }
|
{ }
|
|
|
template
|
template
|
Graph::Graph(const Graph& other):
|
Graph::Graph(const Graph& other):
|
vertices()
|
vertices()
|
{
|
{
|
for (Pix vx=firstV(); 0 != vx; nextV(vx)) {
|
for (Pix vx=firstV(); 0 != vx; nextV(vx)) {
|
for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) {
|
for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) {
|
add(V(vx), V1(vx, vx1));
|
add(V(vx), V1(vx, vx1));
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
template
|
template
|
Graph::~Graph()
|
Graph::~Graph()
|
{
|
{
|
clear();
|
clear();
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
Graph::add(const T& from, const T& to)
|
Graph::add(const T& from, const T& to)
|
{
|
{
|
vertex *fromv = lookup_new(from);
|
vertex *fromv = lookup_new(from);
|
if (from == to)
|
if (from == to)
|
return;
|
return;
|
vertex *tov = lookup_new(to);
|
vertex *tov = lookup_new(to);
|
fromv->fanout.append(tov);
|
fromv->fanout.append(tov);
|
}
|
}
|
|
|
template
|
template
|
bool
|
bool
|
Graph::contains(const T& from, const T& to) const
|
Graph::contains(const T& from, const T& to) const
|
{
|
{
|
vertex *fromv = lookup(from);
|
vertex *fromv = lookup(from);
|
if (0 == fromv)
|
if (0 == fromv)
|
return FALSE;
|
return FALSE;
|
|
|
for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
|
for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
|
if (fromv->fanout(x)->item == to)
|
if (fromv->fanout(x)->item == to)
|
return TRUE;
|
return TRUE;
|
}
|
}
|
|
|
return FALSE;
|
return FALSE;
|
}
|
}
|
|
|
template
|
template
|
vertex *
|
vertex *
|
Graph::lookup(const T& from) const
|
Graph::lookup(const T& from) const
|
{
|
{
|
for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
|
for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
|
if (vertices(x).item == from)
|
if (vertices(x).item == from)
|
return &vertices(x);
|
return &vertices(x);
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
|
|
template
|
template
|
vertex *
|
vertex *
|
Graph::lookup_new(const T& from)
|
Graph::lookup_new(const T& from)
|
{
|
{
|
vertex *v = lookup(from);
|
vertex *v = lookup(from);
|
if (0 == v) {
|
if (0 == v) {
|
vertices.append(from);
|
vertices.append(from);
|
return &vertices(vertices.last());
|
return &vertices(vertices.last());
|
}
|
}
|
return v;
|
return v;
|
}
|
}
|
|
|
template
|
template
|
Pix
|
Pix
|
Graph::firstV1(Pix vx) const
|
Graph::firstV1(Pix vx) const
|
{
|
{
|
vertex *v = (vertex *) vx;
|
vertex *v = (vertex *) vx;
|
return v->fanout.first();
|
return v->fanout.first();
|
}
|
}
|
|
|
template
|
template
|
void
|
void
|
Graph::nextV1(Pix vx, Pix& x) const
|
Graph::nextV1(Pix vx, Pix& x) const
|
{
|
{
|
vertex *v = (vertex *) vx;
|
vertex *v = (vertex *) vx;
|
return v->fanout.next(x);
|
return v->fanout.next(x);
|
}
|
}
|
|
|
template
|
template
|
T&
|
T&
|
Graph::V1(Pix vx, Pix x) const
|
Graph::V1(Pix vx, Pix x) const
|
{
|
{
|
vertex *v = (vertex *) vx;
|
vertex *v = (vertex *) vx;
|
static T x1;
|
static T x1;
|
return x1;
|
return x1;
|
}
|
}
|
|
|
class STRLIdentifier;
|
class STRLIdentifier;
|
|
|
extern int x(List_DL);
|
extern int x(List_DL);
|
extern int x(List_DLS);
|
extern int x(List_DLS);
|
|
|
extern int x(Set);
|
extern int x(Set);
|
extern int x(Set_DL);
|
extern int x(Set_DL);
|
extern int x(Set_DLp);
|
extern int x(Set_DLp);
|
|
|
extern int x(Graph);
|
extern int x(Graph);
|
|
|
class STRLIdentifier {
|
class STRLIdentifier {
|
char buf[10];
|
char buf[10];
|
};
|
};
|
|
|
extern int operator==(vertex&, vertex&); // { dg-error "" } const subversion
|
extern int operator==(vertex&, vertex&); // { dg-error "" } const subversion
|
extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-error "" } fn ref in err msg
|
extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-error "" } fn ref in err msg
|
|
|
extern int x(List_DLSp);
|
extern int x(List_DLSp);
|
|
|
template class Graph;
|
template class Graph;
|
template class List_DLS >;
|
template class List_DLS >;
|
|
|
