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