Changeset 782:df2e45e09652 in lemon-0.x for src/hugo/list_graph.h
- Timestamp:
- 09/02/04 12:07:30 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1075
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/list_graph.h
r774 r782 9 9 10 10 #include <vector> 11 #include < limits.h>11 #include <climits> 12 12 13 13 #include <hugo/invalid.h> 14 15 #include <hugo/map_registry.h> 16 #include <hugo/array_map_factory.h> 17 18 #include <hugo/sym_map_factory.h> 19 20 #include <hugo/map_defines.h> 21 14 22 15 23 namespace hugo { … … 18 26 /// @{ 19 27 20 class SymListGraph;28 // class SymListGraph; 21 29 22 30 ///A list graph class. … … 57 65 int first_free_edge; 58 66 59 protected: 60 61 template <typename Key> class DynMapBase 62 { 63 protected: 64 const ListGraph* G; 65 public: 66 virtual void add(const Key k) = 0; 67 virtual void erase(const Key k) = 0; 68 DynMapBase(const ListGraph &_G) : G(&_G) {} 69 virtual ~DynMapBase() {} 70 friend class ListGraph; 71 }; 72 73 public: 74 template <typename T> class EdgeMap; 75 template <typename T> class NodeMap; 67 public: 68 69 typedef ListGraph Graph; 76 70 77 71 class Node; 78 72 class Edge; 79 73 80 // protected:81 // HELPME:82 protected:83 ///\bug It must be public because of SymEdgeMap.84 ///85 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;86 ///\bug It must be public because of SymEdgeMap.87 ///88 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;89 74 90 75 public: … … 94 79 class OutEdgeIt; 95 80 class InEdgeIt; 96 97 public: 98 99 ListGraph() : nodes(), first_node(-1), 100 first_free_node(-1), edges(), first_free_edge(-1) {} 101 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node), 102 first_free_node(_g.first_free_node), 103 edges(_g.edges), 104 first_free_edge(_g.first_free_edge) {} 105 106 ~ListGraph() 107 { 108 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 109 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 110 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 111 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 112 } 113 81 82 CREATE_MAP_REGISTRIES; 83 CREATE_MAPS(ArrayMapFactory); 84 85 public: 86 87 ListGraph() 88 : nodes(), first_node(-1), 89 first_free_node(-1), edges(), first_free_edge(-1) {} 90 91 ListGraph(const ListGraph &_g) 92 : nodes(_g.nodes), first_node(_g.first_node), 93 first_free_node(_g.first_free_node), edges(_g.edges), 94 first_free_edge(_g.first_free_edge) {} 95 114 96 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 115 97 int edgeNum() const { return edges.size(); } //FIXME: What is this? … … 171 153 172 154 //Update dynamic maps 173 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 174 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 155 node_maps.add(nn); 175 156 176 157 return nn; … … 203 184 204 185 //Update dynamic maps 205 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 206 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 186 edge_maps.add(e); 207 187 208 188 return e; … … 245 225 //Update dynamic maps 246 226 Edge e; e.n=n; 247 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();248 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); 227 edge_maps.erase(e); 228 249 229 } 250 230 … … 266 246 267 247 //Update dynamic maps 268 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();269 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 248 node_maps.erase(nn); 249 270 250 } 271 251 272 252 void erase(Edge e) { eraseEdge(e.n); } 273 253 274 ///\bug Dynamic maps must be updated!275 ///276 254 void clear() { 277 nodes.clear();edges.clear(); 255 edge_maps.clear(); 256 edges.clear(); 257 node_maps.clear(); 258 nodes.clear(); 278 259 first_node=first_free_node=first_free_edge=-1; 279 260 } … … 411 392 // operator bool() { return Edge::operator bool(); } 412 393 }; 413 414 template <typename T> class NodeMap : public DynMapBase<Node>415 {416 std::vector<T> container;417 418 public:419 typedef T ValueType;420 typedef Node KeyType;421 422 NodeMap(const ListGraph &_G) :423 DynMapBase<Node>(_G), container(_G.maxNodeId())424 {425 G->dyn_node_maps.push_back(this);426 }427 NodeMap(const ListGraph &_G,const T &t) :428 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)429 {430 G->dyn_node_maps.push_back(this);431 }432 433 NodeMap(const NodeMap<T> &m) :434 DynMapBase<Node>(*m.G), container(m.container)435 {436 G->dyn_node_maps.push_back(this);437 }438 439 template<typename TT> friend class NodeMap;440 441 ///\todo It can copy between different types.442 ///443 template<typename TT> NodeMap(const NodeMap<TT> &m) :444 DynMapBase<Node>(*m.G), container(m.container.size())445 446 {447 G->dyn_node_maps.push_back(this);448 typename std::vector<TT>::const_iterator i;449 for(typename std::vector<TT>::const_iterator i=m.container.begin();450 i!=m.container.end();451 i++)452 container.push_back(*i);453 }454 ~NodeMap()455 {456 if(G) {457 std::vector<DynMapBase<Node>* >::iterator i;458 for(i=G->dyn_node_maps.begin();459 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;460 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...461 //A better way to do that: (Is this really important?)462 if(*i==this) {463 *i=G->dyn_node_maps.back();464 G->dyn_node_maps.pop_back();465 }466 }467 }468 469 void add(const Node k)470 {471 if(k.n>=int(container.size())) container.resize(k.n+1);472 }473 474 void erase(const Node) { }475 476 void set(Node n, T a) { container[n.n]=a; }477 //'T& operator[](Node n)' would be wrong here478 typename std::vector<T>::reference479 operator[](Node n) { return container[n.n]; }480 //'const T& operator[](Node n)' would be wrong here481 typename std::vector<T>::const_reference482 operator[](Node n) const { return container[n.n]; }483 484 ///\warning There is no safety check at all!485 ///Using operator = between maps attached to different graph may486 ///cause serious problem.487 ///\todo Is this really so?488 ///\todo It can copy between different types.489 const NodeMap<T>& operator=(const NodeMap<T> &m)490 {491 container = m.container;492 return *this;493 }494 template<typename TT>495 const NodeMap<T>& operator=(const NodeMap<TT> &m)496 {497 std::copy(m.container.begin(), m.container.end(), container.begin());498 return *this;499 }500 501 void update() {} //Useless for Dynamic Maps502 void update(T a) {} //Useless for Dynamic Maps503 };504 505 template <typename T> class EdgeMap : public DynMapBase<Edge>506 {507 protected:508 std::vector<T> container;509 510 public:511 typedef T ValueType;512 typedef Edge KeyType;513 514 EdgeMap(const ListGraph &_G) :515 DynMapBase<Edge>(_G), container(_G.maxEdgeId())516 {517 //FIXME: What if there are empty Id's?518 //FIXME: Can I use 'this' in a constructor?519 G->dyn_edge_maps.push_back(this);520 }521 EdgeMap(const ListGraph &_G,const T &t) :522 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)523 {524 G->dyn_edge_maps.push_back(this);525 }526 EdgeMap(const EdgeMap<T> &m) :527 DynMapBase<Edge>(*m.G), container(m.container)528 {529 G->dyn_edge_maps.push_back(this);530 }531 532 template<typename TT> friend class EdgeMap;533 534 ///\todo It can copy between different types.535 ///536 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :537 DynMapBase<Edge>(*m.G), container(m.container.size())538 {539 G->dyn_edge_maps.push_back(this);540 typename std::vector<TT>::const_iterator i;541 for(typename std::vector<TT>::const_iterator i=m.container.begin();542 i!=m.container.end();543 i++)544 container.push_back(*i);545 }546 ~EdgeMap()547 {548 if(G) {549 std::vector<DynMapBase<Edge>* >::iterator i;550 for(i=G->dyn_edge_maps.begin();551 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;552 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...553 //A better way to do that: (Is this really important?)554 if(*i==this) {555 *i=G->dyn_edge_maps.back();556 G->dyn_edge_maps.pop_back();557 }558 }559 }560 561 void add(const Edge k)562 {563 if(k.n>=int(container.size())) container.resize(k.n+1);564 }565 void erase(const Edge) { }566 567 void set(Edge n, T a) { container[n.n]=a; }568 //T get(Edge n) const { return container[n.n]; }569 typename std::vector<T>::reference570 operator[](Edge n) { return container[n.n]; }571 typename std::vector<T>::const_reference572 operator[](Edge n) const { return container[n.n]; }573 574 ///\warning There is no safety check at all!575 ///Using operator = between maps attached to different graph may576 ///cause serious problem.577 ///\todo Is this really so?578 ///\todo It can copy between different types.579 const EdgeMap<T>& operator=(const EdgeMap<T> &m)580 {581 container = m.container;582 return *this;583 }584 template<typename TT>585 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)586 {587 std::copy(m.container.begin(), m.container.end(), container.begin());588 return *this;589 }590 591 void update() {} //Useless for DynMaps592 void update(T a) {} //Useless for DynMaps593 };594 595 394 }; 596 395 … … 616 415 ///\todo this date structure need some reconsiderations. Maybe it 617 416 ///should be implemented independently from ListGraph. 618 417 619 418 class SymListGraph : public ListGraph 620 419 { 621 420 public: 622 template<typename T> class SymEdgeMap; 623 template<typename T> friend class SymEdgeMap; 421 422 typedef SymListGraph Graph; 423 424 KEEP_NODE_MAP(ListGraph); 425 KEEP_EDGE_MAP(ListGraph); 426 427 CREATE_SYM_EDGE_MAP_REGISTRY; 428 CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory); 429 IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory); 624 430 625 431 SymListGraph() : ListGraph() { } … … 629 435 { 630 436 Edge e = ListGraph::addEdge(u,v); 631 ListGraph::addEdge(v,u); 437 Edge f = ListGraph::addEdge(v,u); 438 sym_edge_maps.add(e); 439 sym_edge_maps.add(f); 440 632 441 return e; 633 442 } 634 443 635 void erase(Node n) { ListGraph::erase(n); 444 void erase(Node n) { ListGraph::erase(n);} 636 445 ///The oppositely directed edge. 637 446 … … 647 456 ///Removes a pair of oppositely directed edges to the graph. 648 457 void erase(Edge e) { 649 ListGraph::erase(opposite(e)); 458 Edge f = opposite(e); 459 sym_edge_maps.erase(e); 460 sym_edge_maps.erase(f); 461 ListGraph::erase(f); 650 462 ListGraph::erase(e); 651 } 652 653 ///Common data storage for the edge pairs. 654 655 ///This map makes it possible to store data shared by the oppositely 656 ///directed pairs of edges. 657 template <typename T> class SymEdgeMap : public DynMapBase<Edge> 658 { 659 std::vector<T> container; 660 661 public: 662 typedef T ValueType; 663 typedef Edge KeyType; 664 665 SymEdgeMap(const SymListGraph &_G) : 666 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) 667 { 668 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this); 669 } 670 SymEdgeMap(const SymListGraph &_G,const T &t) : 671 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) 672 { 673 G->dyn_edge_maps.push_back(this); 674 } 675 676 SymEdgeMap(const SymEdgeMap<T> &m) : 677 DynMapBase<SymEdge>(*m.G), container(m.container) 678 { 679 G->dyn_node_maps.push_back(this); 680 } 681 682 // template<typename TT> friend class SymEdgeMap; 683 684 ///\todo It can copy between different types. 685 /// 686 687 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) : 688 DynMapBase<SymEdge>(*m.G), container(m.container.size()) 689 { 690 G->dyn_node_maps.push_back(this); 691 typename std::vector<TT>::const_iterator i; 692 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 693 i!=m.container.end(); 694 i++) 695 container.push_back(*i); 696 } 697 698 ~SymEdgeMap() 699 { 700 if(G) { 701 std::vector<DynMapBase<Edge>* >::iterator i; 702 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin(); 703 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end() 704 && *i!=this; ++i) ; 705 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... 706 //A better way to do that: (Is this really important?) 707 if(*i==this) { 708 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back(); 709 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back(); 710 } 711 } 712 } 713 714 void add(const Edge k) 715 { 716 if(!k.idref()%2&&k.idref()/2>=int(container.size())) 717 container.resize(k.idref()/2+1); 718 } 719 void erase(const Edge k) { } 720 721 void set(Edge n, T a) { container[n.idref()/2]=a; } 722 //T get(Edge n) const { return container[n.idref()/2]; } 723 typename std::vector<T>::reference 724 operator[](Edge n) { return container[n.idref()/2]; } 725 typename std::vector<T>::const_reference 726 operator[](Edge n) const { return container[n.idref()/2]; } 727 728 ///\warning There is no safety check at all! 729 ///Using operator = between maps attached to different graph may 730 ///cause serious problem. 731 ///\todo Is this really so? 732 ///\todo It can copy between different types. 733 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m) 734 { 735 container = m.container; 736 return *this; 737 } 738 template<typename TT> 739 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m) 740 { 741 std::copy(m.container.begin(), m.container.end(), container.begin()); 742 return *this; 743 } 744 745 void update() {} //Useless for DynMaps 746 void update(T a) {} //Useless for DynMaps 747 748 }; 749 463 } 750 464 }; 751 465 752 466 753 467 ///A graph class containing only nodes. … … 780 494 int first_free_node; 781 495 782 protected: 783 784 template <typename Key> class DynMapBase 785 { 786 protected: 787 const NodeSet* G; 788 public: 789 virtual void add(const Key k) = 0; 790 virtual void erase(const Key k) = 0; 791 DynMapBase(const NodeSet &_G) : G(&_G) {} 792 virtual ~DynMapBase() {} 793 friend class NodeSet; 794 }; 795 796 public: 797 template <typename T> class EdgeMap; 798 template <typename T> class NodeMap; 496 public: 497 498 typedef NodeSet Graph; 799 499 800 500 class Node; 801 501 class Edge; 802 502 803 // protected:804 // HELPME:805 protected:806 ///\bug It must be public because of SymEdgeMap.807 ///808 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;809 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;810 811 503 public: 812 504 … … 816 508 class InEdgeIt; 817 509 818 template <typename T> class NodeMap;819 template <typename T> class EdgeMap;510 CREATE_MAP_REGISTRIES; 511 CREATE_MAPS(ArrayMapFactory); 820 512 821 513 public: 822 514 823 515 ///Default constructor 824 NodeSet() : nodes(), first_node(-1),825 516 NodeSet() 517 : nodes(), first_node(-1), first_free_node(-1) {} 826 518 ///Copy constructor 827 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), 828 first_free_node(_g.first_free_node) {} 829 830 ~NodeSet() 831 { 832 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 833 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 834 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 835 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 836 } 837 519 NodeSet(const NodeSet &_g) 520 : nodes(_g.nodes), first_node(_g.first_node), 521 first_free_node(_g.first_free_node) {} 522 838 523 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 839 524 int edgeNum() const { return 0; } //FIXME: What is this? … … 888 573 889 574 //Update dynamic maps 890 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 891 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 575 node_maps.add(nn); 892 576 893 577 return nn; … … 905 589 906 590 //Update dynamic maps 907 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 908 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 591 node_maps.erase(nn); 909 592 } 910 593 … … 915 598 } 916 599 917 ///\bug Dynamic maps must be updated!918 ///919 600 void clear() { 601 node_maps.clear(); 920 602 nodes.clear(); 921 603 first_node = first_free_node = -1; … … 1013 695 }; 1014 696 1015 template <typename T> class NodeMap : public DynMapBase<Node>1016 {1017 std::vector<T> container;1018 1019 public:1020 typedef T ValueType;1021 typedef Node KeyType;1022 1023 NodeMap(const NodeSet &_G) :1024 DynMapBase<Node>(_G), container(_G.maxNodeId())1025 {1026 G->dyn_node_maps.push_back(this);1027 }1028 NodeMap(const NodeSet &_G,const T &t) :1029 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)1030 {1031 G->dyn_node_maps.push_back(this);1032 }1033 1034 NodeMap(const NodeMap<T> &m) :1035 DynMapBase<Node>(*m.G), container(m.container)1036 {1037 G->dyn_node_maps.push_back(this);1038 }1039 1040 template<typename TT> friend class NodeMap;1041 1042 ///\todo It can copy between different types.1043 ///1044 template<typename TT> NodeMap(const NodeMap<TT> &m) :1045 DynMapBase<Node>(*m.G), container(m.container.size())1046 {1047 G->dyn_node_maps.push_back(this);1048 typename std::vector<TT>::const_iterator i;1049 for(typename std::vector<TT>::const_iterator i=m.container.begin();1050 i!=m.container.end();1051 i++)1052 container.push_back(*i);1053 }1054 ~NodeMap()1055 {1056 if(G) {1057 std::vector<DynMapBase<Node>* >::iterator i;1058 for(i=G->dyn_node_maps.begin();1059 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;1060 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...1061 //A better way to do that: (Is this really important?)1062 if(*i==this) {1063 *i=G->dyn_node_maps.back();1064 G->dyn_node_maps.pop_back();1065 }1066 }1067 }1068 1069 void add(const Node k)1070 {1071 if(k.n>=int(container.size())) container.resize(k.n+1);1072 }1073 1074 void erase(const Node) { }1075 1076 void set(Node n, T a) { container[n.n]=a; }1077 //'T& operator[](Node n)' would be wrong here1078 typename std::vector<T>::reference1079 operator[](Node n) { return container[n.n]; }1080 //'const T& operator[](Node n)' would be wrong here1081 typename std::vector<T>::const_reference1082 operator[](Node n) const { return container[n.n]; }1083 1084 ///\warning There is no safety check at all!1085 ///Using operator = between maps attached to different graph may1086 ///cause serious problem.1087 ///\todo Is this really so?1088 ///\todo It can copy between different types.1089 const NodeMap<T>& operator=(const NodeMap<T> &m)1090 {1091 container = m.container;1092 return *this;1093 }1094 template<typename TT>1095 const NodeMap<T>& operator=(const NodeMap<TT> &m)1096 {1097 std::copy(m.container.begin(), m.container.end(), container.begin());1098 return *this;1099 }1100 1101 void update() {} //Useless for Dynamic Maps1102 void update(T a) {} //Useless for Dynamic Maps1103 };1104 1105 template <typename T> class EdgeMap1106 {1107 public:1108 typedef T ValueType;1109 typedef Edge KeyType;1110 1111 EdgeMap(const NodeSet &) { }1112 EdgeMap(const NodeSet &,const T &) { }1113 EdgeMap(const EdgeMap<T> &) { }1114 // template<typename TT> friend class EdgeMap;1115 1116 ///\todo It can copy between different types.1117 ///1118 template<typename TT> EdgeMap(const EdgeMap<TT> &) { }1119 ~EdgeMap() { }1120 1121 void add(const Edge ) { }1122 void erase(const Edge) { }1123 1124 void set(Edge, T) { }1125 //T get(Edge n) const { return container[n.n]; }1126 ValueType &operator[](Edge) { return *((T*)(NULL)); }1127 const ValueType &operator[](Edge) const { return *((T*)(NULL)); }1128 1129 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }1130 1131 template<typename TT>1132 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }1133 1134 void update() {}1135 void update(T a) {}1136 };1137 697 }; 1138 698 … … 1167 727 1168 728 public: 729 1169 730 class Node; 1170 731 class Edge; … … 1172 733 class InEdgeIt; 1173 734 class SymEdge; 735 736 typedef EdgeSet Graph; 737 1174 738 int id(Node v) const; 1175 739 … … 1230 794 int first_free_edge; 1231 795 1232 protected: 1233 1234 template <typename Key> class DynMapBase 1235 { 1236 protected: 1237 const EdgeSet* G; 1238 public: 1239 virtual void add(const Key k) = 0; 1240 virtual void erase(const Key k) = 0; 1241 DynMapBase(const EdgeSet &_G) : G(&_G) {} 1242 virtual ~DynMapBase() {} 1243 friend class EdgeSet; 1244 }; 1245 1246 public: 1247 //template <typename T> class NodeMap; 1248 template <typename T> class EdgeMap; 796 public: 1249 797 1250 798 class Node; 1251 799 class Edge; 1252 1253 // protected:1254 // HELPME:1255 protected:1256 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;1257 ///\bug It must be public because of SymEdgeMap.1258 ///1259 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;1260 1261 public:1262 800 1263 801 class NodeIt; … … 1265 803 class OutEdgeIt; 1266 804 class InEdgeIt; 1267 1268 template <typename T> class NodeMap; 1269 template <typename T> class EdgeMap; 805 806 807 CREATE_EDGE_MAP_REGISTRY; 808 CREATE_EDGE_MAP_FACTORY(ArrayMapFactory); 809 IMPORT_EDGE_MAP(EdgeMapFactory); 810 1270 811 1271 812 public: … … 1276 817 ///\param _G the base graph. 1277 818 ///\todo It looks like a copy constructor, but it isn't. 1278 EdgeSet(NodeGraphType &_G) : G(_G),1279 1280 first_free_edge(-1) {}819 EdgeSet(NodeGraphType &_G) 820 : G(_G), nodes(_G), edges(), 821 first_free_edge(-1) {} 1281 822 ///Copy constructor 1282 823 1283 824 ///Makes a copy of an EdgeSet. 1284 825 ///It will be based on the same graph. 1285 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), 1286 first_free_edge(_g.first_free_edge) { } 1287 1288 ~EdgeSet() 1289 { 1290 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 1291 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 1292 for(typename std::vector<DynMapBase<Edge> * >::iterator 1293 i=dyn_edge_maps.begin(); 1294 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 1295 } 1296 826 EdgeSet(const EdgeSet &_g) 827 : G(_g.G), nodes(_g.G), edges(_g.edges), 828 first_free_edge(_g.first_free_edge) {} 829 1297 830 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? 1298 831 int edgeNum() const { return edges.size(); } //FIXME: What is this? … … 1348 881 1349 882 //Update dynamic maps 1350 for(typename std::vector<DynMapBase<Edge> * >::iterator 1351 i=dyn_edge_maps.begin(); 1352 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 883 edge_maps.add(e); 1353 884 1354 885 return e; … … 1390 921 1391 922 //Update dynamic maps 1392 Edge e; e.n=n; 1393 for(typename std::vector<DynMapBase<Edge> * >::iterator 1394 i=dyn_edge_maps.begin(); 1395 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); 923 Edge e; e.n = n; 924 edge_maps.erase(e); 1396 925 } 1397 926 … … 1409 938 ///Clear all edges. (Doesn't clear the nodes!) 1410 939 void clear() { 940 edge_maps.clear(); 1411 941 edges.clear(); 1412 942 first_free_edge=-1; … … 1414 944 1415 945 1416 // //\bug Dynamic maps must be updated!1417 // //1418 // void clear() {1419 // nodes.clear();edges.clear();1420 // first_node=first_free_node=first_free_edge=-1;1421 // }1422 1423 public:1424 template <typename T> class EdgeMap;1425 1426 ///1427 946 class Edge { 1428 947 public: … … 1491 1010 OutEdgeIt(const EdgeSet& _G,const Node v) : 1492 1011 Edge(_G.nodes[v].first_out), G(&_G) { } 1493 OutEdgeIt &operator++() { n =G->edges[n].next_out; return *this; }1012 OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; } 1494 1013 }; 1495 1014 … … 1506 1025 }; 1507 1026 1508 template <typename T> class NodeMap : 1509 public NodeGraphType::template NodeMap<T> 1027 1028 template <typename V> class NodeMap 1029 : public NodeGraphType::template NodeMap<V> 1510 1030 { 1511 1031 //This is a must, the constructors need it. 1512 typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap; 1513 public: 1514 NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { } 1515 NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { } 1516 //It is unnecessary 1517 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) : 1518 ParentNodeMap(m) { } 1519 1520 ///\todo It can copy between different types. 1521 /// 1522 template<typename TT> 1523 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m) 1524 : ParentNodeMap(m) { } 1525 }; 1526 1527 /// 1528 template <typename T> class EdgeMap : public DynMapBase<Edge> 1529 { 1530 protected: 1531 public: 1532 ///\bug It should be at least protected 1533 /// 1534 std::vector<T> container; 1535 1536 public: 1537 typedef T ValueType; 1538 typedef Edge KeyType; 1539 1540 EdgeMap(const EdgeSet &_G) : 1541 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 1542 { 1543 //FIXME: What if there are empty Id's? 1544 //FIXME: Can I use 'this' in a constructor? 1545 this->G->dyn_edge_maps.push_back(this); 1546 } 1547 EdgeMap(const EdgeSet &_G,const T &t) : 1548 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) 1549 { 1550 this->G->dyn_edge_maps.push_back(this); 1551 } 1552 EdgeMap(const EdgeMap<T> &m) : 1553 DynMapBase<Edge>(*m.G), container(m.container) 1554 { 1555 this->G->dyn_edge_maps.push_back(this); 1556 } 1557 1558 ///\todo It can copy between different types. 1559 /// 1560 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : 1561 DynMapBase<Edge>(*m.G), container(m.container.size()) 1562 { 1563 this->G->dyn_edge_maps.push_back(this); 1564 typename std::vector<TT>::const_iterator i; 1565 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 1566 i!=m.container.end(); 1567 i++) 1568 container.push_back(*i); 1569 } 1570 ~EdgeMap() 1571 { 1572 if(this->G) { 1573 typename std::vector<DynMapBase<Edge>* >::iterator i; 1574 for(i=this->G->dyn_edge_maps.begin(); 1575 i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; 1576 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... 1577 //A better way to do that: (Is this really important?) 1578 if(*i==this) { 1579 *i=this->G->dyn_edge_maps.back(); 1580 this->G->dyn_edge_maps.pop_back(); 1581 } 1582 } 1583 } 1584 1585 void add(const Edge k) 1586 { 1587 if(k.n>=int(container.size())) container.resize(k.n+1); 1588 } 1589 void erase(const Edge) { } 1590 1591 ///\bug This doesn't work. Why? 1592 /// void set(Edge n, T a) { container[n.n]=a; } 1593 void set(Edge n, T a) { container[this->G->id(n)]=a; } 1594 //T get(Edge n) const { return container[n.n]; } 1595 typename std::vector<T>::reference 1596 ///\bug This doesn't work. Why? 1597 /// operator[](Edge n) { return container[n.n]; } 1598 operator[](Edge n) { return container[this->G->id(n)]; } 1599 typename std::vector<T>::const_reference 1600 ///\bug This doesn't work. Why? 1601 /// operator[](Edge n) const { return container[n.n]; } 1602 operator[](Edge n) const { return container[this->G->id(n)]; } 1603 1604 ///\warning There is no safety check at all! 1605 ///Using operator = between maps attached to different graph may 1606 ///cause serious problem. 1607 ///\todo Is this really so? 1608 ///\todo It can copy between different types. 1609 const EdgeMap<T>& operator=(const EdgeMap<T> &m) 1610 { 1611 container = m.container; 1032 typedef typename NodeGraphType::template NodeMap<V> MapImpl; 1033 typedef V Value; 1034 public: 1035 NodeMap() : MapImpl() {} 1036 1037 NodeMap(const EdgeSet& graph) 1038 : MapImpl(graph.G) { } 1039 1040 NodeMap(const EdgeSet& graph, const Value& value) 1041 : MapImpl(graph.G, value) { } 1042 1043 NodeMap(const NodeMap& copy) 1044 : MapImpl(static_cast<const MapImpl&>(copy)) {} 1045 1046 template<typename CMap> 1047 NodeMap(const CMap& copy) 1048 : MapImpl(copy) { } 1049 1050 NodeMap& operator=(const NodeMap& copy) { 1051 MapImpl::operator=(static_cast<const MapImpl&>(copy)); 1612 1052 return *this; 1613 1053 } 1614 1615 template<typename TT> friend class EdgeMap; 1616 1617 template<typename TT> 1618 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) 1619 { 1620 std::copy(m.container.begin(), m.container.end(), container.begin()); 1054 1055 template <typename CMap> 1056 NodeMap& operator=(const CMap& copy) { 1057 MapImpl::operator=(copy); 1621 1058 return *this; 1622 1059 } 1623 1624 void update() {} //Useless for DynMaps 1625 void update(T a) {} //Useless for DynMaps 1626 }; 1627 1060 1061 }; 1628 1062 }; 1629 1063
Note: See TracChangeset
for help on using the changeset viewer.