Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

map_utils.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
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 

Generated on Mon Feb 21 15:02:21 2005 for LEMON by  doxygen 1.4.1