lemon-1.0: lemon/maps.h@112ed801139d (annotated)

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
alpar@25	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
alpar@25	4	*
alpar@39	5	* Copyright (C) 2003-2008
alpar@25	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25	8	*
alpar@25	9	* Permission to use, modify and distribute this software is granted
alpar@25	10	* provided that this copyright notice appears in all copies. For
alpar@25	11	* precise terms see the accompanying LICENSE file.
alpar@25	12	*
alpar@25	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@25	14	* express or implied, and with no claim as to its suitability for any
alpar@25	15	* purpose.
alpar@25	16	*
alpar@25	17	*/
alpar@25	18
alpar@25	19	#ifndef LEMON_MAPS_H
alpar@25	20	#define LEMON_MAPS_H
alpar@25	21
alpar@25	22	#include <iterator>
alpar@25	23	#include <functional>
alpar@25	24	#include <vector>
alpar@25	25
deba@220	26	#include <lemon/core.h>
alpar@25	27
alpar@25	28	///\file
alpar@25	29	///\ingroup maps
alpar@25	30	///\brief Miscellaneous property maps
kpeter@80	31
alpar@25	32	#include <map>
alpar@25	33
alpar@25	34	namespace lemon {
alpar@25	35
alpar@25	36	/// \addtogroup maps
alpar@25	37	/// @{
alpar@25	38
alpar@25	39	/// Base class of maps.
alpar@25	40
kpeter@80	41	/// Base class of maps. It provides the necessary type definitions
kpeter@80	42	/// required by the map %concepts.
kpeter@80	43	template<typename K, typename V>
alpar@25	44	class MapBase {
alpar@25	45	public:
kpeter@80	46	/// \biref The key type of the map.
alpar@25	47	typedef K Key;
kpeter@80	48	/// \brief The value type of the map.
kpeter@80	49	/// (The type of objects associated with the keys).
kpeter@80	50	typedef V Value;
alpar@25	51	};
alpar@25	52
kpeter@80	53
alpar@25	54	/// Null map. (a.k.a. DoNothingMap)
alpar@25	55
kpeter@29	56	/// This map can be used if you have to provide a map only for
kpeter@80	57	/// its type definitions, or if you have to provide a writable map,
kpeter@80	58	/// but data written to it is not required (i.e. it will be sent to
kpeter@29	59	/// <tt>/dev/null</tt>).
kpeter@80	60	/// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80	61	///
kpeter@80	62	/// \sa ConstMap
kpeter@80	63	template<typename K, typename V>
kpeter@80	64	class NullMap : public MapBase<K, V> {
alpar@25	65	public:
kpeter@80	66	typedef MapBase<K, V> Parent;
alpar@25	67	typedef typename Parent::Key Key;
alpar@25	68	typedef typename Parent::Value Value;
kpeter@80	69
alpar@25	70	/// Gives back a default constructed element.
kpeter@80	71	Value operator[](const Key&) const { return Value(); }
alpar@25	72	/// Absorbs the value.
kpeter@80	73	void set(const Key&, const Value&) {}
alpar@25	74	};
alpar@25	75
kpeter@80	76	/// Returns a \ref NullMap class
kpeter@29	77
kpeter@80	78	/// This function just returns a \ref NullMap class.
kpeter@80	79	/// \relates NullMap
kpeter@80	80	template <typename K, typename V>
alpar@25	81	NullMap<K, V> nullMap() {
alpar@25	82	return NullMap<K, V>();
alpar@25	83	}
alpar@25	84
alpar@25	85
alpar@25	86	/// Constant map.
alpar@25	87
kpeter@82	88	/// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82	89	/// value to each key.
kpeter@80	90	///
kpeter@80	91	/// In other aspects it is equivalent to \ref NullMap.
kpeter@80	92	/// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80	93	/// concept, but it absorbs the data written to it.
kpeter@80	94	///
kpeter@80	95	/// The simplest way of using this map is through the constMap()
kpeter@80	96	/// function.
kpeter@80	97	///
kpeter@80	98	/// \sa NullMap
kpeter@80	99	/// \sa IdentityMap
kpeter@80	100	template<typename K, typename V>
kpeter@80	101	class ConstMap : public MapBase<K, V> {
alpar@25	102	private:
kpeter@80	103	V _value;
alpar@25	104	public:
kpeter@80	105	typedef MapBase<K, V> Parent;
alpar@25	106	typedef typename Parent::Key Key;
alpar@25	107	typedef typename Parent::Value Value;
alpar@25	108
alpar@25	109	/// Default constructor
alpar@25	110
kpeter@29	111	/// Default constructor.
kpeter@80	112	/// The value of the map will be default constructed.
alpar@25	113	ConstMap() {}
kpeter@80	114
kpeter@29	115	/// Constructor with specified initial value
alpar@25	116
kpeter@29	117	/// Constructor with specified initial value.
kpeter@123	118	/// \param v The initial value of the map.
kpeter@80	119	ConstMap(const Value &v) : _value(v) {}
alpar@25	120
kpeter@80	121	/// Gives back the specified value.
kpeter@80	122	Value operator[](const Key&) const { return _value; }
alpar@25	123
kpeter@80	124	/// Absorbs the value.
kpeter@80	125	void set(const Key&, const Value&) {}
kpeter@80	126
kpeter@80	127	/// Sets the value that is assigned to each key.
kpeter@80	128	void setAll(const Value &v) {
kpeter@80	129	_value = v;
kpeter@80	130	}
kpeter@80	131
kpeter@80	132	template<typename V1>
kpeter@80	133	ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
alpar@25	134	};
alpar@25	135
kpeter@80	136	/// Returns a \ref ConstMap class
alpar@25	137
kpeter@80	138	/// This function just returns a \ref ConstMap class.
kpeter@80	139	/// \relates ConstMap
kpeter@80	140	template<typename K, typename V>
alpar@25	141	inline ConstMap<K, V> constMap(const V &v) {
alpar@25	142	return ConstMap<K, V>(v);
alpar@25	143	}
alpar@25	144
kpeter@123	145	template<typename K, typename V>
kpeter@123	146	inline ConstMap<K, V> constMap() {
kpeter@123	147	return ConstMap<K, V>();
kpeter@123	148	}
kpeter@123	149
alpar@25	150
alpar@25	151	template<typename T, T v>
kpeter@80	152	struct Const {};
alpar@25	153
alpar@25	154	/// Constant map with inlined constant value.
alpar@25	155
kpeter@82	156	/// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82	157	/// value to each key.
kpeter@80	158	///
kpeter@80	159	/// In other aspects it is equivalent to \ref NullMap.
kpeter@80	160	/// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80	161	/// concept, but it absorbs the data written to it.
kpeter@80	162	///
kpeter@80	163	/// The simplest way of using this map is through the constMap()
kpeter@80	164	/// function.
kpeter@80	165	///
kpeter@80	166	/// \sa NullMap
kpeter@80	167	/// \sa IdentityMap
alpar@25	168	template<typename K, typename V, V v>
alpar@25	169	class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
alpar@25	170	public:
alpar@25	171	typedef MapBase<K, V> Parent;
alpar@25	172	typedef typename Parent::Key Key;
alpar@25	173	typedef typename Parent::Value Value;
alpar@25	174
kpeter@80	175	/// Constructor.
kpeter@80	176	ConstMap() {}
kpeter@80	177
kpeter@80	178	/// Gives back the specified value.
kpeter@80	179	Value operator[](const Key&) const { return v; }
kpeter@80	180
kpeter@80	181	/// Absorbs the value.
kpeter@80	182	void set(const Key&, const Value&) {}
alpar@25	183	};
alpar@25	184
kpeter@80	185	/// Returns a \ref ConstMap class with inlined constant value
alpar@25	186
kpeter@80	187	/// This function just returns a \ref ConstMap class with inlined
kpeter@80	188	/// constant value.
kpeter@80	189	/// \relates ConstMap
kpeter@80	190	template<typename K, typename V, V v>
alpar@25	191	inline ConstMap<K, Const<V, v> > constMap() {
alpar@25	192	return ConstMap<K, Const<V, v> >();
alpar@25	193	}
alpar@25	194
alpar@25	195
kpeter@82	196	/// Identity map.
kpeter@82	197
kpeter@82	198	/// This \ref concepts::ReadMap "read-only map" gives back the given
kpeter@82	199	/// key as value without any modification.
kpeter@80	200	///
kpeter@80	201	/// \sa ConstMap
kpeter@80	202	template <typename T>
kpeter@80	203	class IdentityMap : public MapBase<T, T> {
kpeter@80	204	public:
kpeter@80	205	typedef MapBase<T, T> Parent;
kpeter@80	206	typedef typename Parent::Key Key;
kpeter@80	207	typedef typename Parent::Value Value;
kpeter@80	208
kpeter@80	209	/// Gives back the given value without any modification.
kpeter@82	210	Value operator[](const Key &k) const {
kpeter@82	211	return k;
kpeter@80	212	}
kpeter@80	213	};
kpeter@80	214
kpeter@80	215	/// Returns an \ref IdentityMap class
kpeter@80	216
kpeter@80	217	/// This function just returns an \ref IdentityMap class.
kpeter@80	218	/// \relates IdentityMap
kpeter@80	219	template<typename T>
kpeter@80	220	inline IdentityMap<T> identityMap() {
kpeter@80	221	return IdentityMap<T>();
kpeter@80	222	}
kpeter@80	223
kpeter@80	224
kpeter@80	225	/// \brief Map for storing values for integer keys from the range
kpeter@80	226	/// <tt>[0..size-1]</tt>.
kpeter@80	227	///
kpeter@80	228	/// This map is essentially a wrapper for \c std::vector. It assigns
kpeter@80	229	/// values to integer keys from the range <tt>[0..size-1]</tt>.
kpeter@80	230	/// It can be used with some data structures, for example
kpeter@80	231	/// \ref UnionFind, \ref BinHeap, when the used items are small
kpeter@80	232	/// integers. This map conforms the \ref concepts::ReferenceMap
kpeter@80	233	/// "ReferenceMap" concept.
kpeter@80	234	///
kpeter@80	235	/// The simplest way of using this map is through the rangeMap()
kpeter@80	236	/// function.
kpeter@80	237	template <typename V>
kpeter@80	238	class RangeMap : public MapBase<int, V> {
kpeter@80	239	template <typename V1>
kpeter@80	240	friend class RangeMap;
kpeter@80	241	private:
kpeter@80	242
kpeter@80	243	typedef std::vector<V> Vector;
kpeter@80	244	Vector _vector;
kpeter@80	245
alpar@25	246	public:
alpar@25	247
kpeter@80	248	typedef MapBase<int, V> Parent;
kpeter@80	249	/// Key type
kpeter@45	250	typedef typename Parent::Key Key;
kpeter@80	251	/// Value type
kpeter@45	252	typedef typename Parent::Value Value;
kpeter@80	253	/// Reference type
kpeter@80	254	typedef typename Vector::reference Reference;
kpeter@80	255	/// Const reference type
kpeter@80	256	typedef typename Vector::const_reference ConstReference;
kpeter@80	257
kpeter@80	258	typedef True ReferenceMapTag;
kpeter@80	259
kpeter@80	260	public:
kpeter@80	261
kpeter@80	262	/// Constructor with specified default value.
kpeter@80	263	RangeMap(int size = 0, const Value &value = Value())
kpeter@80	264	: _vector(size, value) {}
kpeter@80	265
kpeter@80	266	/// Constructs the map from an appropriate \c std::vector.
kpeter@80	267	template <typename V1>
kpeter@80	268	RangeMap(const std::vector<V1>& vector)
kpeter@80	269	: _vector(vector.begin(), vector.end()) {}
kpeter@80	270
kpeter@80	271	/// Constructs the map from another \ref RangeMap.
kpeter@80	272	template <typename V1>
kpeter@80	273	RangeMap(const RangeMap<V1> &c)
kpeter@80	274	: _vector(c._vector.begin(), c._vector.end()) {}
kpeter@80	275
kpeter@80	276	/// Returns the size of the map.
kpeter@80	277	int size() {
kpeter@80	278	return _vector.size();
kpeter@80	279	}
kpeter@80	280
kpeter@80	281	/// Resizes the map.
kpeter@80	282
kpeter@80	283	/// Resizes the underlying \c std::vector container, so changes the
kpeter@80	284	/// keyset of the map.
kpeter@80	285	/// \param size The new size of the map. The new keyset will be the
kpeter@80	286	/// range <tt>[0..size-1]</tt>.
kpeter@80	287	/// \param value The default value to assign to the new keys.
kpeter@80	288	void resize(int size, const Value &value = Value()) {
kpeter@80	289	_vector.resize(size, value);
kpeter@80	290	}
kpeter@80	291
kpeter@80	292	private:
kpeter@80	293
kpeter@80	294	RangeMap& operator=(const RangeMap&);
kpeter@80	295
kpeter@80	296	public:
kpeter@80	297
kpeter@80	298	///\e
kpeter@80	299	Reference operator[](const Key &k) {
kpeter@80	300	return _vector[k];
kpeter@80	301	}
kpeter@80	302
kpeter@80	303	///\e
kpeter@80	304	ConstReference operator[](const Key &k) const {
kpeter@80	305	return _vector[k];
kpeter@80	306	}
kpeter@80	307
kpeter@80	308	///\e
kpeter@80	309	void set(const Key &k, const Value &v) {
kpeter@80	310	_vector[k] = v;
kpeter@80	311	}
kpeter@80	312	};
kpeter@80	313
kpeter@80	314	/// Returns a \ref RangeMap class
kpeter@80	315
kpeter@80	316	/// This function just returns a \ref RangeMap class.
kpeter@80	317	/// \relates RangeMap
kpeter@80	318	template<typename V>
kpeter@80	319	inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
kpeter@80	320	return RangeMap<V>(size, value);
kpeter@80	321	}
kpeter@80	322
kpeter@80	323	/// \brief Returns a \ref RangeMap class created from an appropriate
kpeter@80	324	/// \c std::vector
kpeter@80	325
kpeter@80	326	/// This function just returns a \ref RangeMap class created from an
kpeter@80	327	/// appropriate \c std::vector.
kpeter@80	328	/// \relates RangeMap
kpeter@80	329	template<typename V>
kpeter@80	330	inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
kpeter@80	331	return RangeMap<V>(vector);
kpeter@80	332	}
kpeter@80	333
kpeter@80	334
kpeter@80	335	/// Map type based on \c std::map
kpeter@80	336
kpeter@80	337	/// This map is essentially a wrapper for \c std::map with addition
kpeter@80	338	/// that you can specify a default value for the keys that are not
kpeter@80	339	/// stored actually. This value can be different from the default
kpeter@80	340	/// contructed value (i.e. \c %Value()).
kpeter@80	341	/// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
kpeter@80	342	/// concept.
kpeter@80	343	///
kpeter@80	344	/// This map is useful if a default value should be assigned to most of
kpeter@80	345	/// the keys and different values should be assigned only to a few
kpeter@80	346	/// keys (i.e. the map is "sparse").
kpeter@80	347	/// The name of this type also refers to this important usage.
kpeter@80	348	///
kpeter@80	349	/// Apart form that this map can be used in many other cases since it
kpeter@80	350	/// is based on \c std::map, which is a general associative container.
kpeter@80	351	/// However keep in mind that it is usually not as efficient as other
kpeter@80	352	/// maps.
kpeter@80	353	///
kpeter@80	354	/// The simplest way of using this map is through the sparseMap()
kpeter@80	355	/// function.
kpeter@80	356	template <typename K, typename V, typename Compare = std::less<K> >
kpeter@80	357	class SparseMap : public MapBase<K, V> {
kpeter@80	358	template <typename K1, typename V1, typename C1>
kpeter@80	359	friend class SparseMap;
kpeter@80	360	public:
kpeter@80	361
kpeter@80	362	typedef MapBase<K, V> Parent;
kpeter@80	363	/// Key type
kpeter@80	364	typedef typename Parent::Key Key;
kpeter@80	365	/// Value type
kpeter@80	366	typedef typename Parent::Value Value;
kpeter@80	367	/// Reference type
kpeter@80	368	typedef Value& Reference;
kpeter@80	369	/// Const reference type
kpeter@80	370	typedef const Value& ConstReference;
alpar@25	371
kpeter@45	372	typedef True ReferenceMapTag;
kpeter@45	373
alpar@25	374	private:
kpeter@80	375
kpeter@80	376	typedef std::map<K, V, Compare> Map;
kpeter@80	377	Map _map;
alpar@25	378	Value _value;
alpar@25	379
alpar@25	380	public:
alpar@25	381
kpeter@80	382	/// \brief Constructor with specified default value.
kpeter@80	383	SparseMap(const Value &value = Value()) : _value(value) {}
kpeter@80	384	/// \brief Constructs the map from an appropriate \c std::map, and
kpeter@47	385	/// explicitly specifies a default value.
kpeter@80	386	template <typename V1, typename Comp1>
kpeter@80	387	SparseMap(const std::map<Key, V1, Comp1> &map,
kpeter@80	388	const Value &value = Value())
alpar@25	389	: _map(map.begin(), map.end()), _value(value) {}
kpeter@80	390
kpeter@80	391	/// \brief Constructs the map from another \ref SparseMap.
kpeter@80	392	template<typename V1, typename Comp1>
kpeter@80	393	SparseMap(const SparseMap<Key, V1, Comp1> &c)
alpar@25	394	: _map(c._map.begin(), c._map.end()), _value(c._value) {}
alpar@25	395
alpar@25	396	private:
alpar@25	397
kpeter@80	398	SparseMap& operator=(const SparseMap&);
alpar@25	399
alpar@25	400	public:
alpar@25	401
alpar@25	402	///\e
alpar@25	403	Reference operator[](const Key &k) {
alpar@25	404	typename Map::iterator it = _map.lower_bound(k);
alpar@25	405	if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209	406	return it->second;
alpar@25	407	else
alpar@209	408	return _map.insert(it, std::make_pair(k, _value))->second;
alpar@25	409	}
alpar@25	410
kpeter@80	411	///\e
alpar@25	412	ConstReference operator[](const Key &k) const {
alpar@25	413	typename Map::const_iterator it = _map.find(k);
alpar@25	414	if (it != _map.end())
alpar@209	415	return it->second;
alpar@25	416	else
alpar@209	417	return _value;
alpar@25	418	}
alpar@25	419
kpeter@80	420	///\e
kpeter@80	421	void set(const Key &k, const Value &v) {
alpar@25	422	typename Map::iterator it = _map.lower_bound(k);
alpar@25	423	if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209	424	it->second = v;
alpar@25	425	else
alpar@209	426	_map.insert(it, std::make_pair(k, v));
alpar@25	427	}
alpar@25	428
kpeter@80	429	///\e
kpeter@80	430	void setAll(const Value &v) {
kpeter@80	431	_value = v;
alpar@25	432	_map.clear();
kpeter@80	433	}
kpeter@80	434	};
alpar@25	435
kpeter@80	436	/// Returns a \ref SparseMap class
kpeter@45	437
kpeter@80	438	/// This function just returns a \ref SparseMap class with specified
kpeter@80	439	/// default value.
kpeter@80	440	/// \relates SparseMap
kpeter@80	441	template<typename K, typename V, typename Compare>
kpeter@80	442	inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
kpeter@80	443	return SparseMap<K, V, Compare>(value);
kpeter@54	444	}
kpeter@45	445
kpeter@80	446	template<typename K, typename V>
kpeter@80	447	inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
kpeter@80	448	return SparseMap<K, V, std::less<K> >(value);
kpeter@45	449	}
alpar@25	450
kpeter@80	451	/// \brief Returns a \ref SparseMap class created from an appropriate
kpeter@80	452	/// \c std::map
alpar@25	453
kpeter@80	454	/// This function just returns a \ref SparseMap class created from an
kpeter@80	455	/// appropriate \c std::map.
kpeter@80	456	/// \relates SparseMap
kpeter@80	457	template<typename K, typename V, typename Compare>
kpeter@80	458	inline SparseMap<K, V, Compare>
kpeter@80	459	sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
kpeter@80	460	{
kpeter@80	461	return SparseMap<K, V, Compare>(map, value);
kpeter@45	462	}
alpar@25	463
alpar@25	464	/// @}
alpar@25	465
alpar@25	466	/// \addtogroup map_adaptors
alpar@25	467	/// @{
alpar@25	468
kpeter@80	469	/// Composition of two maps
kpeter@80	470
kpeter@82	471	/// This \ref concepts::ReadMap "read-only map" returns the
kpeter@80	472	/// composition of two given maps. That is to say, if \c m1 is of
kpeter@80	473	/// type \c M1 and \c m2 is of \c M2, then for
kpeter@80	474	/// \code
kpeter@80	475	/// ComposeMap<M1, M2> cm(m1,m2);
kpeter@80	476	/// \endcode
kpeter@80	477	/// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
alpar@25	478	///
kpeter@80	479	/// The \c Key type of the map is inherited from \c M2 and the
kpeter@80	480	/// \c Value type is from \c M1.
kpeter@80	481	/// \c M2::Value must be convertible to \c M1::Key.
kpeter@80	482	///
kpeter@80	483	/// The simplest way of using this map is through the composeMap()
kpeter@80	484	/// function.
kpeter@80	485	///
kpeter@80	486	/// \sa CombineMap
kpeter@80	487	///
kpeter@80	488	/// \todo Check the requirements.
kpeter@80	489	template <typename M1, typename M2>
kpeter@80	490	class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
kpeter@80	491	const M1 &_m1;
kpeter@80	492	const M2 &_m2;
alpar@25	493	public:
kpeter@80	494	typedef MapBase<typename M2::Key, typename M1::Value> Parent;
alpar@25	495	typedef typename Parent::Key Key;
alpar@25	496	typedef typename Parent::Value Value;
alpar@25	497
kpeter@80	498	/// Constructor
kpeter@80	499	ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	500
alpar@25	501	/// \e
kpeter@80	502	typename MapTraits<M1>::ConstReturnValue
kpeter@80	503	operator[](const Key &k) const { return _m1[_m2[k]]; }
alpar@25	504	};
alpar@25	505
kpeter@80	506	/// Returns a \ref ComposeMap class
alpar@25	507
kpeter@80	508	/// This function just returns a \ref ComposeMap class.
kpeter@80	509	///
kpeter@80	510	/// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
kpeter@80	511	/// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
kpeter@80	512	/// will be equal to <tt>m1[m2[x]]</tt>.
kpeter@80	513	///
kpeter@80	514	/// \relates ComposeMap
kpeter@80	515	template <typename M1, typename M2>
kpeter@80	516	inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
kpeter@80	517	return ComposeMap<M1, M2>(m1, m2);
alpar@25	518	}
alpar@25	519
kpeter@80	520
kpeter@80	521	/// Combination of two maps using an STL (binary) functor.
kpeter@80	522
kpeter@82	523	/// This \ref concepts::ReadMap "read-only map" takes two maps and a
kpeter@80	524	/// binary functor and returns the combination of the two given maps
kpeter@80	525	/// using the functor.
kpeter@80	526	/// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
kpeter@80	527	/// and \c f is of \c F, then for
kpeter@80	528	/// \code
kpeter@80	529	/// CombineMap<M1,M2,F,V> cm(m1,m2,f);
kpeter@80	530	/// \endcode
kpeter@80	531	/// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
alpar@26	532	///
kpeter@80	533	/// The \c Key type of the map is inherited from \c M1 (\c M1::Key
kpeter@80	534	/// must be convertible to \c M2::Key) and the \c Value type is \c V.
kpeter@80	535	/// \c M2::Value and \c M1::Value must be convertible to the
kpeter@80	536	/// corresponding input parameter of \c F and the return type of \c F
kpeter@80	537	/// must be convertible to \c V.
kpeter@80	538	///
kpeter@80	539	/// The simplest way of using this map is through the combineMap()
kpeter@80	540	/// function.
kpeter@80	541	///
kpeter@80	542	/// \sa ComposeMap
kpeter@80	543	///
kpeter@80	544	/// \todo Check the requirements.
kpeter@80	545	template<typename M1, typename M2, typename F,
alpar@209	546	typename V = typename F::result_type>
kpeter@80	547	class CombineMap : public MapBase<typename M1::Key, V> {
kpeter@80	548	const M1 &_m1;
kpeter@80	549	const M2 &_m2;
kpeter@80	550	F _f;
alpar@25	551	public:
kpeter@80	552	typedef MapBase<typename M1::Key, V> Parent;
alpar@25	553	typedef typename Parent::Key Key;
alpar@25	554	typedef typename Parent::Value Value;
alpar@25	555
kpeter@80	556	/// Constructor
kpeter@80	557	CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
kpeter@80	558	: _m1(m1), _m2(m2), _f(f) {}
kpeter@80	559	/// \e
kpeter@80	560	Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
kpeter@80	561	};
alpar@25	562
kpeter@80	563	/// Returns a \ref CombineMap class
alpar@25	564
kpeter@80	565	/// This function just returns a \ref CombineMap class.
kpeter@80	566	///
kpeter@80	567	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	568	/// values, then
kpeter@80	569	/// \code
kpeter@80	570	/// combineMap(m1,m2,std::plus<double>())
kpeter@80	571	/// \endcode
kpeter@80	572	/// is equivalent to
kpeter@80	573	/// \code
kpeter@80	574	/// addMap(m1,m2)
kpeter@80	575	/// \endcode
kpeter@80	576	///
kpeter@80	577	/// This function is specialized for adaptable binary function
kpeter@80	578	/// classes and C++ functions.
kpeter@80	579	///
kpeter@80	580	/// \relates CombineMap
kpeter@80	581	template<typename M1, typename M2, typename F, typename V>
kpeter@80	582	inline CombineMap<M1, M2, F, V>
kpeter@80	583	combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80	584	return CombineMap<M1, M2, F, V>(m1,m2,f);
alpar@25	585	}
alpar@25	586
kpeter@80	587	template<typename M1, typename M2, typename F>
kpeter@80	588	inline CombineMap<M1, M2, F, typename F::result_type>
kpeter@80	589	combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80	590	return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
kpeter@80	591	}
alpar@25	592
kpeter@80	593	template<typename M1, typename M2, typename K1, typename K2, typename V>
kpeter@80	594	inline CombineMap<M1, M2, V (*)(K1, K2), V>
kpeter@80	595	combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
kpeter@80	596	return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
kpeter@80	597	}
kpeter@80	598
kpeter@80	599
kpeter@80	600	/// Converts an STL style (unary) functor to a map
kpeter@80	601
kpeter@82	602	/// This \ref concepts::ReadMap "read-only map" returns the value
kpeter@80	603	/// of a given functor. Actually, it just wraps the functor and
kpeter@80	604	/// provides the \c Key and \c Value typedefs.
alpar@26	605	///
kpeter@80	606	/// Template parameters \c K and \c V will become its \c Key and
kpeter@80	607	/// \c Value. In most cases they have to be given explicitly because
kpeter@80	608	/// a functor typically does not provide \c argument_type and
kpeter@80	609	/// \c result_type typedefs.
kpeter@80	610	/// Parameter \c F is the type of the used functor.
kpeter@29	611	///
kpeter@80	612	/// The simplest way of using this map is through the functorToMap()
kpeter@80	613	/// function.
kpeter@80	614	///
kpeter@80	615	/// \sa MapToFunctor
kpeter@80	616	template<typename F,
alpar@209	617	typename K = typename F::argument_type,
alpar@209	618	typename V = typename F::result_type>
kpeter@80	619	class FunctorToMap : public MapBase<K, V> {
kpeter@123	620	F _f;
kpeter@80	621	public:
kpeter@80	622	typedef MapBase<K, V> Parent;
kpeter@80	623	typedef typename Parent::Key Key;
kpeter@80	624	typedef typename Parent::Value Value;
alpar@25	625
kpeter@80	626	/// Constructor
kpeter@80	627	FunctorToMap(const F &f = F()) : _f(f) {}
kpeter@80	628	/// \e
kpeter@80	629	Value operator[](const Key &k) const { return _f(k); }
kpeter@80	630	};
kpeter@80	631
kpeter@80	632	/// Returns a \ref FunctorToMap class
kpeter@80	633
kpeter@80	634	/// This function just returns a \ref FunctorToMap class.
kpeter@80	635	///
kpeter@80	636	/// This function is specialized for adaptable binary function
kpeter@80	637	/// classes and C++ functions.
kpeter@80	638	///
kpeter@80	639	/// \relates FunctorToMap
kpeter@80	640	template<typename K, typename V, typename F>
kpeter@80	641	inline FunctorToMap<F, K, V> functorToMap(const F &f) {
kpeter@80	642	return FunctorToMap<F, K, V>(f);
kpeter@80	643	}
kpeter@80	644
kpeter@80	645	template <typename F>
kpeter@80	646	inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
kpeter@80	647	functorToMap(const F &f)
kpeter@80	648	{
kpeter@80	649	return FunctorToMap<F, typename F::argument_type,
kpeter@80	650	typename F::result_type>(f);
kpeter@80	651	}
kpeter@80	652
kpeter@80	653	template <typename K, typename V>
kpeter@80	654	inline FunctorToMap<V ()(K), K, V> functorToMap(V (f)(K)) {
kpeter@80	655	return FunctorToMap<V (*)(K), K, V>(f);
kpeter@80	656	}
kpeter@80	657
kpeter@80	658
kpeter@80	659	/// Converts a map to an STL style (unary) functor
kpeter@80	660
kpeter@80	661	/// This class converts a map to an STL style (unary) functor.
kpeter@80	662	/// That is it provides an <tt>operator()</tt> to read its values.
kpeter@80	663	///
kpeter@80	664	/// For the sake of convenience it also works as a usual
kpeter@80	665	/// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
kpeter@80	666	/// and the \c Key and \c Value typedefs also exist.
kpeter@80	667	///
kpeter@80	668	/// The simplest way of using this map is through the mapToFunctor()
kpeter@80	669	/// function.
kpeter@80	670	///
kpeter@80	671	///\sa FunctorToMap
kpeter@80	672	template <typename M>
kpeter@80	673	class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	674	const M &_m;
alpar@25	675	public:
alpar@25	676	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	677	typedef typename Parent::Key Key;
alpar@25	678	typedef typename Parent::Value Value;
alpar@25	679
kpeter@80	680	typedef typename Parent::Key argument_type;
kpeter@80	681	typedef typename Parent::Value result_type;
kpeter@80	682
kpeter@80	683	/// Constructor
kpeter@80	684	MapToFunctor(const M &m) : _m(m) {}
kpeter@80	685	/// \e
kpeter@80	686	Value operator()(const Key &k) const { return _m[k]; }
kpeter@80	687	/// \e
kpeter@80	688	Value operator[](const Key &k) const { return _m[k]; }
alpar@25	689	};
kpeter@45	690
kpeter@80	691	/// Returns a \ref MapToFunctor class
kpeter@80	692
kpeter@80	693	/// This function just returns a \ref MapToFunctor class.
kpeter@80	694	/// \relates MapToFunctor
kpeter@45	695	template<typename M>
kpeter@80	696	inline MapToFunctor<M> mapToFunctor(const M &m) {
kpeter@80	697	return MapToFunctor<M>(m);
kpeter@45	698	}
alpar@25	699
alpar@25	700
kpeter@80	701	/// \brief Map adaptor to convert the \c Value type of a map to
kpeter@80	702	/// another type using the default conversion.
kpeter@80	703
kpeter@80	704	/// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
kpeter@80	705	/// "readable map" to another type using the default conversion.
kpeter@80	706	/// The \c Key type of it is inherited from \c M and the \c Value
kpeter@80	707	/// type is \c V.
kpeter@80	708	/// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
alpar@26	709	///
kpeter@80	710	/// The simplest way of using this map is through the convertMap()
kpeter@80	711	/// function.
kpeter@80	712	template <typename M, typename V>
kpeter@80	713	class ConvertMap : public MapBase<typename M::Key, V> {
kpeter@80	714	const M &_m;
kpeter@80	715	public:
kpeter@80	716	typedef MapBase<typename M::Key, V> Parent;
kpeter@80	717	typedef typename Parent::Key Key;
kpeter@80	718	typedef typename Parent::Value Value;
kpeter@80	719
kpeter@80	720	/// Constructor
kpeter@80	721
kpeter@80	722	/// Constructor.
kpeter@80	723	/// \param m The underlying map.
kpeter@80	724	ConvertMap(const M &m) : _m(m) {}
kpeter@80	725
kpeter@80	726	/// \e
kpeter@80	727	Value operator[](const Key &k) const { return _m[k]; }
kpeter@80	728	};
kpeter@80	729
kpeter@80	730	/// Returns a \ref ConvertMap class
kpeter@80	731
kpeter@80	732	/// This function just returns a \ref ConvertMap class.
kpeter@80	733	/// \relates ConvertMap
kpeter@80	734	template<typename V, typename M>
kpeter@80	735	inline ConvertMap<M, V> convertMap(const M &map) {
kpeter@80	736	return ConvertMap<M, V>(map);
kpeter@80	737	}
kpeter@80	738
kpeter@80	739
kpeter@80	740	/// Applies all map setting operations to two maps
kpeter@80	741
kpeter@80	742	/// This map has two \ref concepts::WriteMap "writable map" parameters
kpeter@80	743	/// and each write request will be passed to both of them.
kpeter@80	744	/// If \c M1 is also \ref concepts::ReadMap "readable", then the read
kpeter@80	745	/// operations will return the corresponding values of \c M1.
kpeter@29	746	///
kpeter@80	747	/// The \c Key and \c Value types are inherited from \c M1.
kpeter@80	748	/// The \c Key and \c Value of \c M2 must be convertible from those
kpeter@80	749	/// of \c M1.
kpeter@80	750	///
kpeter@80	751	/// The simplest way of using this map is through the forkMap()
kpeter@80	752	/// function.
kpeter@80	753	template<typename M1, typename M2>
kpeter@80	754	class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	755	M1 &_m1;
kpeter@80	756	M2 &_m2;
kpeter@80	757	public:
kpeter@80	758	typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80	759	typedef typename Parent::Key Key;
kpeter@80	760	typedef typename Parent::Value Value;
alpar@25	761
kpeter@80	762	/// Constructor
kpeter@80	763	ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	764	/// Returns the value associated with the given key in the first map.
kpeter@80	765	Value operator[](const Key &k) const { return _m1[k]; }
kpeter@80	766	/// Sets the value associated with the given key in both maps.
kpeter@80	767	void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
kpeter@80	768	};
kpeter@80	769
kpeter@80	770	/// Returns a \ref ForkMap class
kpeter@80	771
kpeter@80	772	/// This function just returns a \ref ForkMap class.
kpeter@80	773	/// \relates ForkMap
kpeter@80	774	template <typename M1, typename M2>
kpeter@80	775	inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
kpeter@80	776	return ForkMap<M1,M2>(m1,m2);
kpeter@80	777	}
kpeter@80	778
kpeter@80	779
kpeter@80	780	/// Sum of two maps
kpeter@80	781
kpeter@82	782	/// This \ref concepts::ReadMap "read-only map" returns the sum
kpeter@80	783	/// of the values of the two given maps.
kpeter@80	784	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	785	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	786	/// \c M1.
kpeter@80	787	///
kpeter@80	788	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	789	/// \code
kpeter@80	790	/// AddMap<M1,M2> am(m1,m2);
kpeter@80	791	/// \endcode
kpeter@80	792	/// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
kpeter@80	793	///
kpeter@80	794	/// The simplest way of using this map is through the addMap()
kpeter@80	795	/// function.
kpeter@80	796	///
kpeter@80	797	/// \sa SubMap, MulMap, DivMap
kpeter@80	798	/// \sa ShiftMap, ShiftWriteMap
kpeter@80	799	template<typename M1, typename M2>
alpar@25	800	class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	801	const M1 &_m1;
kpeter@80	802	const M2 &_m2;
alpar@25	803	public:
alpar@25	804	typedef MapBase<typename M1::Key, typename M1::Value> Parent;
alpar@25	805	typedef typename Parent::Key Key;
alpar@25	806	typedef typename Parent::Value Value;
alpar@25	807
kpeter@80	808	/// Constructor
kpeter@80	809	AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	810	/// \e
kpeter@80	811	Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
alpar@25	812	};
alpar@25	813
kpeter@80	814	/// Returns an \ref AddMap class
kpeter@80	815
kpeter@80	816	/// This function just returns an \ref AddMap class.
alpar@25	817	///
kpeter@80	818	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	819	/// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
kpeter@80	820	/// <tt>m1[x]+m2[x]</tt>.
kpeter@80	821	///
kpeter@80	822	/// \relates AddMap
kpeter@80	823	template<typename M1, typename M2>
kpeter@80	824	inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
alpar@25	825	return AddMap<M1, M2>(m1,m2);
alpar@25	826	}
alpar@25	827
alpar@25	828
kpeter@80	829	/// Difference of two maps
kpeter@80	830
kpeter@82	831	/// This \ref concepts::ReadMap "read-only map" returns the difference
kpeter@80	832	/// of the values of the two given maps.
kpeter@80	833	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	834	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	835	/// \c M1.
alpar@25	836	///
kpeter@80	837	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	838	/// \code
kpeter@80	839	/// SubMap<M1,M2> sm(m1,m2);
kpeter@80	840	/// \endcode
kpeter@80	841	/// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
kpeter@29	842	///
kpeter@80	843	/// The simplest way of using this map is through the subMap()
kpeter@80	844	/// function.
kpeter@80	845	///
kpeter@80	846	/// \sa AddMap, MulMap, DivMap
kpeter@80	847	template<typename M1, typename M2>
kpeter@80	848	class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	849	const M1 &_m1;
kpeter@80	850	const M2 &_m2;
kpeter@80	851	public:
kpeter@80	852	typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80	853	typedef typename Parent::Key Key;
kpeter@80	854	typedef typename Parent::Value Value;
kpeter@80	855
kpeter@80	856	/// Constructor
kpeter@80	857	SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	858	/// \e
kpeter@80	859	Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
kpeter@80	860	};
kpeter@80	861
kpeter@80	862	/// Returns a \ref SubMap class
kpeter@80	863
kpeter@80	864	/// This function just returns a \ref SubMap class.
kpeter@80	865	///
kpeter@80	866	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	867	/// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
kpeter@80	868	/// <tt>m1[x]-m2[x]</tt>.
kpeter@80	869	///
kpeter@80	870	/// \relates SubMap
kpeter@80	871	template<typename M1, typename M2>
kpeter@80	872	inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
kpeter@80	873	return SubMap<M1, M2>(m1,m2);
kpeter@80	874	}
kpeter@80	875
kpeter@80	876
kpeter@80	877	/// Product of two maps
kpeter@80	878
kpeter@82	879	/// This \ref concepts::ReadMap "read-only map" returns the product
kpeter@80	880	/// of the values of the two given maps.
kpeter@80	881	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	882	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	883	/// \c M1.
kpeter@80	884	///
kpeter@80	885	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	886	/// \code
kpeter@80	887	/// MulMap<M1,M2> mm(m1,m2);
kpeter@80	888	/// \endcode
kpeter@80	889	/// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
kpeter@80	890	///
kpeter@80	891	/// The simplest way of using this map is through the mulMap()
kpeter@80	892	/// function.
kpeter@80	893	///
kpeter@80	894	/// \sa AddMap, SubMap, DivMap
kpeter@80	895	/// \sa ScaleMap, ScaleWriteMap
kpeter@80	896	template<typename M1, typename M2>
kpeter@80	897	class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	898	const M1 &_m1;
kpeter@80	899	const M2 &_m2;
kpeter@80	900	public:
kpeter@80	901	typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80	902	typedef typename Parent::Key Key;
kpeter@80	903	typedef typename Parent::Value Value;
kpeter@80	904
kpeter@80	905	/// Constructor
kpeter@80	906	MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	907	/// \e
kpeter@80	908	Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
kpeter@80	909	};
kpeter@80	910
kpeter@80	911	/// Returns a \ref MulMap class
kpeter@80	912
kpeter@80	913	/// This function just returns a \ref MulMap class.
kpeter@80	914	///
kpeter@80	915	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	916	/// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
kpeter@80	917	/// <tt>m1[x]*m2[x]</tt>.
kpeter@80	918	///
kpeter@80	919	/// \relates MulMap
kpeter@80	920	template<typename M1, typename M2>
kpeter@80	921	inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
kpeter@80	922	return MulMap<M1, M2>(m1,m2);
kpeter@80	923	}
kpeter@80	924
kpeter@80	925
kpeter@80	926	/// Quotient of two maps
kpeter@80	927
kpeter@82	928	/// This \ref concepts::ReadMap "read-only map" returns the quotient
kpeter@80	929	/// of the values of the two given maps.
kpeter@80	930	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	931	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	932	/// \c M1.
kpeter@80	933	///
kpeter@80	934	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	935	/// \code
kpeter@80	936	/// DivMap<M1,M2> dm(m1,m2);
kpeter@80	937	/// \endcode
kpeter@80	938	/// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
kpeter@80	939	///
kpeter@80	940	/// The simplest way of using this map is through the divMap()
kpeter@80	941	/// function.
kpeter@80	942	///
kpeter@80	943	/// \sa AddMap, SubMap, MulMap
kpeter@80	944	template<typename M1, typename M2>
kpeter@80	945	class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	946	const M1 &_m1;
kpeter@80	947	const M2 &_m2;
kpeter@80	948	public:
kpeter@80	949	typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80	950	typedef typename Parent::Key Key;
kpeter@80	951	typedef typename Parent::Value Value;
kpeter@80	952
kpeter@80	953	/// Constructor
kpeter@80	954	DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	955	/// \e
kpeter@80	956	Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
kpeter@80	957	};
kpeter@80	958
kpeter@80	959	/// Returns a \ref DivMap class
kpeter@80	960
kpeter@80	961	/// This function just returns a \ref DivMap class.
kpeter@80	962	///
kpeter@80	963	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	964	/// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
kpeter@80	965	/// <tt>m1[x]/m2[x]</tt>.
kpeter@80	966	///
kpeter@80	967	/// \relates DivMap
kpeter@80	968	template<typename M1, typename M2>
kpeter@80	969	inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
kpeter@80	970	return DivMap<M1, M2>(m1,m2);
kpeter@80	971	}
kpeter@80	972
kpeter@80	973
kpeter@80	974	/// Shifts a map with a constant.
kpeter@80	975
kpeter@82	976	/// This \ref concepts::ReadMap "read-only map" returns the sum of
kpeter@80	977	/// the given map and a constant value (i.e. it shifts the map with
kpeter@80	978	/// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80	979	///
kpeter@80	980	/// Actually,
kpeter@80	981	/// \code
kpeter@80	982	/// ShiftMap<M> sh(m,v);
kpeter@80	983	/// \endcode
kpeter@80	984	/// is equivalent to
kpeter@80	985	/// \code
kpeter@80	986	/// ConstMap<M::Key, M::Value> cm(v);
kpeter@80	987	/// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
kpeter@80	988	/// \endcode
kpeter@80	989	///
kpeter@80	990	/// The simplest way of using this map is through the shiftMap()
kpeter@80	991	/// function.
kpeter@80	992	///
kpeter@80	993	/// \sa ShiftWriteMap
kpeter@80	994	template<typename M, typename C = typename M::Value>
alpar@25	995	class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	996	const M &_m;
kpeter@80	997	C _v;
alpar@25	998	public:
alpar@25	999	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1000	typedef typename Parent::Key Key;
alpar@25	1001	typedef typename Parent::Value Value;
alpar@25	1002
kpeter@80	1003	/// Constructor
alpar@25	1004
kpeter@80	1005	/// Constructor.
kpeter@80	1006	/// \param m The undelying map.
kpeter@80	1007	/// \param v The constant value.
kpeter@80	1008	ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@80	1009	/// \e
kpeter@80	1010	Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25	1011	};
alpar@25	1012
kpeter@80	1013	/// Shifts a map with a constant (read-write version).
alpar@25	1014
kpeter@80	1015	/// This \ref concepts::ReadWriteMap "read-write map" returns the sum
kpeter@80	1016	/// of the given map and a constant value (i.e. it shifts the map with
kpeter@80	1017	/// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80	1018	/// It makes also possible to write the map.
alpar@25	1019	///
kpeter@80	1020	/// The simplest way of using this map is through the shiftWriteMap()
kpeter@80	1021	/// function.
kpeter@80	1022	///
kpeter@80	1023	/// \sa ShiftMap
kpeter@80	1024	template<typename M, typename C = typename M::Value>
alpar@25	1025	class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1026	M &_m;
kpeter@80	1027	C _v;
alpar@25	1028	public:
alpar@25	1029	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1030	typedef typename Parent::Key Key;
alpar@25	1031	typedef typename Parent::Value Value;
alpar@25	1032
kpeter@80	1033	/// Constructor
alpar@25	1034
kpeter@80	1035	/// Constructor.
kpeter@80	1036	/// \param m The undelying map.
kpeter@80	1037	/// \param v The constant value.
kpeter@80	1038	ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
alpar@25	1039	/// \e
kpeter@80	1040	Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25	1041	/// \e
kpeter@80	1042	void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
alpar@25	1043	};
alpar@25	1044
kpeter@80	1045	/// Returns a \ref ShiftMap class
kpeter@80	1046
kpeter@80	1047	/// This function just returns a \ref ShiftMap class.
kpeter@80	1048	///
kpeter@80	1049	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1050	/// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
kpeter@80	1051	/// <tt>m[x]+v</tt>.
kpeter@80	1052	///
kpeter@80	1053	/// \relates ShiftMap
kpeter@80	1054	template<typename M, typename C>
kpeter@80	1055	inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
alpar@25	1056	return ShiftMap<M, C>(m,v);
alpar@25	1057	}
alpar@25	1058
kpeter@80	1059	/// Returns a \ref ShiftWriteMap class
kpeter@29	1060
kpeter@80	1061	/// This function just returns a \ref ShiftWriteMap class.
kpeter@80	1062	///
kpeter@80	1063	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1064	/// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
kpeter@80	1065	/// <tt>m[x]+v</tt>.
kpeter@80	1066	/// Moreover it makes also possible to write the map.
kpeter@80	1067	///
kpeter@80	1068	/// \relates ShiftWriteMap
kpeter@80	1069	template<typename M, typename C>
kpeter@80	1070	inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
alpar@25	1071	return ShiftWriteMap<M, C>(m,v);
alpar@25	1072	}
alpar@25	1073
alpar@25	1074
kpeter@80	1075	/// Scales a map with a constant.
kpeter@80	1076
kpeter@82	1077	/// This \ref concepts::ReadMap "read-only map" returns the value of
kpeter@80	1078	/// the given map multiplied from the left side with a constant value.
kpeter@80	1079	/// Its \c Key and \c Value are inherited from \c M.
alpar@26	1080	///
kpeter@80	1081	/// Actually,
kpeter@80	1082	/// \code
kpeter@80	1083	/// ScaleMap<M> sc(m,v);
kpeter@80	1084	/// \endcode
kpeter@80	1085	/// is equivalent to
kpeter@80	1086	/// \code
kpeter@80	1087	/// ConstMap<M::Key, M::Value> cm(v);
kpeter@80	1088	/// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
kpeter@80	1089	/// \endcode
alpar@25	1090	///
kpeter@80	1091	/// The simplest way of using this map is through the scaleMap()
kpeter@80	1092	/// function.
alpar@25	1093	///
kpeter@80	1094	/// \sa ScaleWriteMap
kpeter@80	1095	template<typename M, typename C = typename M::Value>
alpar@25	1096	class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1097	const M &_m;
kpeter@80	1098	C _v;
alpar@25	1099	public:
alpar@25	1100	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1101	typedef typename Parent::Key Key;
alpar@25	1102	typedef typename Parent::Value Value;
alpar@25	1103
kpeter@80	1104	/// Constructor
alpar@25	1105
kpeter@80	1106	/// Constructor.
kpeter@80	1107	/// \param m The undelying map.
kpeter@80	1108	/// \param v The constant value.
kpeter@80	1109	ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
alpar@25	1110	/// \e
kpeter@80	1111	Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25	1112	};
alpar@25	1113
kpeter@80	1114	/// Scales a map with a constant (read-write version).
alpar@25	1115
kpeter@80	1116	/// This \ref concepts::ReadWriteMap "read-write map" returns the value of
kpeter@80	1117	/// the given map multiplied from the left side with a constant value.
kpeter@80	1118	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1119	/// It can also be used as write map if the \c / operator is defined
kpeter@80	1120	/// between \c Value and \c C and the given multiplier is not zero.
kpeter@29	1121	///
kpeter@80	1122	/// The simplest way of using this map is through the scaleWriteMap()
kpeter@80	1123	/// function.
kpeter@80	1124	///
kpeter@80	1125	/// \sa ScaleMap
kpeter@80	1126	template<typename M, typename C = typename M::Value>
alpar@25	1127	class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1128	M &_m;
kpeter@80	1129	C _v;
alpar@25	1130	public:
alpar@25	1131	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1132	typedef typename Parent::Key Key;
alpar@25	1133	typedef typename Parent::Value Value;
alpar@25	1134
kpeter@80	1135	/// Constructor
alpar@25	1136
kpeter@80	1137	/// Constructor.
kpeter@80	1138	/// \param m The undelying map.
kpeter@80	1139	/// \param v The constant value.
kpeter@80	1140	ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
alpar@25	1141	/// \e
kpeter@80	1142	Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25	1143	/// \e
kpeter@80	1144	void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
alpar@25	1145	};
alpar@25	1146
kpeter@80	1147	/// Returns a \ref ScaleMap class
kpeter@80	1148
kpeter@80	1149	/// This function just returns a \ref ScaleMap class.
kpeter@80	1150	///
kpeter@80	1151	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1152	/// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
kpeter@80	1153	/// <tt>v*m[x]</tt>.
kpeter@80	1154	///
kpeter@80	1155	/// \relates ScaleMap
kpeter@80	1156	template<typename M, typename C>
kpeter@80	1157	inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
alpar@25	1158	return ScaleMap<M, C>(m,v);
alpar@25	1159	}
alpar@25	1160
kpeter@80	1161	/// Returns a \ref ScaleWriteMap class
kpeter@29	1162
kpeter@80	1163	/// This function just returns a \ref ScaleWriteMap class.
kpeter@80	1164	///
kpeter@80	1165	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1166	/// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
kpeter@80	1167	/// <tt>v*m[x]</tt>.
kpeter@80	1168	/// Moreover it makes also possible to write the map.
kpeter@80	1169	///
kpeter@80	1170	/// \relates ScaleWriteMap
kpeter@80	1171	template<typename M, typename C>
kpeter@80	1172	inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
alpar@25	1173	return ScaleWriteMap<M, C>(m,v);
alpar@25	1174	}
alpar@25	1175
alpar@25	1176
kpeter@80	1177	/// Negative of a map
alpar@25	1178
kpeter@82	1179	/// This \ref concepts::ReadMap "read-only map" returns the negative
kpeter@80	1180	/// of the values of the given map (using the unary \c - operator).
kpeter@80	1181	/// Its \c Key and \c Value are inherited from \c M.
alpar@25	1182	///
kpeter@80	1183	/// If M::Value is \c int, \c double etc., then
kpeter@80	1184	/// \code
kpeter@80	1185	/// NegMap<M> neg(m);
kpeter@80	1186	/// \endcode
kpeter@80	1187	/// is equivalent to
kpeter@80	1188	/// \code
kpeter@80	1189	/// ScaleMap<M> neg(m,-1);
kpeter@80	1190	/// \endcode
kpeter@29	1191	///
kpeter@80	1192	/// The simplest way of using this map is through the negMap()
kpeter@80	1193	/// function.
kpeter@29	1194	///
kpeter@80	1195	/// \sa NegWriteMap
kpeter@80	1196	template<typename M>
alpar@25	1197	class NegMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1198	const M& _m;
alpar@25	1199	public:
alpar@25	1200	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1201	typedef typename Parent::Key Key;
alpar@25	1202	typedef typename Parent::Value Value;
alpar@25	1203
kpeter@80	1204	/// Constructor
kpeter@80	1205	NegMap(const M &m) : _m(m) {}
alpar@25	1206	/// \e
kpeter@80	1207	Value operator[](const Key &k) const { return -_m[k]; }
alpar@25	1208	};
alpar@25	1209
kpeter@80	1210	/// Negative of a map (read-write version)
kpeter@80	1211
kpeter@80	1212	/// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80	1213	/// negative of the values of the given map (using the unary \c -
kpeter@80	1214	/// operator).
kpeter@80	1215	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1216	/// It makes also possible to write the map.
kpeter@80	1217	///
kpeter@80	1218	/// If M::Value is \c int, \c double etc., then
kpeter@80	1219	/// \code
kpeter@80	1220	/// NegWriteMap<M> neg(m);
kpeter@80	1221	/// \endcode
kpeter@80	1222	/// is equivalent to
kpeter@80	1223	/// \code
kpeter@80	1224	/// ScaleWriteMap<M> neg(m,-1);
kpeter@80	1225	/// \endcode
kpeter@80	1226	///
kpeter@80	1227	/// The simplest way of using this map is through the negWriteMap()
kpeter@80	1228	/// function.
kpeter@29	1229	///
kpeter@29	1230	/// \sa NegMap
kpeter@80	1231	template<typename M>
alpar@25	1232	class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1233	M &_m;
alpar@25	1234	public:
alpar@25	1235	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1236	typedef typename Parent::Key Key;
alpar@25	1237	typedef typename Parent::Value Value;
alpar@25	1238
kpeter@80	1239	/// Constructor
kpeter@80	1240	NegWriteMap(M &m) : _m(m) {}
alpar@25	1241	/// \e
kpeter@80	1242	Value operator[](const Key &k) const { return -_m[k]; }
alpar@25	1243	/// \e
kpeter@80	1244	void set(const Key &k, const Value &v) { _m.set(k, -v); }
alpar@25	1245	};
alpar@25	1246
kpeter@80	1247	/// Returns a \ref NegMap class
alpar@25	1248
kpeter@80	1249	/// This function just returns a \ref NegMap class.
kpeter@80	1250	///
kpeter@80	1251	/// For example, if \c m is a map with \c double values, then
kpeter@80	1252	/// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80	1253	///
kpeter@80	1254	/// \relates NegMap
kpeter@80	1255	template <typename M>
alpar@25	1256	inline NegMap<M> negMap(const M &m) {
alpar@25	1257	return NegMap<M>(m);
alpar@25	1258	}
alpar@25	1259
kpeter@80	1260	/// Returns a \ref NegWriteMap class
kpeter@29	1261
kpeter@80	1262	/// This function just returns a \ref NegWriteMap class.
kpeter@80	1263	///
kpeter@80	1264	/// For example, if \c m is a map with \c double values, then
kpeter@80	1265	/// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80	1266	/// Moreover it makes also possible to write the map.
kpeter@80	1267	///
kpeter@80	1268	/// \relates NegWriteMap
kpeter@80	1269	template <typename M>
kpeter@80	1270	inline NegWriteMap<M> negWriteMap(M &m) {
alpar@25	1271	return NegWriteMap<M>(m);
alpar@25	1272	}
alpar@25	1273
alpar@25	1274
kpeter@80	1275	/// Absolute value of a map
kpeter@80	1276
kpeter@82	1277	/// This \ref concepts::ReadMap "read-only map" returns the absolute
kpeter@80	1278	/// value of the values of the given map.
kpeter@80	1279	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1280	/// \c Value must be comparable to \c 0 and the unary \c -
kpeter@80	1281	/// operator must be defined for it, of course.
kpeter@80	1282	///
kpeter@80	1283	/// The simplest way of using this map is through the absMap()
kpeter@80	1284	/// function.
kpeter@80	1285	template<typename M>
alpar@25	1286	class AbsMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1287	const M &_m;
alpar@25	1288	public:
alpar@25	1289	typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25	1290	typedef typename Parent::Key Key;
alpar@25	1291	typedef typename Parent::Value Value;
alpar@25	1292
kpeter@80	1293	/// Constructor
kpeter@80	1294	AbsMap(const M &m) : _m(m) {}
alpar@25	1295	/// \e
kpeter@80	1296	Value operator[](const Key &k) const {
kpeter@80	1297	Value tmp = _m[k];
alpar@25	1298	return tmp >= 0 ? tmp : -tmp;
alpar@25	1299	}
alpar@25	1300
alpar@25	1301	};
alpar@25	1302
kpeter@80	1303	/// Returns an \ref AbsMap class
kpeter@80	1304
kpeter@80	1305	/// This function just returns an \ref AbsMap class.
kpeter@80	1306	///
kpeter@80	1307	/// For example, if \c m is a map with \c double values, then
kpeter@80	1308	/// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
kpeter@80	1309	/// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
kpeter@80	1310	/// negative.
kpeter@80	1311	///
kpeter@80	1312	/// \relates AbsMap
kpeter@80	1313	template<typename M>
alpar@25	1314	inline AbsMap<M> absMap(const M &m) {
alpar@25	1315	return AbsMap<M>(m);
alpar@25	1316	}
alpar@25	1317
kpeter@82	1318	/// @}
alpar@209	1319
kpeter@82	1320	// Logical maps and map adaptors:
kpeter@82	1321
kpeter@82	1322	/// \addtogroup maps
kpeter@82	1323	/// @{
kpeter@82	1324
kpeter@82	1325	/// Constant \c true map.
kpeter@82	1326
kpeter@82	1327	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1328	/// each key.
kpeter@82	1329	///
kpeter@82	1330	/// Note that
kpeter@82	1331	/// \code
kpeter@82	1332	/// TrueMap<K> tm;
kpeter@82	1333	/// \endcode
kpeter@82	1334	/// is equivalent to
kpeter@82	1335	/// \code
kpeter@82	1336	/// ConstMap<K,bool> tm(true);
kpeter@82	1337	/// \endcode
kpeter@82	1338	///
kpeter@82	1339	/// \sa FalseMap
kpeter@82	1340	/// \sa ConstMap
kpeter@82	1341	template <typename K>
kpeter@82	1342	class TrueMap : public MapBase<K, bool> {
kpeter@82	1343	public:
kpeter@82	1344	typedef MapBase<K, bool> Parent;
kpeter@82	1345	typedef typename Parent::Key Key;
kpeter@82	1346	typedef typename Parent::Value Value;
kpeter@82	1347
kpeter@82	1348	/// Gives back \c true.
kpeter@82	1349	Value operator[](const Key&) const { return true; }
kpeter@82	1350	};
kpeter@82	1351
kpeter@82	1352	/// Returns a \ref TrueMap class
kpeter@82	1353
kpeter@82	1354	/// This function just returns a \ref TrueMap class.
kpeter@82	1355	/// \relates TrueMap
kpeter@82	1356	template<typename K>
kpeter@82	1357	inline TrueMap<K> trueMap() {
kpeter@82	1358	return TrueMap<K>();
kpeter@82	1359	}
kpeter@82	1360
kpeter@82	1361
kpeter@82	1362	/// Constant \c false map.
kpeter@82	1363
kpeter@82	1364	/// This \ref concepts::ReadMap "read-only map" assigns \c false to
kpeter@82	1365	/// each key.
kpeter@82	1366	///
kpeter@82	1367	/// Note that
kpeter@82	1368	/// \code
kpeter@82	1369	/// FalseMap<K> fm;
kpeter@82	1370	/// \endcode
kpeter@82	1371	/// is equivalent to
kpeter@82	1372	/// \code
kpeter@82	1373	/// ConstMap<K,bool> fm(false);
kpeter@82	1374	/// \endcode
kpeter@82	1375	///
kpeter@82	1376	/// \sa TrueMap
kpeter@82	1377	/// \sa ConstMap
kpeter@82	1378	template <typename K>
kpeter@82	1379	class FalseMap : public MapBase<K, bool> {
kpeter@82	1380	public:
kpeter@82	1381	typedef MapBase<K, bool> Parent;
kpeter@82	1382	typedef typename Parent::Key Key;
kpeter@82	1383	typedef typename Parent::Value Value;
kpeter@82	1384
kpeter@82	1385	/// Gives back \c false.
kpeter@82	1386	Value operator[](const Key&) const { return false; }
kpeter@82	1387	};
kpeter@82	1388
kpeter@82	1389	/// Returns a \ref FalseMap class
kpeter@82	1390
kpeter@82	1391	/// This function just returns a \ref FalseMap class.
kpeter@82	1392	/// \relates FalseMap
kpeter@82	1393	template<typename K>
kpeter@82	1394	inline FalseMap<K> falseMap() {
kpeter@82	1395	return FalseMap<K>();
kpeter@82	1396	}
kpeter@82	1397
kpeter@82	1398	/// @}
kpeter@82	1399
kpeter@82	1400	/// \addtogroup map_adaptors
kpeter@82	1401	/// @{
kpeter@82	1402
kpeter@82	1403	/// Logical 'and' of two maps
kpeter@82	1404
kpeter@82	1405	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82	1406	/// 'and' of the values of the two given maps.
kpeter@82	1407	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1408	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1409	///
kpeter@82	1410	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1411	/// \code
kpeter@82	1412	/// AndMap<M1,M2> am(m1,m2);
kpeter@82	1413	/// \endcode
kpeter@82	1414	/// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
kpeter@82	1415	///
kpeter@82	1416	/// The simplest way of using this map is through the andMap()
kpeter@82	1417	/// function.
kpeter@82	1418	///
kpeter@82	1419	/// \sa OrMap
kpeter@82	1420	/// \sa NotMap, NotWriteMap
kpeter@82	1421	template<typename M1, typename M2>
kpeter@82	1422	class AndMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1423	const M1 &_m1;
kpeter@82	1424	const M2 &_m2;
kpeter@82	1425	public:
kpeter@82	1426	typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82	1427	typedef typename Parent::Key Key;
kpeter@82	1428	typedef typename Parent::Value Value;
kpeter@82	1429
kpeter@82	1430	/// Constructor
kpeter@82	1431	AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82	1432	/// \e
kpeter@82	1433	Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
kpeter@82	1434	};
kpeter@82	1435
kpeter@82	1436	/// Returns an \ref AndMap class
kpeter@82	1437
kpeter@82	1438	/// This function just returns an \ref AndMap class.
kpeter@82	1439	///
kpeter@82	1440	/// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82	1441	/// then <tt>andMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1442	/// <tt>m1[x]&&m2[x]</tt>.
kpeter@82	1443	///
kpeter@82	1444	/// \relates AndMap
kpeter@82	1445	template<typename M1, typename M2>
kpeter@82	1446	inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
kpeter@82	1447	return AndMap<M1, M2>(m1,m2);
kpeter@82	1448	}
kpeter@82	1449
kpeter@82	1450
kpeter@82	1451	/// Logical 'or' of two maps
kpeter@82	1452
kpeter@82	1453	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82	1454	/// 'or' of the values of the two given maps.
kpeter@82	1455	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1456	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1457	///
kpeter@82	1458	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1459	/// \code
kpeter@82	1460	/// OrMap<M1,M2> om(m1,m2);
kpeter@82	1461	/// \endcode
kpeter@82	1462	/// <tt>om[x]</tt> will be equal to <tt>m1[x]\|\|m2[x]</tt>.
kpeter@82	1463	///
kpeter@82	1464	/// The simplest way of using this map is through the orMap()
kpeter@82	1465	/// function.
kpeter@82	1466	///
kpeter@82	1467	/// \sa AndMap
kpeter@82	1468	/// \sa NotMap, NotWriteMap
kpeter@82	1469	template<typename M1, typename M2>
kpeter@82	1470	class OrMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1471	const M1 &_m1;
kpeter@82	1472	const M2 &_m2;
kpeter@82	1473	public:
kpeter@82	1474	typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82	1475	typedef typename Parent::Key Key;
kpeter@82	1476	typedef typename Parent::Value Value;
kpeter@82	1477
kpeter@82	1478	/// Constructor
kpeter@82	1479	OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82	1480	/// \e
kpeter@82	1481	Value operator[](const Key &k) const { return _m1[k]\|\|_m2[k]; }
kpeter@82	1482	};
kpeter@82	1483
kpeter@82	1484	/// Returns an \ref OrMap class
kpeter@82	1485
kpeter@82	1486	/// This function just returns an \ref OrMap class.
kpeter@82	1487	///
kpeter@82	1488	/// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82	1489	/// then <tt>orMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1490	/// <tt>m1[x]\|\|m2[x]</tt>.
kpeter@82	1491	///
kpeter@82	1492	/// \relates OrMap
kpeter@82	1493	template<typename M1, typename M2>
kpeter@82	1494	inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
kpeter@82	1495	return OrMap<M1, M2>(m1,m2);
kpeter@82	1496	}
kpeter@82	1497
alpar@25	1498
kpeter@80	1499	/// Logical 'not' of a map
kpeter@80	1500
kpeter@82	1501	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@80	1502	/// negation of the values of the given map.
kpeter@80	1503	/// Its \c Key is inherited from \c M and its \c Value is \c bool.
alpar@25	1504	///
kpeter@80	1505	/// The simplest way of using this map is through the notMap()
kpeter@80	1506	/// function.
alpar@25	1507	///
kpeter@80	1508	/// \sa NotWriteMap
kpeter@80	1509	template <typename M>
alpar@25	1510	class NotMap : public MapBase<typename M::Key, bool> {
kpeter@80	1511	const M &_m;
alpar@25	1512	public:
alpar@25	1513	typedef MapBase<typename M::Key, bool> Parent;
alpar@25	1514	typedef typename Parent::Key Key;
alpar@25	1515	typedef typename Parent::Value Value;
alpar@25	1516
alpar@25	1517	/// Constructor
kpeter@80	1518	NotMap(const M &m) : _m(m) {}
kpeter@80	1519	/// \e
kpeter@80	1520	Value operator[](const Key &k) const { return !_m[k]; }
alpar@25	1521	};
alpar@25	1522
kpeter@80	1523	/// Logical 'not' of a map (read-write version)
kpeter@80	1524
kpeter@80	1525	/// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80	1526	/// logical negation of the values of the given map.
kpeter@80	1527	/// Its \c Key is inherited from \c M and its \c Value is \c bool.
kpeter@80	1528	/// It makes also possible to write the map. When a value is set,
kpeter@80	1529	/// the opposite value is set to the original map.
kpeter@29	1530	///
kpeter@80	1531	/// The simplest way of using this map is through the notWriteMap()
kpeter@80	1532	/// function.
kpeter@80	1533	///
kpeter@80	1534	/// \sa NotMap
kpeter@80	1535	template <typename M>
alpar@25	1536	class NotWriteMap : public MapBase<typename M::Key, bool> {
kpeter@80	1537	M &_m;
alpar@25	1538	public:
alpar@25	1539	typedef MapBase<typename M::Key, bool> Parent;
alpar@25	1540	typedef typename Parent::Key Key;
alpar@25	1541	typedef typename Parent::Value Value;
alpar@25	1542
alpar@25	1543	/// Constructor
kpeter@80	1544	NotWriteMap(M &m) : _m(m) {}
kpeter@80	1545	/// \e
kpeter@80	1546	Value operator[](const Key &k) const { return !_m[k]; }
kpeter@80	1547	/// \e
kpeter@80	1548	void set(const Key &k, bool v) { _m.set(k, !v); }
alpar@25	1549	};
kpeter@80	1550
kpeter@80	1551	/// Returns a \ref NotMap class
kpeter@80	1552
kpeter@80	1553	/// This function just returns a \ref NotMap class.
kpeter@80	1554	///
kpeter@80	1555	/// For example, if \c m is a map with \c bool values, then
kpeter@80	1556	/// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80	1557	///
kpeter@80	1558	/// \relates NotMap
kpeter@80	1559	template <typename M>
alpar@25	1560	inline NotMap<M> notMap(const M &m) {
alpar@25	1561	return NotMap<M>(m);
alpar@25	1562	}
kpeter@80	1563
kpeter@80	1564	/// Returns a \ref NotWriteMap class
kpeter@80	1565
kpeter@80	1566	/// This function just returns a \ref NotWriteMap class.
kpeter@80	1567	///
kpeter@80	1568	/// For example, if \c m is a map with \c bool values, then
kpeter@80	1569	/// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80	1570	/// Moreover it makes also possible to write the map.
kpeter@80	1571	///
kpeter@80	1572	/// \relates NotWriteMap
kpeter@80	1573	template <typename M>
kpeter@80	1574	inline NotWriteMap<M> notWriteMap(M &m) {
alpar@25	1575	return NotWriteMap<M>(m);
alpar@25	1576	}
alpar@25	1577
kpeter@82	1578
kpeter@82	1579	/// Combination of two maps using the \c == operator
kpeter@82	1580
kpeter@82	1581	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1582	/// the keys for which the corresponding values of the two maps are
kpeter@82	1583	/// equal.
kpeter@82	1584	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1585	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1586	///
kpeter@82	1587	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1588	/// \code
kpeter@82	1589	/// EqualMap<M1,M2> em(m1,m2);
kpeter@82	1590	/// \endcode
kpeter@82	1591	/// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
kpeter@82	1592	///
kpeter@82	1593	/// The simplest way of using this map is through the equalMap()
kpeter@82	1594	/// function.
kpeter@82	1595	///
kpeter@82	1596	/// \sa LessMap
kpeter@82	1597	template<typename M1, typename M2>
kpeter@82	1598	class EqualMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1599	const M1 &_m1;
kpeter@82	1600	const M2 &_m2;
kpeter@82	1601	public:
kpeter@82	1602	typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82	1603	typedef typename Parent::Key Key;
kpeter@82	1604	typedef typename Parent::Value Value;
kpeter@82	1605
kpeter@82	1606	/// Constructor
kpeter@82	1607	EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82	1608	/// \e
kpeter@82	1609	Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
kpeter@82	1610	};
kpeter@82	1611
kpeter@82	1612	/// Returns an \ref EqualMap class
kpeter@82	1613
kpeter@82	1614	/// This function just returns an \ref EqualMap class.
kpeter@82	1615	///
kpeter@82	1616	/// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82	1617	/// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1618	/// <tt>m1[x]==m2[x]</tt>.
kpeter@82	1619	///
kpeter@82	1620	/// \relates EqualMap
kpeter@82	1621	template<typename M1, typename M2>
kpeter@82	1622	inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
kpeter@82	1623	return EqualMap<M1, M2>(m1,m2);
kpeter@82	1624	}
kpeter@82	1625
kpeter@82	1626
kpeter@82	1627	/// Combination of two maps using the \c < operator
kpeter@82	1628
kpeter@82	1629	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1630	/// the keys for which the corresponding value of the first map is
kpeter@82	1631	/// less then the value of the second map.
kpeter@82	1632	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1633	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1634	///
kpeter@82	1635	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1636	/// \code
kpeter@82	1637	/// LessMap<M1,M2> lm(m1,m2);
kpeter@82	1638	/// \endcode
kpeter@82	1639	/// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
kpeter@82	1640	///
kpeter@82	1641	/// The simplest way of using this map is through the lessMap()
kpeter@82	1642	/// function.
kpeter@82	1643	///
kpeter@82	1644	/// \sa EqualMap
kpeter@82	1645	template<typename M1, typename M2>
kpeter@82	1646	class LessMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1647	const M1 &_m1;
kpeter@82	1648	const M2 &_m2;
kpeter@82	1649	public:
kpeter@82	1650	typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82	1651	typedef typename Parent::Key Key;
kpeter@82	1652	typedef typename Parent::Value Value;
kpeter@82	1653
kpeter@82	1654	/// Constructor
kpeter@82	1655	LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82	1656	/// \e
kpeter@82	1657	Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
kpeter@82	1658	};
kpeter@82	1659
kpeter@82	1660	/// Returns an \ref LessMap class
kpeter@82	1661
kpeter@82	1662	/// This function just returns an \ref LessMap class.
kpeter@82	1663	///
kpeter@82	1664	/// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82	1665	/// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1666	/// <tt>m1[x]<m2[x]</tt>.
kpeter@82	1667	///
kpeter@82	1668	/// \relates LessMap
kpeter@82	1669	template<typename M1, typename M2>
kpeter@82	1670	inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
kpeter@82	1671	return LessMap<M1, M2>(m1,m2);
kpeter@82	1672	}
kpeter@82	1673
alpar@104	1674	namespace _maps_bits {
alpar@104	1675
alpar@104	1676	template <typename _Iterator, typename Enable = void>
alpar@104	1677	struct IteratorTraits {
alpar@104	1678	typedef typename std::iterator_traits<_Iterator>::value_type Value;
alpar@104	1679	};
alpar@104	1680
alpar@104	1681	template <typename _Iterator>
alpar@104	1682	struct IteratorTraits<_Iterator,
alpar@104	1683	typename exists<typename _Iterator::container_type>::type>
alpar@104	1684	{
alpar@104	1685	typedef typename _Iterator::container_type::value_type Value;
alpar@104	1686	};
alpar@104	1687
alpar@104	1688	}
alpar@104	1689
alpar@104	1690	/// \brief Writable bool map for logging each \c true assigned element
alpar@104	1691	///
kpeter@159	1692	/// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104	1693	/// each \c true assigned element, i.e it copies subsequently each
alpar@104	1694	/// keys set to \c true to the given iterator.
kpeter@159	1695	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1696	/// that were marked \c true by an algorithm.
alpar@104	1697	///
kpeter@159	1698	/// There are several algorithms that provide solutions through bool
kpeter@159	1699	/// maps and most of them assign \c true at most once for each key.
kpeter@159	1700	/// In these cases it is a natural request to store each \c true
kpeter@159	1701	/// assigned elements (in order of the assignment), which can be
kpeter@167	1702	/// easily done with LoggerBoolMap.
kpeter@159	1703	///
kpeter@167	1704	/// The simplest way of using this map is through the loggerBoolMap()
kpeter@159	1705	/// function.
kpeter@159	1706	///
kpeter@159	1707	/// \tparam It The type of the iterator.
kpeter@159	1708	/// \tparam Ke The key type of the map. The default value set
kpeter@159	1709	/// according to the iterator type should work in most cases.
alpar@104	1710	///
alpar@104	1711	/// \note The container of the iterator must contain enough space
kpeter@159	1712	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1713	#ifdef DOXYGEN
kpeter@159	1714	template <typename It, typename Ke>
kpeter@159	1715	#else
alpar@104	1716	template <typename It,
alpar@209	1717	typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
kpeter@159	1718	#endif
kpeter@167	1719	class LoggerBoolMap {
alpar@104	1720	public:
alpar@104	1721	typedef It Iterator;
alpar@104	1722
alpar@104	1723	typedef Ke Key;
alpar@104	1724	typedef bool Value;
alpar@104	1725
alpar@104	1726	/// Constructor
kpeter@167	1727	LoggerBoolMap(Iterator it)
alpar@104	1728	: _begin(it), _end(it) {}
alpar@104	1729
alpar@104	1730	/// Gives back the given iterator set for the first key
alpar@104	1731	Iterator begin() const {
alpar@104	1732	return _begin;
alpar@104	1733	}
alpar@104	1734
alpar@104	1735	/// Gives back the the 'after the last' iterator
alpar@104	1736	Iterator end() const {
alpar@104	1737	return _end;
alpar@104	1738	}
alpar@104	1739
alpar@104	1740	/// The set function of the map
kpeter@159	1741	void set(const Key& key, Value value) {
alpar@104	1742	if (value) {
alpar@209	1743	*_end++ = key;
alpar@104	1744	}
alpar@104	1745	}
alpar@104	1746
alpar@104	1747	private:
alpar@104	1748	Iterator _begin;
kpeter@159	1749	Iterator _end;
alpar@104	1750	};
alpar@209	1751
kpeter@167	1752	/// Returns a \ref LoggerBoolMap class
kpeter@159	1753
kpeter@167	1754	/// This function just returns a \ref LoggerBoolMap class.
kpeter@159	1755	///
kpeter@159	1756	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1757	/// that were marked \c true by an algorithm.
kpeter@159	1758	/// For example it makes easier to store the nodes in the processing
kpeter@159	1759	/// order of Dfs algorithm, as the following examples show.
kpeter@159	1760	/// \code
kpeter@159	1761	/// std::vector<Node> v;
kpeter@167	1762	/// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@159	1763	/// \endcode
kpeter@159	1764	/// \code
kpeter@159	1765	/// std::vector<Node> v(countNodes(g));
kpeter@167	1766	/// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
kpeter@159	1767	/// \endcode
kpeter@159	1768	///
kpeter@159	1769	/// \note The container of the iterator must contain enough space
kpeter@159	1770	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1771	///
kpeter@167	1772	/// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@159	1773	/// it cannot be used when a readable map is needed, for example as
kpeter@167	1774	/// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
kpeter@159	1775	///
kpeter@167	1776	/// \relates LoggerBoolMap
kpeter@159	1777	template<typename Iterator>
kpeter@167	1778	inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167	1779	return LoggerBoolMap<Iterator>(it);
kpeter@159	1780	}
alpar@104	1781
deba@220	1782	/// Provides an immutable and unique id for each item in the graph.
deba@220	1783
deba@220	1784	/// The IdMap class provides a unique and immutable id for each item of the
deba@220	1785	/// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
deba@220	1786	/// different items (nodes) get different ids <li>\b immutable: the id of an
deba@220	1787	/// item (node) does not change (even if you delete other nodes). </ul>
deba@220	1788	/// Through this map you get access (i.e. can read) the inner id values of
deba@220	1789	/// the items stored in the graph. This map can be inverted with its member
deba@220	1790	/// class \c InverseMap or with the \c operator() member.
deba@220	1791	///
deba@220	1792	template <typename _Graph, typename _Item>
deba@220	1793	class IdMap {
deba@220	1794	public:
deba@220	1795	typedef _Graph Graph;
deba@220	1796	typedef int Value;
deba@220	1797	typedef _Item Item;
deba@220	1798	typedef _Item Key;
deba@220	1799
deba@220	1800	/// \brief Constructor.
deba@220	1801	///
deba@220	1802	/// Constructor of the map.
deba@220	1803	explicit IdMap(const Graph& graph) : _graph(&graph) {}
deba@220	1804
deba@220	1805	/// \brief Gives back the \e id of the item.
deba@220	1806	///
deba@220	1807	/// Gives back the immutable and unique \e id of the item.
deba@220	1808	int operator[](const Item& item) const { return _graph->id(item);}
deba@220	1809
deba@220	1810	/// \brief Gives back the item by its id.
deba@220	1811	///
deba@220	1812	/// Gives back the item by its id.
deba@220	1813	Item operator()(int id) { return _graph->fromId(id, Item()); }
deba@220	1814
deba@220	1815	private:
deba@220	1816	const Graph* _graph;
deba@220	1817
deba@220	1818	public:
deba@220	1819
deba@220	1820	/// \brief The class represents the inverse of its owner (IdMap).
deba@220	1821	///
deba@220	1822	/// The class represents the inverse of its owner (IdMap).
deba@220	1823	/// \see inverse()
deba@220	1824	class InverseMap {
deba@220	1825	public:
deba@220	1826
deba@220	1827	/// \brief Constructor.
deba@220	1828	///
deba@220	1829	/// Constructor for creating an id-to-item map.
deba@220	1830	explicit InverseMap(const Graph& graph) : _graph(&graph) {}
deba@220	1831
deba@220	1832	/// \brief Constructor.
deba@220	1833	///
deba@220	1834	/// Constructor for creating an id-to-item map.
deba@220	1835	explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
deba@220	1836
deba@220	1837	/// \brief Gives back the given item from its id.
deba@220	1838	///
deba@220	1839	/// Gives back the given item from its id.
deba@220	1840	///
deba@220	1841	Item operator[](int id) const { return _graph->fromId(id, Item());}
deba@220	1842
deba@220	1843	private:
deba@220	1844	const Graph* _graph;
deba@220	1845	};
deba@220	1846
deba@220	1847	/// \brief Gives back the inverse of the map.
deba@220	1848	///
deba@220	1849	/// Gives back the inverse of the IdMap.
deba@220	1850	InverseMap inverse() const { return InverseMap(*_graph);}
deba@220	1851
deba@220	1852	};
deba@220	1853
deba@220	1854
deba@220	1855	/// \brief General invertable graph-map type.
deba@220	1856
deba@220	1857	/// This type provides simple invertable graph-maps.
deba@220	1858	/// The InvertableMap wraps an arbitrary ReadWriteMap
deba@220	1859	/// and if a key is set to a new value then store it
deba@220	1860	/// in the inverse map.
deba@220	1861	///
deba@220	1862	/// The values of the map can be accessed
deba@220	1863	/// with stl compatible forward iterator.
deba@220	1864	///
deba@220	1865	/// \tparam _Graph The graph type.
deba@220	1866	/// \tparam _Item The item type of the graph.
deba@220	1867	/// \tparam _Value The value type of the map.
deba@220	1868	///
deba@220	1869	/// \see IterableValueMap
deba@220	1870	template <typename _Graph, typename _Item, typename _Value>
deba@220	1871	class InvertableMap
deba@220	1872	: protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
deba@220	1873	private:
deba@220	1874
deba@220	1875	typedef typename ItemSetTraits<_Graph, _Item>::
deba@220	1876	template Map<_Value>::Type Map;
deba@220	1877	typedef _Graph Graph;
deba@220	1878
deba@220	1879	typedef std::map<_Value, _Item> Container;
deba@220	1880	Container _inv_map;
deba@220	1881
deba@220	1882	public:
deba@220	1883
deba@220	1884	/// The key type of InvertableMap (Node, Arc, Edge).
deba@220	1885	typedef typename Map::Key Key;
deba@220	1886	/// The value type of the InvertableMap.
deba@220	1887	typedef typename Map::Value Value;
deba@220	1888
deba@220	1889
deba@220	1890
deba@220	1891	/// \brief Constructor.
deba@220	1892	///
deba@220	1893	/// Construct a new InvertableMap for the graph.
deba@220	1894	///
deba@220	1895	explicit InvertableMap(const Graph& graph) : Map(graph) {}
deba@220	1896
deba@220	1897	/// \brief Forward iterator for values.
deba@220	1898	///
deba@220	1899	/// This iterator is an stl compatible forward
deba@220	1900	/// iterator on the values of the map. The values can
deba@220	1901	/// be accessed in the [beginValue, endValue) range.
deba@220	1902	///
deba@220	1903	class ValueIterator
deba@220	1904	: public std::iterator<std::forward_iterator_tag, Value> {
deba@220	1905	friend class InvertableMap;
deba@220	1906	private:
deba@220	1907	ValueIterator(typename Container::const_iterator _it)
deba@220	1908	: it(_it) {}
deba@220	1909	public:
deba@220	1910
deba@220	1911	ValueIterator() {}
deba@220	1912
deba@220	1913	ValueIterator& operator++() { ++it; return *this; }
deba@220	1914	ValueIterator operator++(int) {
deba@220	1915	ValueIterator tmp(*this);
deba@220	1916	operator++();
deba@220	1917	return tmp;
deba@220	1918	}
deba@220	1919
deba@220	1920	const Value& operator*() const { return it->first; }
deba@220	1921	const Value* operator->() const { return &(it->first); }
deba@220	1922
deba@220	1923	bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@220	1924	bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@220	1925
deba@220	1926	private:
deba@220	1927	typename Container::const_iterator it;
deba@220	1928	};
deba@220	1929
deba@220	1930	/// \brief Returns an iterator to the first value.
deba@220	1931	///
deba@220	1932	/// Returns an stl compatible iterator to the
deba@220	1933	/// first value of the map. The values of the
deba@220	1934	/// map can be accessed in the [beginValue, endValue)
deba@220	1935	/// range.
deba@220	1936	ValueIterator beginValue() const {
deba@220	1937	return ValueIterator(_inv_map.begin());
deba@220	1938	}
deba@220	1939
deba@220	1940	/// \brief Returns an iterator after the last value.
deba@220	1941	///
deba@220	1942	/// Returns an stl compatible iterator after the
deba@220	1943	/// last value of the map. The values of the
deba@220	1944	/// map can be accessed in the [beginValue, endValue)
deba@220	1945	/// range.
deba@220	1946	ValueIterator endValue() const {
deba@220	1947	return ValueIterator(_inv_map.end());
deba@220	1948	}
deba@220	1949
deba@220	1950	/// \brief The setter function of the map.
deba@220	1951	///
deba@220	1952	/// Sets the mapped value.
deba@220	1953	void set(const Key& key, const Value& val) {
deba@220	1954	Value oldval = Map::operator[](key);
deba@220	1955	typename Container::iterator it = _inv_map.find(oldval);
deba@220	1956	if (it != _inv_map.end() && it->second == key) {
deba@220	1957	_inv_map.erase(it);
deba@220	1958	}
deba@220	1959	_inv_map.insert(make_pair(val, key));
deba@220	1960	Map::set(key, val);
deba@220	1961	}
deba@220	1962
deba@220	1963	/// \brief The getter function of the map.
deba@220	1964	///
deba@220	1965	/// It gives back the value associated with the key.
deba@220	1966	typename MapTraits<Map>::ConstReturnValue
deba@220	1967	operator[](const Key& key) const {
deba@220	1968	return Map::operator[](key);
deba@220	1969	}
deba@220	1970
deba@220	1971	/// \brief Gives back the item by its value.
deba@220	1972	///
deba@220	1973	/// Gives back the item by its value.
deba@220	1974	Key operator()(const Value& key) const {
deba@220	1975	typename Container::const_iterator it = _inv_map.find(key);
deba@220	1976	return it != _inv_map.end() ? it->second : INVALID;
deba@220	1977	}
deba@220	1978
deba@220	1979	protected:
deba@220	1980
deba@220	1981	/// \brief Erase the key from the map.
deba@220	1982	///
deba@220	1983	/// Erase the key to the map. It is called by the
deba@220	1984	/// \c AlterationNotifier.
deba@220	1985	virtual void erase(const Key& key) {
deba@220	1986	Value val = Map::operator[](key);
deba@220	1987	typename Container::iterator it = _inv_map.find(val);
deba@220	1988	if (it != _inv_map.end() && it->second == key) {
deba@220	1989	_inv_map.erase(it);
deba@220	1990	}
deba@220	1991	Map::erase(key);
deba@220	1992	}
deba@220	1993
deba@220	1994	/// \brief Erase more keys from the map.
deba@220	1995	///
deba@220	1996	/// Erase more keys from the map. It is called by the
deba@220	1997	/// \c AlterationNotifier.
deba@220	1998	virtual void erase(const std::vector<Key>& keys) {
deba@220	1999	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2000	Value val = Map::operator[](keys[i]);
deba@220	2001	typename Container::iterator it = _inv_map.find(val);
deba@220	2002	if (it != _inv_map.end() && it->second == keys[i]) {
deba@220	2003	_inv_map.erase(it);
deba@220	2004	}
deba@220	2005	}
deba@220	2006	Map::erase(keys);
deba@220	2007	}
deba@220	2008
deba@220	2009	/// \brief Clear the keys from the map and inverse map.
deba@220	2010	///
deba@220	2011	/// Clear the keys from the map and inverse map. It is called by the
deba@220	2012	/// \c AlterationNotifier.
deba@220	2013	virtual void clear() {
deba@220	2014	_inv_map.clear();
deba@220	2015	Map::clear();
deba@220	2016	}
deba@220	2017
deba@220	2018	public:
deba@220	2019
deba@220	2020	/// \brief The inverse map type.
deba@220	2021	///
deba@220	2022	/// The inverse of this map. The subscript operator of the map
deba@220	2023	/// gives back always the item what was last assigned to the value.
deba@220	2024	class InverseMap {
deba@220	2025	public:
deba@220	2026	/// \brief Constructor of the InverseMap.
deba@220	2027	///
deba@220	2028	/// Constructor of the InverseMap.
deba@220	2029	explicit InverseMap(const InvertableMap& inverted)
deba@220	2030	: _inverted(inverted) {}
deba@220	2031
deba@220	2032	/// The value type of the InverseMap.
deba@220	2033	typedef typename InvertableMap::Key Value;
deba@220	2034	/// The key type of the InverseMap.
deba@220	2035	typedef typename InvertableMap::Value Key;
deba@220	2036
deba@220	2037	/// \brief Subscript operator.
deba@220	2038	///
deba@220	2039	/// Subscript operator. It gives back always the item
deba@220	2040	/// what was last assigned to the value.
deba@220	2041	Value operator[](const Key& key) const {
deba@220	2042	return _inverted(key);
deba@220	2043	}
deba@220	2044
deba@220	2045	private:
deba@220	2046	const InvertableMap& _inverted;
deba@220	2047	};
deba@220	2048
deba@220	2049	/// \brief It gives back the just readable inverse map.
deba@220	2050	///
deba@220	2051	/// It gives back the just readable inverse map.
deba@220	2052	InverseMap inverse() const {
deba@220	2053	return InverseMap(*this);
deba@220	2054	}
deba@220	2055
deba@220	2056
deba@220	2057
deba@220	2058	};
deba@220	2059
deba@220	2060	/// \brief Provides a mutable, continuous and unique descriptor for each
deba@220	2061	/// item in the graph.
deba@220	2062	///
deba@220	2063	/// The DescriptorMap class provides a unique and continuous (but mutable)
deba@220	2064	/// descriptor (id) for each item of the same type (e.g. node) in the
deba@220	2065	/// graph. This id is <ul><li>\b unique: different items (nodes) get
deba@220	2066	/// different ids <li>\b continuous: the range of the ids is the set of
deba@220	2067	/// integers between 0 and \c n-1, where \c n is the number of the items of
deba@220	2068	/// this type (e.g. nodes) (so the id of a node can change if you delete an
deba@220	2069	/// other node, i.e. this id is mutable). </ul> This map can be inverted
deba@220	2070	/// with its member class \c InverseMap, or with the \c operator() member.
deba@220	2071	///
deba@220	2072	/// \tparam _Graph The graph class the \c DescriptorMap belongs to.
deba@220	2073	/// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
deba@220	2074	/// Edge.
deba@220	2075	template <typename _Graph, typename _Item>
deba@220	2076	class DescriptorMap
deba@220	2077	: protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
deba@220	2078
deba@220	2079	typedef _Item Item;
deba@220	2080	typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
deba@220	2081
deba@220	2082	public:
deba@220	2083	/// The graph class of DescriptorMap.
deba@220	2084	typedef _Graph Graph;
deba@220	2085
deba@220	2086	/// The key type of DescriptorMap (Node, Arc, Edge).
deba@220	2087	typedef typename Map::Key Key;
deba@220	2088	/// The value type of DescriptorMap.
deba@220	2089	typedef typename Map::Value Value;
deba@220	2090
deba@220	2091	/// \brief Constructor.
deba@220	2092	///
deba@220	2093	/// Constructor for descriptor map.
deba@220	2094	explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
deba@220	2095	Item it;
deba@220	2096	const typename Map::Notifier* nf = Map::notifier();
deba@220	2097	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2098	Map::set(it, _inv_map.size());
deba@220	2099	_inv_map.push_back(it);
deba@220	2100	}
deba@220	2101	}
deba@220	2102
deba@220	2103	protected:
deba@220	2104
deba@220	2105	/// \brief Add a new key to the map.
deba@220	2106	///
deba@220	2107	/// Add a new key to the map. It is called by the
deba@220	2108	/// \c AlterationNotifier.
deba@220	2109	virtual void add(const Item& item) {
deba@220	2110	Map::add(item);
deba@220	2111	Map::set(item, _inv_map.size());
deba@220	2112	_inv_map.push_back(item);
deba@220	2113	}
deba@220	2114
deba@220	2115	/// \brief Add more new keys to the map.
deba@220	2116	///
deba@220	2117	/// Add more new keys to the map. It is called by the
deba@220	2118	/// \c AlterationNotifier.
deba@220	2119	virtual void add(const std::vector<Item>& items) {
deba@220	2120	Map::add(items);
deba@220	2121	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2122	Map::set(items[i], _inv_map.size());
deba@220	2123	_inv_map.push_back(items[i]);
deba@220	2124	}
deba@220	2125	}
deba@220	2126
deba@220	2127	/// \brief Erase the key from the map.
deba@220	2128	///
deba@220	2129	/// Erase the key from the map. It is called by the
deba@220	2130	/// \c AlterationNotifier.
deba@220	2131	virtual void erase(const Item& item) {
deba@220	2132	Map::set(_inv_map.back(), Map::operator[](item));
deba@220	2133	_inv_map[Map::operator[](item)] = _inv_map.back();
deba@220	2134	_inv_map.pop_back();
deba@220	2135	Map::erase(item);
deba@220	2136	}
deba@220	2137
deba@220	2138	/// \brief Erase more keys from the map.
deba@220	2139	///
deba@220	2140	/// Erase more keys from the map. It is called by the
deba@220	2141	/// \c AlterationNotifier.
deba@220	2142	virtual void erase(const std::vector<Item>& items) {
deba@220	2143	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2144	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@220	2145	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@220	2146	_inv_map.pop_back();
deba@220	2147	}
deba@220	2148	Map::erase(items);
deba@220	2149	}
deba@220	2150
deba@220	2151	/// \brief Build the unique map.
deba@220	2152	///
deba@220	2153	/// Build the unique map. It is called by the
deba@220	2154	/// \c AlterationNotifier.
deba@220	2155	virtual void build() {
deba@220	2156	Map::build();
deba@220	2157	Item it;
deba@220	2158	const typename Map::Notifier* nf = Map::notifier();
deba@220	2159	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2160	Map::set(it, _inv_map.size());
deba@220	2161	_inv_map.push_back(it);
deba@220	2162	}
deba@220	2163	}
deba@220	2164
deba@220	2165	/// \brief Clear the keys from the map.
deba@220	2166	///
deba@220	2167	/// Clear the keys from the map. It is called by the
deba@220	2168	/// \c AlterationNotifier.
deba@220	2169	virtual void clear() {
deba@220	2170	_inv_map.clear();
deba@220	2171	Map::clear();
deba@220	2172	}
deba@220	2173
deba@220	2174	public:
deba@220	2175
deba@220	2176	/// \brief Returns the maximal value plus one.
deba@220	2177	///
deba@220	2178	/// Returns the maximal value plus one in the map.
deba@220	2179	unsigned int size() const {
deba@220	2180	return _inv_map.size();
deba@220	2181	}
deba@220	2182
deba@220	2183	/// \brief Swaps the position of the two items in the map.
deba@220	2184	///
deba@220	2185	/// Swaps the position of the two items in the map.
deba@220	2186	void swap(const Item& p, const Item& q) {
deba@220	2187	int pi = Map::operator[](p);
deba@220	2188	int qi = Map::operator[](q);
deba@220	2189	Map::set(p, qi);
deba@220	2190	_inv_map[qi] = p;
deba@220	2191	Map::set(q, pi);
deba@220	2192	_inv_map[pi] = q;
deba@220	2193	}
deba@220	2194
deba@220	2195	/// \brief Gives back the \e descriptor of the item.
deba@220	2196	///
deba@220	2197	/// Gives back the mutable and unique \e descriptor of the map.
deba@220	2198	int operator[](const Item& item) const {
deba@220	2199	return Map::operator[](item);
deba@220	2200	}
deba@220	2201
deba@220	2202	/// \brief Gives back the item by its descriptor.
deba@220	2203	///
deba@220	2204	/// Gives back th item by its descriptor.
deba@220	2205	Item operator()(int id) const {
deba@220	2206	return _inv_map[id];
deba@220	2207	}
deba@220	2208
deba@220	2209	private:
deba@220	2210
deba@220	2211	typedef std::vector<Item> Container;
deba@220	2212	Container _inv_map;
deba@220	2213
deba@220	2214	public:
deba@220	2215	/// \brief The inverse map type of DescriptorMap.
deba@220	2216	///
deba@220	2217	/// The inverse map type of DescriptorMap.
deba@220	2218	class InverseMap {
deba@220	2219	public:
deba@220	2220	/// \brief Constructor of the InverseMap.
deba@220	2221	///
deba@220	2222	/// Constructor of the InverseMap.
deba@220	2223	explicit InverseMap(const DescriptorMap& inverted)
deba@220	2224	: _inverted(inverted) {}
deba@220	2225
deba@220	2226
deba@220	2227	/// The value type of the InverseMap.
deba@220	2228	typedef typename DescriptorMap::Key Value;
deba@220	2229	/// The key type of the InverseMap.
deba@220	2230	typedef typename DescriptorMap::Value Key;
deba@220	2231
deba@220	2232	/// \brief Subscript operator.
deba@220	2233	///
deba@220	2234	/// Subscript operator. It gives back the item
deba@220	2235	/// that the descriptor belongs to currently.
deba@220	2236	Value operator[](const Key& key) const {
deba@220	2237	return _inverted(key);
deba@220	2238	}
deba@220	2239
deba@220	2240	/// \brief Size of the map.
deba@220	2241	///
deba@220	2242	/// Returns the size of the map.
deba@220	2243	unsigned int size() const {
deba@220	2244	return _inverted.size();
deba@220	2245	}
deba@220	2246
deba@220	2247	private:
deba@220	2248	const DescriptorMap& _inverted;
deba@220	2249	};
deba@220	2250
deba@220	2251	/// \brief Gives back the inverse of the map.
deba@220	2252	///
deba@220	2253	/// Gives back the inverse of the map.
deba@220	2254	const InverseMap inverse() const {
deba@220	2255	return InverseMap(*this);
deba@220	2256	}
deba@220	2257	};
deba@220	2258
deba@220	2259	/// \brief Returns the source of the given arc.
deba@220	2260	///
deba@220	2261	/// The SourceMap gives back the source Node of the given arc.
deba@220	2262	/// \see TargetMap
deba@220	2263	template <typename Digraph>
deba@220	2264	class SourceMap {
deba@220	2265	public:
deba@220	2266
deba@220	2267	typedef typename Digraph::Node Value;
deba@220	2268	typedef typename Digraph::Arc Key;
deba@220	2269
deba@220	2270	/// \brief Constructor
deba@220	2271	///
deba@220	2272	/// Constructor
deba@220	2273	/// \param _digraph The digraph that the map belongs to.
deba@220	2274	explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
deba@220	2275
deba@220	2276	/// \brief The subscript operator.
deba@220	2277	///
deba@220	2278	/// The subscript operator.
deba@220	2279	/// \param arc The arc
deba@220	2280	/// \return The source of the arc
deba@220	2281	Value operator[](const Key& arc) const {
deba@220	2282	return _digraph.source(arc);
deba@220	2283	}
deba@220	2284
deba@220	2285	private:
deba@220	2286	const Digraph& _digraph;
deba@220	2287	};
deba@220	2288
deba@220	2289	/// \brief Returns a \ref SourceMap class.
deba@220	2290	///
deba@220	2291	/// This function just returns an \ref SourceMap class.
deba@220	2292	/// \relates SourceMap
deba@220	2293	template <typename Digraph>
deba@220	2294	inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
deba@220	2295	return SourceMap<Digraph>(digraph);
deba@220	2296	}
deba@220	2297
deba@220	2298	/// \brief Returns the target of the given arc.
deba@220	2299	///
deba@220	2300	/// The TargetMap gives back the target Node of the given arc.
deba@220	2301	/// \see SourceMap
deba@220	2302	template <typename Digraph>
deba@220	2303	class TargetMap {
deba@220	2304	public:
deba@220	2305
deba@220	2306	typedef typename Digraph::Node Value;
deba@220	2307	typedef typename Digraph::Arc Key;
deba@220	2308
deba@220	2309	/// \brief Constructor
deba@220	2310	///
deba@220	2311	/// Constructor
deba@220	2312	/// \param _digraph The digraph that the map belongs to.
deba@220	2313	explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
deba@220	2314
deba@220	2315	/// \brief The subscript operator.
deba@220	2316	///
deba@220	2317	/// The subscript operator.
deba@220	2318	/// \param e The arc
deba@220	2319	/// \return The target of the arc
deba@220	2320	Value operator[](const Key& e) const {
deba@220	2321	return _digraph.target(e);
deba@220	2322	}
deba@220	2323
deba@220	2324	private:
deba@220	2325	const Digraph& _digraph;
deba@220	2326	};
deba@220	2327
deba@220	2328	/// \brief Returns a \ref TargetMap class.
deba@220	2329	///
deba@220	2330	/// This function just returns a \ref TargetMap class.
deba@220	2331	/// \relates TargetMap
deba@220	2332	template <typename Digraph>
deba@220	2333	inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
deba@220	2334	return TargetMap<Digraph>(digraph);
deba@220	2335	}
deba@220	2336
deba@220	2337	/// \brief Returns the "forward" directed arc view of an edge.
deba@220	2338	///
deba@220	2339	/// Returns the "forward" directed arc view of an edge.
deba@220	2340	/// \see BackwardMap
deba@220	2341	template <typename Graph>
deba@220	2342	class ForwardMap {
deba@220	2343	public:
deba@220	2344
deba@220	2345	typedef typename Graph::Arc Value;
deba@220	2346	typedef typename Graph::Edge Key;
deba@220	2347
deba@220	2348	/// \brief Constructor
deba@220	2349	///
deba@220	2350	/// Constructor
deba@220	2351	/// \param _graph The graph that the map belongs to.
deba@220	2352	explicit ForwardMap(const Graph& graph) : _graph(graph) {}
deba@220	2353
deba@220	2354	/// \brief The subscript operator.
deba@220	2355	///
deba@220	2356	/// The subscript operator.
deba@220	2357	/// \param key An edge
deba@220	2358	/// \return The "forward" directed arc view of edge
deba@220	2359	Value operator[](const Key& key) const {
deba@220	2360	return _graph.direct(key, true);
deba@220	2361	}
deba@220	2362
deba@220	2363	private:
deba@220	2364	const Graph& _graph;
deba@220	2365	};
deba@220	2366
deba@220	2367	/// \brief Returns a \ref ForwardMap class.
deba@220	2368	///
deba@220	2369	/// This function just returns an \ref ForwardMap class.
deba@220	2370	/// \relates ForwardMap
deba@220	2371	template <typename Graph>
deba@220	2372	inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@220	2373	return ForwardMap<Graph>(graph);
deba@220	2374	}
deba@220	2375
deba@220	2376	/// \brief Returns the "backward" directed arc view of an edge.
deba@220	2377	///
deba@220	2378	/// Returns the "backward" directed arc view of an edge.
deba@220	2379	/// \see ForwardMap
deba@220	2380	template <typename Graph>
deba@220	2381	class BackwardMap {
deba@220	2382	public:
deba@220	2383
deba@220	2384	typedef typename Graph::Arc Value;
deba@220	2385	typedef typename Graph::Edge Key;
deba@220	2386
deba@220	2387	/// \brief Constructor
deba@220	2388	///
deba@220	2389	/// Constructor
deba@220	2390	/// \param _graph The graph that the map belongs to.
deba@220	2391	explicit BackwardMap(const Graph& graph) : _graph(graph) {}
deba@220	2392
deba@220	2393	/// \brief The subscript operator.
deba@220	2394	///
deba@220	2395	/// The subscript operator.
deba@220	2396	/// \param key An edge
deba@220	2397	/// \return The "backward" directed arc view of edge
deba@220	2398	Value operator[](const Key& key) const {
deba@220	2399	return _graph.direct(key, false);
deba@220	2400	}
deba@220	2401
deba@220	2402	private:
deba@220	2403	const Graph& _graph;
deba@220	2404	};
deba@220	2405
deba@220	2406	/// \brief Returns a \ref BackwardMap class
deba@220	2407
deba@220	2408	/// This function just returns a \ref BackwardMap class.
deba@220	2409	/// \relates BackwardMap
deba@220	2410	template <typename Graph>
deba@220	2411	inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@220	2412	return BackwardMap<Graph>(graph);
deba@220	2413	}
deba@220	2414
deba@220	2415	/// \brief Potential difference map
deba@220	2416	///
deba@220	2417	/// If there is an potential map on the nodes then we
deba@220	2418	/// can get an arc map as we get the substraction of the
deba@220	2419	/// values of the target and source.
deba@220	2420	template <typename Digraph, typename NodeMap>
deba@220	2421	class PotentialDifferenceMap {
deba@220	2422	public:
deba@220	2423	typedef typename Digraph::Arc Key;
deba@220	2424	typedef typename NodeMap::Value Value;
deba@220	2425
deba@220	2426	/// \brief Constructor
deba@220	2427	///
deba@220	2428	/// Contructor of the map
deba@220	2429	explicit PotentialDifferenceMap(const Digraph& digraph,
deba@220	2430	const NodeMap& potential)
deba@220	2431	: _digraph(digraph), _potential(potential) {}
deba@220	2432
deba@220	2433	/// \brief Const subscription operator
deba@220	2434	///
deba@220	2435	/// Const subscription operator
deba@220	2436	Value operator[](const Key& arc) const {
deba@220	2437	return _potential[_digraph.target(arc)] -
deba@220	2438	_potential[_digraph.source(arc)];
deba@220	2439	}
deba@220	2440
deba@220	2441	private:
deba@220	2442	const Digraph& _digraph;
deba@220	2443	const NodeMap& _potential;
deba@220	2444	};
deba@220	2445
deba@220	2446	/// \brief Returns a PotentialDifferenceMap.
deba@220	2447	///
deba@220	2448	/// This function just returns a PotentialDifferenceMap.
deba@220	2449	/// \relates PotentialDifferenceMap
deba@220	2450	template <typename Digraph, typename NodeMap>
deba@220	2451	PotentialDifferenceMap<Digraph, NodeMap>
deba@220	2452	potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
deba@220	2453	return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
deba@220	2454	}
deba@220	2455
deba@220	2456	/// \brief Map of the node in-degrees.
deba@220	2457	///
deba@220	2458	/// This map returns the in-degree of a node. Once it is constructed,
deba@220	2459	/// the degrees are stored in a standard NodeMap, so each query is done
deba@220	2460	/// in constant time. On the other hand, the values are updated automatically
deba@220	2461	/// whenever the digraph changes.
deba@220	2462	///
deba@220	2463	/// \warning Besides addNode() and addArc(), a digraph structure may provide
deba@220	2464	/// alternative ways to modify the digraph. The correct behavior of InDegMap
deba@220	2465	/// is not guarantied if these additional features are used. For example
deba@220	2466	/// the functions \ref ListDigraph::changeSource() "changeSource()",
deba@220	2467	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	2468	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	2469	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	2470	///
deba@220	2471	/// \sa OutDegMap
deba@220	2472
deba@220	2473	template <typename _Digraph>
deba@220	2474	class InDegMap
deba@220	2475	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
deba@220	2476	::ItemNotifier::ObserverBase {
deba@220	2477
deba@220	2478	public:
deba@220	2479
deba@220	2480	typedef _Digraph Digraph;
deba@220	2481	typedef int Value;
deba@220	2482	typedef typename Digraph::Node Key;
deba@220	2483
deba@220	2484	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	2485	::ItemNotifier::ObserverBase Parent;
deba@220	2486
deba@220	2487	private:
deba@220	2488
deba@220	2489	class AutoNodeMap
deba@220	2490	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	2491	public:
deba@220	2492
deba@220	2493	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	2494	template Map<int>::Type Parent;
deba@220	2495
deba@220	2496	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	2497
deba@220	2498	virtual void add(const Key& key) {
deba@220	2499	Parent::add(key);
deba@220	2500	Parent::set(key, 0);
deba@220	2501	}
deba@220	2502
deba@220	2503	virtual void add(const std::vector<Key>& keys) {
deba@220	2504	Parent::add(keys);
deba@220	2505	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2506	Parent::set(keys[i], 0);
deba@220	2507	}
deba@220	2508	}
deba@220	2509
deba@220	2510	virtual void build() {
deba@220	2511	Parent::build();
deba@220	2512	Key it;
deba@220	2513	typename Parent::Notifier* nf = Parent::notifier();
deba@220	2514	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2515	Parent::set(it, 0);
deba@220	2516	}
deba@220	2517	}
deba@220	2518	};
deba@220	2519
deba@220	2520	public:
deba@220	2521
deba@220	2522	/// \brief Constructor.
deba@220	2523	///
deba@220	2524	/// Constructor for creating in-degree map.
deba@220	2525	explicit InDegMap(const Digraph& digraph)
deba@220	2526	: _digraph(digraph), _deg(digraph) {
deba@220	2527	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	2528
deba@220	2529	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2530	_deg[it] = countInArcs(_digraph, it);
deba@220	2531	}
deba@220	2532	}
deba@220	2533
deba@220	2534	/// Gives back the in-degree of a Node.
deba@220	2535	int operator[](const Key& key) const {
deba@220	2536	return _deg[key];
deba@220	2537	}
deba@220	2538
deba@220	2539	protected:
deba@220	2540
deba@220	2541	typedef typename Digraph::Arc Arc;
deba@220	2542
deba@220	2543	virtual void add(const Arc& arc) {
deba@220	2544	++_deg[_digraph.target(arc)];
deba@220	2545	}
deba@220	2546
deba@220	2547	virtual void add(const std::vector<Arc>& arcs) {
deba@220	2548	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2549	++_deg[_digraph.target(arcs[i])];
deba@220	2550	}
deba@220	2551	}
deba@220	2552
deba@220	2553	virtual void erase(const Arc& arc) {
deba@220	2554	--_deg[_digraph.target(arc)];
deba@220	2555	}
deba@220	2556
deba@220	2557	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	2558	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2559	--_deg[_digraph.target(arcs[i])];
deba@220	2560	}
deba@220	2561	}
deba@220	2562
deba@220	2563	virtual void build() {
deba@220	2564	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2565	_deg[it] = countInArcs(_digraph, it);
deba@220	2566	}
deba@220	2567	}
deba@220	2568
deba@220	2569	virtual void clear() {
deba@220	2570	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2571	_deg[it] = 0;
deba@220	2572	}
deba@220	2573	}
deba@220	2574	private:
deba@220	2575
deba@220	2576	const Digraph& _digraph;
deba@220	2577	AutoNodeMap _deg;
deba@220	2578	};
deba@220	2579
deba@220	2580	/// \brief Map of the node out-degrees.
deba@220	2581	///
deba@220	2582	/// This map returns the out-degree of a node. Once it is constructed,
deba@220	2583	/// the degrees are stored in a standard NodeMap, so each query is done
deba@220	2584	/// in constant time. On the other hand, the values are updated automatically
deba@220	2585	/// whenever the digraph changes.
deba@220	2586	///
deba@220	2587	/// \warning Besides addNode() and addArc(), a digraph structure may provide
deba@220	2588	/// alternative ways to modify the digraph. The correct behavior of OutDegMap
deba@220	2589	/// is not guarantied if these additional features are used. For example
deba@220	2590	/// the functions \ref ListDigraph::changeSource() "changeSource()",
deba@220	2591	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	2592	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	2593	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	2594	///
deba@220	2595	/// \sa InDegMap
deba@220	2596
deba@220	2597	template <typename _Digraph>
deba@220	2598	class OutDegMap
deba@220	2599	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
deba@220	2600	::ItemNotifier::ObserverBase {
deba@220	2601
deba@220	2602	public:
deba@220	2603
deba@220	2604	typedef _Digraph Digraph;
deba@220	2605	typedef int Value;
deba@220	2606	typedef typename Digraph::Node Key;
deba@220	2607
deba@220	2608	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	2609	::ItemNotifier::ObserverBase Parent;
deba@220	2610
deba@220	2611	private:
deba@220	2612
deba@220	2613	class AutoNodeMap
deba@220	2614	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	2615	public:
deba@220	2616
deba@220	2617	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	2618	template Map<int>::Type Parent;
deba@220	2619
deba@220	2620	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	2621
deba@220	2622	virtual void add(const Key& key) {
deba@220	2623	Parent::add(key);
deba@220	2624	Parent::set(key, 0);
deba@220	2625	}
deba@220	2626	virtual void add(const std::vector<Key>& keys) {
deba@220	2627	Parent::add(keys);
deba@220	2628	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2629	Parent::set(keys[i], 0);
deba@220	2630	}
deba@220	2631	}
deba@220	2632	virtual void build() {
deba@220	2633	Parent::build();
deba@220	2634	Key it;
deba@220	2635	typename Parent::Notifier* nf = Parent::notifier();
deba@220	2636	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2637	Parent::set(it, 0);
deba@220	2638	}
deba@220	2639	}
deba@220	2640	};
deba@220	2641
deba@220	2642	public:
deba@220	2643
deba@220	2644	/// \brief Constructor.
deba@220	2645	///
deba@220	2646	/// Constructor for creating out-degree map.
deba@220	2647	explicit OutDegMap(const Digraph& digraph)
deba@220	2648	: _digraph(digraph), _deg(digraph) {
deba@220	2649	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	2650
deba@220	2651	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2652	_deg[it] = countOutArcs(_digraph, it);
deba@220	2653	}
deba@220	2654	}
deba@220	2655
deba@220	2656	/// Gives back the out-degree of a Node.
deba@220	2657	int operator[](const Key& key) const {
deba@220	2658	return _deg[key];
deba@220	2659	}
deba@220	2660
deba@220	2661	protected:
deba@220	2662
deba@220	2663	typedef typename Digraph::Arc Arc;
deba@220	2664
deba@220	2665	virtual void add(const Arc& arc) {
deba@220	2666	++_deg[_digraph.source(arc)];
deba@220	2667	}
deba@220	2668
deba@220	2669	virtual void add(const std::vector<Arc>& arcs) {
deba@220	2670	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2671	++_deg[_digraph.source(arcs[i])];
deba@220	2672	}
deba@220	2673	}
deba@220	2674
deba@220	2675	virtual void erase(const Arc& arc) {
deba@220	2676	--_deg[_digraph.source(arc)];
deba@220	2677	}
deba@220	2678
deba@220	2679	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	2680	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2681	--_deg[_digraph.source(arcs[i])];
deba@220	2682	}
deba@220	2683	}
deba@220	2684
deba@220	2685	virtual void build() {
deba@220	2686	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2687	_deg[it] = countOutArcs(_digraph, it);
deba@220	2688	}
deba@220	2689	}
deba@220	2690
deba@220	2691	virtual void clear() {
deba@220	2692	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2693	_deg[it] = 0;
deba@220	2694	}
deba@220	2695	}
deba@220	2696	private:
deba@220	2697
deba@220	2698	const Digraph& _digraph;
deba@220	2699	AutoNodeMap _deg;
deba@220	2700	};
deba@220	2701
alpar@25	2702	/// @}
alpar@25	2703	}
alpar@25	2704
alpar@25	2705	#endif // LEMON_MAPS_H

author	Akos Ladanyi <ladanyi@tmit.bme.hu>
	Sun, 21 Sep 2008 14:46:01 +0100
changeset 266	112ed801139d
parent 209	765619b7cbb2
child 280	e7f8647ce760
permissions	-rw-r--r--