gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 4 0
merge default
0 files changed with 1605 insertions and 1386 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
1 1
/* -*- C++ -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
/**
20 20
@defgroup datas Data Structures
21 21
This group describes the several data structures implemented in LEMON.
22 22
*/
23 23

	
24 24
/**
25 25
@defgroup graphs Graph Structures
26 26
@ingroup datas
27 27
\brief Graph structures implemented in LEMON.
28 28

	
29 29
The implementation of combinatorial algorithms heavily relies on 
30 30
efficient graph implementations. LEMON offers data structures which are 
31 31
planned to be easily used in an experimental phase of implementation studies, 
32 32
and thereafter the program code can be made efficient by small modifications. 
33 33

	
34 34
The most efficient implementation of diverse applications require the
35 35
usage of different physical graph implementations. These differences
36 36
appear in the size of graph we require to handle, memory or time usage
37 37
limitations or in the set of operations through which the graph can be
38 38
accessed.  LEMON provides several physical graph structures to meet
39 39
the diverging requirements of the possible users.  In order to save on
40 40
running time or on memory usage, some structures may fail to provide
41
some graph features like edge or node deletion.
41
some graph features like arc/edge or node deletion.
42 42

	
43 43
Alteration of standard containers need a very limited number of 
44 44
operations, these together satisfy the everyday requirements. 
45 45
In the case of graph structures, different operations are needed which do 
46 46
not alter the physical graph, but gives another view. If some nodes or 
47
edges have to be hidden or the reverse oriented graph have to be used, then 
47
arcs have to be hidden or the reverse oriented graph have to be used, then
48 48
this is the case. It also may happen that in a flow implementation 
49 49
the residual graph can be accessed by another algorithm, or a node-set 
50 50
is to be shrunk for another algorithm. 
51 51
LEMON also provides a variety of graphs for these requirements called 
52 52
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
53 53
in conjunction with other graph representations. 
54 54

	
55 55
You are free to use the graph structure that fit your requirements
56 56
the best, most graph algorithms and auxiliary data structures can be used
57 57
with any graph structures. 
58 58
*/
59 59

	
60 60
/**
61 61
@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
62 62
@ingroup graphs
63 63
\brief Graph types between real graphs and graph adaptors.
64 64

	
65 65
This group describes some graph types between real graphs and graph adaptors.
66 66
These classes wrap graphs to give new functionality as the adaptors do it. 
67 67
On the other hand they are not light-weight structures as the adaptors.
68 68
*/
69 69

	
70 70
/**
71 71
@defgroup maps Maps 
72 72
@ingroup datas
73 73
\brief Map structures implemented in LEMON.
74 74

	
75 75
This group describes the map structures implemented in LEMON.
76 76

	
77 77
LEMON provides several special purpose maps that e.g. combine
78 78
new maps from existing ones.
79 79
*/
80 80

	
81 81
/**
82 82
@defgroup graph_maps Graph Maps 
83 83
@ingroup maps
84
\brief Special Graph-Related Maps.
84
\brief Special graph-related maps.
85 85

	
86 86
This group describes maps that are specifically designed to assign
87
values to the nodes and edges of graphs.
87
values to the nodes and arcs of graphs.
88 88
*/
89 89

	
90 90

	
91 91
/**
92 92
\defgroup map_adaptors Map Adaptors
93 93
\ingroup maps
94 94
\brief Tools to create new maps from existing ones
95 95

	
96 96
This group describes map adaptors that are used to create "implicit"
97 97
maps from other maps.
98 98

	
99
Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
100
make arithmetic operations between one or two maps (negation, scaling,
101
addition, multiplication etc.) or e.g. convert a map to another one
102
of different Value type.
99
Most of them are \ref lemon::concepts::ReadMap "read-only maps".
100
They can make arithmetic and logical operations between one or two maps
101
(negation, shifting, addition, multiplication, logical 'and', 'or',
102
'not' etc.) or e.g. convert a map to another one of different Value type.
103 103

	
104 104
The typical usage of this classes is passing implicit maps to
105 105
algorithms.  If a function type algorithm is called then the function
106 106
type map adaptors can be used comfortable. For example let's see the
107
usage of map adaptors with the \c graphToEps() function:
107
usage of map adaptors with the \c digraphToEps() function.
108 108
\code
109 109
  Color nodeColor(int deg) {
110 110
    if (deg >= 2) {
111 111
      return Color(0.5, 0.0, 0.5);
112 112
    } else if (deg == 1) {
113 113
      return Color(1.0, 0.5, 1.0);
114 114
    } else {
115 115
      return Color(0.0, 0.0, 0.0);
116 116
    }
117 117
  }
118 118
  
119
  Graph::NodeMap<int> degree_map(graph);
119
  Digraph::NodeMap<int> degree_map(graph);
120 120
  
121
  graphToEps(graph, "graph.eps")
121
  digraphToEps(graph, "graph.eps")
122 122
    .coords(coords).scaleToA4().undirected()
123
    .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 
123
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
124 124
    .run();
125 125
\endcode 
126
The \c functorMap() function makes an \c int to \c Color map from the
126
The \c functorToMap() function makes an \c int to \c Color map from the
127 127
\e nodeColor() function. The \c composeMap() compose the \e degree_map
128
and the previous created map. The composed map is proper function to
129
get color of each node.
128
and the previously created map. The composed map is a proper function to
129
get the color of each node.
130 130

	
131 131
The usage with class type algorithms is little bit harder. In this
132 132
case the function type map adaptors can not be used, because the
133 133
function map adaptors give back temporary objects.
134 134
\code
135
  Graph graph;
136
  
137
  typedef Graph::EdgeMap<double> DoubleEdgeMap;
138
  DoubleEdgeMap length(graph);
139
  DoubleEdgeMap speed(graph);
140
  
141
  typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
142
  
135
  Digraph graph;
136

	
137
  typedef Digraph::ArcMap<double> DoubleArcMap;
138
  DoubleArcMap length(graph);
139
  DoubleArcMap speed(graph);
140

	
141
  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
143 142
  TimeMap time(length, speed);
144 143
  
145
  Dijkstra<Graph, TimeMap> dijkstra(graph, time);
144
  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
146 145
  dijkstra.run(source, target);
147 146
\endcode
148

	
149
We have a length map and a maximum speed map on a graph. The minimum
150
time to pass the edge can be calculated as the division of the two
151
maps which can be done implicitly with the \c DivMap template
147
We have a length map and a maximum speed map on the arcs of a digraph.
148
The minimum time to pass the arc can be calculated as the division of
149
the two maps which can be done implicitly with the \c DivMap template
152 150
class. We use the implicit minimum time map as the length map of the
153 151
\c Dijkstra algorithm.
154 152
*/
155 153

	
156 154
/**
157 155
@defgroup matrices Matrices 
158 156
@ingroup datas
159 157
\brief Two dimensional data storages implemented in LEMON.
160 158

	
161 159
This group describes two dimensional data storages implemented in LEMON.
162 160
*/
163 161

	
164 162
/**
165 163
@defgroup paths Path Structures
166 164
@ingroup datas
167 165
\brief Path structures implemented in LEMON.
168 166

	
169 167
This group describes the path structures implemented in LEMON.
170 168

	
171 169
LEMON provides flexible data structures to work with paths.
172 170
All of them have similar interfaces and they can be copied easily with
173 171
assignment operators and copy constructors. This makes it easy and
174 172
efficient to have e.g. the Dijkstra algorithm to store its result in
175 173
any kind of path structure.
176 174

	
177 175
\sa lemon::concepts::Path
178 176

	
179 177
*/
180 178

	
181 179
/**
182 180
@defgroup auxdat Auxiliary Data Structures
183 181
@ingroup datas
184 182
\brief Auxiliary data structures implemented in LEMON.
185 183

	
186 184
This group describes some data structures implemented in LEMON in
187 185
order to make it easier to implement combinatorial algorithms.
188 186
*/
189 187

	
190 188

	
191 189
/**
192 190
@defgroup algs Algorithms
193 191
\brief This group describes the several algorithms
194 192
implemented in LEMON.
195 193

	
196 194
This group describes the several algorithms
197 195
implemented in LEMON.
198 196
*/
199 197

	
200 198
/**
201 199
@defgroup search Graph Search
202 200
@ingroup algs
203 201
\brief Common graph search algorithms.
204 202

	
205 203
This group describes the common graph search algorithms like 
206 204
Breadth-first search (Bfs) and Depth-first search (Dfs).
207 205
*/
208 206

	
209 207
/**
210 208
@defgroup shortest_path Shortest Path algorithms
211 209
@ingroup algs
212 210
\brief Algorithms for finding shortest paths.
213 211

	
214 212
This group describes the algorithms for finding shortest paths in graphs.
215 213
*/
216 214

	
217 215
/** 
218 216
@defgroup max_flow Maximum Flow algorithms 
219 217
@ingroup algs 
220 218
\brief Algorithms for finding maximum flows.
221 219

	
222 220
This group describes the algorithms for finding maximum flows and
223 221
feasible circulations.
224 222

	
225 223
The maximum flow problem is to find a flow between a single source and
226 224
a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
227 225
directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
228 226
function and given \f$s, t \in V\f$ source and target node. The
229 227
maximum flow is the \f$f_a\f$ solution of the next optimization problem:
230 228

	
231 229
\f[ 0 \le f_a \le c_a \f]
232 230
\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]
233 231
\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
234 232

	
235 233
LEMON contains several algorithms for solving maximum flow problems:
236 234
- \ref lemon::EdmondsKarp "Edmonds-Karp" 
237 235
- \ref lemon::Preflow "Goldberg's Preflow algorithm"
238 236
- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
239 237
- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
240 238

	
241 239
In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
242 240
fastest method to compute the maximum flow. All impelementations
243 241
provides functions to query the minimum cut, which is the dual linear
244 242
programming problem of the maximum flow.
245 243

	
246 244
*/
247 245

	
248 246
/**
249 247
@defgroup min_cost_flow Minimum Cost Flow algorithms
250 248
@ingroup algs
251 249

	
252 250
\brief Algorithms for finding minimum cost flows and circulations.
253 251

	
254 252
This group describes the algorithms for finding minimum cost flows and
255 253
circulations.  
256 254
*/
257 255

	
258 256
/**
259 257
@defgroup min_cut Minimum Cut algorithms 
260 258
@ingroup algs 
261 259

	
262 260
\brief Algorithms for finding minimum cut in graphs.
263 261

	
264 262
This group describes the algorithms for finding minimum cut in graphs.
265 263

	
266 264
The minimum cut problem is to find a non-empty and non-complete
267 265
\f$X\f$ subset of the vertices with minimum overall capacity on
268 266
outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
269 267
\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
270 268
cut is the \f$X\f$ solution of the next optimization problem:
271 269

	
272 270
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
273 271

	
274 272
LEMON contains several algorithms related to minimum cut problems:
275 273

	
276 274
- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
277 275
  in directed graphs  
278 276
- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
279 277
  calculate minimum cut in undirected graphs
280 278
- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
281 279
  pairs minimum cut in undirected graphs
282 280

	
283 281
If you want to find minimum cut just between two distinict nodes,
284 282
please see the \ref max_flow "Maximum Flow page".
285 283

	
286 284
*/
287 285

	
288 286
/**
289 287
@defgroup graph_prop Connectivity and other graph properties
290 288
@ingroup algs
291 289
\brief Algorithms for discovering the graph properties
292 290

	
293 291
This group describes the algorithms for discovering the graph properties
294 292
like connectivity, bipartiteness, euler property, simplicity etc.
295 293

	
296 294
\image html edge_biconnected_components.png
297 295
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
298 296
*/
299 297

	
300 298
/**
301 299
@defgroup planar Planarity embedding and drawing
302 300
@ingroup algs
303 301
\brief Algorithms for planarity checking, embedding and drawing
304 302

	
305 303
This group describes the algorithms for planarity checking, embedding and drawing.
306 304

	
307 305
\image html planar.png
308 306
\image latex planar.eps "Plane graph" width=\textwidth
309 307
*/
310 308

	
311 309
/**
312 310
@defgroup matching Matching algorithms 
313 311
@ingroup algs
314 312
\brief Algorithms for finding matchings in graphs and bipartite graphs.
315 313

	
316 314
This group contains algorithm objects and functions to calculate
317 315
matchings in graphs and bipartite graphs. The general matching problem is
318
finding a subset of the edges which does not shares common endpoints.
316
finding a subset of the arcs which does not shares common endpoints.
319 317
 
320 318
There are several different algorithms for calculate matchings in
321 319
graphs.  The matching problems in bipartite graphs are generally
322 320
easier than in general graphs. The goal of the matching optimization
323 321
can be the finding maximum cardinality, maximum weight or minimum cost
324 322
matching. The search can be constrained to find perfect or
325 323
maximum cardinality matching.
326 324

	
327 325
Lemon contains the next algorithms:
328 326
- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
329 327
  augmenting path algorithm for calculate maximum cardinality matching in 
330 328
  bipartite graphs
331 329
- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
332 330
  algorithm for calculate maximum cardinality matching in bipartite graphs 
333 331
- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
334 332
  Successive shortest path algorithm for calculate maximum weighted matching 
335 333
  and maximum weighted bipartite matching in bipartite graph
336 334
- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
337 335
  Successive shortest path algorithm for calculate minimum cost maximum 
338 336
  matching in bipartite graph
339 337
- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
340 338
  for calculate maximum cardinality matching in general graph
341 339
- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
342 340
  shrinking algorithm for calculate maximum weighted matching in general
343 341
  graph
344 342
- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
345 343
  Edmond's blossom shrinking algorithm for calculate maximum weighted
346 344
  perfect matching in general graph
347 345

	
348 346
\image html bipartite_matching.png
349 347
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
350 348

	
351 349
*/
352 350

	
353 351
/**
354 352
@defgroup spantree Minimum Spanning Tree algorithms
355 353
@ingroup algs
356 354
\brief Algorithms for finding a minimum cost spanning tree in a graph.
357 355

	
358 356
This group describes the algorithms for finding a minimum cost spanning
359 357
tree in a graph
360 358
*/
361 359

	
362 360

	
363 361
/**
364 362
@defgroup auxalg Auxiliary algorithms
365 363
@ingroup algs
366 364
\brief Auxiliary algorithms implemented in LEMON.
367 365

	
368 366
This group describes some algorithms implemented in LEMON
369 367
in order to make it easier to implement complex algorithms.
370 368
*/
371 369

	
372 370
/**
373 371
@defgroup approx Approximation algorithms
374 372
\brief Approximation algorithms.
375 373

	
376 374
This group describes the approximation and heuristic algorithms
377 375
implemented in LEMON.
378 376
*/
379 377

	
380 378
/**
381 379
@defgroup gen_opt_group General Optimization Tools
382 380
\brief This group describes some general optimization frameworks
383 381
implemented in LEMON.
384 382

	
385 383
This group describes some general optimization frameworks
386 384
implemented in LEMON.
387 385

	
388 386
*/
389 387

	
390 388
/**
391 389
@defgroup lp_group Lp and Mip solvers
392 390
@ingroup gen_opt_group
393 391
\brief Lp and Mip solver interfaces for LEMON.
394 392

	
395 393
This group describes Lp and Mip solver interfaces for LEMON. The
396 394
various LP solvers could be used in the same manner with this
397 395
interface.
398 396

	
399 397
*/
400 398

	
401 399
/** 
402 400
@defgroup lp_utils Tools for Lp and Mip solvers 
403 401
@ingroup lp_group
404 402
\brief Helper tools to the Lp and Mip solvers.
405 403

	
406 404
This group adds some helper tools to general optimization framework
407 405
implemented in LEMON.
408 406
*/
409 407

	
410 408
/**
411 409
@defgroup metah Metaheuristics
412 410
@ingroup gen_opt_group
413 411
\brief Metaheuristics for LEMON library.
414 412

	
Ignore white space 192 line context
1 1
/* -*- C++ -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_CONCEPT_MAPS_H
20 20
#define LEMON_CONCEPT_MAPS_H
21 21

	
22 22
#include <lemon/bits/utility.h>
23 23
#include <lemon/concept_check.h>
24 24

	
25 25
///\ingroup concept
26 26
///\file
27 27
///\brief Map concepts checking classes for testing and documenting.
28 28

	
29 29
namespace lemon {
30 30

	
31 31
  namespace concepts {
32
  
32

	
33 33
    /// \addtogroup concept
34 34
    /// @{
35 35

	
36 36
    /// Readable map concept
37 37

	
38 38
    /// Readable map concept.
39 39
    ///
40 40
    template<typename K, typename T>
41 41
    class ReadMap
42 42
    {
43 43
    public:
44 44
      /// The key type of the map.
45
      typedef K Key;    
45
      typedef K Key;
46 46
      /// The value type of the map. (The type of objects associated with the keys).
47 47
      typedef T Value;
48 48

	
49
      /// Returns the value associated with a key.
49
      /// Returns the value associated with the given key.
50 50

	
51
      /// Returns the value associated with a key.
52
      /// \bug Value shouldn't need to be default constructible.
53
      ///
54
      Value operator[](const Key &) const {return Value();}
51
      /// Returns the value associated with the given key.
52
      /// \bug Value shouldn't need to be default constructible. 
53
      Value operator[](const Key &) const { return Value(); }
55 54

	
56 55
      template<typename _ReadMap>
57 56
      struct Constraints {
58 57
	void constraints() {
59 58
	  Value val = m[key];
60 59
	  val = m[key];
61
	  typename _ReadMap::Value own_val = m[own_key]; 
62
	  own_val = m[own_key]; 
60
	  typename _ReadMap::Value own_val = m[own_key];
61
	  own_val = m[own_key];
63 62

	
63
	  ignore_unused_variable_warning(key);
64 64
	  ignore_unused_variable_warning(val);
65
	  ignore_unused_variable_warning(own_key);
65 66
	  ignore_unused_variable_warning(own_val);
66
	  ignore_unused_variable_warning(key);
67 67
	}
68
	Key& key;
69
	typename _ReadMap::Key& own_key;
70
	_ReadMap& m;
68
	const Key& key;
69
	const typename _ReadMap::Key& own_key;
70
	const _ReadMap& m;
71 71
      };
72
      
72

	
73 73
    };
74 74

	
75 75

	
76 76
    /// Writable map concept
77
    
77

	
78 78
    /// Writable map concept.
79 79
    ///
80 80
    template<typename K, typename T>
81 81
    class WriteMap
82 82
    {
83 83
    public:
84 84
      /// The key type of the map.
85
      typedef K Key;    
85
      typedef K Key;
86 86
      /// The value type of the map. (The type of objects associated with the keys).
87 87
      typedef T Value;
88 88

	
89
      /// Sets the value associated with a key.
90
      void set(const Key &,const Value &) {}
89
      /// Sets the value associated with the given key.
90
      void set(const Key &, const Value &) {}
91 91

	
92
      ///Default constructor
92
      /// Default constructor.
93 93
      WriteMap() {}
94 94

	
95 95
      template <typename _WriteMap>
96 96
      struct Constraints {
97 97
	void constraints() {
98
	  // No constraints for constructor.
99 98
	  m.set(key, val);
100 99
	  m.set(own_key, own_val);
100

	
101 101
	  ignore_unused_variable_warning(key);
102 102
	  ignore_unused_variable_warning(val);
103 103
	  ignore_unused_variable_warning(own_key);
104 104
	  ignore_unused_variable_warning(own_val);
105 105
	}
106

	
107
	Value& val;
108
	typename _WriteMap::Value own_val;
109
	Key& key;
110
	typename _WriteMap::Key& own_key;
106
	const Key& key;
107
	const Value& val;
108
	const typename _WriteMap::Key& own_key;
109
	const typename _WriteMap::Value own_val;
111 110
	_WriteMap& m;
112

	
113 111
      };
114 112
    };
115 113

	
116 114
    /// Read/writable map concept
117
    
115

	
118 116
    /// Read/writable map concept.
119 117
    ///
120 118
    template<typename K, typename T>
121 119
    class ReadWriteMap : public ReadMap<K,T>,
122 120
			 public WriteMap<K,T>
123 121
    {
124 122
    public:
125 123
      /// The key type of the map.
126
      typedef K Key;    
124
      typedef K Key;
127 125
      /// The value type of the map. (The type of objects associated with the keys).
128 126
      typedef T Value;
129 127

	
130
      /// Returns the value associated with a key.
131
      Value operator[](const Key &) const {return Value();}
132
      /// Sets the value associated with a key.
133
      void set(const Key & ,const Value &) {}
128
      /// Returns the value associated with the given key.
129
      Value operator[](const Key &) const { return Value(); }
130

	
131
      /// Sets the value associated with the given key.
132
      void set(const Key &, const Value &) {}
134 133

	
135 134
      template<typename _ReadWriteMap>
136 135
      struct Constraints {
137 136
	void constraints() {
138 137
	  checkConcept<ReadMap<K, T>, _ReadWriteMap >();
139 138
	  checkConcept<WriteMap<K, T>, _ReadWriteMap >();
140 139
	}
141 140
      };
142 141
    };
143
  
144
  
142

	
143

	
145 144
    /// Dereferable map concept
146
    
145

	
147 146
    /// Dereferable map concept.
148 147
    ///
149
    /// \todo Rethink this concept.
150 148
    template<typename K, typename T, typename R, typename CR>
151 149
    class ReferenceMap : public ReadWriteMap<K,T>
152 150
    {
153 151
    public:
154 152
      /// Tag for reference maps.
155 153
      typedef True ReferenceMapTag;
156 154
      /// The key type of the map.
157
      typedef K Key;    
155
      typedef K Key;
158 156
      /// The value type of the map. (The type of objects associated with the keys).
159 157
      typedef T Value;
160 158
      /// The reference type of the map.
161 159
      typedef R Reference;
162 160
      /// The const reference type of the map.
163 161
      typedef CR ConstReference;
164 162

	
165 163
    protected:
166 164
      Value tmp;
167 165
    public:
168 166

	
169
      ///Returns a reference to the value associated with a key.
167
      /// Returns a reference to the value associated with the given key.
170 168
      Reference operator[](const Key &) { return tmp; }
171
      ///Returns a const reference to the value associated with a key.
169

	
170
      /// Returns a const reference to the value associated with the given key.
172 171
      ConstReference operator[](const Key &) const { return tmp; }
173
      /// Sets the value associated with a key.
172

	
173
      /// Sets the value associated with the given key.
174 174
      void set(const Key &k,const Value &t) { operator[](k)=t; }
175 175

	
176 176
      template<typename _ReferenceMap>
177 177
      struct Constraints {
178 178
	void constraints() {
179 179
	  checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
180
	  ref = m[key];
180 181
	  m[key] = val;
181
	  val  = m[key];
182 182
	  m[key] = ref;
183
	  ref = m[key];
183
	  m[key] = cref;
184
	  own_ref = m[own_key];
184 185
	  m[own_key] = own_val;
185
	  own_val  = m[own_key];
186 186
	  m[own_key] = own_ref;
187
	  own_ref = m[own_key];	  	  
187
	  m[own_key] = own_cref;
188
	  m[key] = m[own_key];
189
	  m[own_key] = m[key];
188 190
	}
189

	
190
	typename _ReferenceMap::Key& own_key;
191
	const Key& key;
192
	Value& val;
193
	Reference ref;
194
	ConstReference cref;
195
	const typename _ReferenceMap::Key& own_key;
191 196
	typename _ReferenceMap::Value& own_val;
192 197
	typename _ReferenceMap::Reference own_ref;
193
	Key& key;
194
	Value& val;
195
	Reference ref;
198
	typename _ReferenceMap::ConstReference own_cref;
196 199
	_ReferenceMap& m;
197 200
      };
198 201
    };
199 202

	
200 203
    // @}
201 204

	
202 205
  } //namespace concepts
203 206

	
204 207
} //namespace lemon
205 208

	
206 209
#endif // LEMON_CONCEPT_MAPS_H
Ignore white space 6 line context
1 1
/* -*- C++ -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_MAPS_H
20 20
#define LEMON_MAPS_H
21 21

	
22 22
#include <iterator>
23 23
#include <functional>
24 24
#include <vector>
25 25

	
26 26
#include <lemon/bits/utility.h>
27
// #include <lemon/bits/traits.h>
27
#include <lemon/bits/traits.h>
28 28

	
29 29
///\file
30 30
///\ingroup maps
31 31
///\brief Miscellaneous property maps
32
///
32

	
33 33
#include <map>
34 34

	
35 35
namespace lemon {
36 36

	
37 37
  /// \addtogroup maps
38 38
  /// @{
39 39

	
40 40
  /// Base class of maps.
41 41

	
42
  /// Base class of maps.
43
  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
44
  template<typename K, typename T>
42
  /// Base class of maps. It provides the necessary type definitions
43
  /// required by the map %concepts.
44
  template<typename K, typename V>
45 45
  class MapBase {
46 46
  public:
47
    /// The key type of the map.
47
    /// \biref The key type of the map.
48 48
    typedef K Key;
49
    /// The value type of the map. (The type of objects associated with the keys).
50
    typedef T Value;
49
    /// \brief The value type of the map.
50
    /// (The type of objects associated with the keys).
51
    typedef V Value;
51 52
  };
52 53

	
54

	
53 55
  /// Null map. (a.k.a. DoNothingMap)
54 56

	
55 57
  /// This map can be used if you have to provide a map only for
56
  /// its type definitions, or if you have to provide a writable map, 
57
  /// but data written to it is not required (i.e. it will be sent to 
58
  /// its type definitions, or if you have to provide a writable map,
59
  /// but data written to it is not required (i.e. it will be sent to
58 60
  /// <tt>/dev/null</tt>).
59
  template<typename K, typename T>
60
  class NullMap : public MapBase<K, T> {
61
  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
62
  ///
63
  /// \sa ConstMap
64
  template<typename K, typename V>
65
  class NullMap : public MapBase<K, V> {
61 66
  public:
62
    typedef MapBase<K, T> Parent;
67
    typedef MapBase<K, V> Parent;
63 68
    typedef typename Parent::Key Key;
64 69
    typedef typename Parent::Value Value;
65
    
70

	
66 71
    /// Gives back a default constructed element.
67
    T operator[](const K&) const { return T(); }
72
    Value operator[](const Key&) const { return Value(); }
68 73
    /// Absorbs the value.
69
    void set(const K&, const T&) {}
74
    void set(const Key&, const Value&) {}
70 75
  };
71 76

	
72
  ///Returns a \c NullMap class
77
  /// Returns a \ref NullMap class
73 78

	
74
  ///This function just returns a \c NullMap class.
75
  ///\relates NullMap
76
  template <typename K, typename V> 
79
  /// This function just returns a \ref NullMap class.
80
  /// \relates NullMap
81
  template <typename K, typename V>
77 82
  NullMap<K, V> nullMap() {
78 83
    return NullMap<K, V>();
79 84
  }
80 85

	
81 86

	
82 87
  /// Constant map.
83 88

	
84
  /// This is a \ref concepts::ReadMap "readable" map which assigns a 
85
  /// specified value to each key.
86
  /// In other aspects it is equivalent to \c NullMap.
87
  template<typename K, typename T>
88
  class ConstMap : public MapBase<K, T> {
89
  /// This \ref concepts::ReadMap "readable map" assigns a specified
90
  /// value to each key.
91
  ///
92
  /// In other aspects it is equivalent to \ref NullMap.
93
  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
94
  /// concept, but it absorbs the data written to it.
95
  ///
96
  /// The simplest way of using this map is through the constMap()
97
  /// function.
98
  ///
99
  /// \sa NullMap
100
  /// \sa IdentityMap
101
  template<typename K, typename V>
102
  class ConstMap : public MapBase<K, V> {
89 103
  private:
90
    T v;
104
    V _value;
91 105
  public:
92

	
93
    typedef MapBase<K, T> Parent;
106
    typedef MapBase<K, V> Parent;
94 107
    typedef typename Parent::Key Key;
95 108
    typedef typename Parent::Value Value;
96 109

	
97 110
    /// Default constructor
98 111

	
99 112
    /// Default constructor.
100
    /// The value of the map will be uninitialized. 
101
    /// (More exactly it will be default constructed.)
113
    /// The value of the map will be default constructed.
102 114
    ConstMap() {}
103
    
115

	
104 116
    /// Constructor with specified initial value
105 117

	
106 118
    /// Constructor with specified initial value.
107
    /// \param _v is the initial value of the map.
108
    ConstMap(const T &_v) : v(_v) {}
109
    
110
    ///\e
111
    T operator[](const K&) const { return v; }
119
    /// \param v is the initial value of the map.
120
    ConstMap(const Value &v) : _value(v) {}
112 121

	
113
    ///\e
114
    void setAll(const T &t) {
115
      v = t;
116
    }    
122
    /// Gives back the specified value.
123
    Value operator[](const Key&) const { return _value; }
117 124

	
118
    template<typename T1>
119
    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
125
    /// Absorbs the value.
126
    void set(const Key&, const Value&) {}
127

	
128
    /// Sets the value that is assigned to each key.
129
    void setAll(const Value &v) {
130
      _value = v;
131
    }
132

	
133
    template<typename V1>
134
    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
120 135
  };
121 136

	
122
  ///Returns a \c ConstMap class
137
  /// Returns a \ref ConstMap class
123 138

	
124
  ///This function just returns a \c ConstMap class.
125
  ///\relates ConstMap
126
  template<typename K, typename V> 
139
  /// This function just returns a \ref ConstMap class.
140
  /// \relates ConstMap
141
  template<typename K, typename V>
127 142
  inline ConstMap<K, V> constMap(const V &v) {
128 143
    return ConstMap<K, V>(v);
129 144
  }
130 145

	
131 146

	
132 147
  template<typename T, T v>
133
  struct Const { };
148
  struct Const {};
134 149

	
135 150
  /// Constant map with inlined constant value.
136 151

	
137
  /// This is a \ref concepts::ReadMap "readable" map which assigns a 
138
  /// specified value to each key.
139
  /// In other aspects it is equivalent to \c NullMap.
152
  /// This \ref concepts::ReadMap "readable map" assigns a specified
153
  /// value to each key.
154
  ///
155
  /// In other aspects it is equivalent to \ref NullMap.
156
  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
157
  /// concept, but it absorbs the data written to it.
158
  ///
159
  /// The simplest way of using this map is through the constMap()
160
  /// function.
161
  ///
162
  /// \sa NullMap
163
  /// \sa IdentityMap
140 164
  template<typename K, typename V, V v>
141 165
  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
142 166
  public:
143 167
    typedef MapBase<K, V> Parent;
144 168
    typedef typename Parent::Key Key;
145 169
    typedef typename Parent::Value Value;
146 170

	
147
    ConstMap() { }
148
    ///\e
149
    V operator[](const K&) const { return v; }
150
    ///\e
151
    void set(const K&, const V&) { }
171
    /// Constructor.
172
    ConstMap() {}
173

	
174
    /// Gives back the specified value.
175
    Value operator[](const Key&) const { return v; }
176

	
177
    /// Absorbs the value.
178
    void set(const Key&, const Value&) {}
152 179
  };
153 180

	
154
  ///Returns a \c ConstMap class with inlined value
181
  /// Returns a \ref ConstMap class with inlined constant value
155 182

	
156
  ///This function just returns a \c ConstMap class with inlined value.
157
  ///\relates ConstMap
158
  template<typename K, typename V, V v> 
183
  /// This function just returns a \ref ConstMap class with inlined
184
  /// constant value.
185
  /// \relates ConstMap
186
  template<typename K, typename V, V v>
159 187
  inline ConstMap<K, Const<V, v> > constMap() {
160 188
    return ConstMap<K, Const<V, v> >();
161 189
  }
162 190

	
163
  ///Map based on \c std::map
164 191

	
165
  ///This is essentially a wrapper for \c std::map with addition that
166
  ///you can specify a default value different from \c Value().
167
  ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
168
  template <typename K, typename T, typename Compare = std::less<K> >
169
  class StdMap : public MapBase<K, T> {
170
    template <typename K1, typename T1, typename C1>
171
    friend class StdMap;
192
  /// Identity map.
193

	
194
  /// This \ref concepts::ReadMap "read-only map" gives back the given
195
  /// key as value without any modification.
196
  ///
197
  /// \sa ConstMap
198
  template <typename T>
199
  class IdentityMap : public MapBase<T, T> {
200
  public:
201
    typedef MapBase<T, T> Parent;
202
    typedef typename Parent::Key Key;
203
    typedef typename Parent::Value Value;
204

	
205
    /// Gives back the given value without any modification.
206
    Value operator[](const Key &k) const {
207
      return k;
208
    }
209
  };
210

	
211
  /// Returns an \ref IdentityMap class
212

	
213
  /// This function just returns an \ref IdentityMap class.
214
  /// \relates IdentityMap
215
  template<typename T>
216
  inline IdentityMap<T> identityMap() {
217
    return IdentityMap<T>();
218
  }
219

	
220

	
221
  /// \brief Map for storing values for integer keys from the range
222
  /// <tt>[0..size-1]</tt>.
223
  ///
224
  /// This map is essentially a wrapper for \c std::vector. It assigns
225
  /// values to integer keys from the range <tt>[0..size-1]</tt>.
226
  /// It can be used with some data structures, for example
227
  /// \ref UnionFind, \ref BinHeap, when the used items are small
228
  /// integers. This map conforms the \ref concepts::ReferenceMap
229
  /// "ReferenceMap" concept.
230
  ///
231
  /// The simplest way of using this map is through the rangeMap()
232
  /// function.
233
  template <typename V>
234
  class RangeMap : public MapBase<int, V> {
235
    template <typename V1>
236
    friend class RangeMap;
237
  private:
238

	
239
    typedef std::vector<V> Vector;
240
    Vector _vector;
241

	
172 242
  public:
173 243

	
174
    typedef MapBase<K, T> Parent;
175
    ///Key type
244
    typedef MapBase<int, V> Parent;
245
    /// Key type
176 246
    typedef typename Parent::Key Key;
177
    ///Value type
247
    /// Value type
178 248
    typedef typename Parent::Value Value;
179
    ///Reference Type
180
    typedef T& Reference;
181
    ///Const reference type
182
    typedef const T& ConstReference;
249
    /// Reference type
250
    typedef typename Vector::reference Reference;
251
    /// Const reference type
252
    typedef typename Vector::const_reference ConstReference;
253

	
254
    typedef True ReferenceMapTag;
255

	
256
  public:
257

	
258
    /// Constructor with specified default value.
259
    RangeMap(int size = 0, const Value &value = Value())
260
      : _vector(size, value) {}
261

	
262
    /// Constructs the map from an appropriate \c std::vector.
263
    template <typename V1>
264
    RangeMap(const std::vector<V1>& vector)
265
      : _vector(vector.begin(), vector.end()) {}
266

	
267
    /// Constructs the map from another \ref RangeMap.
268
    template <typename V1>
269
    RangeMap(const RangeMap<V1> &c)
270
      : _vector(c._vector.begin(), c._vector.end()) {}
271

	
272
    /// Returns the size of the map.
273
    int size() {
274
      return _vector.size();
275
    }
276

	
277
    /// Resizes the map.
278

	
279
    /// Resizes the underlying \c std::vector container, so changes the
280
    /// keyset of the map.
281
    /// \param size The new size of the map. The new keyset will be the
282
    /// range <tt>[0..size-1]</tt>.
283
    /// \param value The default value to assign to the new keys.
284
    void resize(int size, const Value &value = Value()) {
285
      _vector.resize(size, value);
286
    }
287

	
288
  private:
289

	
290
    RangeMap& operator=(const RangeMap&);
291

	
292
  public:
293

	
294
    ///\e
295
    Reference operator[](const Key &k) {
296
      return _vector[k];
297
    }
298

	
299
    ///\e
300
    ConstReference operator[](const Key &k) const {
301
      return _vector[k];
302
    }
303

	
304
    ///\e
305
    void set(const Key &k, const Value &v) {
306
      _vector[k] = v;
307
    }
308
  };
309

	
310
  /// Returns a \ref RangeMap class
311

	
312
  /// This function just returns a \ref RangeMap class.
313
  /// \relates RangeMap
314
  template<typename V>
315
  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
316
    return RangeMap<V>(size, value);
317
  }
318

	
319
  /// \brief Returns a \ref RangeMap class created from an appropriate
320
  /// \c std::vector
321

	
322
  /// This function just returns a \ref RangeMap class created from an
323
  /// appropriate \c std::vector.
324
  /// \relates RangeMap
325
  template<typename V>
326
  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
327
    return RangeMap<V>(vector);
328
  }
329

	
330

	
331
  /// Map type based on \c std::map
332

	
333
  /// This map is essentially a wrapper for \c std::map with addition
334
  /// that you can specify a default value for the keys that are not
335
  /// stored actually. This value can be different from the default
336
  /// contructed value (i.e. \c %Value()).
337
  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
338
  /// concept.
339
  ///
340
  /// This map is useful if a default value should be assigned to most of
341
  /// the keys and different values should be assigned only to a few
342
  /// keys (i.e. the map is "sparse").
343
  /// The name of this type also refers to this important usage.
344
  ///
345
  /// Apart form that this map can be used in many other cases since it
346
  /// is based on \c std::map, which is a general associative container.
347
  /// However keep in mind that it is usually not as efficient as other
348
  /// maps.
349
  ///
350
  /// The simplest way of using this map is through the sparseMap()
351
  /// function.
352
  template <typename K, typename V, typename Compare = std::less<K> >
353
  class SparseMap : public MapBase<K, V> {
354
    template <typename K1, typename V1, typename C1>
355
    friend class SparseMap;
356
  public:
357

	
358
    typedef MapBase<K, V> Parent;
359
    /// Key type
360
    typedef typename Parent::Key Key;
361
    /// Value type
362
    typedef typename Parent::Value Value;
363
    /// Reference type
364
    typedef Value& Reference;
365
    /// Const reference type
366
    typedef const Value& ConstReference;
183 367

	
184 368
    typedef True ReferenceMapTag;
185 369

	
186 370
  private:
187
    
188
    typedef std::map<K, T, Compare> Map;
371

	
372
    typedef std::map<K, V, Compare> Map;
373
    Map _map;
189 374
    Value _value;
190
    Map _map;
191 375

	
192 376
  public:
193 377

	
194
    /// Constructor with specified default value
195
    StdMap(const T& value = T()) : _value(value) {}
196
    /// \brief Constructs the map from an appropriate \c std::map, and 
378
    /// \brief Constructor with specified default value.
379
    SparseMap(const Value &value = Value()) : _value(value) {}
380
    /// \brief Constructs the map from an appropriate \c std::map, and
197 381
    /// explicitly specifies a default value.
198
    template <typename T1, typename Comp1>
199
    StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 
382
    template <typename V1, typename Comp1>
383
    SparseMap(const std::map<Key, V1, Comp1> &map,
384
              const Value &value = Value())
200 385
      : _map(map.begin(), map.end()), _value(value) {}
201
    
202
    /// \brief Constructs a map from an other \ref StdMap.
203
    template<typename T1, typename Comp1>
204
    StdMap(const StdMap<Key, T1, Comp1> &c) 
386

	
387
    /// \brief Constructs the map from another \ref SparseMap.
388
    template<typename V1, typename Comp1>
389
    SparseMap(const SparseMap<Key, V1, Comp1> &c)
205 390
      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
206 391

	
207 392
  private:
208 393

	
209
    StdMap& operator=(const StdMap&);
394
    SparseMap& operator=(const SparseMap&);
210 395

	
211 396
  public:
212 397

	
213 398
    ///\e
214 399
    Reference operator[](const Key &k) {
215 400
      typename Map::iterator it = _map.lower_bound(k);
216 401
      if (it != _map.end() && !_map.key_comp()(k, it->first))
217 402
	return it->second;
218 403
      else
219 404
	return _map.insert(it, std::make_pair(k, _value))->second;
220 405
    }
221 406

	
222
    /// \e 
407
    ///\e
223 408
    ConstReference operator[](const Key &k) const {
224 409
      typename Map::const_iterator it = _map.find(k);
225 410
      if (it != _map.end())
226 411
	return it->second;
227 412
      else
228 413
	return _value;
229 414
    }
230 415

	
231
    /// \e 
232
    void set(const Key &k, const T &t) {
416
    ///\e
417
    void set(const Key &k, const Value &v) {
233 418
      typename Map::iterator it = _map.lower_bound(k);
234 419
      if (it != _map.end() && !_map.key_comp()(k, it->first))
235
	it->second = t;
420
	it->second = v;
236 421
      else
237
	_map.insert(it, std::make_pair(k, t));
422
	_map.insert(it, std::make_pair(k, v));
238 423
    }
239 424

	
240
    /// \e
241
    void setAll(const T &t) {
242
      _value = t;
425
    ///\e
426
    void setAll(const Value &v) {
427
      _value = v;
243 428
      _map.clear();
244
    }    
429
    }
430
  };
245 431

	
246
  };
247
  
248
  ///Returns a \c StdMap class
432
  /// Returns a \ref SparseMap class
249 433

	
250
  ///This function just returns a \c StdMap class with specified 
251
  ///default value.
252
  ///\relates StdMap
253
  template<typename K, typename V, typename Compare> 
254
  inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
255
    return StdMap<K, V, Compare>(value);
256
  }
257
  
258
  ///Returns a \c StdMap class
259

	
260
  ///This function just returns a \c StdMap class with specified 
261
  ///default value.
262
  ///\relates StdMap
263
  template<typename K, typename V> 
264
  inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
265
    return StdMap<K, V, std::less<K> >(value);
266
  }
267
  
268
  ///Returns a \c StdMap class created from an appropriate std::map
269

	
270
  ///This function just returns a \c StdMap class created from an 
271
  ///appropriate std::map.
272
  ///\relates StdMap
273
  template<typename K, typename V, typename Compare> 
274
  inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map, 
275
                                       const V& value = V() ) {
276
    return StdMap<K, V, Compare>(map, value);
434
  /// This function just returns a \ref SparseMap class with specified
435
  /// default value.
436
  /// \relates SparseMap
437
  template<typename K, typename V, typename Compare>
438
  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
439
    return SparseMap<K, V, Compare>(value);
277 440
  }
278 441

	
279
  ///Returns a \c StdMap class created from an appropriate std::map
280

	
281
  ///This function just returns a \c StdMap class created from an 
282
  ///appropriate std::map.
283
  ///\relates StdMap
284
  template<typename K, typename V> 
285
  inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map, 
286
                                             const V& value = V() ) {
287
    return StdMap<K, V, std::less<K> >(map, value);
442
  template<typename K, typename V>
443
  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
444
    return SparseMap<K, V, std::less<K> >(value);
288 445
  }
289 446

	
290
  /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
291
  ///
292
  /// This map has the <tt>[0..size-1]</tt> keyset and the values
293
  /// are stored in a \c std::vector<T>  container. It can be used with
294
  /// some data structures, for example \c UnionFind, \c BinHeap, when 
295
  /// the used items are small integer numbers.
296
  /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
297
  ///
298
  /// \todo Revise its name
299
  template <typename T>
300
  class IntegerMap : public MapBase<int, T> {
447
  /// \brief Returns a \ref SparseMap class created from an appropriate
448
  /// \c std::map
301 449

	
302
    template <typename T1>
303
    friend class IntegerMap;
304

	
305
  public:
306

	
307
    typedef MapBase<int, T> Parent;
308
    ///\e
309
    typedef typename Parent::Key Key;
310
    ///\e
311
    typedef typename Parent::Value Value;
312
    ///\e
313
    typedef T& Reference;
314
    ///\e
315
    typedef const T& ConstReference;
316

	
317
    typedef True ReferenceMapTag;
318

	
319
  private:
320
    
321
    typedef std::vector<T> Vector;
322
    Vector _vector;
323

	
324
  public:
325

	
326
    /// Constructor with specified default value
327
    IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
328

	
329
    /// \brief Constructs the map from an appropriate \c std::vector.
330
    template <typename T1>
331
    IntegerMap(const std::vector<T1>& vector) 
332
      : _vector(vector.begin(), vector.end()) {}
333
    
334
    /// \brief Constructs a map from an other \ref IntegerMap.
335
    template <typename T1>
336
    IntegerMap(const IntegerMap<T1> &c) 
337
      : _vector(c._vector.begin(), c._vector.end()) {}
338

	
339
    /// \brief Resize the container
340
    void resize(int size, const T& value = T()) {
341
      _vector.resize(size, value);
342
    }
343

	
344
  private:
345

	
346
    IntegerMap& operator=(const IntegerMap&);
347

	
348
  public:
349

	
350
    ///\e
351
    Reference operator[](Key k) {
352
      return _vector[k];
353
    }
354

	
355
    /// \e 
356
    ConstReference operator[](Key k) const {
357
      return _vector[k];
358
    }
359

	
360
    /// \e 
361
    void set(const Key &k, const T& t) {
362
      _vector[k] = t;
363
    }
364

	
365
  };
366
  
367
  ///Returns an \c IntegerMap class
368

	
369
  ///This function just returns an \c IntegerMap class.
370
  ///\relates IntegerMap
371
  template<typename T>
372
  inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
373
    return IntegerMap<T>(size, value);
450
  /// This function just returns a \ref SparseMap class created from an
451
  /// appropriate \c std::map.
452
  /// \relates SparseMap
453
  template<typename K, typename V, typename Compare>
454
  inline SparseMap<K, V, Compare>
455
    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
456
  {
457
    return SparseMap<K, V, Compare>(map, value);
374 458
  }
375 459

	
376 460
  /// @}
377 461

	
378 462
  /// \addtogroup map_adaptors
379 463
  /// @{
380 464

	
381
  /// \brief Identity map.
465
  /// Composition of two maps
466

	
467
  /// This \ref concepts::ReadMap "read-only map" returns the
468
  /// composition of two given maps. That is to say, if \c m1 is of
469
  /// type \c M1 and \c m2 is of \c M2, then for
470
  /// \code
471
  ///   ComposeMap<M1, M2> cm(m1,m2);
472
  /// \endcode
473
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
382 474
  ///
383
  /// This map gives back the given key as value without any
384
  /// modification. 
385
  template <typename T>
386
  class IdentityMap : public MapBase<T, T> {
475
  /// The \c Key type of the map is inherited from \c M2 and the
476
  /// \c Value type is from \c M1.
477
  /// \c M2::Value must be convertible to \c M1::Key.
478
  ///
479
  /// The simplest way of using this map is through the composeMap()
480
  /// function.
481
  ///
482
  /// \sa CombineMap
483
  ///
484
  /// \todo Check the requirements.
485
  template <typename M1, typename M2>
486
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
487
    const M1 &_m1;
488
    const M2 &_m2;
387 489
  public:
388
    typedef MapBase<T, T> Parent;
490
    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
389 491
    typedef typename Parent::Key Key;
390 492
    typedef typename Parent::Value Value;
391 493

	
494
    /// Constructor
495
    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
496

	
392 497
    /// \e
393
    const T& operator[](const T& t) const {
394
      return t;
395
    }
498
    typename MapTraits<M1>::ConstReturnValue
499
    operator[](const Key &k) const { return _m1[_m2[k]]; }
396 500
  };
397 501

	
398
  ///Returns an \c IdentityMap class
502
  /// Returns a \ref ComposeMap class
399 503

	
400
  ///This function just returns an \c IdentityMap class.
401
  ///\relates IdentityMap
402
  template<typename T>
403
  inline IdentityMap<T> identityMap() {
404
    return IdentityMap<T>();
504
  /// This function just returns a \ref ComposeMap class.
505
  ///
506
  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
507
  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
508
  /// will be equal to <tt>m1[m2[x]]</tt>.
509
  ///
510
  /// \relates ComposeMap
511
  template <typename M1, typename M2>
512
  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
513
    return ComposeMap<M1, M2>(m1, m2);
405 514
  }
406
  
407 515

	
408
  ///\brief Convert the \c Value of a map to another type using
409
  ///the default conversion.
516

	
517
  /// Combination of two maps using an STL (binary) functor.
518

	
519
  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
520
  /// binary functor and returns the combination of the two given maps
521
  /// using the functor.
522
  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
523
  /// and \c f is of \c F, then for
524
  /// \code
525
  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
526
  /// \endcode
527
  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
410 528
  ///
411
  ///This \ref concepts::ReadMap "read only map"
412
  ///converts the \c Value of a map to type \c T.
413
  ///Its \c Key is inherited from \c M.
414
  template <typename M, typename T> 
415
  class ConvertMap : public MapBase<typename M::Key, T> {
416
    const M& m;
529
  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
530
  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
531
  /// \c M2::Value and \c M1::Value must be convertible to the
532
  /// corresponding input parameter of \c F and the return type of \c F
533
  /// must be convertible to \c V.
534
  ///
535
  /// The simplest way of using this map is through the combineMap()
536
  /// function.
537
  ///
538
  /// \sa ComposeMap
539
  ///
540
  /// \todo Check the requirements.
541
  template<typename M1, typename M2, typename F,
542
	   typename V = typename F::result_type>
543
  class CombineMap : public MapBase<typename M1::Key, V> {
544
    const M1 &_m1;
545
    const M2 &_m2;
546
    F _f;
417 547
  public:
418
    typedef MapBase<typename M::Key, T> Parent;
548
    typedef MapBase<typename M1::Key, V> Parent;
419 549
    typedef typename Parent::Key Key;
420 550
    typedef typename Parent::Value Value;
421 551

	
422
    ///Constructor
552
    /// Constructor
553
    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
554
      : _m1(m1), _m2(m2), _f(f) {}
555
    /// \e
556
    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
557
  };
423 558

	
424
    ///Constructor.
425
    ///\param _m is the underlying map.
426
    ConvertMap(const M &_m) : m(_m) {};
559
  /// Returns a \ref CombineMap class
427 560

	
428
    ///\e
429
    Value operator[](const Key& k) const {return m[k];}
430
  };
431
  
432
  ///Returns a \c ConvertMap class
433

	
434
  ///This function just returns a \c ConvertMap class.
435
  ///\relates ConvertMap
436
  template<typename T, typename M>
437
  inline ConvertMap<M, T> convertMap(const M &m) {
438
    return ConvertMap<M, T>(m);
561
  /// This function just returns a \ref CombineMap class.
562
  ///
563
  /// For example, if \c m1 and \c m2 are both maps with \c double
564
  /// values, then
565
  /// \code
566
  ///   combineMap(m1,m2,std::plus<double>())
567
  /// \endcode
568
  /// is equivalent to
569
  /// \code
570
  ///   addMap(m1,m2)
571
  /// \endcode
572
  ///
573
  /// This function is specialized for adaptable binary function
574
  /// classes and C++ functions.
575
  ///
576
  /// \relates CombineMap
577
  template<typename M1, typename M2, typename F, typename V>
578
  inline CombineMap<M1, M2, F, V>
579
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
580
    return CombineMap<M1, M2, F, V>(m1,m2,f);
439 581
  }
440 582

	
441
  ///Simple wrapping of a map
583
  template<typename M1, typename M2, typename F>
584
  inline CombineMap<M1, M2, F, typename F::result_type>
585
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
586
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
587
  }
442 588

	
443
  ///This \ref concepts::ReadMap "read only map" returns the simple
444
  ///wrapping of the given map. Sometimes the reference maps cannot be
445
  ///combined with simple read maps. This map adaptor wraps the given
446
  ///map to simple read map.
589
  template<typename M1, typename M2, typename K1, typename K2, typename V>
590
  inline CombineMap<M1, M2, V (*)(K1, K2), V>
591
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
592
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
593
  }
594

	
595

	
596
  /// Converts an STL style (unary) functor to a map
597

	
598
  /// This \ref concepts::ReadMap "read-only map" returns the value
599
  /// of a given functor. Actually, it just wraps the functor and
600
  /// provides the \c Key and \c Value typedefs.
447 601
  ///
448
  ///\sa SimpleWriteMap
602
  /// Template parameters \c K and \c V will become its \c Key and
603
  /// \c Value. In most cases they have to be given explicitly because
604
  /// a functor typically does not provide \c argument_type and
605
  /// \c result_type typedefs.
606
  /// Parameter \c F is the type of the used functor.
449 607
  ///
450
  /// \todo Revise the misleading name 
451
  template<typename M> 
452
  class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
453
    const M& m;
608
  /// The simplest way of using this map is through the functorToMap()
609
  /// function.
610
  ///
611
  /// \sa MapToFunctor
612
  template<typename F,
613
	   typename K = typename F::argument_type,
614
	   typename V = typename F::result_type>
615
  class FunctorToMap : public MapBase<K, V> {
616
    const F &_f;
617
  public:
618
    typedef MapBase<K, V> Parent;
619
    typedef typename Parent::Key Key;
620
    typedef typename Parent::Value Value;
454 621

	
622
    /// Constructor
623
    FunctorToMap(const F &f = F()) : _f(f) {}
624
    /// \e
625
    Value operator[](const Key &k) const { return _f(k); }
626
  };
627

	
628
  /// Returns a \ref FunctorToMap class
629

	
630
  /// This function just returns a \ref FunctorToMap class.
631
  ///
632
  /// This function is specialized for adaptable binary function
633
  /// classes and C++ functions.
634
  ///
635
  /// \relates FunctorToMap
636
  template<typename K, typename V, typename F>
637
  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
638
    return FunctorToMap<F, K, V>(f);
639
  }
640

	
641
  template <typename F>
642
  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
643
    functorToMap(const F &f)
644
  {
645
    return FunctorToMap<F, typename F::argument_type,
646
      typename F::result_type>(f);
647
  }
648

	
649
  template <typename K, typename V>
650
  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
651
    return FunctorToMap<V (*)(K), K, V>(f);
652
  }
653

	
654

	
655
  /// Converts a map to an STL style (unary) functor
656

	
657
  /// This class converts a map to an STL style (unary) functor.
658
  /// That is it provides an <tt>operator()</tt> to read its values.
659
  ///
660
  /// For the sake of convenience it also works as a usual
661
  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
662
  /// and the \c Key and \c Value typedefs also exist.
663
  ///
664
  /// The simplest way of using this map is through the mapToFunctor()
665
  /// function.
666
  ///
667
  ///\sa FunctorToMap
668
  template <typename M>
669
  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
670
    const M &_m;
455 671
  public:
456 672
    typedef MapBase<typename M::Key, typename M::Value> Parent;
457 673
    typedef typename Parent::Key Key;
458 674
    typedef typename Parent::Value Value;
459 675

	
460
    ///Constructor
461
    SimpleMap(const M &_m) : m(_m) {};
462
    ///\e
463
    Value operator[](Key k) const {return m[k];}
676
    typedef typename Parent::Key argument_type;
677
    typedef typename Parent::Value result_type;
678

	
679
    /// Constructor
680
    MapToFunctor(const M &m) : _m(m) {}
681
    /// \e
682
    Value operator()(const Key &k) const { return _m[k]; }
683
    /// \e
684
    Value operator[](const Key &k) const { return _m[k]; }
464 685
  };
465
  
466
  ///Returns a \c SimpleMap class
467 686

	
468
  ///This function just returns a \c SimpleMap class.
469
  ///\relates SimpleMap
687
  /// Returns a \ref MapToFunctor class
688

	
689
  /// This function just returns a \ref MapToFunctor class.
690
  /// \relates MapToFunctor
470 691
  template<typename M>
471
  inline SimpleMap<M> simpleMap(const M &m) {
472
    return SimpleMap<M>(m);
692
  inline MapToFunctor<M> mapToFunctor(const M &m) {
693
    return MapToFunctor<M>(m);
473 694
  }
474 695

	
475
  ///Simple writable wrapping of a map
476 696

	
477
  ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
478
  ///wrapping of the given map. Sometimes the reference maps cannot be
479
  ///combined with simple read-write maps. This map adaptor wraps the
480
  ///given map to simple read-write map.
697
  /// \brief Map adaptor to convert the \c Value type of a map to
698
  /// another type using the default conversion.
699

	
700
  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
701
  /// "readable map" to another type using the default conversion.
702
  /// The \c Key type of it is inherited from \c M and the \c Value
703
  /// type is \c V.
704
  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
481 705
  ///
482
  ///\sa SimpleMap
706
  /// The simplest way of using this map is through the convertMap()
707
  /// function.
708
  template <typename M, typename V>
709
  class ConvertMap : public MapBase<typename M::Key, V> {
710
    const M &_m;
711
  public:
712
    typedef MapBase<typename M::Key, V> Parent;
713
    typedef typename Parent::Key Key;
714
    typedef typename Parent::Value Value;
715

	
716
    /// Constructor
717

	
718
    /// Constructor.
719
    /// \param m The underlying map.
720
    ConvertMap(const M &m) : _m(m) {}
721

	
722
    /// \e
723
    Value operator[](const Key &k) const { return _m[k]; }
724
  };
725

	
726
  /// Returns a \ref ConvertMap class
727

	
728
  /// This function just returns a \ref ConvertMap class.
729
  /// \relates ConvertMap
730
  template<typename V, typename M>
731
  inline ConvertMap<M, V> convertMap(const M &map) {
732
    return ConvertMap<M, V>(map);
733
  }
734

	
735

	
736
  /// Applies all map setting operations to two maps
737

	
738
  /// This map has two \ref concepts::WriteMap "writable map" parameters
739
  /// and each write request will be passed to both of them.
740
  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
741
  /// operations will return the corresponding values of \c M1.
483 742
  ///
484
  /// \todo Revise the misleading name
485
  template<typename M> 
486
  class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
487
    M& m;
743
  /// The \c Key and \c Value types are inherited from \c M1.
744
  /// The \c Key and \c Value of \c M2 must be convertible from those
745
  /// of \c M1.
746
  ///
747
  /// The simplest way of using this map is through the forkMap()
748
  /// function.
749
  template<typename  M1, typename M2>
750
  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
751
    M1 &_m1;
752
    M2 &_m2;
753
  public:
754
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
755
    typedef typename Parent::Key Key;
756
    typedef typename Parent::Value Value;
488 757

	
758
    /// Constructor
759
    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
760
    /// Returns the value associated with the given key in the first map.
761
    Value operator[](const Key &k) const { return _m1[k]; }
762
    /// Sets the value associated with the given key in both maps.
763
    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
764
  };
765

	
766
  /// Returns a \ref ForkMap class
767

	
768
  /// This function just returns a \ref ForkMap class.
769
  /// \relates ForkMap
770
  template <typename M1, typename M2>
771
  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
772
    return ForkMap<M1,M2>(m1,m2);
773
  }
774

	
775

	
776
  /// Sum of two maps
777

	
778
  /// This \ref concepts::ReadMap "read-only map" returns the sum
779
  /// of the values of the two given maps.
780
  /// Its \c Key and \c Value types are inherited from \c M1.
781
  /// The \c Key and \c Value of \c M2 must be convertible to those of
782
  /// \c M1.
783
  ///
784
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
785
  /// \code
786
  ///   AddMap<M1,M2> am(m1,m2);
787
  /// \endcode
788
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
789
  ///
790
  /// The simplest way of using this map is through the addMap()
791
  /// function.
792
  ///
793
  /// \sa SubMap, MulMap, DivMap
794
  /// \sa ShiftMap, ShiftWriteMap
795
  template<typename M1, typename M2>
796
  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
797
    const M1 &_m1;
798
    const M2 &_m2;
799
  public:
800
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
801
    typedef typename Parent::Key Key;
802
    typedef typename Parent::Value Value;
803

	
804
    /// Constructor
805
    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
806
    /// \e
807
    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
808
  };
809

	
810
  /// Returns an \ref AddMap class
811

	
812
  /// This function just returns an \ref AddMap class.
813
  ///
814
  /// For example, if \c m1 and \c m2 are both maps with \c double
815
  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
816
  /// <tt>m1[x]+m2[x]</tt>.
817
  ///
818
  /// \relates AddMap
819
  template<typename M1, typename M2>
820
  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
821
    return AddMap<M1, M2>(m1,m2);
822
  }
823

	
824

	
825
  /// Difference of two maps
826

	
827
  /// This \ref concepts::ReadMap "read-only map" returns the difference
828
  /// of the values of the two given maps.
829
  /// Its \c Key and \c Value types are inherited from \c M1.
830
  /// The \c Key and \c Value of \c M2 must be convertible to those of
831
  /// \c M1.
832
  ///
833
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
834
  /// \code
835
  ///   SubMap<M1,M2> sm(m1,m2);
836
  /// \endcode
837
  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
838
  ///
839
  /// The simplest way of using this map is through the subMap()
840
  /// function.
841
  ///
842
  /// \sa AddMap, MulMap, DivMap
843
  template<typename M1, typename M2>
844
  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
845
    const M1 &_m1;
846
    const M2 &_m2;
847
  public:
848
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
849
    typedef typename Parent::Key Key;
850
    typedef typename Parent::Value Value;
851

	
852
    /// Constructor
853
    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
854
    /// \e
855
    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
856
  };
857

	
858
  /// Returns a \ref SubMap class
859

	
860
  /// This function just returns a \ref SubMap class.
861
  ///
862
  /// For example, if \c m1 and \c m2 are both maps with \c double
863
  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
864
  /// <tt>m1[x]-m2[x]</tt>.
865
  ///
866
  /// \relates SubMap
867
  template<typename M1, typename M2>
868
  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
869
    return SubMap<M1, M2>(m1,m2);
870
  }
871

	
872

	
873
  /// Product of two maps
874

	
875
  /// This \ref concepts::ReadMap "read-only map" returns the product
876
  /// of the values of the two given maps.
877
  /// Its \c Key and \c Value types are inherited from \c M1.
878
  /// The \c Key and \c Value of \c M2 must be convertible to those of
879
  /// \c M1.
880
  ///
881
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
882
  /// \code
883
  ///   MulMap<M1,M2> mm(m1,m2);
884
  /// \endcode
885
  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
886
  ///
887
  /// The simplest way of using this map is through the mulMap()
888
  /// function.
889
  ///
890
  /// \sa AddMap, SubMap, DivMap
891
  /// \sa ScaleMap, ScaleWriteMap
892
  template<typename M1, typename M2>
893
  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
894
    const M1 &_m1;
895
    const M2 &_m2;
896
  public:
897
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
898
    typedef typename Parent::Key Key;
899
    typedef typename Parent::Value Value;
900

	
901
    /// Constructor
902
    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
903
    /// \e
904
    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
905
  };
906

	
907
  /// Returns a \ref MulMap class
908

	
909
  /// This function just returns a \ref MulMap class.
910
  ///
911
  /// For example, if \c m1 and \c m2 are both maps with \c double
912
  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
913
  /// <tt>m1[x]*m2[x]</tt>.
914
  ///
915
  /// \relates MulMap
916
  template<typename M1, typename M2>
917
  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
918
    return MulMap<M1, M2>(m1,m2);
919
  }
920

	
921

	
922
  /// Quotient of two maps
923

	
924
  /// This \ref concepts::ReadMap "read-only map" returns the quotient
925
  /// of the values of the two given maps.
926
  /// Its \c Key and \c Value types are inherited from \c M1.
927
  /// The \c Key and \c Value of \c M2 must be convertible to those of
928
  /// \c M1.
929
  ///
930
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
931
  /// \code
932
  ///   DivMap<M1,M2> dm(m1,m2);
933
  /// \endcode
934
  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
935
  ///
936
  /// The simplest way of using this map is through the divMap()
937
  /// function.
938
  ///
939
  /// \sa AddMap, SubMap, MulMap
940
  template<typename M1, typename M2>
941
  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
942
    const M1 &_m1;
943
    const M2 &_m2;
944
  public:
945
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
946
    typedef typename Parent::Key Key;
947
    typedef typename Parent::Value Value;
948

	
949
    /// Constructor
950
    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
951
    /// \e
952
    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
953
  };
954

	
955
  /// Returns a \ref DivMap class
956

	
957
  /// This function just returns a \ref DivMap class.
958
  ///
959
  /// For example, if \c m1 and \c m2 are both maps with \c double
960
  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
961
  /// <tt>m1[x]/m2[x]</tt>.
962
  ///
963
  /// \relates DivMap
964
  template<typename M1, typename M2>
965
  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
966
    return DivMap<M1, M2>(m1,m2);
967
  }
968

	
969

	
970
  /// Shifts a map with a constant.
971

	
972
  /// This \ref concepts::ReadMap "read-only map" returns the sum of
973
  /// the given map and a constant value (i.e. it shifts the map with
974
  /// the constant). Its \c Key and \c Value are inherited from \c M.
975
  ///
976
  /// Actually,
977
  /// \code
978
  ///   ShiftMap<M> sh(m,v);
979
  /// \endcode
980
  /// is equivalent to
981
  /// \code
982
  ///   ConstMap<M::Key, M::Value> cm(v);
983
  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
984
  /// \endcode
985
  ///
986
  /// The simplest way of using this map is through the shiftMap()
987
  /// function.
988
  ///
989
  /// \sa ShiftWriteMap
990
  template<typename M, typename C = typename M::Value>
991
  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
992
    const M &_m;
993
    C _v;
489 994
  public:
490 995
    typedef MapBase<typename M::Key, typename M::Value> Parent;
491 996
    typedef typename Parent::Key Key;
492 997
    typedef typename Parent::Value Value;
493 998

	
494
    ///Constructor
495
    SimpleWriteMap(M &_m) : m(_m) {};
496
    ///\e
497
    Value operator[](Key k) const {return m[k];}
498
    ///\e
499
    void set(Key k, const Value& c) { m.set(k, c); }
999
    /// Constructor
1000

	
1001
    /// Constructor.
1002
    /// \param m The undelying map.
1003
    /// \param v The constant value.
1004
    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1005
    /// \e
1006
    Value operator[](const Key &k) const { return _m[k]+_v; }
500 1007
  };
501 1008

	
502
  ///Returns a \c SimpleWriteMap class
1009
  /// Shifts a map with a constant (read-write version).
503 1010

	
504
  ///This function just returns a \c SimpleWriteMap class.
505
  ///\relates SimpleWriteMap
506
  template<typename M>
507
  inline SimpleWriteMap<M> simpleWriteMap(M &m) {
508
    return SimpleWriteMap<M>(m);
509
  }
510

	
511
  ///Sum of two maps
512

	
513
  ///This \ref concepts::ReadMap "read only map" returns the sum of the two
514
  ///given maps.
515
  ///Its \c Key and \c Value are inherited from \c M1.
516
  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
517
  template<typename M1, typename M2> 
518
  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
519
    const M1& m1;
520
    const M2& m2;
521

	
522
  public:
523
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
524
    typedef typename Parent::Key Key;
525
    typedef typename Parent::Value Value;
526

	
527
    ///Constructor
528
    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
529
    ///\e
530
    Value operator[](Key k) const {return m1[k]+m2[k];}
531
  };
532
  
533
  ///Returns an \c AddMap class
534

	
535
  ///This function just returns an \c AddMap class.
536
  ///\todo Extend the documentation: how to call these type of functions?
1011
  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1012
  /// of the given map and a constant value (i.e. it shifts the map with
1013
  /// the constant). Its \c Key and \c Value are inherited from \c M.
1014
  /// It makes also possible to write the map.
537 1015
  ///
538
  ///\relates AddMap
539
  template<typename M1, typename M2> 
540
  inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
541
    return AddMap<M1, M2>(m1,m2);
542
  }
543

	
544
  ///Shift a map with a constant.
545

	
546
  ///This \ref concepts::ReadMap "read only map" returns the sum of the
547
  ///given map and a constant value.
548
  ///Its \c Key and \c Value are inherited from \c M.
1016
  /// The simplest way of using this map is through the shiftWriteMap()
1017
  /// function.
549 1018
  ///
550
  ///Actually,
551
  ///\code
552
  ///  ShiftMap<X> sh(x,v);
553
  ///\endcode
554
  ///is equivalent to
555
  ///\code
556
  ///  ConstMap<X::Key, X::Value> c_tmp(v);
557
  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
558
  ///\endcode
559
  ///
560
  ///\sa ShiftWriteMap
561
  template<typename M, typename C = typename M::Value> 
562
  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
563
    const M& m;
564
    C v;
1019
  /// \sa ShiftMap
1020
  template<typename M, typename C = typename M::Value>
1021
  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1022
    M &_m;
1023
    C _v;
565 1024
  public:
566 1025
    typedef MapBase<typename M::Key, typename M::Value> Parent;
567 1026
    typedef typename Parent::Key Key;
568 1027
    typedef typename Parent::Value Value;
569 1028

	
570
    ///Constructor
1029
    /// Constructor
571 1030

	
572
    ///Constructor.
573
    ///\param _m is the undelying map.
574
    ///\param _v is the shift value.
575
    ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
576
    ///\e
577
    Value operator[](Key k) const {return m[k] + v;}
1031
    /// Constructor.
1032
    /// \param m The undelying map.
1033
    /// \param v The constant value.
1034
    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1035
    /// \e
1036
    Value operator[](const Key &k) const { return _m[k]+_v; }
1037
    /// \e
1038
    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
578 1039
  };
579 1040

	
580
  ///Shift a map with a constant (ReadWrite version).
1041
  /// Returns a \ref ShiftMap class
581 1042

	
582
  ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
583
  ///given map and a constant value. It makes also possible to write the map.
584
  ///Its \c Key and \c Value are inherited from \c M.
1043
  /// This function just returns a \ref ShiftMap class.
585 1044
  ///
586
  ///\sa ShiftMap
587
  template<typename M, typename C = typename M::Value> 
588
  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
589
    M& m;
590
    C v;
1045
  /// For example, if \c m is a map with \c double values and \c v is
1046
  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1047
  /// <tt>m[x]+v</tt>.
1048
  ///
1049
  /// \relates ShiftMap
1050
  template<typename M, typename C>
1051
  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1052
    return ShiftMap<M, C>(m,v);
1053
  }
1054

	
1055
  /// Returns a \ref ShiftWriteMap class
1056

	
1057
  /// This function just returns a \ref ShiftWriteMap class.
1058
  ///
1059
  /// For example, if \c m is a map with \c double values and \c v is
1060
  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1061
  /// <tt>m[x]+v</tt>.
1062
  /// Moreover it makes also possible to write the map.
1063
  ///
1064
  /// \relates ShiftWriteMap
1065
  template<typename M, typename C>
1066
  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1067
    return ShiftWriteMap<M, C>(m,v);
1068
  }
1069

	
1070

	
1071
  /// Scales a map with a constant.
1072

	
1073
  /// This \ref concepts::ReadMap "read-only map" returns the value of
1074
  /// the given map multiplied from the left side with a constant value.
1075
  /// Its \c Key and \c Value are inherited from \c M.
1076
  ///
1077
  /// Actually,
1078
  /// \code
1079
  ///   ScaleMap<M> sc(m,v);
1080
  /// \endcode
1081
  /// is equivalent to
1082
  /// \code
1083
  ///   ConstMap<M::Key, M::Value> cm(v);
1084
  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1085
  /// \endcode
1086
  ///
1087
  /// The simplest way of using this map is through the scaleMap()
1088
  /// function.
1089
  ///
1090
  /// \sa ScaleWriteMap
1091
  template<typename M, typename C = typename M::Value>
1092
  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1093
    const M &_m;
1094
    C _v;
591 1095
  public:
592 1096
    typedef MapBase<typename M::Key, typename M::Value> Parent;
593 1097
    typedef typename Parent::Key Key;
594 1098
    typedef typename Parent::Value Value;
595 1099

	
596
    ///Constructor
1100
    /// Constructor
597 1101

	
598
    ///Constructor.
599
    ///\param _m is the undelying map.
600
    ///\param _v is the shift value.
601
    ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1102
    /// Constructor.
1103
    /// \param m The undelying map.
1104
    /// \param v The constant value.
1105
    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
602 1106
    /// \e
603
    Value operator[](Key k) const {return m[k] + v;}
604
    /// \e
605
    void set(Key k, const Value& c) { m.set(k, c - v); }
1107
    Value operator[](const Key &k) const { return _v*_m[k]; }
606 1108
  };
607
  
608
  ///Returns a \c ShiftMap class
609 1109

	
610
  ///This function just returns a \c ShiftMap class.
611
  ///\relates ShiftMap
612
  template<typename M, typename C> 
613
  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
614
    return ShiftMap<M, C>(m,v);
615
  }
1110
  /// Scales a map with a constant (read-write version).
616 1111

	
617
  ///Returns a \c ShiftWriteMap class
618

	
619
  ///This function just returns a \c ShiftWriteMap class.
620
  ///\relates ShiftWriteMap
621
  template<typename M, typename C> 
622
  inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
623
    return ShiftWriteMap<M, C>(m,v);
624
  }
625

	
626
  ///Difference of two maps
627

	
628
  ///This \ref concepts::ReadMap "read only map" returns the difference
629
  ///of the values of the two given maps.
630
  ///Its \c Key and \c Value are inherited from \c M1.
631
  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1112
  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1113
  /// the given map multiplied from the left side with a constant value.
1114
  /// Its \c Key and \c Value are inherited from \c M.
1115
  /// It can also be used as write map if the \c / operator is defined
1116
  /// between \c Value and \c C and the given multiplier is not zero.
632 1117
  ///
633
  /// \todo Revise the misleading name
634
  template<typename M1, typename M2> 
635
  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
636
    const M1& m1;
637
    const M2& m2;
638
  public:
639
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
640
    typedef typename Parent::Key Key;
641
    typedef typename Parent::Value Value;
642

	
643
    ///Constructor
644
    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
645
    /// \e
646
    Value operator[](Key k) const {return m1[k]-m2[k];}
647
  };
648
  
649
  ///Returns a \c SubMap class
650

	
651
  ///This function just returns a \c SubMap class.
1118
  /// The simplest way of using this map is through the scaleWriteMap()
1119
  /// function.
652 1120
  ///
653
  ///\relates SubMap
654
  template<typename M1, typename M2> 
655
  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
656
    return SubMap<M1, M2>(m1, m2);
657
  }
658

	
659
  ///Product of two maps
660

	
661
  ///This \ref concepts::ReadMap "read only map" returns the product of the
662
  ///values of the two given maps.
663
  ///Its \c Key and \c Value are inherited from \c M1.
664
  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
665
  template<typename M1, typename M2> 
666
  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
667
    const M1& m1;
668
    const M2& m2;
669
  public:
670
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
671
    typedef typename Parent::Key Key;
672
    typedef typename Parent::Value Value;
673

	
674
    ///Constructor
675
    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
676
    /// \e
677
    Value operator[](Key k) const {return m1[k]*m2[k];}
678
  };
679
  
680
  ///Returns a \c MulMap class
681

	
682
  ///This function just returns a \c MulMap class.
683
  ///\relates MulMap
684
  template<typename M1, typename M2> 
685
  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
686
    return MulMap<M1, M2>(m1,m2);
687
  }
688
 
689
  ///Scales a map with a constant.
690

	
691
  ///This \ref concepts::ReadMap "read only map" returns the value of the
692
  ///given map multiplied from the left side with a constant value.
693
  ///Its \c Key and \c Value are inherited from \c M.
694
  ///
695
  ///Actually,
696
  ///\code
697
  ///  ScaleMap<X> sc(x,v);
698
  ///\endcode
699
  ///is equivalent to
700
  ///\code
701
  ///  ConstMap<X::Key, X::Value> c_tmp(v);
702
  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
703
  ///\endcode
704
  ///
705
  ///\sa ScaleWriteMap
706
  template<typename M, typename C = typename M::Value> 
707
  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
708
    const M& m;
709
    C v;
1121
  /// \sa ScaleMap
1122
  template<typename M, typename C = typename M::Value>
1123
  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1124
    M &_m;
1125
    C _v;
710 1126
  public:
711 1127
    typedef MapBase<typename M::Key, typename M::Value> Parent;
712 1128
    typedef typename Parent::Key Key;
713 1129
    typedef typename Parent::Value Value;
714 1130

	
715
    ///Constructor
1131
    /// Constructor
716 1132

	
717
    ///Constructor.
718
    ///\param _m is the undelying map.
719
    ///\param _v is the scaling value.
720
    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
1133
    /// Constructor.
1134
    /// \param m The undelying map.
1135
    /// \param v The constant value.
1136
    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
721 1137
    /// \e
722
    Value operator[](Key k) const {return v * m[k];}
1138
    Value operator[](const Key &k) const { return _v*_m[k]; }
1139
    /// \e
1140
    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
723 1141
  };
724 1142

	
725
  ///Scales a map with a constant (ReadWrite version).
1143
  /// Returns a \ref ScaleMap class
726 1144

	
727
  ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
728
  ///given map multiplied from the left side with a constant value. It can
729
  ///also be used as write map if the \c / operator is defined between
730
  ///\c Value and \c C and the given multiplier is not zero.
731
  ///Its \c Key and \c Value are inherited from \c M.
1145
  /// This function just returns a \ref ScaleMap class.
732 1146
  ///
733
  ///\sa ScaleMap
734
  template<typename M, typename C = typename M::Value> 
735
  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
736
    M& m;
737
    C v;
1147
  /// For example, if \c m is a map with \c double values and \c v is
1148
  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1149
  /// <tt>v*m[x]</tt>.
1150
  ///
1151
  /// \relates ScaleMap
1152
  template<typename M, typename C>
1153
  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1154
    return ScaleMap<M, C>(m,v);
1155
  }
1156

	
1157
  /// Returns a \ref ScaleWriteMap class
1158

	
1159
  /// This function just returns a \ref ScaleWriteMap class.
1160
  ///
1161
  /// For example, if \c m is a map with \c double values and \c v is
1162
  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1163
  /// <tt>v*m[x]</tt>.
1164
  /// Moreover it makes also possible to write the map.
1165
  ///
1166
  /// \relates ScaleWriteMap
1167
  template<typename M, typename C>
1168
  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1169
    return ScaleWriteMap<M, C>(m,v);
1170
  }
1171

	
1172

	
1173
  /// Negative of a map
1174

	
1175
  /// This \ref concepts::ReadMap "read-only map" returns the negative
1176
  /// of the values of the given map (using the unary \c - operator).
1177
  /// Its \c Key and \c Value are inherited from \c M.
1178
  ///
1179
  /// If M::Value is \c int, \c double etc., then
1180
  /// \code
1181
  ///   NegMap<M> neg(m);
1182
  /// \endcode
1183
  /// is equivalent to
1184
  /// \code
1185
  ///   ScaleMap<M> neg(m,-1);
1186
  /// \endcode
1187
  ///
1188
  /// The simplest way of using this map is through the negMap()
1189
  /// function.
1190
  ///
1191
  /// \sa NegWriteMap
1192
  template<typename M>
1193
  class NegMap : public MapBase<typename M::Key, typename M::Value> {
1194
    const M& _m;
738 1195
  public:
739 1196
    typedef MapBase<typename M::Key, typename M::Value> Parent;
740 1197
    typedef typename Parent::Key Key;
741 1198
    typedef typename Parent::Value Value;
742 1199

	
743
    ///Constructor
744

	
745
    ///Constructor.
746
    ///\param _m is the undelying map.
747
    ///\param _v is the scaling value.
748
    ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1200
    /// Constructor
1201
    NegMap(const M &m) : _m(m) {}
749 1202
    /// \e
750
    Value operator[](Key k) const {return v * m[k];}
751
    /// \e
752
    void set(Key k, const Value& c) { m.set(k, c / v);}
753
  };
754
  
755
  ///Returns a \c ScaleMap class
756

	
757
  ///This function just returns a \c ScaleMap class.
758
  ///\relates ScaleMap
759
  template<typename M, typename C> 
760
  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
761
    return ScaleMap<M, C>(m,v);
762
  }
763

	
764
  ///Returns a \c ScaleWriteMap class
765

	
766
  ///This function just returns a \c ScaleWriteMap class.
767
  ///\relates ScaleWriteMap
768
  template<typename M, typename C> 
769
  inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
770
    return ScaleWriteMap<M, C>(m,v);
771
  }
772

	
773
  ///Quotient of two maps
774

	
775
  ///This \ref concepts::ReadMap "read only map" returns the quotient of the
776
  ///values of the two given maps.
777
  ///Its \c Key and \c Value are inherited from \c M1.
778
  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
779
  template<typename M1, typename M2> 
780
  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
781
    const M1& m1;
782
    const M2& m2;
783
  public:
784
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
785
    typedef typename Parent::Key Key;
786
    typedef typename Parent::Value Value;
787

	
788
    ///Constructor
789
    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
790
    /// \e
791
    Value operator[](Key k) const {return m1[k]/m2[k];}
792
  };
793
  
794
  ///Returns a \c DivMap class
795

	
796
  ///This function just returns a \c DivMap class.
797
  ///\relates DivMap
798
  template<typename M1, typename M2> 
799
  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
800
    return DivMap<M1, M2>(m1,m2);
801
  }
802
  
803
  ///Composition of two maps
804

	
805
  ///This \ref concepts::ReadMap "read only map" returns the composition of
806
  ///two given maps.
807
  ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
808
  ///then for
809
  ///\code
810
  ///  ComposeMap<M1, M2> cm(m1,m2);
811
  ///\endcode
812
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
813
  ///
814
  ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
815
  ///\c M2::Value must be convertible to \c M1::Key.
816
  ///
817
  ///\sa CombineMap
818
  ///
819
  ///\todo Check the requirements.
820
  template <typename M1, typename M2> 
821
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
822
    const M1& m1;
823
    const M2& m2;
824
  public:
825
    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
826
    typedef typename Parent::Key Key;
827
    typedef typename Parent::Value Value;
828

	
829
    ///Constructor
830
    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
831
    
832
    /// \e
833

	
834

	
835
    /// \todo Use the  MapTraits once it is ported.
836
    ///
837

	
838
    //typename MapTraits<M1>::ConstReturnValue
839
    typename M1::Value
840
    operator[](Key k) const {return m1[m2[k]];}
1203
    Value operator[](const Key &k) const { return -_m[k]; }
841 1204
  };
842 1205

	
843
  ///Returns a \c ComposeMap class
1206
  /// Negative of a map (read-write version)
844 1207

	
845
  ///This function just returns a \c ComposeMap class.
846
  ///\relates ComposeMap
847
  template <typename M1, typename M2> 
848
  inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
849
    return ComposeMap<M1, M2>(m1,m2);
850
  }
851
  
852
  ///Combine of two maps using an STL (binary) functor.
853

	
854
  ///Combine of two maps using an STL (binary) functor.
1208
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1209
  /// negative of the values of the given map (using the unary \c -
1210
  /// operator).
1211
  /// Its \c Key and \c Value are inherited from \c M.
1212
  /// It makes also possible to write the map.
855 1213
  ///
856
  ///This \ref concepts::ReadMap "read only map" takes two maps and a
857
  ///binary functor and returns the composition of the two
858
  ///given maps unsing the functor. 
859
  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
860
  ///and \c f is of \c F, then for
861
  ///\code
862
  ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
863
  ///\endcode
864
  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
1214
  /// If M::Value is \c int, \c double etc., then
1215
  /// \code
1216
  ///   NegWriteMap<M> neg(m);
1217
  /// \endcode
1218
  /// is equivalent to
1219
  /// \code
1220
  ///   ScaleWriteMap<M> neg(m,-1);
1221
  /// \endcode
865 1222
  ///
866
  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
867
  ///\c M2::Value and \c M1::Value must be convertible to the corresponding
868
  ///input parameter of \c F and the return type of \c F must be convertible
869
  ///to \c V.
1223
  /// The simplest way of using this map is through the negWriteMap()
1224
  /// function.
870 1225
  ///
871
  ///\sa ComposeMap
872
  ///
873
  ///\todo Check the requirements.
874
  template<typename M1, typename M2, typename F,
875
	   typename V = typename F::result_type> 
876
  class CombineMap : public MapBase<typename M1::Key, V> {
877
    const M1& m1;
878
    const M2& m2;
879
    F f;
880
  public:
881
    typedef MapBase<typename M1::Key, V> Parent;
882
    typedef typename Parent::Key Key;
883
    typedef typename Parent::Value Value;
884

	
885
    ///Constructor
886
    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
887
      : m1(_m1), m2(_m2), f(_f) {};
888
    /// \e
889
    Value operator[](Key k) const {return f(m1[k],m2[k]);}
890
  };
891
  
892
  ///Returns a \c CombineMap class
893

	
894
  ///This function just returns a \c CombineMap class.
895
  ///
896
  ///For example if \c m1 and \c m2 are both \c double valued maps, then 
897
  ///\code
898
  ///combineMap(m1,m2,std::plus<double>())
899
  ///\endcode
900
  ///is equivalent to
901
  ///\code
902
  ///addMap(m1,m2)
903
  ///\endcode
904
  ///
905
  ///This function is specialized for adaptable binary function
906
  ///classes and C++ functions.
907
  ///
908
  ///\relates CombineMap
909
  template<typename M1, typename M2, typename F, typename V> 
910
  inline CombineMap<M1, M2, F, V> 
911
  combineMap(const M1& m1,const M2& m2, const F& f) {
912
    return CombineMap<M1, M2, F, V>(m1,m2,f);
913
  }
914

	
915
  template<typename M1, typename M2, typename F> 
916
  inline CombineMap<M1, M2, F, typename F::result_type> 
917
  combineMap(const M1& m1, const M2& m2, const F& f) {
918
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
919
  }
920

	
921
  template<typename M1, typename M2, typename K1, typename K2, typename V> 
922
  inline CombineMap<M1, M2, V (*)(K1, K2), V> 
923
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
924
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
925
  }
926

	
927
  ///Negative value of a map
928

	
929
  ///This \ref concepts::ReadMap "read only map" returns the negative
930
  ///value of the value returned by the given map.
931
  ///Its \c Key and \c Value are inherited from \c M.
932
  ///The unary \c - operator must be defined for \c Value, of course.
933
  ///
934
  ///\sa NegWriteMap
935
  template<typename M> 
936
  class NegMap : public MapBase<typename M::Key, typename M::Value> {
937
    const M& m;
1226
  /// \sa NegMap
1227
  template<typename M>
1228
  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1229
    M &_m;
938 1230
  public:
939 1231
    typedef MapBase<typename M::Key, typename M::Value> Parent;
940 1232
    typedef typename Parent::Key Key;
941 1233
    typedef typename Parent::Value Value;
942 1234

	
943
    ///Constructor
944
    NegMap(const M &_m) : m(_m) {};
1235
    /// Constructor
1236
    NegWriteMap(M &m) : _m(m) {}
945 1237
    /// \e
946
    Value operator[](Key k) const {return -m[k];}
1238
    Value operator[](const Key &k) const { return -_m[k]; }
1239
    /// \e
1240
    void set(const Key &k, const Value &v) { _m.set(k, -v); }
947 1241
  };
948
  
949
  ///Negative value of a map (ReadWrite version)
950 1242

	
951
  ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
952
  ///value of the value returned by the given map.
953
  ///Its \c Key and \c Value are inherited from \c M.
954
  ///The unary \c - operator must be defined for \c Value, of course.
1243
  /// Returns a \ref NegMap class
1244

	
1245
  /// This function just returns a \ref NegMap class.
955 1246
  ///
956
  /// \sa NegMap
957
  template<typename M> 
958
  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
959
    M& m;
1247
  /// For example, if \c m is a map with \c double values, then
1248
  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1249
  ///
1250
  /// \relates NegMap
1251
  template <typename M>
1252
  inline NegMap<M> negMap(const M &m) {
1253
    return NegMap<M>(m);
1254
  }
1255

	
1256
  /// Returns a \ref NegWriteMap class
1257

	
1258
  /// This function just returns a \ref NegWriteMap class.
1259
  ///
1260
  /// For example, if \c m is a map with \c double values, then
1261
  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1262
  /// Moreover it makes also possible to write the map.
1263
  ///
1264
  /// \relates NegWriteMap
1265
  template <typename M>
1266
  inline NegWriteMap<M> negWriteMap(M &m) {
1267
    return NegWriteMap<M>(m);
1268
  }
1269

	
1270

	
1271
  /// Absolute value of a map
1272

	
1273
  /// This \ref concepts::ReadMap "read-only map" returns the absolute
1274
  /// value of the values of the given map.
1275
  /// Its \c Key and \c Value are inherited from \c M.
1276
  /// \c Value must be comparable to \c 0 and the unary \c -
1277
  /// operator must be defined for it, of course.
1278
  ///
1279
  /// The simplest way of using this map is through the absMap()
1280
  /// function.
1281
  template<typename M>
1282
  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1283
    const M &_m;
960 1284
  public:
961 1285
    typedef MapBase<typename M::Key, typename M::Value> Parent;
962 1286
    typedef typename Parent::Key Key;
963 1287
    typedef typename Parent::Value Value;
964 1288

	
965
    ///Constructor
966
    NegWriteMap(M &_m) : m(_m) {};
1289
    /// Constructor
1290
    AbsMap(const M &m) : _m(m) {}
967 1291
    /// \e
968
    Value operator[](Key k) const {return -m[k];}
969
    /// \e
970
    void set(Key k, const Value& v) { m.set(k, -v); }
971
  };
972

	
973
  ///Returns a \c NegMap class
974

	
975
  ///This function just returns a \c NegMap class.
976
  ///\relates NegMap
977
  template <typename M> 
978
  inline NegMap<M> negMap(const M &m) {
979
    return NegMap<M>(m);
980
  }
981

	
982
  ///Returns a \c NegWriteMap class
983

	
984
  ///This function just returns a \c NegWriteMap class.
985
  ///\relates NegWriteMap
986
  template <typename M> 
987
  inline NegWriteMap<M> negMap(M &m) {
988
    return NegWriteMap<M>(m);
989
  }
990

	
991
  ///Absolute value of a map
992

	
993
  ///This \ref concepts::ReadMap "read only map" returns the absolute value
994
  ///of the value returned by the given map.
995
  ///Its \c Key and \c Value are inherited from \c M. 
996
  ///\c Value must be comparable to \c 0 and the unary \c -
997
  ///operator must be defined for it, of course.
998
  template<typename M> 
999
  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1000
    const M& m;
1001
  public:
1002
    typedef MapBase<typename M::Key, typename M::Value> Parent;
1003
    typedef typename Parent::Key Key;
1004
    typedef typename Parent::Value Value;
1005

	
1006
    ///Constructor
1007
    AbsMap(const M &_m) : m(_m) {};
1008
    /// \e
1009
    Value operator[](Key k) const {
1010
      Value tmp = m[k]; 
1292
    Value operator[](const Key &k) const {
1293
      Value tmp = _m[k];
1011 1294
      return tmp >= 0 ? tmp : -tmp;
1012 1295
    }
1013 1296

	
1014 1297
  };
1015
  
1016
  ///Returns an \c AbsMap class
1017 1298

	
1018
  ///This function just returns an \c AbsMap class.
1019
  ///\relates AbsMap
1020
  template<typename M> 
1299
  /// Returns an \ref AbsMap class
1300

	
1301
  /// This function just returns an \ref AbsMap class.
1302
  ///
1303
  /// For example, if \c m is a map with \c double values, then
1304
  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1305
  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1306
  /// negative.
1307
  ///
1308
  /// \relates AbsMap
1309
  template<typename M>
1021 1310
  inline AbsMap<M> absMap(const M &m) {
1022 1311
    return AbsMap<M>(m);
1023 1312
  }
1024 1313

	
1025
  ///Converts an STL style functor to a map
1314
  /// @}
1315
  
1316
  // Logical maps and map adaptors:
1026 1317

	
1027
  ///This \ref concepts::ReadMap "read only map" returns the value
1028
  ///of a given functor.
1318
  /// \addtogroup maps
1319
  /// @{
1320

	
1321
  /// Constant \c true map.
1322

	
1323
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1324
  /// each key.
1029 1325
  ///
1030
  ///Template parameters \c K and \c V will become its
1031
  ///\c Key and \c Value. 
1032
  ///In most cases they have to be given explicitly because a 
1033
  ///functor typically does not provide \c argument_type and 
1034
  ///\c result_type typedefs.
1326
  /// Note that
1327
  /// \code
1328
  ///   TrueMap<K> tm;
1329
  /// \endcode
1330
  /// is equivalent to
1331
  /// \code
1332
  ///   ConstMap<K,bool> tm(true);
1333
  /// \endcode
1035 1334
  ///
1036
  ///Parameter \c F is the type of the used functor.
1037
  ///
1038
  ///\sa MapFunctor
1039
  template<typename F, 
1040
	   typename K = typename F::argument_type, 
1041
	   typename V = typename F::result_type> 
1042
  class FunctorMap : public MapBase<K, V> {
1043
    F f;
1335
  /// \sa FalseMap
1336
  /// \sa ConstMap
1337
  template <typename K>
1338
  class TrueMap : public MapBase<K, bool> {
1044 1339
  public:
1045
    typedef MapBase<K, V> Parent;
1340
    typedef MapBase<K, bool> Parent;
1046 1341
    typedef typename Parent::Key Key;
1047 1342
    typedef typename Parent::Value Value;
1048 1343

	
1049
    ///Constructor
1050
    FunctorMap(const F &_f = F()) : f(_f) {}
1051
    /// \e
1052
    Value operator[](Key k) const { return f(k);}
1344
    /// Gives back \c true.
1345
    Value operator[](const Key&) const { return true; }
1053 1346
  };
1054
  
1055
  ///Returns a \c FunctorMap class
1056 1347

	
1057
  ///This function just returns a \c FunctorMap class.
1058
  ///
1059
  ///This function is specialized for adaptable binary function
1060
  ///classes and C++ functions.
1061
  ///
1062
  ///\relates FunctorMap
1063
  template<typename K, typename V, typename F> inline 
1064
  FunctorMap<F, K, V> functorMap(const F &f) {
1065
    return FunctorMap<F, K, V>(f);
1348
  /// Returns a \ref TrueMap class
1349

	
1350
  /// This function just returns a \ref TrueMap class.
1351
  /// \relates TrueMap
1352
  template<typename K>
1353
  inline TrueMap<K> trueMap() {
1354
    return TrueMap<K>();
1066 1355
  }
1067 1356

	
1068
  template <typename F> inline 
1069
  FunctorMap<F, typename F::argument_type, typename F::result_type> 
1070
  functorMap(const F &f) {
1071
    return FunctorMap<F, typename F::argument_type, 
1072
      typename F::result_type>(f);
1073
  }
1074 1357

	
1075
  template <typename K, typename V> inline 
1076
  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1077
    return FunctorMap<V (*)(K), K, V>(f);
1078
  }
1358
  /// Constant \c false map.
1079 1359

	
1080

	
1081
  ///Converts a map to an STL style (unary) functor
1082

	
1083
  ///This class Converts a map to an STL style (unary) functor.
1084
  ///That is it provides an <tt>operator()</tt> to read its values.
1360
  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1361
  /// each key.
1085 1362
  ///
1086
  ///For the sake of convenience it also works as
1087
  ///a ususal \ref concepts::ReadMap "readable map",
1088
  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1363
  /// Note that
1364
  /// \code
1365
  ///   FalseMap<K> fm;
1366
  /// \endcode
1367
  /// is equivalent to
1368
  /// \code
1369
  ///   ConstMap<K,bool> fm(false);
1370
  /// \endcode
1089 1371
  ///
1090
  ///\sa FunctorMap
1091
  template <typename M> 
1092
  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1093
    const M& m;
1372
  /// \sa TrueMap
1373
  /// \sa ConstMap
1374
  template <typename K>
1375
  class FalseMap : public MapBase<K, bool> {
1094 1376
  public:
1095
    typedef MapBase<typename M::Key, typename M::Value> Parent;
1377
    typedef MapBase<K, bool> Parent;
1096 1378
    typedef typename Parent::Key Key;
1097 1379
    typedef typename Parent::Value Value;
1098 1380

	
1099
    typedef typename M::Key argument_type;
1100
    typedef typename M::Value result_type;
1381
    /// Gives back \c false.
1382
    Value operator[](const Key&) const { return false; }
1383
  };
1101 1384

	
1102
    ///Constructor
1103
    MapFunctor(const M &_m) : m(_m) {};
1104
    ///\e
1105
    Value operator()(Key k) const {return m[k];}
1106
    ///\e
1107
    Value operator[](Key k) const {return m[k];}
1108
  };
1109
  
1110
  ///Returns a \c MapFunctor class
1385
  /// Returns a \ref FalseMap class
1111 1386

	
1112
  ///This function just returns a \c MapFunctor class.
1113
  ///\relates MapFunctor
1114
  template<typename M> 
1115
  inline MapFunctor<M> mapFunctor(const M &m) {
1116
    return MapFunctor<M>(m);
1387
  /// This function just returns a \ref FalseMap class.
1388
  /// \relates FalseMap
1389
  template<typename K>
1390
  inline FalseMap<K> falseMap() {
1391
    return FalseMap<K>();
1117 1392
  }
1118 1393

	
1119
  ///Just readable version of \ref ForkWriteMap
1394
  /// @}
1120 1395

	
1121
  ///This map has two \ref concepts::ReadMap "readable map"
1122
  ///parameters and each read request will be passed just to the
1123
  ///first map. This class is the just readable map type of \c ForkWriteMap.
1396
  /// \addtogroup map_adaptors
1397
  /// @{
1398

	
1399
  /// Logical 'and' of two maps
1400

	
1401
  /// This \ref concepts::ReadMap "read-only map" returns the logical
1402
  /// 'and' of the values of the two given maps.
1403
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1404
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1124 1405
  ///
1125
  ///The \c Key and \c Value are inherited from \c M1.
1126
  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1406
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1407
  /// \code
1408
  ///   AndMap<M1,M2> am(m1,m2);
1409
  /// \endcode
1410
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1127 1411
  ///
1128
  ///\sa ForkWriteMap
1412
  /// The simplest way of using this map is through the andMap()
1413
  /// function.
1129 1414
  ///
1130
  /// \todo Why is it needed?
1131
  template<typename  M1, typename M2> 
1132
  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1133
    const M1& m1;
1134
    const M2& m2;
1415
  /// \sa OrMap
1416
  /// \sa NotMap, NotWriteMap
1417
  template<typename M1, typename M2>
1418
  class AndMap : public MapBase<typename M1::Key, bool> {
1419
    const M1 &_m1;
1420
    const M2 &_m2;
1135 1421
  public:
1136
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1422
    typedef MapBase<typename M1::Key, bool> Parent;
1137 1423
    typedef typename Parent::Key Key;
1138 1424
    typedef typename Parent::Value Value;
1139 1425

	
1140
    ///Constructor
1141
    ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1426
    /// Constructor
1427
    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1142 1428
    /// \e
1143
    Value operator[](Key k) const {return m1[k];}
1429
    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1144 1430
  };
1145 1431

	
1432
  /// Returns an \ref AndMap class
1146 1433

	
1147
  ///Applies all map setting operations to two maps
1434
  /// This function just returns an \ref AndMap class.
1435
  ///
1436
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1437
  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1438
  /// <tt>m1[x]&&m2[x]</tt>.
1439
  ///
1440
  /// \relates AndMap
1441
  template<typename M1, typename M2>
1442
  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1443
    return AndMap<M1, M2>(m1,m2);
1444
  }
1148 1445

	
1149
  ///This map has two \ref concepts::WriteMap "writable map"
1150
  ///parameters and each write request will be passed to both of them.
1151
  ///If \c M1 is also \ref concepts::ReadMap "readable",
1152
  ///then the read operations will return the
1153
  ///corresponding values of \c M1.
1446

	
1447
  /// Logical 'or' of two maps
1448

	
1449
  /// This \ref concepts::ReadMap "read-only map" returns the logical
1450
  /// 'or' of the values of the two given maps.
1451
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1452
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1154 1453
  ///
1155
  ///The \c Key and \c Value are inherited from \c M1.
1156
  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1454
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1455
  /// \code
1456
  ///   OrMap<M1,M2> om(m1,m2);
1457
  /// \endcode
1458
  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1157 1459
  ///
1158
  ///\sa ForkMap
1159
  template<typename  M1, typename M2> 
1160
  class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1161
    M1& m1;
1162
    M2& m2;
1460
  /// The simplest way of using this map is through the orMap()
1461
  /// function.
1462
  ///
1463
  /// \sa AndMap
1464
  /// \sa NotMap, NotWriteMap
1465
  template<typename M1, typename M2>
1466
  class OrMap : public MapBase<typename M1::Key, bool> {
1467
    const M1 &_m1;
1468
    const M2 &_m2;
1163 1469
  public:
1164
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1470
    typedef MapBase<typename M1::Key, bool> Parent;
1165 1471
    typedef typename Parent::Key Key;
1166 1472
    typedef typename Parent::Value Value;
1167 1473

	
1168
    ///Constructor
1169
    ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1170
    ///\e
1171
    Value operator[](Key k) const {return m1[k];}
1172
    ///\e
1173
    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1474
    /// Constructor
1475
    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1476
    /// \e
1477
    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1174 1478
  };
1175
  
1176
  ///Returns a \c ForkMap class
1177 1479

	
1178
  ///This function just returns a \c ForkMap class.
1179
  ///\relates ForkMap
1180
  template <typename M1, typename M2> 
1181
  inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1182
    return ForkMap<M1, M2>(m1,m2);
1480
  /// Returns an \ref OrMap class
1481

	
1482
  /// This function just returns an \ref OrMap class.
1483
  ///
1484
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1485
  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1486
  /// <tt>m1[x]||m2[x]</tt>.
1487
  ///
1488
  /// \relates OrMap
1489
  template<typename M1, typename M2>
1490
  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1491
    return OrMap<M1, M2>(m1,m2);
1183 1492
  }
1184 1493

	
1185
  ///Returns a \c ForkWriteMap class
1186 1494

	
1187
  ///This function just returns a \c ForkWriteMap class.
1188
  ///\relates ForkWriteMap
1189
  template <typename M1, typename M2> 
1190
  inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1191
    return ForkWriteMap<M1, M2>(m1,m2);
1192
  }
1495
  /// Logical 'not' of a map
1193 1496

	
1194

	
1195
  
1196
  /* ************* BOOL MAPS ******************* */
