[NEWBIE] 2.95.3 loops !!!

[Rullo Patrizio]

Hi all,
when I try to compile this code (in attachment) my g++ loops!
It's a bug of the compiler or I there's something wrong in my code?

Thanks

Rullo Patrizio

***********************************
list.h
***********************************
#include <iostream>
#include <new>
#ifndef __ISS_LIST
#define __ISS_LIST

using namespace std;

template <class T> class list;

export template <class T> class node {
protected:
    T _data;
    node<T> *_next_node;
public:
    // costruttore - default cella chiusa
    node(T data, node<T>* next = NULL)
    {
     _data = data;
     _next_node = next;
    }
    // questo mi funge da selettore e modificatore
    T& data()
    { return _data; }

    // questo mi funge da selettore e modificatore
    node<T>*& next()
    { return _next_node; }

    friend ostream& operator<< <>(ostream&o, list<T> &l);
};

export template <class T> class list {
protected:
    node<T> *_first;
    node<T> *_last;
    node<T> *_current;
public:
    list();
    node<T>& top();
    node<T>& bottom();

    bool isEmpty()
    { return (_first == NULL);  }

    // ritorno *this in modo da poter concatenare l'invocazione dei metodi
    list<T>& push(T to_push);
    list<T>& enqueue(T to_add);

    T pop();
    T dequeue();

    void add_before(const T &before, T to_add);
    void add_after(const T &after, T to_add);
    void remove(T to_remove);

    node<T>& find(T dato);

    friend ostream& operator<< <>(ostream&o, list<T> &l);
};

//export template <class T> ostream& operator<<(ostream& o, list<T> &l);
#include "list.cpp"
#endif

****************************************
list.cpp
****************************************
#include "list.h"
#ifndef __MY_LIST_IMPLEMENTATION
#define __MY_LIST_IMPLEMENTATION
template <class T> node<T>& list<T>::top()
{
    return *_first;
}

template <class T> node<T>& list<T>::bottom()
{
    return *_last;
}

template <class T> list<T>::list()
{
    _first   = NULL;
    _last    = NULL;
    _current = NULL;
}

// PUSH: se la lista è vuota, la coda e la testa devono coincidere
template <class T> list<T>& list<T>::push(T to_push)
{
    _current = new node<T>(to_push, _first);

    if (isEmpty()) {
        _last = _first = _current;
    } else {
        _first = _current;
    }

    return *this;
}

// POP: se la lista si svuota, la coda deve essere messa a NULL
// occhio: _current è lasciato in uno stato inconsistente
template <class T> T list<T>::pop()
{
    T temp_data;

    _current  = _first;
    temp_data = _first->data();

    _first    = _first->next();
    if (_first == NULL) {
        _last = NULL;
    }

    delete _current;
    _current = _first;

    return temp_data;
}

// ACCODO: sposto la coda, e imposto la testa se la coda è vuota
template <class T> list<T>& list<T>::enqueue(T to_add)
{
    _current = new node<T>(to_add);

    if (isEmpty()) {
        _last = _first = _current;
    } else {
        _last->next()    = _current;
        _last            = _current;
    }

    return *this;
}

// CERCA - ciclo sulla lista finchè non trovo il nodo,
//         se non lo trovo restituisco NULL
template <class T> node<T>& list<T>::find(T dato)
{
    node<T>* next = _first;
    while (next != NULL) {
        if (next->data() == dato)
            return *next;
        next = next -> next();
    }
    throw;
}

// STAMPA - ciclo sulla lista a partire dal top
template <class T> ostream& operator<<(ostream& o, list<T> &l)
{
    node<T>* next = &l.top();
    if (next == NULL) return o;

    o << " [" << next->data();
    for (next = next->next(); next != NULL; next = next->next()) {
        o << ";" << next->data();
    }
    o << "] " << endl ;

    return o;
}

/*
int main()
{
    list<int> lista;

    lista.push(5);
    lista.push(10);
    lista.push(20);


    list<int> lista2;

    lista2.push(44);
    lista2.push(55);
    lista2.push(66);
    lista2.enqueue(11);


    list<char> listaC;
    listaC.push('o').push('a').push('i').push('C');
    listaC.enqueue('!').enqueue('!').push('_').enqueue('_');

    cout << "Caratteri: " << listaC << endl;

    list< list<int> > superLista;
    superLista.push(lista);
    superLista.push(lista2);

    cout << "Super lista: " << superLista << endl;

    return 0;
}
*/
#endif

*************************************************
graph.h
*************************************************
#include <iostream>
#include <new>
#ifndef __ISS_GRAPH
#define __ISS_GRAPH

