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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Mon, 12 Jan 2009 08:18:04 +0100
changeset 465	2b5496c62ccd
parent 314	2cc60866a0c9
child 559	c5fd2d996909
permissions	-rw-r--r--