1197
  
1198
  ///Logical 'not' of a map
1199
  
1200
  ///This bool \ref concepts::ReadMap "read only map" returns the 
1201
  ///logical negation of the value returned by the given map.
1202
  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1497
  /// This \ref concepts::ReadMap "read-only map" returns the logical
1498
  /// negation of the values of the given map.
1499
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1203 1500
  ///
1204
  ///\sa NotWriteMap
1205
  template <typename M> 
1501
  /// The simplest way of using this map is through the notMap()
1502
  /// function.
1503
  ///
1504
  /// \sa NotWriteMap
1505
  template <typename M>
1206 1506
  class NotMap : public MapBase<typename M::Key, bool> {
1207
    const M& m;
1507
    const M &_m;
1208 1508
  public:
1209 1509
    typedef MapBase<typename M::Key, bool> Parent;
1210 1510
    typedef typename Parent::Key Key;
1211 1511
    typedef typename Parent::Value Value;
1212 1512

	
1213 1513
    /// Constructor
1214
    NotMap(const M &_m) : m(_m) {};
1215
    ///\e
1216
    Value operator[](Key k) const {return !m[k];}
1514
    NotMap(const M &m) : _m(m) {}
1515
    /// \e
1516
    Value operator[](const Key &k) const { return !_m[k]; }
1217 1517
  };