using namespace std;

template <class T> class arco;

template <class T> class vertice {
protected:
    T _dato;
    list< arco<T>* > _adiacenti;
public:
    vertice<T>(const T& dato) { _dato = dato; }

    T& data() { return _dato; }
    list< arco<T>* >& adj() { return _adiacenti; }

    vertice<T>& operator+=(arco<T>* arco);
    vertice<T>& link(vertice<T>* dest);
    vertice<T>& double_link(vertice<T>* dest);

    vertice<T>& operator-=(arco<T>* arco);
};

template <class T> ostream& operator<<(ostream& o, vertice<T> *v);

/* ARCO */

template <class T> class arco {
protected:
    vertice<T>* _destinazione;
public:
    arco(vertice<T>* dest)
    { _destinazione = dest; }

    vertice<T>* & destinazione()
    { return _destinazione; }

    virtual void print(ostream& o)
    { o << "arco verso vertice " << _destinazione->data(); }
};

template <class T> class arco_pesato: public arco<T> {
protected:
    float _peso;
public:
    arco_pesato(vertice<T>* dest, float peso):
                            arco<T>(dest)
    { _peso = peso; }

    float& peso()
    { return _peso; };

    void print(ostream& o)
    { o << "arco verso " << destinazione() << " con peso " << _peso; }
};

/* TIPI DI ETICHETTA DI VERTICE */

enum color { white, grey, black };

/* BFS */
template <class T> class BFS {
protected:
    T _dato;
    color _colore;
    BFS<T>* _padre;
    long int _distanza_sorgente;
public:
    BFS<T>() {
        _colore = white;
        _padre = NULL;
        _distanza_sorgente = 0;
        }
    BFS<T>(T dato) {
        _dato = dato;
        _colore = white;
        _padre = NULL;
        _distanza_sorgente = 0;
    }

    color& colore() { return _colore; }
    BFS<T>*& padre() { return _padre; }
    T& data() { return _dato;}
    long int& distanza_sorgente() { return _distanza_sorgente; }

/*    bool operator==(const BFS<T>& o) {
         return _dato == o._dato;
    }
*/
};

template <class T> ostream& operator<<(ostream& o, BFS<T> b) ;

/* DFS */
template <class T> class DFS {
protected:
    T _dato;
    color _colore;
    DFS<T>* _padre;
    long int _scoperta;
    long int _fine_visita;
public:
    DFS<T>() {
        _colore = white;
        _padre = NULL;
        _scoperta = 0;
        _fine_visita = 0;
    }
    DFS<T>(T dato) {
        _dato = dato;
        _colore = white;
        _scoperta = 0;
        _fine_visita = 0;
    }

    color& colore() { return _colore; }
    DFS<T>*& padre() { return _padre; }
    long int& tempo_scoperta() { return _scoperta; }
    long int& tempo_fine_visita() { return _fine_visita; }
    T& data() { return _dato; }

/*    bool operator==(const DFS<T>& o) {
        return _dato == o._dato;
    }
*/
};

template <class T> ostream& operator<<(ostream& o, DFS<T> d);

/* GRAFO ASTRATTO */
template <class T> class grafo {
protected:
    list< vertice<T>* > _vertici;
    void DFS_visit_vertice( grafo< DFS<T> > *grafo_dfs,
                            vertice<T>* current,
                            vertice< DFS<T> >* current_dfs,
                            long int &time);
    virtual grafo<DFS<T> >* get_dfs_graph() = 0;
    virtual grafo<BFS<T> >* get_bfs_graph() = 0;
public:
    list< vertice<T>* >& vertexs() { return _vertici; };
    grafo< BFS<T> >* BFS_visit(T sorgente);
    grafo< DFS<T> >* DFS_visit();

    grafo<T>& operator+=(vertice<T>* vertice);
    grafo<T>& operator-=(vertice<T>* vertice);
    virtual void link_vertexs(vertice<T>* a, vertice<T>* b) = 0;

    node< vertice<T>* >* find(const T& label);
};

template <class T> ostream& operator<<(ostream& o, grafo<T> g);

/* GRAFI CONCRETI ORIENTATI E NON */

template <class T> class grafo_orientato:
         public grafo<T>
{
protected:

  grafo<DFS<T> >* get_dfs_graph()
  { return new grafo_orientato<DFS<T> >;  }
  grafo<BFS<T> >* get_bfs_graph()
  { return new grafo_orientato<BFS<T> >; }
public:
  void link_vertexs(vertice<T>* a, vertice<T>* b)
  { a->link(b); }
};

