lemon-main: lemon/maps.h@a4d499904482 (annotated)

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
alpar@25	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
alpar@25	4	*
alpar@39	5	* Copyright (C) 2003-2008
alpar@25	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25	8	*
alpar@25	9	* Permission to use, modify and distribute this software is granted
alpar@25	10	* provided that this copyright notice appears in all copies. For
alpar@25	11	* precise terms see the accompanying LICENSE file.
alpar@25	12	*
alpar@25	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@25	14	* express or implied, and with no claim as to its suitability for any
alpar@25	15	* purpose.
alpar@25	16	*
alpar@25	17	*/
alpar@25	18
alpar@25	19	#ifndef LEMON_MAPS_H
alpar@25	20	#define LEMON_MAPS_H
alpar@25	21
alpar@25	22	#include <iterator>
alpar@25	23	#include <functional>
alpar@25	24	#include <vector>
alpar@25	25
deba@220	26	#include <lemon/core.h>
alpar@25	27
alpar@25	28	///\file
alpar@25	29	///\ingroup maps
alpar@25	30	///\brief Miscellaneous property maps
kpeter@80	31
alpar@25	32	#include <map>
alpar@25	33
alpar@25	34	namespace lemon {
alpar@25	35
alpar@25	36	/// \addtogroup maps
alpar@25	37	/// @{
alpar@25	38
alpar@25	39	/// Base class of maps.
alpar@25	40
kpeter@80	41	/// Base class of maps. It provides the necessary type definitions
kpeter@80	42	/// required by the map %concepts.
kpeter@80	43	template<typename K, typename V>
alpar@25	44	class MapBase {
alpar@25	45	public:
kpeter@80	46	/// \biref The key type of the map.
alpar@25	47	typedef K Key;
kpeter@80	48	/// \brief The value type of the map.
kpeter@80	49	/// (The type of objects associated with the keys).
kpeter@80	50	typedef V Value;
alpar@25	51	};
alpar@25	52
kpeter@80	53
alpar@25	54	/// Null map. (a.k.a. DoNothingMap)
alpar@25	55
kpeter@29	56	/// This map can be used if you have to provide a map only for
kpeter@80	57	/// its type definitions, or if you have to provide a writable map,
kpeter@80	58	/// but data written to it is not required (i.e. it will be sent to
kpeter@29	59	/// <tt>/dev/null</tt>).
kpeter@80	60	/// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80	61	///
kpeter@80	62	/// \sa ConstMap
kpeter@80	63	template<typename K, typename V>
kpeter@80	64	class NullMap : public MapBase<K, V> {
alpar@25	65	public:
kpeter@80	66	typedef MapBase<K, V> Parent;
alpar@25	67	typedef typename Parent::Key Key;
alpar@25	68	typedef typename Parent::Value Value;
kpeter@80	69
alpar@25	70	/// Gives back a default constructed element.
kpeter@80	71	Value operator[](const Key&) const { return Value(); }
alpar@25	72	/// Absorbs the value.
kpeter@80	73	void set(const Key&, const Value&) {}
alpar@25	74	};
alpar@25	75
kpeter@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
alpar@104	1686	/// \brief Writable bool map for logging each \c true assigned element
alpar@104	1687	///
kpeter@159	1688	/// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104	1689	/// each \c true assigned element, i.e it copies subsequently each
alpar@104	1690	/// keys set to \c true to the given iterator.
kpeter@159	1691	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1692	/// that were marked \c true by an algorithm.
alpar@104	1693	///
kpeter@159	1694	/// There are several algorithms that provide solutions through bool
kpeter@159	1695	/// maps and most of them assign \c true at most once for each key.
kpeter@159	1696	/// In these cases it is a natural request to store each \c true
kpeter@159	1697	/// assigned elements (in order of the assignment), which can be
kpeter@167	1698	/// easily done with LoggerBoolMap.
kpeter@159	1699	///
kpeter@167	1700	/// The simplest way of using this map is through the loggerBoolMap()
kpeter@159	1701	/// function.
kpeter@159	1702	///
kpeter@159	1703	/// \tparam It The type of the iterator.
kpeter@159	1704	/// \tparam Ke The key type of the map. The default value set
kpeter@159	1705	/// according to the iterator type should work in most cases.
alpar@104	1706	///
alpar@104	1707	/// \note The container of the iterator must contain enough space
kpeter@159	1708	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1709	#ifdef DOXYGEN
kpeter@159	1710	template <typename It, typename Ke>
kpeter@159	1711	#else
alpar@104	1712	template <typename It,
alpar@209	1713	typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
kpeter@159	1714	#endif
kpeter@167	1715	class LoggerBoolMap {
alpar@104	1716	public:
alpar@104	1717	typedef It Iterator;
alpar@104	1718
alpar@104	1719	typedef Ke Key;
alpar@104	1720	typedef bool Value;
alpar@104	1721
alpar@104	1722	/// Constructor
kpeter@167	1723	LoggerBoolMap(Iterator it)
alpar@104	1724	: _begin(it), _end(it) {}
alpar@104	1725
alpar@104	1726	/// Gives back the given iterator set for the first key
alpar@104	1727	Iterator begin() const {
alpar@104	1728	return _begin;
alpar@104	1729	}
alpar@104	1730
alpar@104	1731	/// Gives back the the 'after the last' iterator
alpar@104	1732	Iterator end() const {
alpar@104	1733	return _end;
alpar@104	1734	}
alpar@104	1735
alpar@104	1736	/// The set function of the map
kpeter@159	1737	void set(const Key& key, Value value) {
alpar@104	1738	if (value) {
alpar@209	1739	*_end++ = key;
alpar@104	1740	}
alpar@104	1741	}
alpar@104	1742
alpar@104	1743	private:
alpar@104	1744	Iterator _begin;
kpeter@159	1745	Iterator _end;
alpar@104	1746	};
alpar@209	1747
kpeter@301	1748	/// Returns a \c LoggerBoolMap class
kpeter@301	1749
kpeter@301	1750	/// This function just returns a \c LoggerBoolMap class.
kpeter@159	1751	///
kpeter@159	1752	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1753	/// that were marked \c true by an algorithm.
kpeter@159	1754	/// For example it makes easier to store the nodes in the processing
kpeter@159	1755	/// order of Dfs algorithm, as the following examples show.
kpeter@159	1756	/// \code
kpeter@159	1757	/// std::vector<Node> v;
kpeter@167	1758	/// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@159	1759	/// \endcode
kpeter@159	1760	/// \code
kpeter@159	1761	/// std::vector<Node> v(countNodes(g));
kpeter@167	1762	/// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
kpeter@159	1763	/// \endcode
kpeter@159	1764	///
kpeter@159	1765	/// \note The container of the iterator must contain enough space
kpeter@159	1766	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1767	///
kpeter@167	1768	/// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@159	1769	/// it cannot be used when a readable map is needed, for example as
kpeter@301	1770	/// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
kpeter@159	1771	///
kpeter@167	1772	/// \relates LoggerBoolMap
kpeter@159	1773	template<typename Iterator>
kpeter@167	1774	inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167	1775	return LoggerBoolMap<Iterator>(it);
kpeter@159	1776	}
alpar@104	1777
deba@220	1778	/// Provides an immutable and unique id for each item in the graph.
deba@220	1779
deba@220	1780	/// The IdMap class provides a unique and immutable id for each item of the
deba@220	1781	/// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
deba@220	1782	/// different items (nodes) get different ids <li>\b immutable: the id of an
deba@220	1783	/// item (node) does not change (even if you delete other nodes). </ul>
deba@220	1784	/// Through this map you get access (i.e. can read) the inner id values of
deba@220	1785	/// the items stored in the graph. This map can be inverted with its member
deba@220	1786	/// class \c InverseMap or with the \c operator() member.
deba@220	1787	///
deba@220	1788	template <typename _Graph, typename _Item>
deba@220	1789	class IdMap {
deba@220	1790	public:
deba@220	1791	typedef _Graph Graph;
deba@220	1792	typedef int Value;
deba@220	1793	typedef _Item Item;
deba@220	1794	typedef _Item Key;
deba@220	1795
deba@220	1796	/// \brief Constructor.
deba@220	1797	///
deba@220	1798	/// Constructor of the map.
deba@220	1799	explicit IdMap(const Graph& graph) : _graph(&graph) {}
deba@220	1800
deba@220	1801	/// \brief Gives back the \e id of the item.
deba@220	1802	///
deba@220	1803	/// Gives back the immutable and unique \e id of the item.
deba@220	1804	int operator[](const Item& item) const { return _graph->id(item);}
deba@220	1805
deba@220	1806	/// \brief Gives back the item by its id.
deba@220	1807	///
deba@220	1808	/// Gives back the item by its id.
deba@220	1809	Item operator()(int id) { return _graph->fromId(id, Item()); }
deba@220	1810
deba@220	1811	private:
deba@220	1812	const Graph* _graph;
deba@220	1813
deba@220	1814	public:
deba@220	1815
deba@220	1816	/// \brief The class represents the inverse of its owner (IdMap).
deba@220	1817	///
deba@220	1818	/// The class represents the inverse of its owner (IdMap).
deba@220	1819	/// \see inverse()
deba@220	1820	class InverseMap {
deba@220	1821	public:
deba@220	1822
deba@220	1823	/// \brief Constructor.
deba@220	1824	///
deba@220	1825	/// Constructor for creating an id-to-item map.
deba@220	1826	explicit InverseMap(const Graph& graph) : _graph(&graph) {}
deba@220	1827
deba@220	1828	/// \brief Constructor.
deba@220	1829	///
deba@220	1830	/// Constructor for creating an id-to-item map.
deba@220	1831	explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
deba@220	1832
deba@220	1833	/// \brief Gives back the given item from its id.
deba@220	1834	///
deba@220	1835	/// Gives back the given item from its id.
deba@220	1836	///
deba@220	1837	Item operator[](int id) const { return _graph->fromId(id, Item());}
deba@220	1838
deba@220	1839	private:
deba@220	1840	const Graph* _graph;
deba@220	1841	};
deba@220	1842
deba@220	1843	/// \brief Gives back the inverse of the map.
deba@220	1844	///
deba@220	1845	/// Gives back the inverse of the IdMap.
deba@220	1846	InverseMap inverse() const { return InverseMap(*_graph);}
deba@220	1847
deba@220	1848	};
deba@220	1849
deba@220	1850
deba@220	1851	/// \brief General invertable graph-map type.
deba@220	1852
deba@220	1853	/// This type provides simple invertable graph-maps.
deba@220	1854	/// The InvertableMap wraps an arbitrary ReadWriteMap
deba@220	1855	/// and if a key is set to a new value then store it
deba@220	1856	/// in the inverse map.
deba@220	1857	///
deba@220	1858	/// The values of the map can be accessed
deba@220	1859	/// with stl compatible forward iterator.
deba@220	1860	///
deba@220	1861	/// \tparam _Graph The graph type.
deba@220	1862	/// \tparam _Item The item type of the graph.
deba@220	1863	/// \tparam _Value The value type of the map.
deba@220	1864	///
deba@220	1865	/// \see IterableValueMap
deba@220	1866	template <typename _Graph, typename _Item, typename _Value>
deba@220	1867	class InvertableMap
deba@220	1868	: protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
deba@220	1869	private:
deba@220	1870
deba@220	1871	typedef typename ItemSetTraits<_Graph, _Item>::
deba@220	1872	template Map<_Value>::Type Map;
deba@220	1873	typedef _Graph Graph;
deba@220	1874
deba@220	1875	typedef std::map<_Value, _Item> Container;
deba@220	1876	Container _inv_map;
deba@220	1877
deba@220	1878	public:
deba@220	1879
deba@220	1880	/// The key type of InvertableMap (Node, Arc, Edge).
deba@220	1881	typedef typename Map::Key Key;
deba@220	1882	/// The value type of the InvertableMap.
deba@220	1883	typedef typename Map::Value Value;
deba@220	1884
deba@220	1885
deba@220	1886
deba@220	1887	/// \brief Constructor.
deba@220	1888	///
deba@220	1889	/// Construct a new InvertableMap for the graph.
deba@220	1890	///
deba@220	1891	explicit InvertableMap(const Graph& graph) : Map(graph) {}
deba@220	1892
deba@220	1893	/// \brief Forward iterator for values.
deba@220	1894	///
deba@220	1895	/// This iterator is an stl compatible forward
deba@220	1896	/// iterator on the values of the map. The values can
deba@220	1897	/// be accessed in the [beginValue, endValue) range.
deba@220	1898	///
deba@220	1899	class ValueIterator
deba@220	1900	: public std::iterator<std::forward_iterator_tag, Value> {
deba@220	1901	friend class InvertableMap;
deba@220	1902	private:
deba@220	1903	ValueIterator(typename Container::const_iterator _it)
deba@220	1904	: it(_it) {}
deba@220	1905	public:
deba@220	1906
deba@220	1907	ValueIterator() {}
deba@220	1908
deba@220	1909	ValueIterator& operator++() { ++it; return *this; }
deba@220	1910	ValueIterator operator++(int) {
deba@220	1911	ValueIterator tmp(*this);
deba@220	1912	operator++();
deba@220	1913	return tmp;
deba@220	1914	}
deba@220	1915
deba@220	1916	const Value& operator*() const { return it->first; }
deba@220	1917	const Value* operator->() const { return &(it->first); }
deba@220	1918
deba@220	1919	bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@220	1920	bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@220	1921
deba@220	1922	private:
deba@220	1923	typename Container::const_iterator it;
deba@220	1924	};
deba@220	1925
deba@220	1926	/// \brief Returns an iterator to the first value.
deba@220	1927	///
deba@220	1928	/// Returns an stl compatible iterator to the
deba@220	1929	/// first value of the map. The values of the
deba@220	1930	/// map can be accessed in the [beginValue, endValue)
deba@220	1931	/// range.
deba@220	1932	ValueIterator beginValue() const {
deba@220	1933	return ValueIterator(_inv_map.begin());
deba@220	1934	}
deba@220	1935
deba@220	1936	/// \brief Returns an iterator after the last value.
deba@220	1937	///
deba@220	1938	/// Returns an stl compatible iterator after the
deba@220	1939	/// last value of the map. The values of the
deba@220	1940	/// map can be accessed in the [beginValue, endValue)
deba@220	1941	/// range.
deba@220	1942	ValueIterator endValue() const {
deba@220	1943	return ValueIterator(_inv_map.end());
deba@220	1944	}
deba@220	1945
deba@220	1946	/// \brief The setter function of the map.
deba@220	1947	///
deba@220	1948	/// Sets the mapped value.
deba@220	1949	void set(const Key& key, const Value& val) {
deba@220	1950	Value oldval = Map::operator[](key);
deba@220	1951	typename Container::iterator it = _inv_map.find(oldval);
deba@220	1952	if (it != _inv_map.end() && it->second == key) {
deba@220	1953	_inv_map.erase(it);
deba@220	1954	}
deba@220	1955	_inv_map.insert(make_pair(val, key));
deba@220	1956	Map::set(key, val);
deba@220	1957	}
deba@220	1958
deba@220	1959	/// \brief The getter function of the map.
deba@220	1960	///
deba@220	1961	/// It gives back the value associated with the key.
deba@220	1962	typename MapTraits<Map>::ConstReturnValue
deba@220	1963	operator[](const Key& key) const {
deba@220	1964	return Map::operator[](key);
deba@220	1965	}
deba@220	1966
deba@220	1967	/// \brief Gives back the item by its value.
deba@220	1968	///
deba@220	1969	/// Gives back the item by its value.
deba@220	1970	Key operator()(const Value& key) const {
deba@220	1971	typename Container::const_iterator it = _inv_map.find(key);
deba@220	1972	return it != _inv_map.end() ? it->second : INVALID;
deba@220	1973	}
deba@220	1974
deba@220	1975	protected:
deba@220	1976
deba@220	1977	/// \brief Erase the key from the map.
deba@220	1978	///
deba@220	1979	/// Erase the key to the map. It is called by the
deba@220	1980	/// \c AlterationNotifier.
deba@220	1981	virtual void erase(const Key& key) {
deba@220	1982	Value val = Map::operator[](key);
deba@220	1983	typename Container::iterator it = _inv_map.find(val);
deba@220	1984	if (it != _inv_map.end() && it->second == key) {
deba@220	1985	_inv_map.erase(it);
deba@220	1986	}
deba@220	1987	Map::erase(key);
deba@220	1988	}
deba@220	1989
deba@220	1990	/// \brief Erase more keys from the map.
deba@220	1991	///
deba@220	1992	/// Erase more keys from the map. It is called by the
deba@220	1993	/// \c AlterationNotifier.
deba@220	1994	virtual void erase(const std::vector<Key>& keys) {
deba@220	1995	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	1996	Value val = Map::operator[](keys[i]);
deba@220	1997	typename Container::iterator it = _inv_map.find(val);
deba@220	1998	if (it != _inv_map.end() && it->second == keys[i]) {
deba@220	1999	_inv_map.erase(it);
deba@220	2000	}
deba@220	2001	}
deba@220	2002	Map::erase(keys);
deba@220	2003	}
deba@220	2004
deba@220	2005	/// \brief Clear the keys from the map and inverse map.
deba@220	2006	///
deba@220	2007	/// Clear the keys from the map and inverse map. It is called by the
deba@220	2008	/// \c AlterationNotifier.
deba@220	2009	virtual void clear() {
deba@220	2010	_inv_map.clear();
deba@220	2011	Map::clear();
deba@220	2012	}
deba@220	2013
deba@220	2014	public:
deba@220	2015
deba@220	2016	/// \brief The inverse map type.
deba@220	2017	///
deba@220	2018	/// The inverse of this map. The subscript operator of the map
deba@220	2019	/// gives back always the item what was last assigned to the value.
deba@220	2020	class InverseMap {
deba@220	2021	public:
deba@220	2022	/// \brief Constructor of the InverseMap.
deba@220	2023	///
deba@220	2024	/// Constructor of the InverseMap.
deba@220	2025	explicit InverseMap(const InvertableMap& inverted)
deba@220	2026	: _inverted(inverted) {}
deba@220	2027
deba@220	2028	/// The value type of the InverseMap.
deba@220	2029	typedef typename InvertableMap::Key Value;
deba@220	2030	/// The key type of the InverseMap.
deba@220	2031	typedef typename InvertableMap::Value Key;
deba@220	2032
deba@220	2033	/// \brief Subscript operator.
deba@220	2034	///
deba@220	2035	/// Subscript operator. It gives back always the item
deba@220	2036	/// what was last assigned to the value.
deba@220	2037	Value operator[](const Key& key) const {
deba@220	2038	return _inverted(key);
deba@220	2039	}
deba@220	2040
deba@220	2041	private:
deba@220	2042	const InvertableMap& _inverted;
deba@220	2043	};
deba@220	2044
deba@220	2045	/// \brief It gives back the just readable inverse map.
deba@220	2046	///
deba@220	2047	/// It gives back the just readable inverse map.
deba@220	2048	InverseMap inverse() const {
deba@220	2049	return InverseMap(*this);
deba@220	2050	}
deba@220	2051
deba@220	2052
deba@220	2053
deba@220	2054	};
deba@220	2055
deba@220	2056	/// \brief Provides a mutable, continuous and unique descriptor for each
deba@220	2057	/// item in the graph.
deba@220	2058	///
deba@220	2059	/// The DescriptorMap class provides a unique and continuous (but mutable)
deba@220	2060	/// descriptor (id) for each item of the same type (e.g. node) in the
deba@220	2061	/// graph. This id is <ul><li>\b unique: different items (nodes) get
deba@220	2062	/// different ids <li>\b continuous: the range of the ids is the set of
deba@220	2063	/// integers between 0 and \c n-1, where \c n is the number of the items of
deba@220	2064	/// this type (e.g. nodes) (so the id of a node can change if you delete an
deba@220	2065	/// other node, i.e. this id is mutable). </ul> This map can be inverted
deba@220	2066	/// with its member class \c InverseMap, or with the \c operator() member.
deba@220	2067	///
deba@220	2068	/// \tparam _Graph The graph class the \c DescriptorMap belongs to.
deba@220	2069	/// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
deba@220	2070	/// Edge.
deba@220	2071	template <typename _Graph, typename _Item>
deba@220	2072	class DescriptorMap
deba@220	2073	: protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
deba@220	2074
deba@220	2075	typedef _Item Item;
deba@220	2076	typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
deba@220	2077
deba@220	2078	public:
deba@220	2079	/// The graph class of DescriptorMap.
deba@220	2080	typedef _Graph Graph;
deba@220	2081
deba@220	2082	/// The key type of DescriptorMap (Node, Arc, Edge).
deba@220	2083	typedef typename Map::Key Key;
deba@220	2084	/// The value type of DescriptorMap.
deba@220	2085	typedef typename Map::Value Value;
deba@220	2086
deba@220	2087	/// \brief Constructor.
deba@220	2088	///
deba@220	2089	/// Constructor for descriptor map.
deba@220	2090	explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
deba@220	2091	Item it;
deba@220	2092	const typename Map::Notifier* nf = Map::notifier();
deba@220	2093	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2094	Map::set(it, _inv_map.size());
deba@220	2095	_inv_map.push_back(it);
deba@220	2096	}
deba@220	2097	}
deba@220	2098
deba@220	2099	protected:
deba@220	2100
deba@220	2101	/// \brief Add a new key to the map.
deba@220	2102	///
deba@220	2103	/// Add a new key to the map. It is called by the
deba@220	2104	/// \c AlterationNotifier.
deba@220	2105	virtual void add(const Item& item) {
deba@220	2106	Map::add(item);
deba@220	2107	Map::set(item, _inv_map.size());
deba@220	2108	_inv_map.push_back(item);
deba@220	2109	}
deba@220	2110
deba@220	2111	/// \brief Add more new keys to the map.
deba@220	2112	///
deba@220	2113	/// Add more new keys to the map. It is called by the
deba@220	2114	/// \c AlterationNotifier.
deba@220	2115	virtual void add(const std::vector<Item>& items) {
deba@220	2116	Map::add(items);
deba@220	2117	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2118	Map::set(items[i], _inv_map.size());
deba@220	2119	_inv_map.push_back(items[i]);
deba@220	2120	}
deba@220	2121	}
deba@220	2122
deba@220	2123	/// \brief Erase the key from the map.
deba@220	2124	///
deba@220	2125	/// Erase the key from the map. It is called by the
deba@220	2126	/// \c AlterationNotifier.
deba@220	2127	virtual void erase(const Item& item) {
deba@220	2128	Map::set(_inv_map.back(), Map::operator[](item));
deba@220	2129	_inv_map[Map::operator[](item)] = _inv_map.back();
deba@220	2130	_inv_map.pop_back();
deba@220	2131	Map::erase(item);
deba@220	2132	}
deba@220	2133
deba@220	2134	/// \brief Erase more keys from the map.
deba@220	2135	///
deba@220	2136	/// Erase more keys from the map. It is called by the
deba@220	2137	/// \c AlterationNotifier.
deba@220	2138	virtual void erase(const std::vector<Item>& items) {
deba@220	2139	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2140	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@220	2141	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@220	2142	_inv_map.pop_back();
deba@220	2143	}
deba@220	2144	Map::erase(items);
deba@220	2145	}
deba@220	2146
deba@220	2147	/// \brief Build the unique map.
deba@220	2148	///
deba@220	2149	/// Build the unique map. It is called by the
deba@220	2150	/// \c AlterationNotifier.
deba@220	2151	virtual void build() {
deba@220	2152	Map::build();
deba@220	2153	Item it;
deba@220	2154	const typename Map::Notifier* nf = Map::notifier();
deba@220	2155	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2156	Map::set(it, _inv_map.size());
deba@220	2157	_inv_map.push_back(it);
deba@220	2158	}
deba@220	2159	}
deba@220	2160
deba@220	2161	/// \brief Clear the keys from the map.
deba@220	2162	///
deba@220	2163	/// Clear the keys from the map. It is called by the
deba@220	2164	/// \c AlterationNotifier.
deba@220	2165	virtual void clear() {
deba@220	2166	_inv_map.clear();
deba@220	2167	Map::clear();
deba@220	2168	}
deba@220	2169
deba@220	2170	public:
deba@220	2171
deba@220	2172	/// \brief Returns the maximal value plus one.
deba@220	2173	///
deba@220	2174	/// Returns the maximal value plus one in the map.
deba@220	2175	unsigned int size() const {
deba@220	2176	return _inv_map.size();
deba@220	2177	}
deba@220	2178
deba@220	2179	/// \brief Swaps the position of the two items in the map.
deba@220	2180	///
deba@220	2181	/// Swaps the position of the two items in the map.
deba@220	2182	void swap(const Item& p, const Item& q) {
deba@220	2183	int pi = Map::operator[](p);
deba@220	2184	int qi = Map::operator[](q);
deba@220	2185	Map::set(p, qi);
deba@220	2186	_inv_map[qi] = p;
deba@220	2187	Map::set(q, pi);
deba@220	2188	_inv_map[pi] = q;
deba@220	2189	}
deba@220	2190
deba@220	2191	/// \brief Gives back the \e descriptor of the item.
deba@220	2192	///
deba@220	2193	/// Gives back the mutable and unique \e descriptor of the map.
deba@220	2194	int operator[](const Item& item) const {
deba@220	2195	return Map::operator[](item);
deba@220	2196	}
deba@220	2197
deba@220	2198	/// \brief Gives back the item by its descriptor.
deba@220	2199	///
deba@220	2200	/// Gives back th item by its descriptor.
deba@220	2201	Item operator()(int id) const {
deba@220	2202	return _inv_map[id];
deba@220	2203	}
deba@220	2204
deba@220	2205	private:
deba@220	2206
deba@220	2207	typedef std::vector<Item> Container;
deba@220	2208	Container _inv_map;
deba@220	2209
deba@220	2210	public:
deba@220	2211	/// \brief The inverse map type of DescriptorMap.
deba@220	2212	///
deba@220	2213	/// The inverse map type of DescriptorMap.
deba@220	2214	class InverseMap {
deba@220	2215	public:
deba@220	2216	/// \brief Constructor of the InverseMap.
deba@220	2217	///
deba@220	2218	/// Constructor of the InverseMap.
deba@220	2219	explicit InverseMap(const DescriptorMap& inverted)
deba@220	2220	: _inverted(inverted) {}
deba@220	2221
deba@220	2222
deba@220	2223	/// The value type of the InverseMap.
deba@220	2224	typedef typename DescriptorMap::Key Value;
deba@220	2225	/// The key type of the InverseMap.
deba@220	2226	typedef typename DescriptorMap::Value Key;
deba@220	2227
deba@220	2228	/// \brief Subscript operator.
deba@220	2229	///
deba@220	2230	/// Subscript operator. It gives back the item
deba@220	2231	/// that the descriptor belongs to currently.
deba@220	2232	Value operator[](const Key& key) const {
deba@220	2233	return _inverted(key);
deba@220	2234	}
deba@220	2235
deba@220	2236	/// \brief Size of the map.
deba@220	2237	///
deba@220	2238	/// Returns the size of the map.
deba@220	2239	unsigned int size() const {
deba@220	2240	return _inverted.size();
deba@220	2241	}
deba@220	2242
deba@220	2243	private:
deba@220	2244	const DescriptorMap& _inverted;
deba@220	2245	};
deba@220	2246
deba@220	2247	/// \brief Gives back the inverse of the map.
deba@220	2248	///
deba@220	2249	/// Gives back the inverse of the map.
deba@220	2250	const InverseMap inverse() const {
deba@220	2251	return InverseMap(*this);
deba@220	2252	}
deba@220	2253	};
deba@220	2254
deba@220	2255	/// \brief Returns the source of the given arc.
deba@220	2256	///
deba@220	2257	/// The SourceMap gives back the source Node of the given arc.
deba@220	2258	/// \see TargetMap
deba@220	2259	template <typename Digraph>
deba@220	2260	class SourceMap {
deba@220	2261	public:
deba@220	2262
deba@220	2263	typedef typename Digraph::Node Value;
deba@220	2264	typedef typename Digraph::Arc Key;
deba@220	2265
deba@220	2266	/// \brief Constructor
deba@220	2267	///
deba@220	2268	/// Constructor
deba@220	2269	/// \param _digraph The digraph that the map belongs to.
deba@220	2270	explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
deba@220	2271
deba@220	2272	/// \brief The subscript operator.
deba@220	2273	///
deba@220	2274	/// The subscript operator.
deba@220	2275	/// \param arc The arc
deba@220	2276	/// \return The source of the arc
deba@220	2277	Value operator[](const Key& arc) const {
deba@220	2278	return _digraph.source(arc);
deba@220	2279	}
deba@220	2280
deba@220	2281	private:
deba@220	2282	const Digraph& _digraph;
deba@220	2283	};
deba@220	2284
kpeter@301	2285	/// \brief Returns a \c SourceMap class.
deba@220	2286	///
kpeter@301	2287	/// This function just returns an \c SourceMap class.
deba@220	2288	/// \relates SourceMap
deba@220	2289	template <typename Digraph>
deba@220	2290	inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
deba@220	2291	return SourceMap<Digraph>(digraph);
deba@220	2292	}
deba@220	2293
deba@220	2294	/// \brief Returns the target of the given arc.
deba@220	2295	///
deba@220	2296	/// The TargetMap gives back the target Node of the given arc.
deba@220	2297	/// \see SourceMap
deba@220	2298	template <typename Digraph>
deba@220	2299	class TargetMap {
deba@220	2300	public:
deba@220	2301
deba@220	2302	typedef typename Digraph::Node Value;
deba@220	2303	typedef typename Digraph::Arc Key;
deba@220	2304
deba@220	2305	/// \brief Constructor
deba@220	2306	///
deba@220	2307	/// Constructor
deba@220	2308	/// \param _digraph The digraph that the map belongs to.
deba@220	2309	explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
deba@220	2310
deba@220	2311	/// \brief The subscript operator.
deba@220	2312	///
deba@220	2313	/// The subscript operator.
deba@220	2314	/// \param e The arc
deba@220	2315	/// \return The target of the arc
deba@220	2316	Value operator[](const Key& e) const {
deba@220	2317	return _digraph.target(e);
deba@220	2318	}
deba@220	2319
deba@220	2320	private:
deba@220	2321	const Digraph& _digraph;
deba@220	2322	};
deba@220	2323
kpeter@301	2324	/// \brief Returns a \c TargetMap class.
deba@220	2325	///
kpeter@301	2326	/// This function just returns a \c TargetMap class.
deba@220	2327	/// \relates TargetMap
deba@220	2328	template <typename Digraph>
deba@220	2329	inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
deba@220	2330	return TargetMap<Digraph>(digraph);
deba@220	2331	}
deba@220	2332
deba@220	2333	/// \brief Returns the "forward" directed arc view of an edge.
deba@220	2334	///
deba@220	2335	/// Returns the "forward" directed arc view of an edge.
deba@220	2336	/// \see BackwardMap
deba@220	2337	template <typename Graph>
deba@220	2338	class ForwardMap {
deba@220	2339	public:
deba@220	2340
deba@220	2341	typedef typename Graph::Arc Value;
deba@220	2342	typedef typename Graph::Edge Key;
deba@220	2343
deba@220	2344	/// \brief Constructor
deba@220	2345	///
deba@220	2346	/// Constructor
deba@220	2347	/// \param _graph The graph that the map belongs to.
deba@220	2348	explicit ForwardMap(const Graph& graph) : _graph(graph) {}
deba@220	2349
deba@220	2350	/// \brief The subscript operator.
deba@220	2351	///
deba@220	2352	/// The subscript operator.
deba@220	2353	/// \param key An edge
deba@220	2354	/// \return The "forward" directed arc view of edge
deba@220	2355	Value operator[](const Key& key) const {
deba@220	2356	return _graph.direct(key, true);
deba@220	2357	}
deba@220	2358
deba@220	2359	private:
deba@220	2360	const Graph& _graph;
deba@220	2361	};
deba@220	2362
kpeter@301	2363	/// \brief Returns a \c ForwardMap class.
deba@220	2364	///
kpeter@301	2365	/// This function just returns an \c ForwardMap class.
deba@220	2366	/// \relates ForwardMap
deba@220	2367	template <typename Graph>
deba@220	2368	inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@220	2369	return ForwardMap<Graph>(graph);
deba@220	2370	}
deba@220	2371
deba@220	2372	/// \brief Returns the "backward" directed arc view of an edge.
deba@220	2373	///
deba@220	2374	/// Returns the "backward" directed arc view of an edge.
deba@220	2375	/// \see ForwardMap
deba@220	2376	template <typename Graph>
deba@220	2377	class BackwardMap {
deba@220	2378	public:
deba@220	2379
deba@220	2380	typedef typename Graph::Arc Value;
deba@220	2381	typedef typename Graph::Edge Key;
deba@220	2382
deba@220	2383	/// \brief Constructor
deba@220	2384	///
deba@220	2385	/// Constructor
deba@220	2386	/// \param _graph The graph that the map belongs to.
deba@220	2387	explicit BackwardMap(const Graph& graph) : _graph(graph) {}
deba@220	2388
deba@220	2389	/// \brief The subscript operator.
deba@220	2390	///
deba@220	2391	/// The subscript operator.
deba@220	2392	/// \param key An edge
deba@220	2393	/// \return The "backward" directed arc view of edge
deba@220	2394	Value operator[](const Key& key) const {
deba@220	2395	return _graph.direct(key, false);
deba@220	2396	}
deba@220	2397
deba@220	2398	private:
deba@220	2399	const Graph& _graph;
deba@220	2400	};
deba@220	2401
kpeter@301	2402	/// \brief Returns a \c BackwardMap class
kpeter@301	2403
kpeter@301	2404	/// This function just returns a \c BackwardMap class.
deba@220	2405	/// \relates BackwardMap
deba@220	2406	template <typename Graph>
deba@220	2407	inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@220	2408	return BackwardMap<Graph>(graph);
deba@220	2409	}
deba@220	2410
deba@220	2411	/// \brief Potential difference map
deba@220	2412	///
deba@220	2413	/// If there is an potential map on the nodes then we
deba@220	2414	/// can get an arc map as we get the substraction of the
deba@220	2415	/// values of the target and source.
deba@220	2416	template <typename Digraph, typename NodeMap>
deba@220	2417	class PotentialDifferenceMap {
deba@220	2418	public:
deba@220	2419	typedef typename Digraph::Arc Key;
deba@220	2420	typedef typename NodeMap::Value Value;
deba@220	2421
deba@220	2422	/// \brief Constructor
deba@220	2423	///
deba@220	2424	/// Contructor of the map
deba@220	2425	explicit PotentialDifferenceMap(const Digraph& digraph,
deba@220	2426	const NodeMap& potential)
deba@220	2427	: _digraph(digraph), _potential(potential) {}
deba@220	2428
deba@220	2429	/// \brief Const subscription operator
deba@220	2430	///
deba@220	2431	/// Const subscription operator
deba@220	2432	Value operator[](const Key& arc) const {
deba@220	2433	return _potential[_digraph.target(arc)] -
deba@220	2434	_potential[_digraph.source(arc)];
deba@220	2435	}
deba@220	2436
deba@220	2437	private:
deba@220	2438	const Digraph& _digraph;
deba@220	2439	const NodeMap& _potential;
deba@220	2440	};
deba@220	2441
deba@220	2442	/// \brief Returns a PotentialDifferenceMap.
deba@220	2443	///
deba@220	2444	/// This function just returns a PotentialDifferenceMap.
deba@220	2445	/// \relates PotentialDifferenceMap
deba@220	2446	template <typename Digraph, typename NodeMap>
deba@220	2447	PotentialDifferenceMap<Digraph, NodeMap>
deba@220	2448	potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
deba@220	2449	return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
deba@220	2450	}
deba@220	2451
deba@220	2452	/// \brief Map of the node in-degrees.
deba@220	2453	///
deba@220	2454	/// This map returns the in-degree of a node. Once it is constructed,
deba@220	2455	/// the degrees are stored in a standard NodeMap, so each query is done
deba@220	2456	/// in constant time. On the other hand, the values are updated automatically
deba@220	2457	/// whenever the digraph changes.
deba@220	2458	///
deba@220	2459	/// \warning Besides addNode() and addArc(), a digraph structure may provide
deba@220	2460	/// alternative ways to modify the digraph. The correct behavior of InDegMap
deba@220	2461	/// is not guarantied if these additional features are used. For example
deba@220	2462	/// the functions \ref ListDigraph::changeSource() "changeSource()",
deba@220	2463	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	2464	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	2465	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	2466	///
deba@220	2467	/// \sa OutDegMap
deba@220	2468
deba@220	2469	template <typename _Digraph>
deba@220	2470	class InDegMap
deba@220	2471	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
deba@220	2472	::ItemNotifier::ObserverBase {
deba@220	2473
deba@220	2474	public:
deba@220	2475
deba@220	2476	typedef _Digraph Digraph;
deba@220	2477	typedef int Value;
deba@220	2478	typedef typename Digraph::Node Key;
deba@220	2479
deba@220	2480	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	2481	::ItemNotifier::ObserverBase Parent;
deba@220	2482
deba@220	2483	private:
deba@220	2484
deba@220	2485	class AutoNodeMap
deba@220	2486	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	2487	public:
deba@220	2488
deba@220	2489	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	2490	template Map<int>::Type Parent;
deba@220	2491
deba@220	2492	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	2493
deba@220	2494	virtual void add(const Key& key) {
deba@220	2495	Parent::add(key);
deba@220	2496	Parent::set(key, 0);
deba@220	2497	}
deba@220	2498
deba@220	2499	virtual void add(const std::vector<Key>& keys) {
deba@220	2500	Parent::add(keys);
deba@220	2501	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2502	Parent::set(keys[i], 0);
deba@220	2503	}
deba@220	2504	}
deba@220	2505
deba@220	2506	virtual void build() {
deba@220	2507	Parent::build();
deba@220	2508	Key it;
deba@220	2509	typename Parent::Notifier* nf = Parent::notifier();
deba@220	2510	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2511	Parent::set(it, 0);
deba@220	2512	}
deba@220	2513	}
deba@220	2514	};
deba@220	2515
deba@220	2516	public:
deba@220	2517
deba@220	2518	/// \brief Constructor.
deba@220	2519	///
deba@220	2520	/// Constructor for creating in-degree map.
deba@220	2521	explicit InDegMap(const Digraph& digraph)
deba@220	2522	: _digraph(digraph), _deg(digraph) {
deba@220	2523	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	2524
deba@220	2525	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2526	_deg[it] = countInArcs(_digraph, it);
deba@220	2527	}
deba@220	2528	}
deba@220	2529
deba@220	2530	/// Gives back the in-degree of a Node.
deba@220	2531	int operator[](const Key& key) const {
deba@220	2532	return _deg[key];
deba@220	2533	}
deba@220	2534
deba@220	2535	protected:
deba@220	2536
deba@220	2537	typedef typename Digraph::Arc Arc;
deba@220	2538
deba@220	2539	virtual void add(const Arc& arc) {
deba@220	2540	++_deg[_digraph.target(arc)];
deba@220	2541	}
deba@220	2542
deba@220	2543	virtual void add(const std::vector<Arc>& arcs) {
deba@220	2544	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2545	++_deg[_digraph.target(arcs[i])];
deba@220	2546	}
deba@220	2547	}
deba@220	2548
deba@220	2549	virtual void erase(const Arc& arc) {
deba@220	2550	--_deg[_digraph.target(arc)];
deba@220	2551	}
deba@220	2552
deba@220	2553	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	2554	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2555	--_deg[_digraph.target(arcs[i])];
deba@220	2556	}
deba@220	2557	}
deba@220	2558
deba@220	2559	virtual void build() {
deba@220	2560	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2561	_deg[it] = countInArcs(_digraph, it);
deba@220	2562	}
deba@220	2563	}
deba@220	2564
deba@220	2565	virtual void clear() {
deba@220	2566	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2567	_deg[it] = 0;
deba@220	2568	}
deba@220	2569	}
deba@220	2570	private:
deba@220	2571
deba@220	2572	const Digraph& _digraph;
deba@220	2573	AutoNodeMap _deg;
deba@220	2574	};
deba@220	2575
deba@220	2576	/// \brief Map of the node out-degrees.
deba@220	2577	///
deba@220	2578	/// This map returns the out-degree of a node. Once it is constructed,
deba@220	2579	/// the degrees are stored in a standard NodeMap, so each query is done
deba@220	2580	/// in constant time. On the other hand, the values are updated automatically
deba@220	2581	/// whenever the digraph changes.
deba@220	2582	///
deba@220	2583	/// \warning Besides addNode() and addArc(), a digraph structure may provide
deba@220	2584	/// alternative ways to modify the digraph. The correct behavior of OutDegMap
deba@220	2585	/// is not guarantied if these additional features are used. For example
deba@220	2586	/// the functions \ref ListDigraph::changeSource() "changeSource()",
deba@220	2587	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	2588	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	2589	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	2590	///
deba@220	2591	/// \sa InDegMap
deba@220	2592
deba@220	2593	template <typename _Digraph>
deba@220	2594	class OutDegMap
deba@220	2595	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
deba@220	2596	::ItemNotifier::ObserverBase {
deba@220	2597
deba@220	2598	public:
deba@220	2599
deba@220	2600	typedef _Digraph Digraph;
deba@220	2601	typedef int Value;
deba@220	2602	typedef typename Digraph::Node Key;
deba@220	2603
deba@220	2604	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	2605	::ItemNotifier::ObserverBase Parent;
deba@220	2606
deba@220	2607	private:
deba@220	2608
deba@220	2609	class AutoNodeMap
deba@220	2610	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	2611	public:
deba@220	2612
deba@220	2613	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	2614	template Map<int>::Type Parent;
deba@220	2615
deba@220	2616	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	2617
deba@220	2618	virtual void add(const Key& key) {
deba@220	2619	Parent::add(key);
deba@220	2620	Parent::set(key, 0);
deba@220	2621	}
deba@220	2622	virtual void add(const std::vector<Key>& keys) {
deba@220	2623	Parent::add(keys);
deba@220	2624	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2625	Parent::set(keys[i], 0);
deba@220	2626	}
deba@220	2627	}
deba@220	2628	virtual void build() {
deba@220	2629	Parent::build();
deba@220	2630	Key it;
deba@220	2631	typename Parent::Notifier* nf = Parent::notifier();
deba@220	2632	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2633	Parent::set(it, 0);
deba@220	2634	}
deba@220	2635	}
deba@220	2636	};
deba@220	2637
deba@220	2638	public:
deba@220	2639
deba@220	2640	/// \brief Constructor.
deba@220	2641	///
deba@220	2642	/// Constructor for creating out-degree map.
deba@220	2643	explicit OutDegMap(const Digraph& digraph)
deba@220	2644	: _digraph(digraph), _deg(digraph) {
deba@220	2645	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	2646
deba@220	2647	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2648	_deg[it] = countOutArcs(_digraph, it);
deba@220	2649	}
deba@220	2650	}
deba@220	2651
deba@220	2652	/// Gives back the out-degree of a Node.
deba@220	2653	int operator[](const Key& key) const {
deba@220	2654	return _deg[key];
deba@220	2655	}
deba@220	2656
deba@220	2657	protected:
deba@220	2658
deba@220	2659	typedef typename Digraph::Arc Arc;
deba@220	2660
deba@220	2661	virtual void add(const Arc& arc) {
deba@220	2662	++_deg[_digraph.source(arc)];
deba@220	2663	}
deba@220	2664
deba@220	2665	virtual void add(const std::vector<Arc>& arcs) {
deba@220	2666	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2667	++_deg[_digraph.source(arcs[i])];
deba@220	2668	}
deba@220	2669	}
deba@220	2670
deba@220	2671	virtual void erase(const Arc& arc) {
deba@220	2672	--_deg[_digraph.source(arc)];
deba@220	2673	}
deba@220	2674
deba@220	2675	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	2676	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	2677	--_deg[_digraph.source(arcs[i])];
deba@220	2678	}
deba@220	2679	}
deba@220	2680
deba@220	2681	virtual void build() {
deba@220	2682	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2683	_deg[it] = countOutArcs(_digraph, it);
deba@220	2684	}
deba@220	2685	}
deba@220	2686
deba@220	2687	virtual void clear() {
deba@220	2688	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	2689	_deg[it] = 0;
deba@220	2690	}
deba@220	2691	}
deba@220	2692	private:
deba@220	2693
deba@220	2694	const Digraph& _digraph;
deba@220	2695	AutoNodeMap _deg;
deba@220	2696	};
deba@220	2697
alpar@25	2698	/// @}
alpar@25	2699	}
alpar@25	2700
alpar@25	2701	#endif // LEMON_MAPS_H

author	Alpar Juttner <alpar@cs.elte.hu>
	Thu, 09 Oct 2008 13:40:40 +0100
changeset 312	a4d499904482
parent 280	e7f8647ce760
child 313	64f8f7cc6168
permissions	-rw-r--r--