1218 1518

	
1219
  ///Logical 'not' of a map (ReadWrie version)
1220
  
1221
  ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 
1222
  ///logical negation of the value returned by the given map. When it is set,
1223
  ///the opposite value is set to the original map.
1224
  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1519
  /// Logical 'not' of a map (read-write version)
1520

	
1521
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1522
  /// logical negation of the values of the given map.
1523
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1524
  /// It makes also possible to write the map. When a value is set,
1525
  /// the opposite value is set to the original map.
1225 1526
  ///
1226
  ///\sa NotMap
1227
  template <typename M> 
1527
  /// The simplest way of using this map is through the notWriteMap()
1528
  /// function.
1529
  ///
1530
  /// \sa NotMap
1531
  template <typename M>
1228 1532
  class NotWriteMap : public MapBase<typename M::Key, bool> {
1229
    M& m;
1533
    M &_m;
1230 1534
  public:
1231 1535
    typedef MapBase<typename M::Key, bool> Parent;
1232 1536
    typedef typename Parent::Key Key;
1233 1537
    typedef typename Parent::Value Value;
1234 1538

	
1235 1539
    /// Constructor
1236
    NotWriteMap(M &_m) : m(_m) {};
1237
    ///\e
1238
    Value operator[](Key k) const {return !m[k];}
1239
    ///\e
1240
    void set(Key k, bool v) { m.set(k, !v); }
1540
    NotWriteMap(M &m) : _m(m) {}
1541
    /// \e
1542
    Value operator[](const Key &k) const { return !_m[k]; }
1543
    /// \e
1544
    void set(const Key &k, bool v) { _m.set(k, !v); }
1241 1545
  };