template <class T> class grafo_non_orientato:
         public grafo<T>
{
protected:
  grafo<DFS<T> >* get_dfs_graph()
  { return new grafo_non_orientato<DFS<T> >;  }
  grafo<BFS<T> >* get_bfs_graph()
  { return new grafo_non_orientato<BFS<T> >; }
public:
  void link_vertexs(vertice<T>* a, vertice<T>* b)
  { a->double_link(b); }
};


//#include "graph.cpp"
#endif

***************************************************+
graph.cpp
***************************************************
#include <iostream>
#include <new>
#include "list.h"
#include "graph.h"

/* VERTICE */

template <class T> vertice<T>& vertice<T>::link(vertice<T>* dest) {
   _adiacenti.enqueue(new arco<T>(dest));
}

template <class T> vertice<T>& vertice<T>::double_link(vertice<T>* dest) {
   _adiacenti.enqueue(new arco<T>(dest));
   dest->adj().enqueue(new arco<T>(this));
}

template <class T> vertice<T>& vertice<T>::operator+=(arco<T>* a)
{
    _adiacenti.enqueue(a);
    return *this;
}

template <class T> vertice<T>& vertice<T>::operator-=(arco<T>* a)
{
    _adiacenti.remove(a);
    return *this;
}

template <class T> ostream& operator<<(ostream& o, vertice<T> *v)
{
    o << "vertice " << v->data() << v->adj();
    return o;
}

/* ARCO */

template <class T> ostream& operator<<(ostream& o, arco<T> *a)
{
 /* subisce l'override nelle varie implementazioni di arco (normale, pesato,
etc.) */
    a->print(o);
    return o;
}

/* TIPI DI ETICHETTA DI VERTICE (BFS, DFS) */

template <class T> ostream& operator<<(ostream& o, BFS<T> b)
{
    if (b.padre() != NULL) {
        o << "BFS " << b.data() << " from " << b.padre()->data() << " dist "
<< b.distanza_sorgente() ;
    } else {
        o << "BFS " << b.data();
    }
    return o;
}

template <class T> ostream& operator<<(ostream& o, DFS<T> d)
{
    o << "DFS " << d.data() << " scoperta: " << d.tempo_scoperta() << " fine
visita: " << d.tempo_fine_visita();
    return o;
}

/* GRAFO ASTRATTO */

template <class T>  node< vertice<T>* >* grafo<T>::find(const T& label)
{
 node< vertice<T>* >* next = &_vertici.top();
 while (next != NULL) {
       if (next->data()->data() == label)
          return next;
       next = next -> next();
 }
 throw;
}

template <class T> ostream& operator<<(ostream& o, grafo<T> g)
{
    o << "Grafo:" << endl << g.vertexs() << endl;
    return o;
}

template <class T> grafo< BFS<T> >* grafo<T>::BFS_visit(T sorgente) {

    grafo< BFS<T> >* grafo_bfs = get_bfs_graph();
    node< vertice<T>* > *current;
    list< arco<T>* > adiacenti;
    node< arco<T>* > *arc;

    node< vertice<BFS<T> > * > *current_bfs, *adj_bfs;

    /* devo creare un grafo BFS copia di quello attuale */
    /* parte 1: copio tutti i vertici */
    for(
        current = &_vertici.top();
        current != NULL;
        current = current -> next()) {

        BFS<T> label(current->data()->data());
        *grafo_bfs += new vertice< BFS<T> >(label);
    }

    /* Inizializzo il vertice sorgente con i seguenti valori
    (utilizzando il costruttore di vertice_BFS):
    colore -> grigio
    distanza dal sorgente -> 0 (è la radice)
    padre -> nessuno */

    current_bfs = grafo_bfs->find(BFS<T>(sorgente));
    current_bfs->data()->data().colore() = grey;
    current_bfs->data()->data().padre() = NULL;
    current_bfs->data()->data().distanza_sorgente() = 0;

    // Inserisco il vertice sorgente nella coda dei vertici grigi
    list< BFS<T>* > vertici_grigi;
    vertici_grigi.enqueue(& current_bfs->data()->data());
    while (!vertici_grigi.isEmpty()) {
          BFS<T>* top = vertici_grigi.top().data();
//          cout << "TOP " << *top << endl;
          current = find(top->data());
          adiacenti = current->data()->adj();
          for (arc = & adiacenti.top(); arc != NULL; arc = arc -> next()) {
              T label = arc->data()->destinazione()->data();
              vertice< BFS<T> >* vert =
grafo_bfs->find(BFS<T>(label))->data();
              vertice< BFS<T> >* dest = grafo_bfs->find(*top)->data();
              BFS<T>& BFS_lbl = vert->data();
              if (BFS_lbl.colore() == white) {
                 BFS_lbl.colore() = grey;
                 BFS_lbl.distanza_sorgente() = top->distanza_sorgente() + 1;
                 BFS_lbl.padre() = top; //& current_bfs->data()->data();
//                 cout << "PUSH " << BFS_lbl << endl;
                 vertici_grigi.enqueue(& BFS_lbl);
                 grafo_bfs->link_vertexs(vert, dest);
              }
          }
          vertici_grigi.pop();
          top->colore() = black;
    }
    return grafo_bfs;
}

