Changeset 867:994c7df296c9 in lemon for lemon
 Timestamp:
 12/10/09 17:05:35 (10 years ago)
 Branch:
 default
 Children:
 868:76689f2fc02d, 869:1b89e29c9fc7, 900:5100072d83ca
 Parents:
 865:e9c203fb003d (diff), 765:703ebf476a1d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Location:
 lemon
 Files:

 1 deleted
 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bits/map_extender.h
r765 r867 85 85 typedef typename Map::Value Value; 86 86 87 MapIt() {}88 89 MapIt(Invalid i) : Parent(i) {}90 91 explicit MapIt(Map& _map) : map( _map) {92 map .notifier()>first(*this);87 MapIt() : map(NULL) {} 88 89 MapIt(Invalid i) : Parent(i), map(NULL) {} 90 91 explicit MapIt(Map& _map) : map(&_map) { 92 map>notifier()>first(*this); 93 93 } 94 94 95 95 MapIt(const Map& _map, const Item& item) 96 : Parent(item), map(&_map) {} 97 98 MapIt& operator++() { 99 map>notifier()>next(*this); 100 return *this; 101 } 102 103 typename MapTraits<Map>::ConstReturnValue operator*() const { 104 return (*map)[*this]; 105 } 106 107 typename MapTraits<Map>::ReturnValue operator*() { 108 return (*map)[*this]; 109 } 110 111 void set(const Value& value) { 112 map>set(*this, value); 113 } 114 115 protected: 116 Map* map; 117 118 }; 119 120 class ConstMapIt : public Item { 121 typedef Item Parent; 122 123 public: 124 125 typedef typename Map::Value Value; 126 127 ConstMapIt() : map(NULL) {} 128 129 ConstMapIt(Invalid i) : Parent(i), map(NULL) {} 130 131 explicit ConstMapIt(Map& _map) : map(&_map) { 132 map>notifier()>first(*this); 133 } 134 135 ConstMapIt(const Map& _map, const Item& item) 96 136 : Parent(item), map(_map) {} 97 137 98 MapIt& operator++() {99 map .notifier()>next(*this);138 ConstMapIt& operator++() { 139 map>notifier()>next(*this); 100 140 return *this; 101 141 } … … 105 145 } 106 146 107 typename MapTraits<Map>::ReturnValue operator*() { 108 return map[*this]; 109 } 110 111 void set(const Value& value) { 112 map.set(*this, value); 113 } 114 115 protected: 116 Map& map; 117 118 }; 119 120 class ConstMapIt : public Item { 121 typedef Item Parent; 122 123 public: 124 125 typedef typename Map::Value Value; 126 127 ConstMapIt() {} 128 129 ConstMapIt(Invalid i) : Parent(i) { } 130 131 explicit ConstMapIt(Map& _map) : map(_map) { 132 map.notifier()>first(*this); 133 } 134 135 ConstMapIt(const Map& _map, const Item& item) 136 : Parent(item), map(_map) {} 137 138 ConstMapIt& operator++() { 139 map.notifier()>next(*this); 140 return *this; 141 } 142 143 typename MapTraits<Map>::ConstReturnValue operator*() const { 144 return map[*this]; 145 } 146 147 protected: 148 const Map& map; 147 protected: 148 const Map* map; 149 149 }; 150 150 … … 153 153 154 154 public: 155 156 ItemIt() {} 157 158 ItemIt(Invalid i) : Parent(i) {}159 160 explicit ItemIt(Map& _map) : map( _map) {161 map .notifier()>first(*this);155 ItemIt() : map(NULL) {} 156 157 158 ItemIt(Invalid i) : Parent(i), map(NULL) {} 159 160 explicit ItemIt(Map& _map) : map(&_map) { 161 map>notifier()>first(*this); 162 162 } 163 163 164 164 ItemIt(const Map& _map, const Item& item) 165 : Parent(item), map( _map) {}165 : Parent(item), map(&_map) {} 166 166 167 167 ItemIt& operator++() { 168 map .notifier()>next(*this);169 return *this; 170 } 171 172 protected: 173 const Map ↦168 map>notifier()>next(*this); 169 return *this; 170 } 171 172 protected: 173 const Map* map; 174 174 175 175 }; … … 232 232 typedef typename Map::Value Value; 233 233 234 MapIt() {}235 236 MapIt(Invalid i) : Parent(i) { }237 238 explicit MapIt(Map& _map) : map( _map) {239 map .graph.first(*this);234 MapIt() : map(NULL) {} 235 236 MapIt(Invalid i) : Parent(i), map(NULL) { } 237 238 explicit MapIt(Map& _map) : map(&_map) { 239 map>graph.first(*this); 240 240 } 241 241 242 242 MapIt(const Map& _map, const Item& item) 243 : Parent(item), map( _map) {}243 : Parent(item), map(&_map) {} 244 244 245 245 MapIt& operator++() { 246 map .graph.next(*this);246 map>graph.next(*this); 247 247 return *this; 248 248 } 249 249 250 250 typename MapTraits<Map>::ConstReturnValue operator*() const { 251 return map[*this];251 return (*map)[*this]; 252 252 } 253 253 254 254 typename MapTraits<Map>::ReturnValue operator*() { 255 return map[*this];255 return (*map)[*this]; 256 256 } 257 257 258 258 void set(const Value& value) { 259 map .set(*this, value);260 } 261 262 protected: 263 Map ↦259 map>set(*this, value); 260 } 261 262 protected: 263 Map* map; 264 264 265 265 }; … … 272 272 typedef typename Map::Value Value; 273 273 274 ConstMapIt() {}275 276 ConstMapIt(Invalid i) : Parent(i) { }277 278 explicit ConstMapIt(Map& _map) : map( _map) {279 map .graph.first(*this);274 ConstMapIt() : map(NULL) {} 275 276 ConstMapIt(Invalid i) : Parent(i), map(NULL) { } 277 278 explicit ConstMapIt(Map& _map) : map(&_map) { 279 map>graph.first(*this); 280 280 } 281 281 282 282 ConstMapIt(const Map& _map, const Item& item) 283 : Parent(item), map( _map) {}283 : Parent(item), map(&_map) {} 284 284 285 285 ConstMapIt& operator++() { 286 map .graph.next(*this);286 map>graph.next(*this); 287 287 return *this; 288 288 } 289 289 290 290 typename MapTraits<Map>::ConstReturnValue operator*() const { 291 return map[*this];292 } 293 294 protected: 295 const Map ↦291 return (*map)[*this]; 292 } 293 294 protected: 295 const Map* map; 296 296 }; 297 297 … … 300 300 301 301 public: 302 303 ItemIt() {} 304 305 ItemIt(Invalid i) : Parent(i) { }306 307 explicit ItemIt(Map& _map) : map( _map) {308 map .graph.first(*this);302 ItemIt() : map(NULL) {} 303 304 305 ItemIt(Invalid i) : Parent(i), map(NULL) { } 306 307 explicit ItemIt(Map& _map) : map(&_map) { 308 map>graph.first(*this); 309 309 } 310 310 311 311 ItemIt(const Map& _map, const Item& item) 312 : Parent(item), map( _map) {}312 : Parent(item), map(&_map) {} 313 313 314 314 ItemIt& operator++() { 315 map .graph.next(*this);316 return *this; 317 } 318 319 protected: 320 const Map ↦315 map>graph.next(*this); 316 return *this; 317 } 318 319 protected: 320 const Map* map; 321 321 322 322 }; 
lemon/bits/map_extender.h
r865 r867 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 template <typename _Map> 38 38 class MapExtender : public _Map { 39 public:40 41 39 typedef _Map Parent; 40 typedef typename Parent::GraphType GraphType; 41 42 public: 43 42 44 typedef MapExtender Map; 43 44 45 typedef typename Parent::Graph Graph;46 45 typedef typename Parent::Key Item; 47 46 48 47 typedef typename Parent::Key Key; 49 48 typedef typename Parent::Value Value; 49 typedef typename Parent::Reference Reference; 50 typedef typename Parent::ConstReference ConstReference; 51 52 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 50 53 51 54 class MapIt; … … 57 60 public: 58 61 59 MapExtender(const Graph & graph)62 MapExtender(const GraphType& graph) 60 63 : Parent(graph) {} 61 64 62 MapExtender(const Graph & graph, const Value& value)65 MapExtender(const GraphType& graph, const Value& value) 63 66 : Parent(graph, value) {} 64 67 … … 76 79 public: 77 80 class MapIt : public Item { 78 public: 79 80 typedef Item Parent; 81 typedef Item Parent; 82 83 public: 84 81 85 typedef typename Map::Value Value; 82 86 … … 115 119 116 120 class ConstMapIt : public Item { 117 public:118 119 typedef Item Parent;121 typedef Item Parent; 122 123 public: 120 124 121 125 typedef typename Map::Value Value; … … 146 150 147 151 class ItemIt : public Item { 148 public: 149 150 typedef Item Parent; 151 152 typedef Item Parent; 153 154 public: 152 155 ItemIt() : map(NULL) {} 156 153 157 154 158 ItemIt(Invalid i) : Parent(i), map(NULL) {} … … 177 181 template <typename _Graph, typename _Map> 178 182 class SubMapExtender : public _Map { 179 public:180 181 183 typedef _Map Parent; 184 typedef _Graph GraphType; 185 186 public: 187 182 188 typedef SubMapExtender Map; 183 184 typedef _Graph Graph;185 186 189 typedef typename Parent::Key Item; 187 190 188 191 typedef typename Parent::Key Key; 189 192 typedef typename Parent::Value Value; 193 typedef typename Parent::Reference Reference; 194 typedef typename Parent::ConstReference ConstReference; 195 196 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 190 197 191 198 class MapIt; … … 197 204 public: 198 205 199 SubMapExtender(const Graph & _graph)206 SubMapExtender(const GraphType& _graph) 200 207 : Parent(_graph), graph(_graph) {} 201 208 202 SubMapExtender(const Graph & _graph, const Value& _value)209 SubMapExtender(const GraphType& _graph, const Value& _value) 203 210 : Parent(_graph, _value), graph(_graph) {} 204 211 … … 220 227 public: 221 228 class MapIt : public Item { 222 public:223 224 typedef Item Parent;229 typedef Item Parent; 230 231 public: 225 232 typedef typename Map::Value Value; 226 233 … … 259 266 260 267 class ConstMapIt : public Item { 261 public:262 263 typedef Item Parent;268 typedef Item Parent; 269 270 public: 264 271 265 272 typedef typename Map::Value Value; … … 290 297 291 298 class ItemIt : public Item { 292 public: 293 294 typedef Item Parent; 295 299 typedef Item Parent; 300 301 public: 296 302 ItemIt() : map(NULL) {} 303 297 304 298 305 ItemIt(Invalid i) : Parent(i), map(NULL) { } … … 317 324 private: 318 325 319 const Graph & graph;326 const GraphType& graph; 320 327 321 328 }; 
lemon/path.h
r606 r867 71 71 template <typename CPath> 72 72 Path(const CPath& cpath) { 73 copyPath(*this, cpath);73 pathCopy(cpath, *this); 74 74 } 75 75 … … 79 79 template <typename CPath> 80 80 Path& operator=(const CPath& cpath) { 81 copyPath(*this, cpath);81 pathCopy(cpath, *this); 82 82 return *this; 83 83 } … … 259 259 template <typename CPath> 260 260 SimplePath(const CPath& cpath) { 261 copyPath(*this, cpath);261 pathCopy(cpath, *this); 262 262 } 263 263 … … 268 268 template <typename CPath> 269 269 SimplePath& operator=(const CPath& cpath) { 270 copyPath(*this, cpath);270 pathCopy(cpath, *this); 271 271 return *this; 272 272 } … … 438 438 template <typename CPath> 439 439 ListPath(const CPath& cpath) : first(0), last(0) { 440 copyPath(*this, cpath);440 pathCopy(cpath, *this); 441 441 } 442 442 … … 454 454 template <typename CPath> 455 455 ListPath& operator=(const CPath& cpath) { 456 copyPath(*this, cpath);456 pathCopy(cpath, *this); 457 457 return *this; 458 458 } … … 764 764 template <typename CPath> 765 765 StaticPath(const CPath& cpath) : arcs(0) { 766 copyPath(*this, cpath);766 pathCopy(cpath, *this); 767 767 } 768 768 … … 780 780 template <typename CPath> 781 781 StaticPath& operator=(const CPath& cpath) { 782 copyPath(*this, cpath);782 pathCopy(cpath, *this); 783 783 return *this; 784 784 } … … 929 929 }; 930 930 931 template <typename Target, typename Source,932 bool buildEnable = BuildTagIndicator<T arget>::value>931 template <typename From, typename To, 932 bool buildEnable = BuildTagIndicator<To>::value> 933 933 struct PathCopySelectorForward { 934 static void copy( Target& target, const Source& source) {935 t arget.clear();936 for (typename Source::ArcIt it(source); it != INVALID; ++it) {937 t arget.addBack(it);934 static void copy(const From& from, To& to) { 935 to.clear(); 936 for (typename From::ArcIt it(from); it != INVALID; ++it) { 937 to.addBack(it); 938 938 } 939 939 } 940 940 }; 941 941 942 template <typename Target, typename Source>943 struct PathCopySelectorForward< Target, Source, true> {944 static void copy( Target& target, const Source& source) {945 t arget.clear();946 t arget.build(source);947 } 948 }; 949 950 template <typename Target, typename Source,951 bool buildEnable = BuildTagIndicator<T arget>::value>942 template <typename From, typename To> 943 struct PathCopySelectorForward<From, To, true> { 944 static void copy(const From& from, To& to) { 945 to.clear(); 946 to.build(from); 947 } 948 }; 949 950 template <typename From, typename To, 951 bool buildEnable = BuildTagIndicator<To>::value> 952 952 struct PathCopySelectorBackward { 953 static void copy( Target& target, const Source& source) {954 t arget.clear();955 for (typename Source::RevArcIt it(source); it != INVALID; ++it) {956 t arget.addFront(it);953 static void copy(const From& from, To& to) { 954 to.clear(); 955 for (typename From::RevArcIt it(from); it != INVALID; ++it) { 956 to.addFront(it); 957 957 } 958 958 } 959 959 }; 960 960 961 template <typename Target, typename Source>962 struct PathCopySelectorBackward< Target, Source, true> {963 static void copy( Target& target, const Source& source) {964 t arget.clear();965 t arget.buildRev(source);961 template <typename From, typename To> 962 struct PathCopySelectorBackward<From, To, true> { 963 static void copy(const From& from, To& to) { 964 to.clear(); 965 to.buildRev(from); 966 966 } 967 967 }; 968 968 969 969 970 template <typename Target, typename Source,971 bool revEnable = RevPathTagIndicator< Source>::value>970 template <typename From, typename To, 971 bool revEnable = RevPathTagIndicator<From>::value> 972 972 struct PathCopySelector { 973 static void copy( Target& target, const Source& source) {974 PathCopySelectorForward< Target, Source>::copy(target, source);973 static void copy(const From& from, To& to) { 974 PathCopySelectorForward<From, To>::copy(from, to); 975 975 } 976 976 }; 977 977 978 template <typename Target, typename Source>979 struct PathCopySelector< Target, Source, true> {980 static void copy( Target& target, const Source& source) {981 PathCopySelectorBackward< Target, Source>::copy(target, source);978 template <typename From, typename To> 979 struct PathCopySelector<From, To, true> { 980 static void copy(const From& from, To& to) { 981 PathCopySelectorBackward<From, To>::copy(from, to); 982 982 } 983 983 }; … … 988 988 /// \brief Make a copy of a path. 989 989 /// 990 /// This function makes a copy of a path. 991 template <typename Target, typename Source> 992 void copyPath(Target& target, const Source& source) { 993 checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>(); 994 _path_bits::PathCopySelector<Target, Source>::copy(target, source); 990 /// This function makes a copy of a path. 991 template <typename From, typename To> 992 void pathCopy(const From& from, To& to) { 993 checkConcept<concepts::PathDumper<typename From::Digraph>, From>(); 994 _path_bits::PathCopySelector<From, To>::copy(from, to); 995 } 996 997 /// \brief Deprecated version of \ref pathCopy(). 998 /// 999 /// Deprecated version of \ref pathCopy() (only for reverse compatibility). 1000 template <typename To, typename From> 1001 void copyPath(To& to, const From& from) { 1002 pathCopy(from, to); 995 1003 } 996 1004 … … 1016 1024 /// \brief The source of a path 1017 1025 /// 1018 /// This function returns the source of the given path. 1026 /// This function returns the source node of the given path. 1027 /// If the path is empty, then it returns \c INVALID. 1019 1028 template <typename Digraph, typename Path> 1020 1029 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { 1021 return digraph.source(path.front());1030 return path.empty() ? INVALID : digraph.source(path.front()); 1022 1031 } 1023 1032 1024 1033 /// \brief The target of a path 1025 1034 /// 1026 /// This function returns the target of the given path. 1035 /// This function returns the target node of the given path. 1036 /// If the path is empty, then it returns \c INVALID. 1027 1037 template <typename Digraph, typename Path> 1028 1038 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { 1029 return digraph.target(path.back());1039 return path.empty() ? INVALID : digraph.target(path.back()); 1030 1040 } 1031 1041 
lemon/path.h
r551 r867 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 41 41 /// 42 42 /// A structure for representing directed path in a digraph. 43 /// \tparam _DigraphThe digraph type in which the path is.43 /// \tparam GR The digraph type in which the path is. 44 44 /// 45 45 /// In a sense, the path can be treated as a list of arcs. The … … 53 53 /// implementation uses two vectors for storing the front and back 54 54 /// insertions. 55 template <typename _Digraph>55 template <typename GR> 56 56 class Path { 57 57 public: 58 58 59 typedef _DigraphDigraph;59 typedef GR Digraph; 60 60 typedef typename Digraph::Arc Arc; 61 61 … … 138 138 /// \brief The nth arc. 139 139 /// 140 /// \pre n is in the [0..length()  1] range140 /// \pre \c n is in the <tt>[0..length()  1]</tt> range. 141 141 const Arc& nth(int n) const { 142 142 return n < int(head.size()) ? *(head.rbegin() + n) : … … 146 146 /// \brief Initialize arc iterator to point to the nth arc 147 147 /// 148 /// \pre n is in the [0..length()  1] range148 /// \pre \c n is in the <tt>[0..length()  1]</tt> range. 149 149 ArcIt nthIt(int n) const { 150 150 return ArcIt(*this, n); … … 229 229 /// 230 230 /// A structure for representing directed path in a digraph. 231 /// \tparam _DigraphThe digraph type in which the path is.231 /// \tparam GR The digraph type in which the path is. 232 232 /// 233 233 /// In a sense, the path can be treated as a list of arcs. The … … 241 241 /// then the \c Path type because it use just one vector for the 242 242 /// arcs. 243 template <typename _Digraph>243 template <typename GR> 244 244 class SimplePath { 245 245 public: 246 246 247 typedef _DigraphDigraph;247 typedef GR Digraph; 248 248 typedef typename Digraph::Arc Arc; 249 249 … … 330 330 /// \brief The nth arc. 331 331 /// 332 /// \pre n is in the [0..length()  1] range332 /// \pre \c n is in the <tt>[0..length()  1]</tt> range. 333 333 const Arc& nth(int n) const { 334 334 return data[n]; … … 393 393 /// 394 394 /// A structure for representing directed path in a digraph. 395 /// \tparam _DigraphThe digraph type in which the path is.395 /// \tparam GR The digraph type in which the path is. 396 396 /// 397 397 /// In a sense, the path can be treated as a list of arcs. The … … 405 405 /// time. The front and back insertion and erasure is O(1) time 406 406 /// and it can be splited and spliced in O(1) time. 407 template <typename _Digraph>407 template <typename GR> 408 408 class ListPath { 409 409 public: 410 410 411 typedef _DigraphDigraph;411 typedef GR Digraph; 412 412 typedef typename Digraph::Arc Arc; 413 413 … … 508 508 /// 509 509 /// This function looks for the nth arc in O(n) time. 510 /// \pre n is in the [0..length()  1] range510 /// \pre \c n is in the <tt>[0..length()  1]</tt> range. 511 511 const Arc& nth(int n) const { 512 512 Node *node = first; … … 733 733 /// 734 734 /// A structure for representing directed path in a digraph. 735 /// \tparam _DigraphThe digraph type in which the path is.735 /// \tparam GR The digraph type in which the path is. 736 736 /// 737 737 /// In a sense, the path can be treated as a list of arcs. The … … 747 747 /// it is intented to be 748 748 /// used when you want to store a large number of paths. 749 template <typename _Digraph>749 template <typename GR> 750 750 class StaticPath { 751 751 public: 752 752 753 typedef _DigraphDigraph;753 typedef GR Digraph; 754 754 typedef typename Digraph::Arc Arc; 755 755 … … 834 834 /// \brief The nth arc. 835 835 /// 836 /// \pre n is in the [0..length()  1] range836 /// \pre \c n is in the <tt>[0..length()  1]</tt> range. 837 837 const Arc& nth(int n) const { 838 838 return arcs[n];
Note: See TracChangeset
for help on using the changeset viewer.