1242
  
1243
  ///Returns a \c NotMap class
1244
  
1245
  ///This function just returns a \c NotMap class.
1246
  ///\relates NotMap
1247
  template <typename M> 
1546

	
1547
  /// Returns a \ref NotMap class
1548

	
1549
  /// This function just returns a \ref NotMap class.
1550
  ///
1551
  /// For example, if \c m is a map with \c bool values, then
1552
  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1553
  ///
1554
  /// \relates NotMap
1555
  template <typename M>
1248 1556
  inline NotMap<M> notMap(const M &m) {
1249 1557
    return NotMap<M>(m);
1250 1558
  }
1251
  
1252
  ///Returns a \c NotWriteMap class
1253
  
1254
  ///This function just returns a \c NotWriteMap class.
1255
  ///\relates NotWriteMap
1256
  template <typename M> 
1257
  inline NotWriteMap<M> notMap(M &m) {
1559

	
1560
  /// Returns a \ref NotWriteMap class
1561

	
1562
  /// This function just returns a \ref NotWriteMap class.
1563
  ///
1564
  /// For example, if \c m is a map with \c bool values, then
1565
  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1566
  /// Moreover it makes also possible to write the map.
1567
  ///
1568
  /// \relates NotWriteMap
1569
  template <typename M>
1570
  inline NotWriteMap<M> notWriteMap(M &m) {
1258 1571
    return NotWriteMap<M>(m);
1259 1572
  }
1260 1573

	
1261
  namespace _maps_bits {
1262 1574

	
1263
    template <typename Value>
1264
    struct Identity {
1265
      typedef Value argument_type;
1266
      typedef Value result_type;
1267
      Value operator()(const Value& val) const {
1268
	return val;
1269
      }
1270
    };
1575
  /// Combination of two maps using the \c == operator
1271 1576

	
1272
    template <typename _Iterator, typename Enable = void>
1273
    struct IteratorTraits {
1274
      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1275
    };
1276

	
1277
    template <typename _Iterator>
1278
    struct IteratorTraits<_Iterator,
1279
      typename exists<typename _Iterator::container_type>::type> 
1280
    {
1281
      typedef typename _Iterator::container_type::value_type Value;
1282
    };
1283

	
1284
  }
1285
  
1286

	
1287
  /// \brief Writable bool map for logging each \c true assigned element
1577
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1578
  /// the keys for which the corresponding values of the two maps are
1579
  /// equal.
1580
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1581
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1288 1582
  ///
1289
  /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 
1290
  /// each \c true assigned element, i.e it copies all the keys set 
1291
  /// to \c true to the given iterator.
1583
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1584
  /// \code
1585
  ///   EqualMap<M1,M2> em(m1,m2);
1586
  /// \endcode
1587
  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1292 1588
  ///
1293
  /// \note The container of the iterator should contain space 
1294
  /// for each element.
1589
  /// The simplest way of using this map is through the equalMap()
1590
  /// function.
1295 1591
  ///
1296
  /// The following example shows how you can write the edges found by 
1297
  /// the \ref Prim algorithm directly to the standard output.
1298
  ///\code
1299
  /// typedef IdMap<Graph, Edge> EdgeIdMap;
1300
  /// EdgeIdMap edgeId(graph);
1301
  ///
1302
  /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1303
  /// EdgeIdFunctor edgeIdFunctor(edgeId);
1304
  ///
1305
  /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> 
1306
  ///   writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1307
  ///
1308
  /// prim(graph, cost, writerMap);
1309
  ///\endcode
1310
  ///
1311
  ///\sa BackInserterBoolMap 
1312
  ///\sa FrontInserterBoolMap 
1313
  ///\sa InserterBoolMap 
1314
  ///
1315
  ///\todo Revise the name of this class and the related ones.
1316
  template <typename _Iterator, 
1317
            typename _Functor =
1318
            _maps_bits::Identity<typename _maps_bits::
1319
                                 IteratorTraits<_Iterator>::Value> >
1320
  class StoreBoolMap {
1592
  /// \sa LessMap
1593
  template<typename M1, typename M2>
1594
  class EqualMap : public MapBase<typename M1::Key, bool> {
1595
    const M1 &_m1;
1596
    const M2 &_m2;
1321 1597
  public:
1322
    typedef _Iterator Iterator;
1323

	
1324
    typedef typename _Functor::argument_type Key;
1325
    typedef bool Value;
1326

	
1327
    typedef _Functor Functor;
1598
    typedef MapBase<typename M1::Key, bool> Parent;
1599
    typedef typename Parent::Key Key;
1600
    typedef typename Parent::Value Value;
1328 1601

	
1329 1602
    /// Constructor
1330
    StoreBoolMap(Iterator it, const Functor& functor = Functor()) 
1331
      : _begin(it), _end(it), _functor(functor) {}
1332

	
1333
    /// Gives back the given iterator set for the first key
1334
    Iterator begin() const {
1335
      return _begin;
1336
    }
1337
 
1338
    /// Gives back the the 'after the last' iterator
1339
    Iterator end() const {
1340
      return _end;
1341
    }
1342

	
1343
    /// The \c set function of the map
1344
    void set(const Key& key, Value value) const {
1345
      if (value) {
1346
	*_end++ = _functor(key);
1347
      }
1348
    }
1349
    
1350
  private:
1351
    Iterator _begin;
1352
    mutable Iterator _end;
1353
    Functor _functor;
1603
    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1604
    /// \e
1605
    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1354 1606
  };
1355 1607

	
1356
  /// \brief Writable bool map for logging each \c true assigned element in 
1357
  /// a back insertable container.
1608
  /// Returns an \ref EqualMap class
1609

	
1610
  /// This function just returns an \ref EqualMap class.
1358 1611
  ///
1359
  /// Writable bool map for logging each \c true assigned element by pushing
1360
  /// them into a back insertable container.
1361
  /// It can be used to retrieve the items into a standard
1362
  /// container. The next example shows how you can store the
1363
  /// edges found by the Prim algorithm in a vector.
1612
  /// For example, if \c m1 and \c m2 are maps with keys and values of
1613
  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1614
  /// <tt>m1[x]==m2[x]</tt>.
1364 1615
  ///
1365
  ///\code
1366
  /// vector<Edge> span_tree_edges;
1367
  /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1368
  /// prim(graph, cost, inserter_map);
1369
  ///\endcode
1616
  /// \relates EqualMap
1617
  template<typename M1, typename M2>
1618
  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1619
    return EqualMap<M1, M2>(m1,m2);
1620
  }
1621

	
1622

	
1623
  /// Combination of two maps using the \c < operator
1624

	
1625
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1626
  /// the keys for which the corresponding value of the first map is
1627
  /// less then the value of the second map.
1628
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1629
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1370 1630
  ///
1371
  ///\sa StoreBoolMap
1372
  ///\sa FrontInserterBoolMap
1373
  ///\sa InserterBoolMap
1374
  template <typename Container,
1375
            typename Functor =
1376
            _maps_bits::Identity<typename Container::value_type> >
1377
  class BackInserterBoolMap {
1631
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1632
  /// \code
1633
  ///   LessMap<M1,M2> lm(m1,m2);
1634
  /// \endcode
1635
  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1636
  ///
1637
  /// The simplest way of using this map is through the lessMap()
1638
  /// function.
1639
  ///
1640
  /// \sa EqualMap
1641
  template<typename M1, typename M2>
1642
  class LessMap : public MapBase<typename M1::Key, bool> {
1643
    const M1 &_m1;
1644
    const M2 &_m2;
1378 1645
  public:
1379
    typedef typename Functor::argument_type Key;
1380
    typedef bool Value;
1646
    typedef MapBase<typename M1::Key, bool> Parent;
1647
    typedef typename Parent::Key Key;
1648
    typedef typename Parent::Value Value;
1381 1649

	
1382 1650
    /// Constructor
1383
    BackInserterBoolMap(Container& _container, 
1384
                        const Functor& _functor = Functor()) 
1385
      : container(_container), functor(_functor) {}
1386

	
1387
    /// The \c set function of the map
1388
    void set(const Key& key, Value value) {
1389
      if (value) {
1390
	container.push_back(functor(key));
1391
      }
1392
    }
1393
    
1394
  private:
1395
    Container& container;
1396
    Functor functor;
1651
    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1652
    /// \e
1653
    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1397 1654
  };
1398 1655

	
1399
  /// \brief Writable bool map for logging each \c true assigned element in 
1400
  /// a front insertable container.
1656
  /// Returns an \ref LessMap class
1657

	
1658
  /// This function just returns an \ref LessMap class.
1401 1659
  ///
1402
  /// Writable bool map for logging each \c true assigned element by pushing
1403
  /// them into a front insertable container.
1404
  /// It can be used to retrieve the items into a standard
1405
  /// container. For example see \ref BackInserterBoolMap.
1660
  /// For example, if \c m1 and \c m2 are maps with keys and values of
1661
  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1662
  /// <tt>m1[x]<m2[x]</tt>.
1406 1663
  ///
1407
  ///\sa BackInserterBoolMap
1408
  ///\sa InserterBoolMap
1409
  template <typename Container,
1410
            typename Functor =
1411
            _maps_bits::Identity<typename Container::value_type> >
1412
  class FrontInserterBoolMap {
1413
  public:
1414
    typedef typename Functor::argument_type Key;
1415
    typedef bool Value;
1416

	
1417
    /// Constructor
1418
    FrontInserterBoolMap(Container& _container,
1419
                         const Functor& _functor = Functor()) 
1420
      : container(_container), functor(_functor) {}
1421

	
1422
    /// The \c set function of the map
1423
    void set(const Key& key, Value value) {
1424
      if (value) {
1425
	container.push_front(functor(key));
1426
      }
1427
    }
1428
    
1429
  private:
1430
    Container& container;    
1431
    Functor functor;
1432
  };
1433

	
1434
  /// \brief Writable bool map for storing each \c true assigned element in 
1435
  /// an insertable container.
1436
  ///
1437
  /// Writable bool map for storing each \c true assigned element in an 
1438
  /// insertable container. It will insert all the keys set to \c true into
1439
  /// the container.
1440
  ///
1441
  /// For example, if you want to store the cut arcs of the strongly
1442
  /// connected components in a set you can use the next code:
1443
  ///
1444
  ///\code
1445
  /// set<Arc> cut_arcs;
1446
  /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1447
  /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1448
  ///\endcode
1449
  ///
1450
  ///\sa BackInserterBoolMap
1451
  ///\sa FrontInserterBoolMap
1452
  template <typename Container,
1453
            typename Functor =
1454
            _maps_bits::Identity<typename Container::value_type> >
1455
  class InserterBoolMap {
1456
  public:
1457
    typedef typename Container::value_type Key;
1458
    typedef bool Value;
1459

	
1460
    /// Constructor with specified iterator
1461
    
1462
    /// Constructor with specified iterator.
1463
    /// \param _container The container for storing the elements.
1464
    /// \param _it The elements will be inserted before this iterator.
1465
    /// \param _functor The functor that is used when an element is stored.
1466
    InserterBoolMap(Container& _container, typename Container::iterator _it,
1467
                    const Functor& _functor = Functor()) 
1468
      : container(_container), it(_it), functor(_functor) {}
1469

	
1470
    /// Constructor
1471

	
1472
    /// Constructor without specified iterator.
1473
    /// The elements will be inserted before <tt>_container.end()</tt>.
1474
    /// \param _container The container for storing the elements.
1475
    /// \param _functor The functor that is used when an element is stored.
1476
    InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1477
      : container(_container), it(_container.end()), functor(_functor) {}
1478

	
1479
    /// The \c set function of the map
1480
    void set(const Key& key, Value value) {
1481
      if (value) {
1482
	it = container.insert(it, functor(key));
1483
        ++it;
1484
      }
1485
    }
1486
    
1487
  private:
1488
    Container& container;
1489
    typename Container::iterator it;
1490
    Functor functor;
1491
  };
1492

	
1493
  /// \brief Writable bool map for filling each \c true assigned element with a 
1494
  /// given value.
1495
  ///
1496
  /// Writable bool map for filling each \c true assigned element with a 
1497
  /// given value. The value can set the container.
1498
  ///
1499
  /// The following code finds the connected components of a graph
1500
  /// and stores it in the \c comp map:
1501
  ///\code
1502
  /// typedef Graph::NodeMap<int> ComponentMap;
1503
  /// ComponentMap comp(graph);
1504
  /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1505
  /// ComponentFillerMap filler(comp, 0);
1506
  ///
1507
  /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1508
  /// dfs.processedMap(filler);
1509
  /// dfs.init();
1510
  /// for (NodeIt it(graph); it != INVALID; ++it) {
1511
  ///   if (!dfs.reached(it)) {
1512
  ///     dfs.addSource(it);
1513
  ///     dfs.start();
1514
  ///     ++filler.fillValue();
1515
  ///   }
1516
  /// }
1517
  ///\endcode
1518
  template <typename Map>
1519
  class FillBoolMap {
1520
  public:
1521
    typedef typename Map::Key Key;
1522
    typedef bool Value;
1523

	
1524
    /// Constructor
1525
    FillBoolMap(Map& _map, const typename Map::Value& _fill) 
1526
      : map(_map), fill(_fill) {}
1527

	
1528
    /// Constructor
1529
    FillBoolMap(Map& _map) 
1530
      : map(_map), fill() {}
1531

	
1532
    /// Gives back the current fill value
1533
    const typename Map::Value& fillValue() const {
1534
      return fill;
1535
    } 
1536

	
1537
    /// Gives back the current fill value
1538
    typename Map::Value& fillValue() {
1539
      return fill;
1540
    } 
1541

	
1542
    /// Sets the current fill value
1543
    void fillValue(const typename Map::Value& _fill) {
1544
      fill = _fill;
1545
    } 
1546

	
1547
    /// The \c set function of the map
1548
    void set(const Key& key, Value value) {
1549
      if (value) {
1550
	map.set(key, fill);
1551
      }
1552
    }
1553
    
1554
  private:
1555
    Map& map;
1556
    typename Map::Value fill;
1557
  };
1558

	
1559

	
1560
  /// \brief Writable bool map for storing the sequence number of 
1561
  /// \c true assignments.  
1562
  /// 
1563
  /// Writable bool map that stores for each \c true assigned elements  
1564
  /// the sequence number of this setting.
1565
  /// It makes it easy to calculate the leaving
1566
  /// order of the nodes in the \c Dfs algorithm.
1567
  ///
1568
  ///\code
1569
  /// typedef Digraph::NodeMap<int> OrderMap;
1570
  /// OrderMap order(digraph);
1571
  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1572
  /// OrderSetterMap setter(order);
1573
  /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1574
  /// dfs.processedMap(setter);
1575
  /// dfs.init();
1576
  /// for (NodeIt it(digraph); it != INVALID; ++it) {
1577
  ///   if (!dfs.reached(it)) {
1578
  ///     dfs.addSource(it);
1579
  ///     dfs.start();
1580
  ///   }
1581
  /// }
1582
  ///\endcode
1583
  ///
1584
  /// The storing of the discovering order is more difficult because the
1585
  /// ReachedMap should be readable in the dfs algorithm but the setting
1586
  /// order map is not readable. Thus we must use the fork map:
1587
  ///
1588
  ///\code
1589
  /// typedef Digraph::NodeMap<int> OrderMap;
1590
  /// OrderMap order(digraph);
1591
  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1592
  /// OrderSetterMap setter(order);
1593
  /// typedef Digraph::NodeMap<bool> StoreMap;
1594
  /// StoreMap store(digraph);
1595
  ///
1596
  /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1597
  /// ReachedMap reached(store, setter);
1598
  ///
1599
  /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1600
  /// dfs.reachedMap(reached);
1601
  /// dfs.init();
1602
  /// for (NodeIt it(digraph); it != INVALID; ++it) {
1603
  ///   if (!dfs.reached(it)) {
1604
  ///     dfs.addSource(it);
1605
  ///     dfs.start();
1606
  ///   }
1607
  /// }
1608
  ///\endcode
1609
  template <typename Map>
1610
  class SettingOrderBoolMap {
1611
  public:
1612
    typedef typename Map::Key Key;
1613
    typedef bool Value;
1614

	
1615
    /// Constructor
1616
    SettingOrderBoolMap(Map& _map) 
1617
      : map(_map), counter(0) {}
1618

	
1619
    /// Number of set operations.
1620
    int num() const {
1621
      return counter;
1622
    }
1623

	
1624
    /// The \c set function of the map
1625
    void set(const Key& key, Value value) {
1626
      if (value) {
1627
	map.set(key, counter++);
1628
      }
1629
    }
1630
    
1631
  private:
1632
    Map& map;
1633
    int counter;
1634
  };
1664
  /// \relates LessMap
1665
  template<typename M1, typename M2>
1666
  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1667
    return LessMap<M1, M2>(m1,m2);
1668
  }
1635 1669

	
1636 1670
  /// @}
1637 1671
}
1638 1672

	
1639 1673
#endif // LEMON_MAPS_H
Ignore white space 6 line context
1 1
/* -*- C++ -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#include <deque>
20 20
#include <set>
21 21

	
22 22
#include <lemon/concept_check.h>
23 23
#include <lemon/concepts/maps.h>
24 24
#include <lemon/maps.h>
25 25

	
26 26
#include "test_tools.h"
27 27

	
28 28
using namespace lemon;
29 29
using namespace lemon::concepts;
30 30

	
31 31
struct A {};
32 32
inline bool operator<(A, A) { return true; }
33 33
struct B {};
34 34

	
35 35
class F {
36 36
public:
37 37
  typedef A argument_type;
38 38
  typedef B result_type;
39 39

	
40
  B operator()(const A &) const {return B();}
40
  B operator()(const A&) const { return B(); }
41
private:
42
  F& operator=(const F&);
41 43
};
42 44

	
43
int func(A) {return 3;}
45
int func(A) { return 3; }
44 46

	
45
int binc(int, B) {return 4;}
47
int binc(int a, B) { return a+1; }
46 48

	
47
typedef ReadMap<A,double> DoubleMap;
48
typedef ReadWriteMap<A, double> WriteDoubleMap;
49
typedef ReadMap<A, double> DoubleMap;
50
typedef ReadWriteMap<A, double> DoubleWriteMap;
51
typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
49 52

	
50
typedef ReadMap<A,bool> BoolMap;
53
typedef ReadMap<A, bool> BoolMap;
51 54
typedef ReadWriteMap<A, bool> BoolWriteMap;
55
typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
52 56

	
53 57
int main()
54
{ // checking graph components
55
  
58
{
59
  // Map concepts
56 60
  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
57 61
  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
58 62
  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
59 63
  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
60 64

	
61
  checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
62
  checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
63
  checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
64
  checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
65
  checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
66
  checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
67
  checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
68
  checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
69
  checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
70
  checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
71
  checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
72
  checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
73
  checkConcept<ReadWriteMap<A,double>, 
74
    ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
75
  
76
  checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
65
  // NullMap
66
  {
67
    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
68
    NullMap<A,B> map1;
69
    NullMap<A,B> map2 = map1;
70
    map1 = nullMap<A,B>();
71
  }
77 72

	
78
  checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
73
  // ConstMap
74
  {
75
    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
76
    ConstMap<A,B> map1;
77
    ConstMap<A,B> map2(B());
78
    ConstMap<A,B> map3 = map1;
79
    map1 = constMap<A>(B());
80
    map1.setAll(B());
79 81

	
80
  checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
81
  checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
82
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
83
    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
82 84

	
83
  checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
84
  checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
85
  checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
86
  checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
87
  checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
88
  checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
85
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
86
    ConstMap<A,Const<int,10> > map4;
87
    ConstMap<A,Const<int,10> > map5 = map4;
88
    map4 = map5;
89
    check(map4[A()] == 10 && map5[A()] == 10, "Something is wrong with ConstMap");
90
  }
89 91

	
90
  int a;
91
  
92
  a=mapFunctor(constMap<A,int>(2))(A());
93
  check(a==2,"Something is wrong with mapFunctor");
92
  // IdentityMap
93
  {
94
    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
95
    IdentityMap<A> map1;
96
    IdentityMap<A> map2 = map1;
97
    map1 = identityMap<A>();
94 98

	
95
  B b;
96
  b=functorMap(F())[A()];
99
    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
100
    check(identityMap<double>()[1.0] == 1.0 && identityMap<double>()[3.14] == 3.14,
101
          "Something is wrong with IdentityMap");
102
  }
97 103

	
98
  a=functorMap(&func)[A()];
99
  check(a==3,"Something is wrong with functorMap");
104
  // RangeMap
105
  {
106
    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
107
    RangeMap<B> map1;
108
    RangeMap<B> map2(10);
109
    RangeMap<B> map3(10,B());
110
    RangeMap<B> map4 = map1;
111
    RangeMap<B> map5 = rangeMap<B>();
112
    RangeMap<B> map6 = rangeMap<B>(10);
113
    RangeMap<B> map7 = rangeMap(10,B());
100 114

	
101
  a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
102
  check(a==4,"Something is wrong with combineMap");
103
  
115
    checkConcept< ReferenceMap<int, double, double&, const double&>,
116
                  RangeMap<double> >();
117
    std::vector<double> v(10, 0);
118
    v[5] = 100;
119
    RangeMap<double> map8(v);
120
    RangeMap<double> map9 = rangeMap(v);
121
    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
122
          "Something is wrong with RangeMap");
123
  }
104 124

	
105
  std::cout << __FILE__ ": All tests passed.\n";
106
  
125
  // SparseMap
126
  {
127
    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
128
    SparseMap<A,B> map1;
129
    SparseMap<A,B> map2(B());
130
    SparseMap<A,B> map3 = sparseMap<A,B>();
131
    SparseMap<A,B> map4 = sparseMap<A>(B());
132

	
133
    checkConcept< ReferenceMap<double, int, int&, const int&>,
134
                  SparseMap<double, int> >();
135
    std::map<double, int> m;
136
    SparseMap<double, int> map5(m);
137
    SparseMap<double, int> map6(m,10);
138
    SparseMap<double, int> map7 = sparseMap(m);
139
    SparseMap<double, int> map8 = sparseMap(m,10);
140

	
141
    check(map5[1.0] == 0 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 10,
142
          "Something is wrong with SparseMap");
143
    map5[1.0] = map6[3.14] = 100;
144
    check(map5[1.0] == 100 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 100,
145
          "Something is wrong with SparseMap");
146
  }
147

	
148
  // ComposeMap
149
  {
150
    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
151
    checkConcept<ReadMap<B,double>, CompMap>();
152
    CompMap map1(DoubleMap(),ReadMap<B,A>());
153
    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
154

	
155
    SparseMap<double, bool> m1(false); m1[3.14] = true;
156
    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
157
    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1], "Something is wrong with ComposeMap")
158
  }
159

	
160
  // CombineMap
161
  {
162
    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
163
    checkConcept<ReadMap<A,double>, CombMap>();
164
    CombMap map1(DoubleMap(), DoubleMap());
165
    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
166

	
167
    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
168
          "Something is wrong with CombineMap");
169
  }
170

	
171
  // FunctorToMap, MapToFunctor
172
  {
173
    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
174
    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
175
    FunctorToMap<F> map1;
176
    FunctorToMap<F> map2(F());
177
    B b = functorToMap(F())[A()];
178

	
179
    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
180
    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
181

	
182
    check(functorToMap(&func)[A()] == 3, "Something is wrong with FunctorToMap");
183
    check(mapToFunctor(constMap<A,int>(2))(A()) == 2, "Something is wrong with MapToFunctor");
184
    check(mapToFunctor(functorToMap(&func))(A()) == 3 && mapToFunctor(functorToMap(&func))[A()] == 3,
185
          "Something is wrong with FunctorToMap or MapToFunctor");
186
    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,
187
          "Something is wrong with FunctorToMap or MapToFunctor");
188
  }
189

	
190
  // ConvertMap
191
  {
192
    checkConcept<ReadMap<double,double>, ConvertMap<ReadMap<double, int>, double> >();
193
    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
194
    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
195
  }
196

	
197
  // ForkMap
198
  {
199
    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
200

	
201
    typedef RangeMap<double> RM;
202
    typedef SparseMap<int, double> SM;
203
    RM m1(10, -1);
204
    SM m2(-1);
205
    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();
206
    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();
207
    ForkMap<RM, SM> map1(m1,m2);
208
    ForkMap<SM, RM> map2 = forkMap(m2,m1);
209
    map2.set(5, 10);
210
    check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 && m2[5] == 10 && map2[1] == -1 && map2[5] == 10,
211
          "Something is wrong with ForkMap");
212
  }
213

	
214
  // Arithmetic maps:
215
  // - AddMap, SubMap, MulMap, DivMap
216
  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap
217
  // - NegMap, NegWriteMap, AbsMap
218
  {
219
    checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();
220
    checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();
221
    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
222
    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
223

	
224
    ConstMap<int, double> c1(1.0), c2(3.14);
225
    IdentityMap<int> im;
226
    ConvertMap<IdentityMap<int>, double> id(im);
227
    check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0, "Something is wrong with AddMap");
228
    check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,  "Something is wrong with SubMap");
229
    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28, "Something is wrong with MulMap");
230
    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57, "Something is wrong with DivMap");
231

	
232
    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
233
    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
234
    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();
235
    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();
236
    checkConcept<DoubleMap, NegMap<DoubleMap> >();
237
    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();
238
    checkConcept<DoubleMap, AbsMap<DoubleMap> >();
239

	
240
    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,
241
          "Something is wrong with ShiftMap");
242
    check(shiftWriteMap(id, 2.0)[1] == 3.0 && shiftWriteMap(id, 2.0)[10] == 12.0,
243
          "Something is wrong with ShiftWriteMap");
244
    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,
245
          "Something is wrong with ScaleMap");
246
    check(scaleWriteMap(id, 2.0)[1] == 2.0 && scaleWriteMap(id, 2.0)[10] == 20.0,
247
          "Something is wrong with ScaleWriteMap");
248
    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,
249
          "Something is wrong with NegMap");
250
    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,
251
          "Something is wrong with NegWriteMap");
252
    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,
253
          "Something is wrong with AbsMap");
254
  }
255

	
256
  // Logical maps:
257
  // - TrueMap, FalseMap
258
  // - AndMap, OrMap
259
  // - NotMap, NotWriteMap
260
  // - EqualMap, LessMap
261
  {
262
    checkConcept<BoolMap, TrueMap<A> >();
263
    checkConcept<BoolMap, FalseMap<A> >();
264
    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
265
    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
266
    checkConcept<BoolMap, NotMap<BoolMap> >();
267
    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
268
    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
269
    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
270

	
271
    TrueMap<int> tm;
272
    FalseMap<int> fm;
273
    RangeMap<bool> rm(2);
274
    rm[0] = true; rm[1] = false;
275
    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] && !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
276
          "Something is wrong with AndMap");
277
    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] && orMap(fm,rm)[0] && !orMap(fm,rm)[1],
278
          "Something is wrong with OrMap");
279
    check(!notMap(rm)[0] && notMap(rm)[1], "Something is wrong with NotMap");
280
    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1], "Something is wrong with NotWriteMap");
281

	
282
    ConstMap<int, double> cm(2.0);
283
    IdentityMap<int> im;
284
    ConvertMap<IdentityMap<int>, double> id(im);
285
    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
286
          "Something is wrong with LessMap");
287
    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
288
          "Something is wrong with EqualMap");
289
  }
290

	
107 291
  return 0;
108 292
}
0 comments (0 inline)