lemon/bits/static_map.h
author alpar
Wed, 16 Nov 2005 13:19:05 +0000
changeset 1805 d284f81f02a5
parent 1703 eb90e3d6bddc
child 1810 474d093466a5
permissions -rw-r--r--
Iterable Bool maps can count the number of true and false values.
     1 /* -*- C++ -*-
     2  * lemon/static_map.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, 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_STATIC_MAP_H
    18 #define LEMON_STATIC_MAP_H
    19 
    20 #include <algorithm>
    21 #include <iostream>
    22 
    23 #include <lemon/utility.h>
    24 #include <lemon/bits/map_iterator.h>
    25 #include <lemon/bits/alteration_notifier.h>
    26 #include <lemon/error.h>
    27 #include <lemon/concept_check.h>
    28 #include <lemon/concept/maps.h>
    29 
    30 /// \ingroup graphmaps
    31 ///
    32 ///\file
    33 ///\brief Static sized graph maps.
    34 
    35 namespace lemon {
    36 
    37   /// \ingroup graphmaps
    38   ///
    39   /// \brief Graph map with static sized storage.
    40   ///
    41   /// The StaticMap template class is graph map structure what
    42   /// does not update automatically the map when a key is added to or 
    43   /// erased from the map rather it throws an exception. This map factory 
    44   /// uses the allocators to implement the container functionality.
    45   ///
    46   /// \param Registry The AlterationNotifier that will notify this map.
    47   /// \param Item The item type of the graph items.
    48   /// \param Value The value type of the map.
    49   /// 
    50   /// \author Balazs Dezso
    51   	
    52 
    53   template <typename _Graph, typename _Item, typename _Value>
    54   class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
    55   public:
    56 
    57     /// \brief Exception class for unsupported exceptions.
    58     class UnsupportedOperation : public lemon::LogicError {
    59     public:
    60       virtual const char* exceptionName() const {
    61 	return "lemon::StaticMap::UnsupportedOperation";
    62       }
    63     };
    64 
    65   private:
    66 		
    67     typedef std::vector<_Value> Container;	
    68 
    69   public:
    70 
    71     /// The graph type of the map. 
    72     typedef _Graph Graph;
    73     /// The reference map tag.
    74     typedef True ReferenceMapTag;
    75 
    76     /// The key type of the map.
    77     typedef _Item Key;
    78     /// The value type of the map.
    79     typedef _Value Value;
    80     /// The const reference type of the map.
    81     typedef typename Container::const_reference ConstReference;
    82     /// The reference type of the map.
    83     typedef typename Container::reference Reference;
    84 
    85     typedef const Value ConstValue;
    86     typedef Value* Pointer;
    87     typedef const Value* ConstPointer;
    88 
    89     typedef AlterationNotifier<_Item> Registry;
    90 
    91     /// The map type.
    92     typedef StaticMap Map;
    93     /// The base class of the map.
    94     typedef typename Registry::ObserverBase Parent;
    95 
    96     /// \brief Constructor to attach the new map into the registry.
    97     ///
    98     /// It constructs a map and attachs it into the registry.
    99     /// It adds all the items of the graph to the map.
   100     StaticMap(const Graph& _g) : graph(&_g) {
   101       attach(_g.getNotifier(_Item()));
   102       build();
   103     }
   104 
   105     /// \brief Constructor uses given value to initialize the map. 
   106     ///
   107     /// It constructs a map uses a given value to initialize the map. 
   108     /// It adds all the items of the graph to the map.     
   109     StaticMap(const Graph& _g, const Value& _v) : graph(&_g) { 
   110       attach(_g.getNotifier(_Item()));
   111       unsigned size = graph->maxId(_Item()) + 1;
   112       container.reserve(size);
   113       container.resize(size, _v);
   114     }
   115 
   116     /// \brief Copy constructor
   117     ///
   118     /// Copy constructor.
   119     StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
   120       if (_copy.attached()) {
   121 	attach(*_copy.getRegistry());
   122 	container = _copy.container;
   123       }
   124     }
   125 
   126     /// \brief Destrcutor
   127     ///
   128     /// Destructor.
   129     virtual ~StaticMap() {
   130       clear();
   131       if (attached()) {
   132 	detach();
   133       }
   134     }
   135 
   136 
   137   private:
   138 
   139     StaticMap& operator=(const StaticMap&);
   140 
   141   protected:
   142 
   143     using Parent::attach;
   144     using Parent::detach;
   145     using Parent::attached;
   146 
   147     const Graph* getGraph() const {
   148       return graph;
   149     }
   150 
   151   public:
   152 
   153     /// \brief The subcript operator.
   154     ///
   155     /// The subscript operator. The map can be subscripted by the
   156     /// actual items of the graph. 
   157      
   158     Reference operator[](const Key& key) {
   159       return container[graph->id(key)];
   160     } 
   161 		
   162     /// \brief The const subcript operator.
   163     ///
   164     /// The const subscript operator. The map can be subscripted by the
   165     /// actual items of the graph. 
   166      
   167     ConstReference operator[](const Key& key) const {
   168       return container[graph->id(key)];
   169     }
   170 
   171 
   172     /// \brief The setter function of the map.
   173     ///
   174     /// It the same as operator[](key) = value expression.
   175     ///
   176     void set(const Key& key, const Value& value) {
   177       (*this)[key] = value;
   178     }
   179 
   180   protected:
   181 
   182     /// \brief Adds a new key to the map.
   183     ///		
   184     /// It adds a new key to the map. It called by the observer registry
   185     /// and it overrides the add() member function of the observer base.
   186      
   187     void add(const Key&) {
   188       throw UnsupportedOperation();
   189     }
   190 
   191     /// \brief Erases a key from the map.
   192     ///
   193     /// Erase a key from the map. It called by the observer registry
   194     /// and it overrides the erase() member function of the observer base.     
   195     void erase(const Key&) {
   196       throw UnsupportedOperation();
   197     }
   198 
   199     /// Buildes the map.
   200 		
   201     /// It buildes the map. It called by the observer registry
   202     /// and it overrides the build() member function of the observer base.
   203 
   204     void build() { 
   205       int size = graph->maxId(_Item()) + 1;
   206       container.reserve(size);
   207       container.resize(size);
   208     }
   209 
   210     /// Clear the map.
   211 
   212     /// It erase all items from the map. It called by the observer registry
   213     /// and it overrides the clear() member function of the observer base.     
   214     void clear() { 
   215       container.clear();
   216     }
   217     
   218   private:
   219 		
   220     Container container;
   221     const Graph *graph;
   222 
   223   };
   224 
   225   /// \e
   226   template <typename _Base> 
   227   class StaticMappableGraphExtender : public _Base {
   228   public:
   229 
   230     typedef StaticMappableGraphExtender<_Base> Graph;
   231     typedef _Base Parent;
   232 
   233     typedef typename Parent::Node Node;
   234     typedef typename Parent::NodeIt NodeIt;
   235 
   236     typedef typename Parent::Edge Edge;
   237     typedef typename Parent::EdgeIt EdgeIt;
   238 
   239     
   240     template <typename _Value>
   241     class NodeMap 
   242       : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
   243     public:
   244       typedef StaticMappableGraphExtender Graph;
   245       typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
   246 
   247       NodeMap(const Graph& _g) 
   248 	: Parent(_g) {}
   249       NodeMap(const Graph& _g, const _Value& _v) 
   250 	: Parent(_g, _v) {}
   251 
   252       NodeMap& operator=(const NodeMap& cmap) {
   253 	return operator=<NodeMap>(cmap);
   254       }
   255 
   256 
   257       /// \brief Template assign operator.
   258       ///
   259       /// The given parameter should be conform to the ReadMap
   260       /// concecpt and could be indiced by the current item set of
   261       /// the NodeMap. In this case the value for each item
   262       /// is assigned by the value of the given ReadMap. 
   263       template <typename CMap>
   264       NodeMap& operator=(const CMap& cmap) {
   265 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
   266 	const typename Parent::Graph* graph = Parent::getGraph();
   267 	Node it;
   268 	for (graph->first(it); it != INVALID; graph->next(it)) {
   269 	  Parent::set(it, cmap[it]);
   270 	}
   271 	return *this;
   272       }
   273 
   274     };
   275 
   276     template <typename _Value>
   277     class EdgeMap 
   278       : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
   279     public:
   280       typedef StaticMappableGraphExtender Graph;
   281       typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
   282 
   283       EdgeMap(const Graph& _g) 
   284 	: Parent(_g) {}
   285       EdgeMap(const Graph& _g, const _Value& _v) 
   286 	: Parent(_g, _v) {}
   287 
   288       EdgeMap& operator=(const EdgeMap& cmap) {
   289 	return operator=<EdgeMap>(cmap);
   290       }
   291 
   292       template <typename CMap>
   293       EdgeMap& operator=(const CMap& cmap) {
   294 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
   295 	const typename Parent::Graph* graph = Parent::getGraph();
   296 	Edge it;
   297 	for (graph->first(it); it != INVALID; graph->next(it)) {
   298 	  Parent::set(it, cmap[it]);
   299 	}
   300 	return *this;
   301       }
   302     };
   303     
   304   };
   305 
   306   /// \e
   307   template <typename _Base> 
   308   class StaticMappableUndirGraphExtender : 
   309     public StaticMappableGraphExtender<_Base> {
   310   public:
   311 
   312     typedef StaticMappableUndirGraphExtender Graph;
   313     typedef StaticMappableGraphExtender<_Base> Parent;
   314 
   315     typedef typename Parent::UndirEdge UndirEdge;
   316 
   317     template <typename _Value>
   318     class UndirEdgeMap 
   319       : public IterableMapExtender<StaticMap<Graph, UndirEdge, _Value> > {
   320     public:
   321       typedef StaticMappableUndirGraphExtender Graph;
   322       typedef IterableMapExtender<
   323 	StaticMap<Graph, UndirEdge, _Value> > Parent;
   324 
   325       UndirEdgeMap(const Graph& _g) 
   326 	: Parent(_g) {}
   327       UndirEdgeMap(const Graph& _g, const _Value& _v) 
   328 	: Parent(_g, _v) {}
   329 
   330       UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
   331 	return operator=<UndirEdgeMap>(cmap);
   332       }
   333 
   334       template <typename CMap>
   335       UndirEdgeMap& operator=(const CMap& cmap) {
   336 	checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
   337 	const typename Parent::Graph* graph = Parent::getGraph();
   338 	UndirEdge it;
   339 	for (graph->first(it); it != INVALID; graph->next(it)) {
   340 	  Parent::set(it, cmap[it]);
   341 	}
   342 	return *this;
   343       }
   344     };
   345 
   346 
   347   };
   348 
   349 }
   350 
   351 #endif