template <class T> grafo< DFS<T> >* grafo<T>::DFS_visit() {
    grafo< DFS<T> >* grafo_dfs = get_dfs_graph();
    node< vertice<T>* > *current;
    list< arco<T>* > adiacenti;
    node< arco<T>* > *arc;
    long int time;

    // Copio tutti i vertici del grafo nel grafo della visita DFS
    for (current = &_vertici.top(); current != NULL; current =
current->next()) {
        DFS<T> label (current->data()->data());
        *grafo_dfs += new vertice< DFS<T> >(label);
    }

    time = 0;

    node< vertice< DFS<T> >* > *current_dfs;
    for (current = &_vertici.top(); current != NULL; current =
current->next()) {
        current_dfs = grafo_dfs->find(current->data()->data());
        if ( current_dfs->data()->data().colore() == white ) {
           DFS_visit_vertice(grafo_dfs, current->data(),
current_dfs->data(), time);
        }
    }

    return grafo_dfs;
}

template <class T> void grafo<T>::DFS_visit_vertice( grafo< DFS<T> >
*grafo_dfs,
                            vertice<T>* current,
                            vertice< DFS<T> >* current_dfs,
                            long int &time) {

    current_dfs->data().colore() = grey;
    current_dfs->data().tempo_scoperta() = ++time;

    list <arco<T>* >& adiacenti = current->adj();
    node <arco<T>* > *arc;
    for ( arc = & adiacenti.top(); arc != NULL; arc = arc->next() ) {
        vertice<T>* dest = arc->data()->destinazione();
        vertice< DFS<T> >* dest_dfs = grafo_dfs->find(dest->data())->data();
        if ( dest_dfs->data().colore() == white ) {
            grafo_dfs->link_vertexs(current_dfs, dest_dfs);
            dest_dfs->data().padre() = & current_dfs->data();
            DFS_visit_vertice(grafo_dfs,dest,dest_dfs,time);
        }
    }
    current_dfs->data().colore() = black;
    current_dfs->data().tempo_fine_visita() = ++time;
}

template <class T> grafo<T>& grafo<T>::operator+=(vertice<T>* v)
{
    _vertici.enqueue(v);
    return *this;
}

template <class T> grafo<T>& grafo<T>::operator-=(vertice<T>* v)
{
    _vertici.remove(v);
    return *this;
}

int main()
{
    grafo<int>* g1 = new grafo_non_orientato<int>;
    grafo<int>* g2 = new grafo_orientato<int>;

/*    vertice<int> v1(1), v2(2), v3(3), v4(4), v5(5), v6(6), v7(7), v8(8);

    v1.double_link(&v2);
    v1.double_link(&v5);
    v2.double_link(&v6);
    v3.double_link(&v4);
    v3.double_link(&v6);
    v3.double_link(&v7);
    v4.double_link(&v8);
    v6.double_link(&v7);
    v7.double_link(&v8);

    *g1 += &v1;
    *g1 += &v2;
    *g1 += &v3;
    *g1 += &v4;
    *g1 += &v5;
    *g1 += &v6;
    *g1 += &v7;
    *g1 += &v8;

    cout << *g1;
    cout << *(g1->BFS_visit(3));

    vertice<int> v9(1), v10(2), v11(3), v12(4), v13(5), v14(6);

    v9  += new arco<int>(&v12);
    v9  += new arco<int>(&v10);
    v10 += new arco<int>(&v13);
    v11 += new arco<int>(&v13);
    v11 += new arco<int>(&v14);
    v12 += new arco<int>(&v10);
    v13 += new arco<int>(&v12);
    v14 += new arco<int>(&v14);

    *g2 += &v9;
    *g2 += &v10;
    *g2 += &v11;
    *g2 += &v12;
    *g2 += &v13;
    *g2 += &v14;

    cout << *g2;
    cout << *(g2->DFS_visit());
*/
    return 0;
}