1 /* -*- C++ -*- |
|
2 * src/lemon/sym_map.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_SYM_MAP_H |
|
18 #define LEMON_SYM_MAP_H |
|
19 |
|
20 ///\ingroup graphmaps |
|
21 ///\file |
|
22 ///\brief Graph maps that construates and destruates |
|
23 ///their elements dynamically. |
|
24 |
|
25 namespace lemon { |
|
26 |
|
27 /// \addtogroup graphmaps |
|
28 /// @{ |
|
29 |
|
30 /** The SymEdgeIt is wrapper class for the EdgeIt. It can be used to |
|
31 * iterate on the symmetric maps when all of the edge - reverse edge pair |
|
32 * has different parity. |
|
33 */ |
|
34 |
|
35 |
|
36 template <typename Graph, typename Edge, typename EdgeIt> |
|
37 class SymEdgeIt : public EdgeIt { |
|
38 public: |
|
39 |
|
40 /** Default constructor. |
|
41 */ |
|
42 SymEdgeIt() |
|
43 : EdgeIt() {} |
|
44 |
|
45 /** Graph initialized constructor. |
|
46 */ |
|
47 SymEdgeIt(const Graph& graph) |
|
48 : EdgeIt(graph) { |
|
49 while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { |
|
50 EdgeIt::operator++(); |
|
51 } |
|
52 } |
|
53 |
|
54 /** Creating invelid SymEdgeIt. |
|
55 */ |
|
56 SymEdgeIt(Invalid invalid) |
|
57 : EdgeIt(invalid) {} |
|
58 |
|
59 /** SymEdgeIt from the given Edge. |
|
60 */ |
|
61 SymEdgeIt(const Graph& graph, const Edge& edge) |
|
62 : EdgeIt(graph, edge) { |
|
63 while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { |
|
64 EdgeIt::operator++(); |
|
65 } |
|
66 } |
|
67 |
|
68 /** Increase operator. |
|
69 */ |
|
70 SymEdgeIt& operator++() { |
|
71 EdgeIt::operator++(); |
|
72 while ( (EdgeIt::n & 1) && EdgeIt::n != -1) { |
|
73 EdgeIt::operator++(); |
|
74 } |
|
75 return *this; |
|
76 } |
|
77 }; |
|
78 |
|
79 /** The SymMap template class is graph map structure what |
|
80 * wraps an other map structure to use as symmetric map structure. |
|
81 * |
|
82 * The template parameter is the MapRegistry that the maps |
|
83 * will belong to and the ValueType. |
|
84 */ |
|
85 template <template <typename, typename> class DynMap, |
|
86 typename MapRegistry, typename Value> |
|
87 class SymMap : public DynMap<MapRegistry, Value>{ |
|
88 |
|
89 private: |
|
90 |
|
91 typedef DynMap<MapRegistry, Value> MapImpl; |
|
92 |
|
93 public: |
|
94 |
|
95 /// The graph type of the maps. |
|
96 typedef typename MapRegistry::Graph Graph; |
|
97 |
|
98 typedef typename MapImpl::KeyType KeyType; |
|
99 |
|
100 public: |
|
101 |
|
102 |
|
103 /** Graph and Registry initialized map constructor. |
|
104 */ |
|
105 SymMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {} |
|
106 |
|
107 /** Constructor to use default value to initialize the map. |
|
108 */ |
|
109 SymMap(const Graph& g, MapRegistry& r, const Value& v) |
|
110 : MapImpl(g, r, v) {} |
|
111 |
|
112 /** Constructor to copy a map of the same map type. |
|
113 */ |
|
114 SymMap(const SymMap& copy) |
|
115 : MapImpl(static_cast<const MapImpl&>(copy)) {} |
|
116 |
|
117 /** Assign operator to copy a map of the same map type. |
|
118 */ |
|
119 SymMap& operator=(const SymMap& copy) { |
|
120 MapImpl::operator=(static_cast<const MapImpl&>(copy)); |
|
121 return *this; |
|
122 } |
|
123 |
|
124 /** Add a new key to the map. It called by the map registry. |
|
125 */ |
|
126 void add(const KeyType& key) { |
|
127 int id = MapImpl::getGraph()->id(key); |
|
128 if (id & 1) return; |
|
129 MapImpl::add(key); |
|
130 } |
|
131 |
|
132 /** Erase a key from the map. It called by the map registry. |
|
133 */ |
|
134 void erase(const KeyType& key) { |
|
135 int id = MapImpl::getGraph()->id(key); |
|
136 if (id & 1) return; |
|
137 MapImpl::add(key); |
|
138 } |
|
139 }; |
|
140 |
|
141 /// @} |
|
142 } |
|
143 |
|
144 #endif |
|