[906] | 1 | /* -*- C++ -*- |
---|
[921] | 2 | * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library |
---|
[906] | 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 | |
---|
[921] | 17 | #ifndef LEMON_MAPS_H |
---|
| 18 | #define LEMON_MAPS_H |
---|
[286] | 19 | |
---|
| 20 | ///\file |
---|
| 21 | ///\brief Miscellaneous property maps |
---|
| 22 | /// |
---|
[959] | 23 | ///\todo This file has the same name as the concept file in concept/, |
---|
[286] | 24 | /// and this is not easily detectable in docs... |
---|
| 25 | |
---|
| 26 | #include <map> |
---|
| 27 | |
---|
[921] | 28 | namespace lemon { |
---|
[286] | 29 | |
---|
[720] | 30 | /// Base class of maps. |
---|
| 31 | |
---|
[805] | 32 | /// Base class of maps. |
---|
| 33 | /// It provides the necessary <tt>typedef</tt>s required by the map concept. |
---|
[720] | 34 | template<typename K, typename T> |
---|
| 35 | class MapBase |
---|
| 36 | { |
---|
| 37 | public: |
---|
[911] | 38 | ///\e |
---|
[987] | 39 | typedef K Key; |
---|
[911] | 40 | ///\e |
---|
[987] | 41 | typedef T Value; |
---|
[720] | 42 | }; |
---|
| 43 | |
---|
[805] | 44 | /// Null map. (a.k.a. DoNothingMap) |
---|
[286] | 45 | |
---|
| 46 | /// If you have to provide a map only for its type definitions, |
---|
[805] | 47 | /// or if you have to provide a writable map, but |
---|
| 48 | /// data written to it will sent to <tt>/dev/null</tt>... |
---|
[286] | 49 | template<typename K, typename T> |
---|
[720] | 50 | class NullMap : public MapBase<K,T> |
---|
[286] | 51 | { |
---|
| 52 | public: |
---|
| 53 | |
---|
[805] | 54 | /// Gives back a default constructed element. |
---|
[286] | 55 | T operator[](const K&) const { return T(); } |
---|
[805] | 56 | /// Absorbs the value. |
---|
[286] | 57 | void set(const K&, const T&) {} |
---|
| 58 | }; |
---|
| 59 | |
---|
| 60 | |
---|
| 61 | /// Constant map. |
---|
| 62 | |
---|
[805] | 63 | /// This is a readable map which assigns a specified value to each key. |
---|
| 64 | /// In other aspects it is equivalent to the \ref NullMap. |
---|
| 65 | /// \todo set could be used to set the value. |
---|
[286] | 66 | template<typename K, typename T> |
---|
[720] | 67 | class ConstMap : public MapBase<K,T> |
---|
[286] | 68 | { |
---|
| 69 | T v; |
---|
| 70 | public: |
---|
| 71 | |
---|
[805] | 72 | /// Default constructor |
---|
| 73 | |
---|
| 74 | /// The value of the map will be uninitialized. |
---|
| 75 | /// (More exactly it will be default constructed.) |
---|
[286] | 76 | ConstMap() {} |
---|
[911] | 77 | ///\e |
---|
[805] | 78 | |
---|
| 79 | /// \param _v The initial value of the map. |
---|
[911] | 80 | /// |
---|
[286] | 81 | ConstMap(const T &_v) : v(_v) {} |
---|
| 82 | |
---|
| 83 | T operator[](const K&) const { return v; } |
---|
| 84 | void set(const K&, const T&) {} |
---|
| 85 | |
---|
| 86 | template<typename T1> |
---|
| 87 | struct rebind { |
---|
| 88 | typedef ConstMap<K,T1> other; |
---|
| 89 | }; |
---|
| 90 | |
---|
| 91 | template<typename T1> |
---|
| 92 | ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {} |
---|
| 93 | }; |
---|
| 94 | |
---|
[890] | 95 | //to document later |
---|
| 96 | template<typename T, T v> |
---|
| 97 | struct Const { }; |
---|
| 98 | //to document later |
---|
| 99 | template<typename K, typename V, V v> |
---|
| 100 | class ConstMap<K, Const<V, v> > : public MapBase<K, V> |
---|
| 101 | { |
---|
| 102 | public: |
---|
| 103 | ConstMap() { } |
---|
| 104 | V operator[](const K&) const { return v; } |
---|
| 105 | void set(const K&, const V&) { } |
---|
| 106 | }; |
---|
[286] | 107 | |
---|
| 108 | /// \c std::map wrapper |
---|
| 109 | |
---|
| 110 | /// This is essentially a wrapper for \c std::map. With addition that |
---|
[987] | 111 | /// you can specify a default value different from \c Value() . |
---|
[286] | 112 | /// |
---|
| 113 | /// \todo Provide allocator parameter... |
---|
[987] | 114 | template <typename K, typename T, typename Compare = std::less<K> > |
---|
| 115 | class StdMap : public std::map<K,T,Compare> { |
---|
| 116 | typedef std::map<K,T,Compare> parent; |
---|
[286] | 117 | T v; |
---|
| 118 | typedef typename parent::value_type PairType; |
---|
| 119 | |
---|
| 120 | public: |
---|
[987] | 121 | typedef K Key; |
---|
| 122 | typedef T Value; |
---|
| 123 | typedef T& Reference; |
---|
| 124 | typedef const T& ConstReference; |
---|
[286] | 125 | |
---|
| 126 | |
---|
[345] | 127 | StdMap() : v() {} |
---|
[286] | 128 | /// Constructor with specified default value |
---|
| 129 | StdMap(const T& _v) : v(_v) {} |
---|
| 130 | |
---|
| 131 | /// \brief Constructs the map from an appropriate std::map. |
---|
| 132 | /// |
---|
| 133 | /// \warning Inefficient: copies the content of \c m ! |
---|
| 134 | StdMap(const parent &m) : parent(m) {} |
---|
| 135 | /// \brief Constructs the map from an appropriate std::map, and explicitly |
---|
| 136 | /// specifies a default value. |
---|
| 137 | /// |
---|
| 138 | /// \warning Inefficient: copies the content of \c m ! |
---|
| 139 | StdMap(const parent &m, const T& _v) : parent(m), v(_v) {} |
---|
| 140 | |
---|
| 141 | template<typename T1, typename Comp1> |
---|
[389] | 142 | StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) { |
---|
| 143 | //FIXME; |
---|
| 144 | } |
---|
[286] | 145 | |
---|
[987] | 146 | Reference operator[](const Key &k) { |
---|
[346] | 147 | return insert(PairType(k,v)).first -> second; |
---|
[286] | 148 | } |
---|
[987] | 149 | ConstReference operator[](const Key &k) const { |
---|
[389] | 150 | typename parent::iterator i = lower_bound(k); |
---|
[391] | 151 | if (i == parent::end() || parent::key_comp()(k, (*i).first)) |
---|
[286] | 152 | return v; |
---|
| 153 | return (*i).second; |
---|
| 154 | } |
---|
[345] | 155 | void set(const Key &k, const T &t) { |
---|
[346] | 156 | parent::operator[](k) = t; |
---|
[345] | 157 | } |
---|
[286] | 158 | |
---|
| 159 | /// Changes the default value of the map. |
---|
| 160 | /// \return Returns the previous default value. |
---|
| 161 | /// |
---|
[805] | 162 | /// \warning The value of some keys (which has already been queried, but |
---|
[286] | 163 | /// the value has been unchanged from the default) may change! |
---|
| 164 | T setDefault(const T &_v) { T old=v; v=_v; return old; } |
---|
| 165 | |
---|
| 166 | template<typename T1> |
---|
| 167 | struct rebind { |
---|
| 168 | typedef StdMap<Key,T1,Compare> other; |
---|
| 169 | }; |
---|
| 170 | }; |
---|
| 171 | |
---|
| 172 | } |
---|
[921] | 173 | #endif // LEMON_MAPS_H |
---|