00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00020
00021 #include <map>
00022
00023
00024 namespace lemon {
00025
00028
00030
00037 template <
00038 typename _Graph,
00039 typename _Map
00040 >
00041 class InversableMap : protected _Map {
00042
00043 public:
00044 typedef _Graph Graph;
00045
00046 typedef _Map Map;
00048 typedef typename _Map::Key Key;
00050 typedef typename _Map::Value Value;
00051 typedef std::map<Value, Key> InverseMap;
00052
00053 typedef typename _Map::ConstReference ConstReference;
00054
00059 InversableMap(const Graph& graph) : Map(graph) {}
00060
00064 void set(const Key& key, const Value& val) {
00065 Value oldval = Map::operator[](key);
00066 typename InverseMap::iterator it = invMap.find(oldval);
00067 if (it != invMap.end() && it->second == key) {
00068 invMap.erase(it);
00069 }
00070 invMap.insert(make_pair(val, key));
00071 Map::set(key, val);
00072 }
00073
00077 ConstReference operator[](const Key& key) const {
00078 return Map::operator[](key);
00079 }
00080
00085 virtual void add(const Key& key) {
00086 Map::add(key);
00087 }
00088
00093 virtual void erase(const Key& key) {
00094 Value val = Map::operator[](key);
00095 typename InverseMap::iterator it = invMap.find(val);
00096 if (it != invMap.end() && it->second == key) {
00097 invMap.erase(it);
00098 }
00099 Map::erase(key);
00100 }
00101
00106 virtual void clear() {
00107 invMap.clear();
00108 Map::clear();
00109 }
00110
00114 const InverseMap& inverse() const {
00115 return invMap;
00116 }
00117
00118
00119 private:
00120 InverseMap invMap;
00121 };
00122
00123
00124
00135
00136 template <
00137 typename _Graph,
00138 typename _Item,
00139 typename _Map
00140 >
00141 class DescriptorMap : protected _Map {
00142
00143 typedef _Item Item;
00144 typedef _Map Map;
00145
00146 public:
00148 typedef _Graph Graph;
00149
00151 typedef typename _Map::Key Key;
00153 typedef typename _Map::Value Value;
00154
00155 typedef std::vector<Item> InverseMap;
00156
00160 DescriptorMap(const Graph& _graph) : Map(_graph) {
00161 build();
00162 }
00163
00168 virtual void add(const Item& item) {
00169 Map::add(item);
00170 Map::set(item, invMap.size());
00171 invMap.push_back(item);
00172 }
00173
00178 virtual void erase(const Item& item) {
00179 Map::set(invMap.back(), Map::operator[](item));
00180 invMap[Map::operator[](item)] = invMap.back();
00181 Map::erase(item);
00182 }
00183
00188 virtual void build() {
00189 Map::build();
00190 Item it;
00191 for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
00192 Map::set(it, invMap.size());
00193 invMap.push_back(it);
00194 }
00195 }
00196
00201 virtual void clear() {
00202 invMap.clear();
00203 Map::clear();
00204 }
00205
00209 int operator[](const Item& item) const {
00210 return Map::operator[](item);
00211 }
00212
00216 const InverseMap inverse() const {
00217 return invMap;
00218 }
00219
00220 private:
00221 vector<Item> invMap;
00222 };
00223
00225
00229 template <typename _Graph, typename _Item>
00230 class IdMap {
00231 public:
00232 typedef _Graph Graph;
00233 typedef int Value;
00234 typedef _Item Item;
00235
00240 class InverseMap {
00241 protected:
00242 InverseMap(const Graph& _graph) : graph(_graph) {}
00243 public:
00248 Item operator[](int id) const { return graph->fromId(id, Item());}
00249 private:
00250 Graph* graph;
00251 };
00252
00256 IdMap(const Graph& _graph) : graph(&_graph) {}
00257
00261 int operator[](const Item& item) const { return graph->id(item);}
00262
00266 InverseMap inverse() const { return InverseMap(*graph);}
00267
00268 private:
00269 const Graph* graph;
00270
00271 };
00272
00273
00274
00275 }
00276