Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/alpar/list_graph.h
changeset 522 a0ed1fa1b800
parent 508 95f8f7171bae
child 531 66f1c466889f
equal deleted inserted replaced
10:0da2b03c39e6 11:6d525f945695 
    61     template <typename Key> class DynMapBase
 
    61     template <typename Key> class DynMapBase
 
    62     {
 
    62     {
 
    63     protected:
 
    63     protected:
 
    64       const ListGraph* G; 
    64       const ListGraph* G; 
    65     public:
 
    65     public:
 
    66       virtual void add(const Key k) = NULL;
 
    66       virtual void add(const Key k) = 0;
 
    67       virtual void erase(const Key k) = NULL;
 
    67       virtual void erase(const Key k) = 0;
 
    68       DynMapBase(const ListGraph &_G) : G(&_G) {}
 
    68       DynMapBase(const ListGraph &_G) : G(&_G) {}
 
    69       virtual ~DynMapBase() {}
 
    69       virtual ~DynMapBase() {}
 
    70       friend class ListGraph;
 
    70       friend class ListGraph;
 
    71     };
 
    71     };
 
    72     
    72     
   761     template <typename Key> class DynMapBase
 
   761     template <typename Key> class DynMapBase
 
   762     {
 
   762     {
 
   763     protected:
 
   763     protected:
 
   764       const NodeSet* G; 
   764       const NodeSet* G; 
   765     public:
 
   765     public:
 
   766       virtual void add(const Key k) = NULL;
 
   766       virtual void add(const Key k) = 0;
 
   767       virtual void erase(const Key k) = NULL;
 
   767       virtual void erase(const Key k) = 0;
 
   768       DynMapBase(const NodeSet &_G) : G(&_G) {}
 
   768       DynMapBase(const NodeSet &_G) : G(&_G) {}
 
   769       virtual ~DynMapBase() {}
 
   769       virtual ~DynMapBase() {}
 
   770       friend class NodeSet;
 
   770       friend class NodeSet;
 
   771     };
 
   771     };
 
   772     
   772     
  1150 
  1150 
  1151     typedef GG NodeGraphType;
 
  1151     typedef GG NodeGraphType;
 
  1152 
  1152 
  1153     NodeGraphType &G;
 
  1153     NodeGraphType &G;
 
  1154 
  1154 
       
  1155   public:
 
  1155     class Node;
 
  1156     class Node;
 
  1156     
  1157 
       
  1158   private:
 
  1157     //Edges are double linked.
 
  1159     //Edges are double linked.
 
  1158     //The free edges are only single linked using the "next_in" field.
 
  1160     //The free edges are only single linked using the "next_in" field.
 
  1159     struct NodeT 
  1161     struct NodeT 
  1160     {
 
  1162     {
 
  1161       int first_in,first_out;
 
  1163       int first_in,first_out;
 
  1168       int prev_in, prev_out;
 
  1170       int prev_in, prev_out;
 
  1169       int next_in, next_out;
 
  1171       int next_in, next_out;
 
  1170     };
 
  1172     };
 
  1171 
  1173 
  1172     
  1174     
  1173     typename NodeGraphType::NodeMap<NodeT> nodes;
 
  1175     typename NodeGraphType::template NodeMap<NodeT> nodes;
 
  1174     
  1176     
  1175     std::vector<EdgeT> edges;
 
  1177     std::vector<EdgeT> edges;
 
  1176     //The first free edge
 
  1178     //The first free edge
 
  1177     int first_free_edge;
 
  1179     int first_free_edge;
 
  1178     
  1180     
  1181     template <typename Key> class DynMapBase
 
  1183     template <typename Key> class DynMapBase
 
  1182     {
 
  1184     {
 
  1183     protected:
 
  1185     protected:
 
  1184       const EdgeSet* G; 
  1186       const EdgeSet* G; 
  1185     public:
 
  1187     public:
 
  1186       virtual void add(const Key k) = NULL;
 
  1188       virtual void add(const Key k) = 0;
 
  1187       virtual void erase(const Key k) = NULL;
 
  1189       virtual void erase(const Key k) = 0;
 
  1188       DynMapBase(const EdgeSet &_G) : G(&_G) {}
 
  1190       DynMapBase(const EdgeSet &_G) : G(&_G) {}
 
  1189       virtual ~DynMapBase() {}
 
  1191       virtual ~DynMapBase() {}
 
  1190       friend class EdgeSet;
 
  1192       friend class EdgeSet;
 
  1191     };
 
  1193     };
 
  1192     
  1194     
  1447       EdgeIt(const EdgeSet& G) : Edge() {
 
  1449       EdgeIt(const EdgeSet& G) : Edge() {
 
  1448 	//      	typename NodeGraphType::Node m;
 
  1450 	//      	typename NodeGraphType::Node m;
 
  1449         NodeIt m;
 
  1451         NodeIt m;
 
  1450 	for(G.first(m);
 
  1452 	for(G.first(m);
 
  1451 	    G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
 
  1453 	    G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
 
  1452 	n = G.valid(m)?-1:G.nodes[m].first_in;
 
  1454 	//AJJAJ! This is a non sense!!!!!!!
 
       
  1455 	this->n = G.valid(m)?-1:G.nodes[m].first_in;
 
  1453       }
 
  1456       }
 
  1454       EdgeIt (Invalid i) : Edge(i) { }
 
  1457       EdgeIt (Invalid i) : Edge(i) { }
 
  1455       EdgeIt() : Edge() { }
 
  1458       EdgeIt() : Edge() { }
 
  1456       ///\bug This is a workaround until somebody tells me how to
 
  1459       ///\bug This is a workaround until somebody tells me how to
 
  1457       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
 
  1460       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
 
  1458       int &idref() {return n;}
 
  1461       int &idref() {return this->n;}
 
  1459     };
 
  1462     };
 
  1460     
  1463     
  1461     class OutEdgeIt : public Edge {
 
  1464     class OutEdgeIt : public Edge {
 
  1462       friend class EdgeSet;
 
  1465       friend class EdgeSet;
 
  1463     public: 
  1466     public: 
  1473       InEdgeIt() : Edge() { }
 
  1476       InEdgeIt() : Edge() { }
 
  1474       InEdgeIt (Invalid i) : Edge(i) { }
 
  1477       InEdgeIt (Invalid i) : Edge(i) { }
 
  1475       InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
 
  1478       InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
 
  1476     };
 
  1479     };
 
  1477 
  1480 
  1478     template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
 
  1481     template <typename T> class NodeMap : 
       
  1482       public NodeGraphType::template NodeMap<T>
 
  1479     {
 
  1483     {
 
  1480     public:
 
  1484     public:
 
  1481       NodeMap(const EdgeSet &_G) :
 
  1485       NodeMap(const EdgeSet &_G) :
 
  1482 	NodeGraphType::NodeMap<T>(_G.G) { }
 
  1486         NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!!
 
  1483       NodeMap(const EdgeSet &_G,const T &t) :
 
  1487       NodeMap(const EdgeSet &_G,const T &t) :
 
  1484 	NodeGraphType::NodeMap<T>(_G.G,t) { }
 
  1488 	NodeGraphType::NodeMap(_G.G,t) { }
 
  1485       //It is unnecessary
 
  1489       //It is unnecessary
 
  1486       NodeMap(const typename NodeGraphType::NodeMap<T> &m)
 
  1490       NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
 
  1487 	: NodeGraphType::NodeMap<T>(m) { }
 
  1491 	NodeGraphType::NodeMap(m) { }
 
  1488 
  1492 
  1489       ///\todo It can copy between different types.
 
  1493       ///\todo It can copy between different types.
 
  1490       ///
 
  1494       ///
 
  1491       template<typename TT>
 
  1495       template<typename TT>
 
  1492       NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
 
  1496       NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
 
  1493 	: NodeGraphType::NodeMap<T>(m) { }
 
  1497 	: NodeGraphType::NodeMap(m) { }
 
  1494     };
 
  1498     };
 
  1495     
  1499     
  1496     template <typename T> class EdgeMap : public DynMapBase<Edge>
 
  1500     template <typename T> class EdgeMap : public DynMapBase<Edge>
 
  1497     {
 
  1501     {
 
  1498       std::vector<T> container;
 
  1502       std::vector<T> container;
lemon-0.x