lemon/bits/map_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 26 Apr 2009 16:44:53 +0200
changeset 625 029a48052c67
parent 580 2313edd0db0b
child 718 703ebf476a1d
permissions -rw-r--r--
Modify the interface of MinCostArborescence + improvements (#267)

- Rename arborescenceValue() to arborescenceCost().
- Rename DefXyz template named paramaters to SetXyz.
- Rearrange public functions (for better doc).
- Doc improvements.
- Extend the test file with interface checking.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_MAP_EXTENDER_H
    20 #define LEMON_BITS_MAP_EXTENDER_H
    21 
    22 #include <iterator>
    23 
    24 #include <lemon/bits/traits.h>
    25 
    26 #include <lemon/concept_check.h>
    27 #include <lemon/concepts/maps.h>
    28 
    29 //\file
    30 //\brief Extenders for iterable maps.
    31 
    32 namespace lemon {
    33 
    34   // \ingroup graphbits
    35   //
    36   // \brief Extender for maps
    37   template <typename _Map>
    38   class MapExtender : public _Map {
    39     typedef _Map Parent;
    40     typedef typename Parent::GraphType GraphType;
    41 
    42   public:
    43 
    44     typedef MapExtender Map;
    45     typedef typename Parent::Key Item;
    46 
    47     typedef typename Parent::Key Key;
    48     typedef typename Parent::Value Value;
    49     typedef typename Parent::Reference Reference;
    50     typedef typename Parent::ConstReference ConstReference;
    51 
    52     class MapIt;
    53     class ConstMapIt;
    54 
    55     friend class MapIt;
    56     friend class ConstMapIt;
    57 
    58   public:
    59 
    60     MapExtender(const GraphType& graph)
    61       : Parent(graph) {}
    62 
    63     MapExtender(const GraphType& graph, const Value& value)
    64       : Parent(graph, value) {}
    65 
    66   private:
    67     MapExtender& operator=(const MapExtender& cmap) {
    68       return operator=<MapExtender>(cmap);
    69     }
    70 
    71     template <typename CMap>
    72     MapExtender& operator=(const CMap& cmap) {
    73       Parent::operator=(cmap);
    74       return *this;
    75     }
    76 
    77   public:
    78     class MapIt : public Item {
    79       typedef Item Parent;
    80 
    81     public:
    82 
    83       typedef typename Map::Value Value;
    84 
    85       MapIt() {}
    86 
    87       MapIt(Invalid i) : Parent(i) { }
    88 
    89       explicit MapIt(Map& _map) : map(_map) {
    90         map.notifier()->first(*this);
    91       }
    92 
    93       MapIt(const Map& _map, const Item& item)
    94         : Parent(item), map(_map) {}
    95 
    96       MapIt& operator++() {
    97         map.notifier()->next(*this);
    98         return *this;
    99       }
   100 
   101       typename MapTraits<Map>::ConstReturnValue operator*() const {
   102         return map[*this];
   103       }
   104 
   105       typename MapTraits<Map>::ReturnValue operator*() {
   106         return map[*this];
   107       }
   108 
   109       void set(const Value& value) {
   110         map.set(*this, value);
   111       }
   112 
   113     protected:
   114       Map& map;
   115 
   116     };
   117 
   118     class ConstMapIt : public Item {
   119       typedef Item Parent;
   120 
   121     public:
   122 
   123       typedef typename Map::Value Value;
   124 
   125       ConstMapIt() {}
   126 
   127       ConstMapIt(Invalid i) : Parent(i) { }
   128 
   129       explicit ConstMapIt(Map& _map) : map(_map) {
   130         map.notifier()->first(*this);
   131       }
   132 
   133       ConstMapIt(const Map& _map, const Item& item)
   134         : Parent(item), map(_map) {}
   135 
   136       ConstMapIt& operator++() {
   137         map.notifier()->next(*this);
   138         return *this;
   139       }
   140 
   141       typename MapTraits<Map>::ConstReturnValue operator*() const {
   142         return map[*this];
   143       }
   144 
   145     protected:
   146       const Map& map;
   147     };
   148 
   149     class ItemIt : public Item {
   150       typedef Item Parent;
   151 
   152     public:
   153 
   154       ItemIt() {}
   155 
   156       ItemIt(Invalid i) : Parent(i) { }
   157 
   158       explicit ItemIt(Map& _map) : map(_map) {
   159         map.notifier()->first(*this);
   160       }
   161 
   162       ItemIt(const Map& _map, const Item& item)
   163         : Parent(item), map(_map) {}
   164 
   165       ItemIt& operator++() {
   166         map.notifier()->next(*this);
   167         return *this;
   168       }
   169 
   170     protected:
   171       const Map& map;
   172 
   173     };
   174   };
   175 
   176   // \ingroup graphbits
   177   //
   178   // \brief Extender for maps which use a subset of the items.
   179   template <typename _Graph, typename _Map>
   180   class SubMapExtender : public _Map {
   181     typedef _Map Parent;
   182     typedef _Graph GraphType;
   183 
   184   public:
   185 
   186     typedef SubMapExtender Map;
   187     typedef typename Parent::Key Item;
   188 
   189     typedef typename Parent::Key Key;
   190     typedef typename Parent::Value Value;
   191     typedef typename Parent::Reference Reference;
   192     typedef typename Parent::ConstReference ConstReference;
   193 
   194     class MapIt;
   195     class ConstMapIt;
   196 
   197     friend class MapIt;
   198     friend class ConstMapIt;
   199 
   200   public:
   201 
   202     SubMapExtender(const GraphType& _graph)
   203       : Parent(_graph), graph(_graph) {}
   204 
   205     SubMapExtender(const GraphType& _graph, const Value& _value)
   206       : Parent(_graph, _value), graph(_graph) {}
   207 
   208   private:
   209     SubMapExtender& operator=(const SubMapExtender& cmap) {
   210       return operator=<MapExtender>(cmap);
   211     }
   212 
   213     template <typename CMap>
   214     SubMapExtender& operator=(const CMap& cmap) {
   215       checkConcept<concepts::ReadMap<Key, Value>, CMap>();
   216       Item it;
   217       for (graph.first(it); it != INVALID; graph.next(it)) {
   218         Parent::set(it, cmap[it]);
   219       }
   220       return *this;
   221     }
   222 
   223   public:
   224     class MapIt : public Item {
   225       typedef Item Parent;
   226 
   227     public:
   228       typedef typename Map::Value Value;
   229 
   230       MapIt() {}
   231 
   232       MapIt(Invalid i) : Parent(i) { }
   233 
   234       explicit MapIt(Map& _map) : map(_map) {
   235         map.graph.first(*this);
   236       }
   237 
   238       MapIt(const Map& _map, const Item& item)
   239         : Parent(item), map(_map) {}
   240 
   241       MapIt& operator++() {
   242         map.graph.next(*this);
   243         return *this;
   244       }
   245 
   246       typename MapTraits<Map>::ConstReturnValue operator*() const {
   247         return map[*this];
   248       }
   249 
   250       typename MapTraits<Map>::ReturnValue operator*() {
   251         return map[*this];
   252       }
   253 
   254       void set(const Value& value) {
   255         map.set(*this, value);
   256       }
   257 
   258     protected:
   259       Map& map;
   260 
   261     };
   262 
   263     class ConstMapIt : public Item {
   264       typedef Item Parent;
   265 
   266     public:
   267 
   268       typedef typename Map::Value Value;
   269 
   270       ConstMapIt() {}
   271 
   272       ConstMapIt(Invalid i) : Parent(i) { }
   273 
   274       explicit ConstMapIt(Map& _map) : map(_map) {
   275         map.graph.first(*this);
   276       }
   277 
   278       ConstMapIt(const Map& _map, const Item& item)
   279         : Parent(item), map(_map) {}
   280 
   281       ConstMapIt& operator++() {
   282         map.graph.next(*this);
   283         return *this;
   284       }
   285 
   286       typename MapTraits<Map>::ConstReturnValue operator*() const {
   287         return map[*this];
   288       }
   289 
   290     protected:
   291       const Map& map;
   292     };
   293 
   294     class ItemIt : public Item {
   295       typedef Item Parent;
   296 
   297     public:
   298 
   299       ItemIt() {}
   300 
   301       ItemIt(Invalid i) : Parent(i) { }
   302 
   303       explicit ItemIt(Map& _map) : map(_map) {
   304         map.graph.first(*this);
   305       }
   306 
   307       ItemIt(const Map& _map, const Item& item)
   308         : Parent(item), map(_map) {}
   309 
   310       ItemIt& operator++() {
   311         map.graph.next(*this);
   312         return *this;
   313       }
   314 
   315     protected:
   316       const Map& map;
   317 
   318     };
   319 
   320   private:
   321 
   322     const GraphType& graph;
   323 
   324   };
   325 
   326 }
   327 
   328 #endif