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

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
alpar@25	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
alpar@25	4	*
alpar@440	5	* Copyright (C) 2003-2009
alpar@25	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25	8	*
alpar@25	9	* Permission to use, modify and distribute this software is granted
alpar@25	10	* provided that this copyright notice appears in all copies. For
alpar@25	11	* precise terms see the accompanying LICENSE file.
alpar@25	12	*
alpar@25	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@25	14	* express or implied, and with no claim as to its suitability for any
alpar@25	15	* purpose.
alpar@25	16	*
alpar@25	17	*/
alpar@25	18
alpar@25	19	#ifndef LEMON_MAPS_H
alpar@25	20	#define LEMON_MAPS_H
alpar@25	21
alpar@25	22	#include <iterator>
alpar@25	23	#include <functional>
alpar@25	24	#include <vector>
alpar@25	25
deba@220	26	#include <lemon/core.h>
deba@693	27	#include <lemon/smart_graph.h>
alpar@25	28
alpar@25	29	///\file
alpar@25	30	///\ingroup maps
alpar@25	31	///\brief Miscellaneous property maps
kpeter@80	32
alpar@25	33	#include <map>
alpar@25	34
alpar@25	35	namespace lemon {
alpar@25	36
alpar@25	37	/// \addtogroup maps
alpar@25	38	/// @{
alpar@25	39
alpar@25	40	/// Base class of maps.
alpar@25	41
kpeter@80	42	/// Base class of maps. It provides the necessary type definitions
kpeter@80	43	/// required by the map %concepts.
kpeter@80	44	template<typename K, typename V>
alpar@25	45	class MapBase {
alpar@25	46	public:
kpeter@313	47	/// \brief The key type of the map.
alpar@25	48	typedef K Key;
kpeter@80	49	/// \brief The value type of the map.
kpeter@80	50	/// (The type of objects associated with the keys).
kpeter@80	51	typedef V Value;
alpar@25	52	};
alpar@25	53
kpeter@80	54
alpar@25	55	/// Null map. (a.k.a. DoNothingMap)
alpar@25	56
kpeter@29	57	/// This map can be used if you have to provide a map only for
kpeter@80	58	/// its type definitions, or if you have to provide a writable map,
kpeter@80	59	/// but data written to it is not required (i.e. it will be sent to
kpeter@29	60	/// <tt>/dev/null</tt>).
kpeter@80	61	/// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80	62	///
kpeter@80	63	/// \sa ConstMap
kpeter@80	64	template<typename K, typename V>
kpeter@80	65	class NullMap : public MapBase<K, V> {
alpar@25	66	public:
kpeter@559	67	///\e
kpeter@559	68	typedef K Key;
kpeter@559	69	///\e
kpeter@559	70	typedef V Value;
kpeter@80	71
alpar@25	72	/// Gives back a default constructed element.
kpeter@80	73	Value operator[](const Key&) const { return Value(); }
alpar@25	74	/// Absorbs the value.
kpeter@80	75	void set(const Key&, const Value&) {}
alpar@25	76	};
alpar@25	77
kpeter@301	78	/// Returns a \c NullMap class
kpeter@301	79
kpeter@301	80	/// This function just returns a \c NullMap class.
kpeter@80	81	/// \relates NullMap
kpeter@80	82	template <typename K, typename V>
alpar@25	83	NullMap<K, V> nullMap() {
alpar@25	84	return NullMap<K, V>();
alpar@25	85	}
alpar@25	86
alpar@25	87
alpar@25	88	/// Constant map.
alpar@25	89
kpeter@82	90	/// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82	91	/// value to each key.
kpeter@80	92	///
kpeter@301	93	/// In other aspects it is equivalent to \c NullMap.
kpeter@80	94	/// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80	95	/// concept, but it absorbs the data written to it.
kpeter@80	96	///
kpeter@80	97	/// The simplest way of using this map is through the constMap()
kpeter@80	98	/// function.
kpeter@80	99	///
kpeter@80	100	/// \sa NullMap
kpeter@80	101	/// \sa IdentityMap
kpeter@80	102	template<typename K, typename V>
kpeter@80	103	class ConstMap : public MapBase<K, V> {
alpar@25	104	private:
kpeter@80	105	V _value;
alpar@25	106	public:
kpeter@559	107	///\e
kpeter@559	108	typedef K Key;
kpeter@559	109	///\e
kpeter@559	110	typedef V Value;
alpar@25	111
alpar@25	112	/// Default constructor
alpar@25	113
kpeter@29	114	/// Default constructor.
kpeter@80	115	/// The value of the map will be default constructed.
alpar@25	116	ConstMap() {}
kpeter@80	117
kpeter@29	118	/// Constructor with specified initial value
alpar@25	119
kpeter@29	120	/// Constructor with specified initial value.
kpeter@123	121	/// \param v The initial value of the map.
kpeter@80	122	ConstMap(const Value &v) : _value(v) {}
alpar@25	123
kpeter@80	124	/// Gives back the specified value.
kpeter@80	125	Value operator[](const Key&) const { return _value; }
alpar@25	126
kpeter@80	127	/// Absorbs the value.
kpeter@80	128	void set(const Key&, const Value&) {}
kpeter@80	129
kpeter@80	130	/// Sets the value that is assigned to each key.
kpeter@80	131	void setAll(const Value &v) {
kpeter@80	132	_value = v;
kpeter@80	133	}
kpeter@80	134
kpeter@80	135	template<typename V1>
kpeter@80	136	ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
alpar@25	137	};
alpar@25	138
kpeter@301	139	/// Returns a \c ConstMap class
kpeter@301	140
kpeter@301	141	/// This function just returns a \c ConstMap class.
kpeter@80	142	/// \relates ConstMap
kpeter@80	143	template<typename K, typename V>
alpar@25	144	inline ConstMap<K, V> constMap(const V &v) {
alpar@25	145	return ConstMap<K, V>(v);
alpar@25	146	}
alpar@25	147
kpeter@123	148	template<typename K, typename V>
kpeter@123	149	inline ConstMap<K, V> constMap() {
kpeter@123	150	return ConstMap<K, V>();
kpeter@123	151	}
kpeter@123	152
alpar@25	153
alpar@25	154	template<typename T, T v>
kpeter@80	155	struct Const {};
alpar@25	156
alpar@25	157	/// Constant map with inlined constant value.
alpar@25	158
kpeter@82	159	/// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82	160	/// value to each key.
kpeter@80	161	///
kpeter@301	162	/// In other aspects it is equivalent to \c NullMap.
kpeter@80	163	/// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80	164	/// concept, but it absorbs the data written to it.
kpeter@80	165	///
kpeter@80	166	/// The simplest way of using this map is through the constMap()
kpeter@80	167	/// function.
kpeter@80	168	///
kpeter@80	169	/// \sa NullMap
kpeter@80	170	/// \sa IdentityMap
alpar@25	171	template<typename K, typename V, V v>
alpar@25	172	class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
alpar@25	173	public:
kpeter@559	174	///\e
kpeter@559	175	typedef K Key;
kpeter@559	176	///\e
kpeter@559	177	typedef V Value;
alpar@25	178
kpeter@80	179	/// Constructor.
kpeter@80	180	ConstMap() {}
kpeter@80	181
kpeter@80	182	/// Gives back the specified value.
kpeter@80	183	Value operator[](const Key&) const { return v; }
kpeter@80	184
kpeter@80	185	/// Absorbs the value.
kpeter@80	186	void set(const Key&, const Value&) {}
alpar@25	187	};
alpar@25	188
kpeter@301	189	/// Returns a \c ConstMap class with inlined constant value
kpeter@301	190
kpeter@301	191	/// This function just returns a \c ConstMap class with inlined
kpeter@80	192	/// constant value.
kpeter@80	193	/// \relates ConstMap
kpeter@80	194	template<typename K, typename V, V v>
alpar@25	195	inline ConstMap<K, Const<V, v> > constMap() {
alpar@25	196	return ConstMap<K, Const<V, v> >();
alpar@25	197	}
alpar@25	198
alpar@25	199
kpeter@82	200	/// Identity map.
kpeter@82	201
kpeter@82	202	/// This \ref concepts::ReadMap "read-only map" gives back the given
kpeter@82	203	/// key as value without any modification.
kpeter@80	204	///
kpeter@80	205	/// \sa ConstMap
kpeter@80	206	template <typename T>
kpeter@80	207	class IdentityMap : public MapBase<T, T> {
kpeter@80	208	public:
kpeter@559	209	///\e
kpeter@559	210	typedef T Key;
kpeter@559	211	///\e
kpeter@559	212	typedef T Value;
kpeter@80	213
kpeter@80	214	/// Gives back the given value without any modification.
kpeter@82	215	Value operator[](const Key &k) const {
kpeter@82	216	return k;
kpeter@80	217	}
kpeter@80	218	};
kpeter@80	219
kpeter@301	220	/// Returns an \c IdentityMap class
kpeter@301	221
kpeter@301	222	/// This function just returns an \c IdentityMap class.
kpeter@80	223	/// \relates IdentityMap
kpeter@80	224	template<typename T>
kpeter@80	225	inline IdentityMap<T> identityMap() {
kpeter@80	226	return IdentityMap<T>();
kpeter@80	227	}
kpeter@80	228
kpeter@80	229
kpeter@80	230	/// \brief Map for storing values for integer keys from the range
kpeter@80	231	/// <tt>[0..size-1]</tt>.
kpeter@80	232	///
kpeter@80	233	/// This map is essentially a wrapper for \c std::vector. It assigns
kpeter@80	234	/// values to integer keys from the range <tt>[0..size-1]</tt>.
kpeter@80	235	/// It can be used with some data structures, for example
kpeter@301	236	/// \c UnionFind, \c BinHeap, when the used items are small
kpeter@80	237	/// integers. This map conforms the \ref concepts::ReferenceMap
kpeter@80	238	/// "ReferenceMap" concept.
kpeter@80	239	///
kpeter@80	240	/// The simplest way of using this map is through the rangeMap()
kpeter@80	241	/// function.
kpeter@80	242	template <typename V>
kpeter@80	243	class RangeMap : public MapBase<int, V> {
kpeter@80	244	template <typename V1>
kpeter@80	245	friend class RangeMap;
kpeter@80	246	private:
kpeter@80	247
kpeter@80	248	typedef std::vector<V> Vector;
kpeter@80	249	Vector _vector;
kpeter@80	250
alpar@25	251	public:
alpar@25	252
kpeter@80	253	/// Key type
kpeter@559	254	typedef int Key;
kpeter@80	255	/// Value type
kpeter@559	256	typedef V Value;
kpeter@80	257	/// Reference type
kpeter@80	258	typedef typename Vector::reference Reference;
kpeter@80	259	/// Const reference type
kpeter@80	260	typedef typename Vector::const_reference ConstReference;
kpeter@80	261
kpeter@80	262	typedef True ReferenceMapTag;
kpeter@80	263
kpeter@80	264	public:
kpeter@80	265
kpeter@80	266	/// Constructor with specified default value.
kpeter@80	267	RangeMap(int size = 0, const Value &value = Value())
kpeter@80	268	: _vector(size, value) {}
kpeter@80	269
kpeter@80	270	/// Constructs the map from an appropriate \c std::vector.
kpeter@80	271	template <typename V1>
kpeter@80	272	RangeMap(const std::vector<V1>& vector)
kpeter@80	273	: _vector(vector.begin(), vector.end()) {}
kpeter@80	274
kpeter@301	275	/// Constructs the map from another \c RangeMap.
kpeter@80	276	template <typename V1>
kpeter@80	277	RangeMap(const RangeMap<V1> &c)
kpeter@80	278	: _vector(c._vector.begin(), c._vector.end()) {}
kpeter@80	279
kpeter@80	280	/// Returns the size of the map.
kpeter@80	281	int size() {
kpeter@80	282	return _vector.size();
kpeter@80	283	}
kpeter@80	284
kpeter@80	285	/// Resizes the map.
kpeter@80	286
kpeter@80	287	/// Resizes the underlying \c std::vector container, so changes the
kpeter@80	288	/// keyset of the map.
kpeter@80	289	/// \param size The new size of the map. The new keyset will be the
kpeter@80	290	/// range <tt>[0..size-1]</tt>.
kpeter@80	291	/// \param value The default value to assign to the new keys.
kpeter@80	292	void resize(int size, const Value &value = Value()) {
kpeter@80	293	_vector.resize(size, value);
kpeter@80	294	}
kpeter@80	295
kpeter@80	296	private:
kpeter@80	297
kpeter@80	298	RangeMap& operator=(const RangeMap&);
kpeter@80	299
kpeter@80	300	public:
kpeter@80	301
kpeter@80	302	///\e
kpeter@80	303	Reference operator[](const Key &k) {
kpeter@80	304	return _vector[k];
kpeter@80	305	}
kpeter@80	306
kpeter@80	307	///\e
kpeter@80	308	ConstReference operator[](const Key &k) const {
kpeter@80	309	return _vector[k];
kpeter@80	310	}
kpeter@80	311
kpeter@80	312	///\e
kpeter@80	313	void set(const Key &k, const Value &v) {
kpeter@80	314	_vector[k] = v;
kpeter@80	315	}
kpeter@80	316	};
kpeter@80	317
kpeter@301	318	/// Returns a \c RangeMap class
kpeter@301	319
kpeter@301	320	/// This function just returns a \c RangeMap class.
kpeter@80	321	/// \relates RangeMap
kpeter@80	322	template<typename V>
kpeter@80	323	inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
kpeter@80	324	return RangeMap<V>(size, value);
kpeter@80	325	}
kpeter@80	326
kpeter@301	327	/// \brief Returns a \c RangeMap class created from an appropriate
kpeter@80	328	/// \c std::vector
kpeter@80	329
kpeter@301	330	/// This function just returns a \c RangeMap class created from an
kpeter@80	331	/// appropriate \c std::vector.
kpeter@80	332	/// \relates RangeMap
kpeter@80	333	template<typename V>
kpeter@80	334	inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
kpeter@80	335	return RangeMap<V>(vector);
kpeter@80	336	}
kpeter@80	337
kpeter@80	338
kpeter@80	339	/// Map type based on \c std::map
kpeter@80	340
kpeter@80	341	/// This map is essentially a wrapper for \c std::map with addition
kpeter@80	342	/// that you can specify a default value for the keys that are not
kpeter@80	343	/// stored actually. This value can be different from the default
kpeter@80	344	/// contructed value (i.e. \c %Value()).
kpeter@80	345	/// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
kpeter@80	346	/// concept.
kpeter@80	347	///
kpeter@80	348	/// This map is useful if a default value should be assigned to most of
kpeter@80	349	/// the keys and different values should be assigned only to a few
kpeter@80	350	/// keys (i.e. the map is "sparse").
kpeter@80	351	/// The name of this type also refers to this important usage.
kpeter@80	352	///
kpeter@80	353	/// Apart form that this map can be used in many other cases since it
kpeter@80	354	/// is based on \c std::map, which is a general associative container.
kpeter@80	355	/// However keep in mind that it is usually not as efficient as other
kpeter@80	356	/// maps.
kpeter@80	357	///
kpeter@80	358	/// The simplest way of using this map is through the sparseMap()
kpeter@80	359	/// function.
kpeter@559	360	template <typename K, typename V, typename Comp = std::less<K> >
kpeter@80	361	class SparseMap : public MapBase<K, V> {
kpeter@80	362	template <typename K1, typename V1, typename C1>
kpeter@80	363	friend class SparseMap;
kpeter@80	364	public:
kpeter@80	365
kpeter@80	366	/// Key type
kpeter@559	367	typedef K Key;
kpeter@80	368	/// Value type
kpeter@559	369	typedef V Value;
kpeter@80	370	/// Reference type
kpeter@80	371	typedef Value& Reference;
kpeter@80	372	/// Const reference type
kpeter@80	373	typedef const Value& ConstReference;
alpar@25	374
kpeter@45	375	typedef True ReferenceMapTag;
kpeter@45	376
alpar@25	377	private:
kpeter@80	378
kpeter@559	379	typedef std::map<K, V, Comp> Map;
kpeter@80	380	Map _map;
alpar@25	381	Value _value;
alpar@25	382
alpar@25	383	public:
alpar@25	384
kpeter@80	385	/// \brief Constructor with specified default value.
kpeter@80	386	SparseMap(const Value &value = Value()) : _value(value) {}
kpeter@80	387	/// \brief Constructs the map from an appropriate \c std::map, and
kpeter@47	388	/// explicitly specifies a default value.
kpeter@80	389	template <typename V1, typename Comp1>
kpeter@80	390	SparseMap(const std::map<Key, V1, Comp1> &map,
kpeter@80	391	const Value &value = Value())
alpar@25	392	: _map(map.begin(), map.end()), _value(value) {}
kpeter@80	393
kpeter@301	394	/// \brief Constructs the map from another \c SparseMap.
kpeter@80	395	template<typename V1, typename Comp1>
kpeter@80	396	SparseMap(const SparseMap<Key, V1, Comp1> &c)
alpar@25	397	: _map(c._map.begin(), c._map.end()), _value(c._value) {}
alpar@25	398
alpar@25	399	private:
alpar@25	400
kpeter@80	401	SparseMap& operator=(const SparseMap&);
alpar@25	402
alpar@25	403	public:
alpar@25	404
alpar@25	405	///\e
alpar@25	406	Reference operator[](const Key &k) {
alpar@25	407	typename Map::iterator it = _map.lower_bound(k);
alpar@25	408	if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209	409	return it->second;
alpar@25	410	else
alpar@209	411	return _map.insert(it, std::make_pair(k, _value))->second;
alpar@25	412	}
alpar@25	413
kpeter@80	414	///\e
alpar@25	415	ConstReference operator[](const Key &k) const {
alpar@25	416	typename Map::const_iterator it = _map.find(k);
alpar@25	417	if (it != _map.end())
alpar@209	418	return it->second;
alpar@25	419	else
alpar@209	420	return _value;
alpar@25	421	}
alpar@25	422
kpeter@80	423	///\e
kpeter@80	424	void set(const Key &k, const Value &v) {
alpar@25	425	typename Map::iterator it = _map.lower_bound(k);
alpar@25	426	if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209	427	it->second = v;
alpar@25	428	else
alpar@209	429	_map.insert(it, std::make_pair(k, v));
alpar@25	430	}
alpar@25	431
kpeter@80	432	///\e
kpeter@80	433	void setAll(const Value &v) {
kpeter@80	434	_value = v;
alpar@25	435	_map.clear();
kpeter@80	436	}
kpeter@80	437	};
alpar@25	438
kpeter@301	439	/// Returns a \c SparseMap class
kpeter@301	440
kpeter@301	441	/// This function just returns a \c SparseMap class with specified
kpeter@80	442	/// default value.
kpeter@80	443	/// \relates SparseMap
kpeter@80	444	template<typename K, typename V, typename Compare>
kpeter@80	445	inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
kpeter@80	446	return SparseMap<K, V, Compare>(value);
kpeter@54	447	}
kpeter@45	448
kpeter@80	449	template<typename K, typename V>
kpeter@80	450	inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
kpeter@80	451	return SparseMap<K, V, std::less<K> >(value);
kpeter@45	452	}
alpar@25	453
kpeter@301	454	/// \brief Returns a \c SparseMap class created from an appropriate
kpeter@80	455	/// \c std::map
alpar@25	456
kpeter@301	457	/// This function just returns a \c SparseMap class created from an
kpeter@80	458	/// appropriate \c std::map.
kpeter@80	459	/// \relates SparseMap
kpeter@80	460	template<typename K, typename V, typename Compare>
kpeter@80	461	inline SparseMap<K, V, Compare>
kpeter@80	462	sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
kpeter@80	463	{
kpeter@80	464	return SparseMap<K, V, Compare>(map, value);
kpeter@45	465	}
alpar@25	466
alpar@25	467	/// @}
alpar@25	468
alpar@25	469	/// \addtogroup map_adaptors
alpar@25	470	/// @{
alpar@25	471
kpeter@80	472	/// Composition of two maps
kpeter@80	473
kpeter@82	474	/// This \ref concepts::ReadMap "read-only map" returns the
kpeter@80	475	/// composition of two given maps. That is to say, if \c m1 is of
kpeter@80	476	/// type \c M1 and \c m2 is of \c M2, then for
kpeter@80	477	/// \code
kpeter@80	478	/// ComposeMap<M1, M2> cm(m1,m2);
kpeter@80	479	/// \endcode
kpeter@80	480	/// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
alpar@25	481	///
kpeter@80	482	/// The \c Key type of the map is inherited from \c M2 and the
kpeter@80	483	/// \c Value type is from \c M1.
kpeter@80	484	/// \c M2::Value must be convertible to \c M1::Key.
kpeter@80	485	///
kpeter@80	486	/// The simplest way of using this map is through the composeMap()
kpeter@80	487	/// function.
kpeter@80	488	///
kpeter@80	489	/// \sa CombineMap
kpeter@80	490	template <typename M1, typename M2>
kpeter@80	491	class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
kpeter@80	492	const M1 &_m1;
kpeter@80	493	const M2 &_m2;
alpar@25	494	public:
kpeter@559	495	///\e
kpeter@559	496	typedef typename M2::Key Key;
kpeter@559	497	///\e
kpeter@559	498	typedef typename M1::Value Value;
alpar@25	499
kpeter@80	500	/// Constructor
kpeter@80	501	ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	502
kpeter@559	503	///\e
kpeter@80	504	typename MapTraits<M1>::ConstReturnValue
kpeter@80	505	operator[](const Key &k) const { return _m1[_m2[k]]; }
alpar@25	506	};
alpar@25	507
kpeter@301	508	/// Returns a \c ComposeMap class
kpeter@301	509
kpeter@301	510	/// This function just returns a \c ComposeMap class.
kpeter@80	511	///
kpeter@80	512	/// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
kpeter@80	513	/// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
kpeter@80	514	/// will be equal to <tt>m1[m2[x]]</tt>.
kpeter@80	515	///
kpeter@80	516	/// \relates ComposeMap
kpeter@80	517	template <typename M1, typename M2>
kpeter@80	518	inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
kpeter@80	519	return ComposeMap<M1, M2>(m1, m2);
alpar@25	520	}
alpar@25	521
kpeter@80	522
kpeter@80	523	/// Combination of two maps using an STL (binary) functor.
kpeter@80	524
kpeter@82	525	/// This \ref concepts::ReadMap "read-only map" takes two maps and a
kpeter@80	526	/// binary functor and returns the combination of the two given maps
kpeter@80	527	/// using the functor.
kpeter@80	528	/// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
kpeter@80	529	/// and \c f is of \c F, then for
kpeter@80	530	/// \code
kpeter@80	531	/// CombineMap<M1,M2,F,V> cm(m1,m2,f);
kpeter@80	532	/// \endcode
kpeter@80	533	/// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
alpar@26	534	///
kpeter@80	535	/// The \c Key type of the map is inherited from \c M1 (\c M1::Key
kpeter@80	536	/// must be convertible to \c M2::Key) and the \c Value type is \c V.
kpeter@80	537	/// \c M2::Value and \c M1::Value must be convertible to the
kpeter@80	538	/// corresponding input parameter of \c F and the return type of \c F
kpeter@80	539	/// must be convertible to \c V.
kpeter@80	540	///
kpeter@80	541	/// The simplest way of using this map is through the combineMap()
kpeter@80	542	/// function.
kpeter@80	543	///
kpeter@80	544	/// \sa ComposeMap
kpeter@80	545	template<typename M1, typename M2, typename F,
alpar@209	546	typename V = typename F::result_type>
kpeter@80	547	class CombineMap : public MapBase<typename M1::Key, V> {
kpeter@80	548	const M1 &_m1;
kpeter@80	549	const M2 &_m2;
kpeter@80	550	F _f;
alpar@25	551	public:
kpeter@559	552	///\e
kpeter@559	553	typedef typename M1::Key Key;
kpeter@559	554	///\e
kpeter@559	555	typedef V Value;
alpar@25	556
kpeter@80	557	/// Constructor
kpeter@80	558	CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
kpeter@80	559	: _m1(m1), _m2(m2), _f(f) {}
kpeter@559	560	///\e
kpeter@80	561	Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
kpeter@80	562	};
alpar@25	563
kpeter@301	564	/// Returns a \c CombineMap class
kpeter@301	565
kpeter@301	566	/// This function just returns a \c CombineMap class.
kpeter@80	567	///
kpeter@80	568	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	569	/// values, then
kpeter@80	570	/// \code
kpeter@80	571	/// combineMap(m1,m2,std::plus<double>())
kpeter@80	572	/// \endcode
kpeter@80	573	/// is equivalent to
kpeter@80	574	/// \code
kpeter@80	575	/// addMap(m1,m2)
kpeter@80	576	/// \endcode
kpeter@80	577	///
kpeter@80	578	/// This function is specialized for adaptable binary function
kpeter@80	579	/// classes and C++ functions.
kpeter@80	580	///
kpeter@80	581	/// \relates CombineMap
kpeter@80	582	template<typename M1, typename M2, typename F, typename V>
kpeter@80	583	inline CombineMap<M1, M2, F, V>
kpeter@80	584	combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80	585	return CombineMap<M1, M2, F, V>(m1,m2,f);
alpar@25	586	}
alpar@25	587
kpeter@80	588	template<typename M1, typename M2, typename F>
kpeter@80	589	inline CombineMap<M1, M2, F, typename F::result_type>
kpeter@80	590	combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80	591	return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
kpeter@80	592	}
alpar@25	593
kpeter@80	594	template<typename M1, typename M2, typename K1, typename K2, typename V>
kpeter@80	595	inline CombineMap<M1, M2, V (*)(K1, K2), V>
kpeter@80	596	combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
kpeter@80	597	return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
kpeter@80	598	}
kpeter@80	599
kpeter@80	600
kpeter@80	601	/// Converts an STL style (unary) functor to a map
kpeter@80	602
kpeter@82	603	/// This \ref concepts::ReadMap "read-only map" returns the value
kpeter@80	604	/// of a given functor. Actually, it just wraps the functor and
kpeter@80	605	/// provides the \c Key and \c Value typedefs.
alpar@26	606	///
kpeter@80	607	/// Template parameters \c K and \c V will become its \c Key and
kpeter@80	608	/// \c Value. In most cases they have to be given explicitly because
kpeter@80	609	/// a functor typically does not provide \c argument_type and
kpeter@80	610	/// \c result_type typedefs.
kpeter@80	611	/// Parameter \c F is the type of the used functor.
kpeter@29	612	///
kpeter@80	613	/// The simplest way of using this map is through the functorToMap()
kpeter@80	614	/// function.
kpeter@80	615	///
kpeter@80	616	/// \sa MapToFunctor
kpeter@80	617	template<typename F,
alpar@209	618	typename K = typename F::argument_type,
alpar@209	619	typename V = typename F::result_type>
kpeter@80	620	class FunctorToMap : public MapBase<K, V> {
kpeter@123	621	F _f;
kpeter@80	622	public:
kpeter@559	623	///\e
kpeter@559	624	typedef K Key;
kpeter@559	625	///\e
kpeter@559	626	typedef V Value;
alpar@25	627
kpeter@80	628	/// Constructor
kpeter@80	629	FunctorToMap(const F &f = F()) : _f(f) {}
kpeter@559	630	///\e
kpeter@80	631	Value operator[](const Key &k) const { return _f(k); }
kpeter@80	632	};
kpeter@80	633
kpeter@301	634	/// Returns a \c FunctorToMap class
kpeter@301	635
kpeter@301	636	/// This function just returns a \c FunctorToMap class.
kpeter@80	637	///
kpeter@80	638	/// This function is specialized for adaptable binary function
kpeter@80	639	/// classes and C++ functions.
kpeter@80	640	///
kpeter@80	641	/// \relates FunctorToMap
kpeter@80	642	template<typename K, typename V, typename F>
kpeter@80	643	inline FunctorToMap<F, K, V> functorToMap(const F &f) {
kpeter@80	644	return FunctorToMap<F, K, V>(f);
kpeter@80	645	}
kpeter@80	646
kpeter@80	647	template <typename F>
kpeter@80	648	inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
kpeter@80	649	functorToMap(const F &f)
kpeter@80	650	{
kpeter@80	651	return FunctorToMap<F, typename F::argument_type,
kpeter@80	652	typename F::result_type>(f);
kpeter@80	653	}
kpeter@80	654
kpeter@80	655	template <typename K, typename V>
kpeter@80	656	inline FunctorToMap<V ()(K), K, V> functorToMap(V (f)(K)) {
kpeter@80	657	return FunctorToMap<V (*)(K), K, V>(f);
kpeter@80	658	}
kpeter@80	659
kpeter@80	660
kpeter@80	661	/// Converts a map to an STL style (unary) functor
kpeter@80	662
kpeter@80	663	/// This class converts a map to an STL style (unary) functor.
kpeter@80	664	/// That is it provides an <tt>operator()</tt> to read its values.
kpeter@80	665	///
kpeter@80	666	/// For the sake of convenience it also works as a usual
kpeter@80	667	/// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
kpeter@80	668	/// and the \c Key and \c Value typedefs also exist.
kpeter@80	669	///
kpeter@80	670	/// The simplest way of using this map is through the mapToFunctor()
kpeter@80	671	/// function.
kpeter@80	672	///
kpeter@80	673	///\sa FunctorToMap
kpeter@80	674	template <typename M>
kpeter@80	675	class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	676	const M &_m;
alpar@25	677	public:
kpeter@559	678	///\e
kpeter@559	679	typedef typename M::Key Key;
kpeter@559	680	///\e
kpeter@559	681	typedef typename M::Value Value;
kpeter@559	682
kpeter@559	683	typedef typename M::Key argument_type;
kpeter@559	684	typedef typename M::Value result_type;
kpeter@80	685
kpeter@80	686	/// Constructor
kpeter@80	687	MapToFunctor(const M &m) : _m(m) {}
kpeter@559	688	///\e
kpeter@80	689	Value operator()(const Key &k) const { return _m[k]; }
kpeter@559	690	///\e
kpeter@80	691	Value operator[](const Key &k) const { return _m[k]; }
alpar@25	692	};
kpeter@45	693
kpeter@301	694	/// Returns a \c MapToFunctor class
kpeter@301	695
kpeter@301	696	/// This function just returns a \c MapToFunctor class.
kpeter@80	697	/// \relates MapToFunctor
kpeter@45	698	template<typename M>
kpeter@80	699	inline MapToFunctor<M> mapToFunctor(const M &m) {
kpeter@80	700	return MapToFunctor<M>(m);
kpeter@45	701	}
alpar@25	702
alpar@25	703
kpeter@80	704	/// \brief Map adaptor to convert the \c Value type of a map to
kpeter@80	705	/// another type using the default conversion.
kpeter@80	706
kpeter@80	707	/// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
kpeter@80	708	/// "readable map" to another type using the default conversion.
kpeter@80	709	/// The \c Key type of it is inherited from \c M and the \c Value
kpeter@80	710	/// type is \c V.
kpeter@80	711	/// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
alpar@26	712	///
kpeter@80	713	/// The simplest way of using this map is through the convertMap()
kpeter@80	714	/// function.
kpeter@80	715	template <typename M, typename V>
kpeter@80	716	class ConvertMap : public MapBase<typename M::Key, V> {
kpeter@80	717	const M &_m;
kpeter@80	718	public:
kpeter@559	719	///\e
kpeter@559	720	typedef typename M::Key Key;
kpeter@559	721	///\e
kpeter@559	722	typedef V Value;
kpeter@80	723
kpeter@80	724	/// Constructor
kpeter@80	725
kpeter@80	726	/// Constructor.
kpeter@80	727	/// \param m The underlying map.
kpeter@80	728	ConvertMap(const M &m) : _m(m) {}
kpeter@80	729
kpeter@559	730	///\e
kpeter@80	731	Value operator[](const Key &k) const { return _m[k]; }
kpeter@80	732	};
kpeter@80	733
kpeter@301	734	/// Returns a \c ConvertMap class
kpeter@301	735
kpeter@301	736	/// This function just returns a \c ConvertMap class.
kpeter@80	737	/// \relates ConvertMap
kpeter@80	738	template<typename V, typename M>
kpeter@80	739	inline ConvertMap<M, V> convertMap(const M &map) {
kpeter@80	740	return ConvertMap<M, V>(map);
kpeter@80	741	}
kpeter@80	742
kpeter@80	743
kpeter@80	744	/// Applies all map setting operations to two maps
kpeter@80	745
kpeter@80	746	/// This map has two \ref concepts::WriteMap "writable map" parameters
kpeter@80	747	/// and each write request will be passed to both of them.
kpeter@80	748	/// If \c M1 is also \ref concepts::ReadMap "readable", then the read
kpeter@80	749	/// operations will return the corresponding values of \c M1.
kpeter@29	750	///
kpeter@80	751	/// The \c Key and \c Value types are inherited from \c M1.
kpeter@80	752	/// The \c Key and \c Value of \c M2 must be convertible from those
kpeter@80	753	/// of \c M1.
kpeter@80	754	///
kpeter@80	755	/// The simplest way of using this map is through the forkMap()
kpeter@80	756	/// function.
kpeter@80	757	template<typename M1, typename M2>
kpeter@80	758	class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	759	M1 &_m1;
kpeter@80	760	M2 &_m2;
kpeter@80	761	public:
kpeter@559	762	///\e
kpeter@559	763	typedef typename M1::Key Key;
kpeter@559	764	///\e
kpeter@559	765	typedef typename M1::Value Value;
alpar@25	766
kpeter@80	767	/// Constructor
kpeter@80	768	ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80	769	/// Returns the value associated with the given key in the first map.
kpeter@80	770	Value operator[](const Key &k) const { return _m1[k]; }
kpeter@80	771	/// Sets the value associated with the given key in both maps.
kpeter@80	772	void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
kpeter@80	773	};
kpeter@80	774
kpeter@301	775	/// Returns a \c ForkMap class
kpeter@301	776
kpeter@301	777	/// This function just returns a \c ForkMap class.
kpeter@80	778	/// \relates ForkMap
kpeter@80	779	template <typename M1, typename M2>
kpeter@80	780	inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
kpeter@80	781	return ForkMap<M1,M2>(m1,m2);
kpeter@80	782	}
kpeter@80	783
kpeter@80	784
kpeter@80	785	/// Sum of two maps
kpeter@80	786
kpeter@82	787	/// This \ref concepts::ReadMap "read-only map" returns the sum
kpeter@80	788	/// of the values of the two given maps.
kpeter@80	789	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	790	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	791	/// \c M1.
kpeter@80	792	///
kpeter@80	793	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	794	/// \code
kpeter@80	795	/// AddMap<M1,M2> am(m1,m2);
kpeter@80	796	/// \endcode
kpeter@80	797	/// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
kpeter@80	798	///
kpeter@80	799	/// The simplest way of using this map is through the addMap()
kpeter@80	800	/// function.
kpeter@80	801	///
kpeter@80	802	/// \sa SubMap, MulMap, DivMap
kpeter@80	803	/// \sa ShiftMap, ShiftWriteMap
kpeter@80	804	template<typename M1, typename M2>
alpar@25	805	class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	806	const M1 &_m1;
kpeter@80	807	const M2 &_m2;
alpar@25	808	public:
kpeter@559	809	///\e
kpeter@559	810	typedef typename M1::Key Key;
kpeter@559	811	///\e
kpeter@559	812	typedef typename M1::Value Value;
alpar@25	813
kpeter@80	814	/// Constructor
kpeter@80	815	AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	816	///\e
kpeter@80	817	Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
alpar@25	818	};
alpar@25	819
kpeter@301	820	/// Returns an \c AddMap class
kpeter@301	821
kpeter@301	822	/// This function just returns an \c AddMap class.
alpar@25	823	///
kpeter@80	824	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	825	/// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
kpeter@80	826	/// <tt>m1[x]+m2[x]</tt>.
kpeter@80	827	///
kpeter@80	828	/// \relates AddMap
kpeter@80	829	template<typename M1, typename M2>
kpeter@80	830	inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
alpar@25	831	return AddMap<M1, M2>(m1,m2);
alpar@25	832	}
alpar@25	833
alpar@25	834
kpeter@80	835	/// Difference of two maps
kpeter@80	836
kpeter@82	837	/// This \ref concepts::ReadMap "read-only map" returns the difference
kpeter@80	838	/// of the values of the two given maps.
kpeter@80	839	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	840	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	841	/// \c M1.
alpar@25	842	///
kpeter@80	843	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	844	/// \code
kpeter@80	845	/// SubMap<M1,M2> sm(m1,m2);
kpeter@80	846	/// \endcode
kpeter@80	847	/// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
kpeter@29	848	///
kpeter@80	849	/// The simplest way of using this map is through the subMap()
kpeter@80	850	/// function.
kpeter@80	851	///
kpeter@80	852	/// \sa AddMap, MulMap, DivMap
kpeter@80	853	template<typename M1, typename M2>
kpeter@80	854	class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	855	const M1 &_m1;
kpeter@80	856	const M2 &_m2;
kpeter@80	857	public:
kpeter@559	858	///\e
kpeter@559	859	typedef typename M1::Key Key;
kpeter@559	860	///\e
kpeter@559	861	typedef typename M1::Value Value;
kpeter@80	862
kpeter@80	863	/// Constructor
kpeter@80	864	SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	865	///\e
kpeter@80	866	Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
kpeter@80	867	};
kpeter@80	868
kpeter@301	869	/// Returns a \c SubMap class
kpeter@301	870
kpeter@301	871	/// This function just returns a \c SubMap class.
kpeter@80	872	///
kpeter@80	873	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	874	/// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
kpeter@80	875	/// <tt>m1[x]-m2[x]</tt>.
kpeter@80	876	///
kpeter@80	877	/// \relates SubMap
kpeter@80	878	template<typename M1, typename M2>
kpeter@80	879	inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
kpeter@80	880	return SubMap<M1, M2>(m1,m2);
kpeter@80	881	}
kpeter@80	882
kpeter@80	883
kpeter@80	884	/// Product of two maps
kpeter@80	885
kpeter@82	886	/// This \ref concepts::ReadMap "read-only map" returns the product
kpeter@80	887	/// of the values of the two given maps.
kpeter@80	888	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	889	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	890	/// \c M1.
kpeter@80	891	///
kpeter@80	892	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	893	/// \code
kpeter@80	894	/// MulMap<M1,M2> mm(m1,m2);
kpeter@80	895	/// \endcode
kpeter@80	896	/// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
kpeter@80	897	///
kpeter@80	898	/// The simplest way of using this map is through the mulMap()
kpeter@80	899	/// function.
kpeter@80	900	///
kpeter@80	901	/// \sa AddMap, SubMap, DivMap
kpeter@80	902	/// \sa ScaleMap, ScaleWriteMap
kpeter@80	903	template<typename M1, typename M2>
kpeter@80	904	class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	905	const M1 &_m1;
kpeter@80	906	const M2 &_m2;
kpeter@80	907	public:
kpeter@559	908	///\e
kpeter@559	909	typedef typename M1::Key Key;
kpeter@559	910	///\e
kpeter@559	911	typedef typename M1::Value Value;
kpeter@80	912
kpeter@80	913	/// Constructor
kpeter@80	914	MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	915	///\e
kpeter@80	916	Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
kpeter@80	917	};
kpeter@80	918
kpeter@301	919	/// Returns a \c MulMap class
kpeter@301	920
kpeter@301	921	/// This function just returns a \c MulMap class.
kpeter@80	922	///
kpeter@80	923	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	924	/// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
kpeter@80	925	/// <tt>m1[x]*m2[x]</tt>.
kpeter@80	926	///
kpeter@80	927	/// \relates MulMap
kpeter@80	928	template<typename M1, typename M2>
kpeter@80	929	inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
kpeter@80	930	return MulMap<M1, M2>(m1,m2);
kpeter@80	931	}
kpeter@80	932
kpeter@80	933
kpeter@80	934	/// Quotient of two maps
kpeter@80	935
kpeter@82	936	/// This \ref concepts::ReadMap "read-only map" returns the quotient
kpeter@80	937	/// of the values of the two given maps.
kpeter@80	938	/// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80	939	/// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80	940	/// \c M1.
kpeter@80	941	///
kpeter@80	942	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80	943	/// \code
kpeter@80	944	/// DivMap<M1,M2> dm(m1,m2);
kpeter@80	945	/// \endcode
kpeter@80	946	/// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
kpeter@80	947	///
kpeter@80	948	/// The simplest way of using this map is through the divMap()
kpeter@80	949	/// function.
kpeter@80	950	///
kpeter@80	951	/// \sa AddMap, SubMap, MulMap
kpeter@80	952	template<typename M1, typename M2>
kpeter@80	953	class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80	954	const M1 &_m1;
kpeter@80	955	const M2 &_m2;
kpeter@80	956	public:
kpeter@559	957	///\e
kpeter@559	958	typedef typename M1::Key Key;
kpeter@559	959	///\e
kpeter@559	960	typedef typename M1::Value Value;
kpeter@80	961
kpeter@80	962	/// Constructor
kpeter@80	963	DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	964	///\e
kpeter@80	965	Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
kpeter@80	966	};
kpeter@80	967
kpeter@301	968	/// Returns a \c DivMap class
kpeter@301	969
kpeter@301	970	/// This function just returns a \c DivMap class.
kpeter@80	971	///
kpeter@80	972	/// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80	973	/// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
kpeter@80	974	/// <tt>m1[x]/m2[x]</tt>.
kpeter@80	975	///
kpeter@80	976	/// \relates DivMap
kpeter@80	977	template<typename M1, typename M2>
kpeter@80	978	inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
kpeter@80	979	return DivMap<M1, M2>(m1,m2);
kpeter@80	980	}
kpeter@80	981
kpeter@80	982
kpeter@80	983	/// Shifts a map with a constant.
kpeter@80	984
kpeter@82	985	/// This \ref concepts::ReadMap "read-only map" returns the sum of
kpeter@80	986	/// the given map and a constant value (i.e. it shifts the map with
kpeter@80	987	/// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80	988	///
kpeter@80	989	/// Actually,
kpeter@80	990	/// \code
kpeter@80	991	/// ShiftMap<M> sh(m,v);
kpeter@80	992	/// \endcode
kpeter@80	993	/// is equivalent to
kpeter@80	994	/// \code
kpeter@80	995	/// ConstMap<M::Key, M::Value> cm(v);
kpeter@80	996	/// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
kpeter@80	997	/// \endcode
kpeter@80	998	///
kpeter@80	999	/// The simplest way of using this map is through the shiftMap()
kpeter@80	1000	/// function.
kpeter@80	1001	///
kpeter@80	1002	/// \sa ShiftWriteMap
kpeter@80	1003	template<typename M, typename C = typename M::Value>
alpar@25	1004	class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1005	const M &_m;
kpeter@80	1006	C _v;
alpar@25	1007	public:
kpeter@559	1008	///\e
kpeter@559	1009	typedef typename M::Key Key;
kpeter@559	1010	///\e
kpeter@559	1011	typedef typename M::Value Value;
alpar@25	1012
kpeter@80	1013	/// Constructor
alpar@25	1014
kpeter@80	1015	/// Constructor.
kpeter@80	1016	/// \param m The undelying map.
kpeter@80	1017	/// \param v The constant value.
kpeter@80	1018	ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559	1019	///\e
kpeter@80	1020	Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25	1021	};
alpar@25	1022
kpeter@80	1023	/// Shifts a map with a constant (read-write version).
alpar@25	1024
kpeter@80	1025	/// This \ref concepts::ReadWriteMap "read-write map" returns the sum
kpeter@80	1026	/// of the given map and a constant value (i.e. it shifts the map with
kpeter@80	1027	/// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80	1028	/// It makes also possible to write the map.
alpar@25	1029	///
kpeter@80	1030	/// The simplest way of using this map is through the shiftWriteMap()
kpeter@80	1031	/// function.
kpeter@80	1032	///
kpeter@80	1033	/// \sa ShiftMap
kpeter@80	1034	template<typename M, typename C = typename M::Value>
alpar@25	1035	class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1036	M &_m;
kpeter@80	1037	C _v;
alpar@25	1038	public:
kpeter@559	1039	///\e
kpeter@559	1040	typedef typename M::Key Key;
kpeter@559	1041	///\e
kpeter@559	1042	typedef typename M::Value Value;
alpar@25	1043
kpeter@80	1044	/// Constructor
alpar@25	1045
kpeter@80	1046	/// Constructor.
kpeter@80	1047	/// \param m The undelying map.
kpeter@80	1048	/// \param v The constant value.
kpeter@80	1049	ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559	1050	///\e
kpeter@80	1051	Value operator[](const Key &k) const { return _m[k]+_v; }
kpeter@559	1052	///\e
kpeter@80	1053	void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
alpar@25	1054	};
alpar@25	1055
kpeter@301	1056	/// Returns a \c ShiftMap class
kpeter@301	1057
kpeter@301	1058	/// This function just returns a \c ShiftMap class.
kpeter@80	1059	///
kpeter@80	1060	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1061	/// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
kpeter@80	1062	/// <tt>m[x]+v</tt>.
kpeter@80	1063	///
kpeter@80	1064	/// \relates ShiftMap
kpeter@80	1065	template<typename M, typename C>
kpeter@80	1066	inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
alpar@25	1067	return ShiftMap<M, C>(m,v);
alpar@25	1068	}
alpar@25	1069
kpeter@301	1070	/// Returns a \c ShiftWriteMap class
kpeter@301	1071
kpeter@301	1072	/// This function just returns a \c ShiftWriteMap class.
kpeter@80	1073	///
kpeter@80	1074	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1075	/// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
kpeter@80	1076	/// <tt>m[x]+v</tt>.
kpeter@80	1077	/// Moreover it makes also possible to write the map.
kpeter@80	1078	///
kpeter@80	1079	/// \relates ShiftWriteMap
kpeter@80	1080	template<typename M, typename C>
kpeter@80	1081	inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
alpar@25	1082	return ShiftWriteMap<M, C>(m,v);
alpar@25	1083	}
alpar@25	1084
alpar@25	1085
kpeter@80	1086	/// Scales a map with a constant.
kpeter@80	1087
kpeter@82	1088	/// This \ref concepts::ReadMap "read-only map" returns the value of
kpeter@80	1089	/// the given map multiplied from the left side with a constant value.
kpeter@80	1090	/// Its \c Key and \c Value are inherited from \c M.
alpar@26	1091	///
kpeter@80	1092	/// Actually,
kpeter@80	1093	/// \code
kpeter@80	1094	/// ScaleMap<M> sc(m,v);
kpeter@80	1095	/// \endcode
kpeter@80	1096	/// is equivalent to
kpeter@80	1097	/// \code
kpeter@80	1098	/// ConstMap<M::Key, M::Value> cm(v);
kpeter@80	1099	/// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
kpeter@80	1100	/// \endcode
alpar@25	1101	///
kpeter@80	1102	/// The simplest way of using this map is through the scaleMap()
kpeter@80	1103	/// function.
alpar@25	1104	///
kpeter@80	1105	/// \sa ScaleWriteMap
kpeter@80	1106	template<typename M, typename C = typename M::Value>
alpar@25	1107	class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1108	const M &_m;
kpeter@80	1109	C _v;
alpar@25	1110	public:
kpeter@559	1111	///\e
kpeter@559	1112	typedef typename M::Key Key;
kpeter@559	1113	///\e
kpeter@559	1114	typedef typename M::Value Value;
alpar@25	1115
kpeter@80	1116	/// Constructor
alpar@25	1117
kpeter@80	1118	/// Constructor.
kpeter@80	1119	/// \param m The undelying map.
kpeter@80	1120	/// \param v The constant value.
kpeter@80	1121	ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559	1122	///\e
kpeter@80	1123	Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25	1124	};
alpar@25	1125
kpeter@80	1126	/// Scales a map with a constant (read-write version).
alpar@25	1127
kpeter@80	1128	/// This \ref concepts::ReadWriteMap "read-write map" returns the value of
kpeter@80	1129	/// the given map multiplied from the left side with a constant value.
kpeter@80	1130	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1131	/// It can also be used as write map if the \c / operator is defined
kpeter@80	1132	/// between \c Value and \c C and the given multiplier is not zero.
kpeter@29	1133	///
kpeter@80	1134	/// The simplest way of using this map is through the scaleWriteMap()
kpeter@80	1135	/// function.
kpeter@80	1136	///
kpeter@80	1137	/// \sa ScaleMap
kpeter@80	1138	template<typename M, typename C = typename M::Value>
alpar@25	1139	class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1140	M &_m;
kpeter@80	1141	C _v;
alpar@25	1142	public:
kpeter@559	1143	///\e
kpeter@559	1144	typedef typename M::Key Key;
kpeter@559	1145	///\e
kpeter@559	1146	typedef typename M::Value Value;
alpar@25	1147
kpeter@80	1148	/// Constructor
alpar@25	1149
kpeter@80	1150	/// Constructor.
kpeter@80	1151	/// \param m The undelying map.
kpeter@80	1152	/// \param v The constant value.
kpeter@80	1153	ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559	1154	///\e
kpeter@80	1155	Value operator[](const Key &k) const { return _v*_m[k]; }
kpeter@559	1156	///\e
kpeter@80	1157	void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
alpar@25	1158	};
alpar@25	1159
kpeter@301	1160	/// Returns a \c ScaleMap class
kpeter@301	1161
kpeter@301	1162	/// This function just returns a \c ScaleMap class.
kpeter@80	1163	///
kpeter@80	1164	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1165	/// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
kpeter@80	1166	/// <tt>v*m[x]</tt>.
kpeter@80	1167	///
kpeter@80	1168	/// \relates ScaleMap
kpeter@80	1169	template<typename M, typename C>
kpeter@80	1170	inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
alpar@25	1171	return ScaleMap<M, C>(m,v);
alpar@25	1172	}
alpar@25	1173
kpeter@301	1174	/// Returns a \c ScaleWriteMap class
kpeter@301	1175
kpeter@301	1176	/// This function just returns a \c ScaleWriteMap class.
kpeter@80	1177	///
kpeter@80	1178	/// For example, if \c m is a map with \c double values and \c v is
kpeter@80	1179	/// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
kpeter@80	1180	/// <tt>v*m[x]</tt>.
kpeter@80	1181	/// Moreover it makes also possible to write the map.
kpeter@80	1182	///
kpeter@80	1183	/// \relates ScaleWriteMap
kpeter@80	1184	template<typename M, typename C>
kpeter@80	1185	inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
alpar@25	1186	return ScaleWriteMap<M, C>(m,v);
alpar@25	1187	}
alpar@25	1188
alpar@25	1189
kpeter@80	1190	/// Negative of a map
alpar@25	1191
kpeter@82	1192	/// This \ref concepts::ReadMap "read-only map" returns the negative
kpeter@80	1193	/// of the values of the given map (using the unary \c - operator).
kpeter@80	1194	/// Its \c Key and \c Value are inherited from \c M.
alpar@25	1195	///
kpeter@80	1196	/// If M::Value is \c int, \c double etc., then
kpeter@80	1197	/// \code
kpeter@80	1198	/// NegMap<M> neg(m);
kpeter@80	1199	/// \endcode
kpeter@80	1200	/// is equivalent to
kpeter@80	1201	/// \code
kpeter@80	1202	/// ScaleMap<M> neg(m,-1);
kpeter@80	1203	/// \endcode
kpeter@29	1204	///
kpeter@80	1205	/// The simplest way of using this map is through the negMap()
kpeter@80	1206	/// function.
kpeter@29	1207	///
kpeter@80	1208	/// \sa NegWriteMap
kpeter@80	1209	template<typename M>
alpar@25	1210	class NegMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1211	const M& _m;
alpar@25	1212	public:
kpeter@559	1213	///\e
kpeter@559	1214	typedef typename M::Key Key;
kpeter@559	1215	///\e
kpeter@559	1216	typedef typename M::Value Value;
alpar@25	1217
kpeter@80	1218	/// Constructor
kpeter@80	1219	NegMap(const M &m) : _m(m) {}
kpeter@559	1220	///\e
kpeter@80	1221	Value operator[](const Key &k) const { return -_m[k]; }
alpar@25	1222	};
alpar@25	1223
kpeter@80	1224	/// Negative of a map (read-write version)
kpeter@80	1225
kpeter@80	1226	/// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80	1227	/// negative of the values of the given map (using the unary \c -
kpeter@80	1228	/// operator).
kpeter@80	1229	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1230	/// It makes also possible to write the map.
kpeter@80	1231	///
kpeter@80	1232	/// If M::Value is \c int, \c double etc., then
kpeter@80	1233	/// \code
kpeter@80	1234	/// NegWriteMap<M> neg(m);
kpeter@80	1235	/// \endcode
kpeter@80	1236	/// is equivalent to
kpeter@80	1237	/// \code
kpeter@80	1238	/// ScaleWriteMap<M> neg(m,-1);
kpeter@80	1239	/// \endcode
kpeter@80	1240	///
kpeter@80	1241	/// The simplest way of using this map is through the negWriteMap()
kpeter@80	1242	/// function.
kpeter@29	1243	///
kpeter@29	1244	/// \sa NegMap
kpeter@80	1245	template<typename M>
alpar@25	1246	class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1247	M &_m;
alpar@25	1248	public:
kpeter@559	1249	///\e
kpeter@559	1250	typedef typename M::Key Key;
kpeter@559	1251	///\e
kpeter@559	1252	typedef typename M::Value Value;
alpar@25	1253
kpeter@80	1254	/// Constructor
kpeter@80	1255	NegWriteMap(M &m) : _m(m) {}
kpeter@559	1256	///\e
kpeter@80	1257	Value operator[](const Key &k) const { return -_m[k]; }
kpeter@559	1258	///\e
kpeter@80	1259	void set(const Key &k, const Value &v) { _m.set(k, -v); }
alpar@25	1260	};
alpar@25	1261
kpeter@301	1262	/// Returns a \c NegMap class
kpeter@301	1263
kpeter@301	1264	/// This function just returns a \c NegMap class.
kpeter@80	1265	///
kpeter@80	1266	/// For example, if \c m is a map with \c double values, then
kpeter@80	1267	/// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80	1268	///
kpeter@80	1269	/// \relates NegMap
kpeter@80	1270	template <typename M>
alpar@25	1271	inline NegMap<M> negMap(const M &m) {
alpar@25	1272	return NegMap<M>(m);
alpar@25	1273	}
alpar@25	1274
kpeter@301	1275	/// Returns a \c NegWriteMap class
kpeter@301	1276
kpeter@301	1277	/// This function just returns a \c NegWriteMap class.
kpeter@80	1278	///
kpeter@80	1279	/// For example, if \c m is a map with \c double values, then
kpeter@80	1280	/// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80	1281	/// Moreover it makes also possible to write the map.
kpeter@80	1282	///
kpeter@80	1283	/// \relates NegWriteMap
kpeter@80	1284	template <typename M>
kpeter@80	1285	inline NegWriteMap<M> negWriteMap(M &m) {
alpar@25	1286	return NegWriteMap<M>(m);
alpar@25	1287	}
alpar@25	1288
alpar@25	1289
kpeter@80	1290	/// Absolute value of a map
kpeter@80	1291
kpeter@82	1292	/// This \ref concepts::ReadMap "read-only map" returns the absolute
kpeter@80	1293	/// value of the values of the given map.
kpeter@80	1294	/// Its \c Key and \c Value are inherited from \c M.
kpeter@80	1295	/// \c Value must be comparable to \c 0 and the unary \c -
kpeter@80	1296	/// operator must be defined for it, of course.
kpeter@80	1297	///
kpeter@80	1298	/// The simplest way of using this map is through the absMap()
kpeter@80	1299	/// function.
kpeter@80	1300	template<typename M>
alpar@25	1301	class AbsMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80	1302	const M &_m;
alpar@25	1303	public:
kpeter@559	1304	///\e
kpeter@559	1305	typedef typename M::Key Key;
kpeter@559	1306	///\e
kpeter@559	1307	typedef typename M::Value Value;
alpar@25	1308
kpeter@80	1309	/// Constructor
kpeter@80	1310	AbsMap(const M &m) : _m(m) {}
kpeter@559	1311	///\e
kpeter@80	1312	Value operator[](const Key &k) const {
kpeter@80	1313	Value tmp = _m[k];
alpar@25	1314	return tmp >= 0 ? tmp : -tmp;
alpar@25	1315	}
alpar@25	1316
alpar@25	1317	};
alpar@25	1318
kpeter@301	1319	/// Returns an \c AbsMap class
kpeter@301	1320
kpeter@301	1321	/// This function just returns an \c AbsMap class.
kpeter@80	1322	///
kpeter@80	1323	/// For example, if \c m is a map with \c double values, then
kpeter@80	1324	/// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
kpeter@80	1325	/// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
kpeter@80	1326	/// negative.
kpeter@80	1327	///
kpeter@80	1328	/// \relates AbsMap
kpeter@80	1329	template<typename M>
alpar@25	1330	inline AbsMap<M> absMap(const M &m) {
alpar@25	1331	return AbsMap<M>(m);
alpar@25	1332	}
alpar@25	1333
kpeter@82	1334	/// @}
alpar@209	1335
kpeter@82	1336	// Logical maps and map adaptors:
kpeter@82	1337
kpeter@82	1338	/// \addtogroup maps
kpeter@82	1339	/// @{
kpeter@82	1340
kpeter@82	1341	/// Constant \c true map.
kpeter@82	1342
kpeter@82	1343	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1344	/// each key.
kpeter@82	1345	///
kpeter@82	1346	/// Note that
kpeter@82	1347	/// \code
kpeter@82	1348	/// TrueMap<K> tm;
kpeter@82	1349	/// \endcode
kpeter@82	1350	/// is equivalent to
kpeter@82	1351	/// \code
kpeter@82	1352	/// ConstMap<K,bool> tm(true);
kpeter@82	1353	/// \endcode
kpeter@82	1354	///
kpeter@82	1355	/// \sa FalseMap
kpeter@82	1356	/// \sa ConstMap
kpeter@82	1357	template <typename K>
kpeter@82	1358	class TrueMap : public MapBase<K, bool> {
kpeter@82	1359	public:
kpeter@559	1360	///\e
kpeter@559	1361	typedef K Key;
kpeter@559	1362	///\e
kpeter@559	1363	typedef bool Value;
kpeter@82	1364
kpeter@82	1365	/// Gives back \c true.
kpeter@82	1366	Value operator[](const Key&) const { return true; }
kpeter@82	1367	};
kpeter@82	1368
kpeter@301	1369	/// Returns a \c TrueMap class
kpeter@301	1370
kpeter@301	1371	/// This function just returns a \c TrueMap class.
kpeter@82	1372	/// \relates TrueMap
kpeter@82	1373	template<typename K>
kpeter@82	1374	inline TrueMap<K> trueMap() {
kpeter@82	1375	return TrueMap<K>();
kpeter@82	1376	}
kpeter@82	1377
kpeter@82	1378
kpeter@82	1379	/// Constant \c false map.
kpeter@82	1380
kpeter@82	1381	/// This \ref concepts::ReadMap "read-only map" assigns \c false to
kpeter@82	1382	/// each key.
kpeter@82	1383	///
kpeter@82	1384	/// Note that
kpeter@82	1385	/// \code
kpeter@82	1386	/// FalseMap<K> fm;
kpeter@82	1387	/// \endcode
kpeter@82	1388	/// is equivalent to
kpeter@82	1389	/// \code
kpeter@82	1390	/// ConstMap<K,bool> fm(false);
kpeter@82	1391	/// \endcode
kpeter@82	1392	///
kpeter@82	1393	/// \sa TrueMap
kpeter@82	1394	/// \sa ConstMap
kpeter@82	1395	template <typename K>
kpeter@82	1396	class FalseMap : public MapBase<K, bool> {
kpeter@82	1397	public:
kpeter@559	1398	///\e
kpeter@559	1399	typedef K Key;
kpeter@559	1400	///\e
kpeter@559	1401	typedef bool Value;
kpeter@82	1402
kpeter@82	1403	/// Gives back \c false.
kpeter@82	1404	Value operator[](const Key&) const { return false; }
kpeter@82	1405	};
kpeter@82	1406
kpeter@301	1407	/// Returns a \c FalseMap class
kpeter@301	1408
kpeter@301	1409	/// This function just returns a \c FalseMap class.
kpeter@82	1410	/// \relates FalseMap
kpeter@82	1411	template<typename K>
kpeter@82	1412	inline FalseMap<K> falseMap() {
kpeter@82	1413	return FalseMap<K>();
kpeter@82	1414	}
kpeter@82	1415
kpeter@82	1416	/// @}
kpeter@82	1417
kpeter@82	1418	/// \addtogroup map_adaptors
kpeter@82	1419	/// @{
kpeter@82	1420
kpeter@82	1421	/// Logical 'and' of two maps
kpeter@82	1422
kpeter@82	1423	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82	1424	/// 'and' of the values of the two given maps.
kpeter@82	1425	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1426	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1427	///
kpeter@82	1428	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1429	/// \code
kpeter@82	1430	/// AndMap<M1,M2> am(m1,m2);
kpeter@82	1431	/// \endcode
kpeter@82	1432	/// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
kpeter@82	1433	///
kpeter@82	1434	/// The simplest way of using this map is through the andMap()
kpeter@82	1435	/// function.
kpeter@82	1436	///
kpeter@82	1437	/// \sa OrMap
kpeter@82	1438	/// \sa NotMap, NotWriteMap
kpeter@82	1439	template<typename M1, typename M2>
kpeter@82	1440	class AndMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1441	const M1 &_m1;
kpeter@82	1442	const M2 &_m2;
kpeter@82	1443	public:
kpeter@559	1444	///\e
kpeter@559	1445	typedef typename M1::Key Key;
kpeter@559	1446	///\e
kpeter@559	1447	typedef bool Value;
kpeter@82	1448
kpeter@82	1449	/// Constructor
kpeter@82	1450	AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	1451	///\e
kpeter@82	1452	Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
kpeter@82	1453	};
kpeter@82	1454
kpeter@301	1455	/// Returns an \c AndMap class
kpeter@301	1456
kpeter@301	1457	/// This function just returns an \c AndMap class.
kpeter@82	1458	///
kpeter@82	1459	/// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82	1460	/// then <tt>andMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1461	/// <tt>m1[x]&&m2[x]</tt>.
kpeter@82	1462	///
kpeter@82	1463	/// \relates AndMap
kpeter@82	1464	template<typename M1, typename M2>
kpeter@82	1465	inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
kpeter@82	1466	return AndMap<M1, M2>(m1,m2);
kpeter@82	1467	}
kpeter@82	1468
kpeter@82	1469
kpeter@82	1470	/// Logical 'or' of two maps
kpeter@82	1471
kpeter@82	1472	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82	1473	/// 'or' of the values of the two given maps.
kpeter@82	1474	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1475	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1476	///
kpeter@82	1477	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1478	/// \code
kpeter@82	1479	/// OrMap<M1,M2> om(m1,m2);
kpeter@82	1480	/// \endcode
kpeter@82	1481	/// <tt>om[x]</tt> will be equal to <tt>m1[x]\|\|m2[x]</tt>.
kpeter@82	1482	///
kpeter@82	1483	/// The simplest way of using this map is through the orMap()
kpeter@82	1484	/// function.
kpeter@82	1485	///
kpeter@82	1486	/// \sa AndMap
kpeter@82	1487	/// \sa NotMap, NotWriteMap
kpeter@82	1488	template<typename M1, typename M2>
kpeter@82	1489	class OrMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1490	const M1 &_m1;
kpeter@82	1491	const M2 &_m2;
kpeter@82	1492	public:
kpeter@559	1493	///\e
kpeter@559	1494	typedef typename M1::Key Key;
kpeter@559	1495	///\e
kpeter@559	1496	typedef bool Value;
kpeter@82	1497
kpeter@82	1498	/// Constructor
kpeter@82	1499	OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	1500	///\e
kpeter@82	1501	Value operator[](const Key &k) const { return _m1[k]\|\|_m2[k]; }
kpeter@82	1502	};
kpeter@82	1503
kpeter@301	1504	/// Returns an \c OrMap class
kpeter@301	1505
kpeter@301	1506	/// This function just returns an \c OrMap class.
kpeter@82	1507	///
kpeter@82	1508	/// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82	1509	/// then <tt>orMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1510	/// <tt>m1[x]\|\|m2[x]</tt>.
kpeter@82	1511	///
kpeter@82	1512	/// \relates OrMap
kpeter@82	1513	template<typename M1, typename M2>
kpeter@82	1514	inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
kpeter@82	1515	return OrMap<M1, M2>(m1,m2);
kpeter@82	1516	}
kpeter@82	1517
alpar@25	1518
kpeter@80	1519	/// Logical 'not' of a map
kpeter@80	1520
kpeter@82	1521	/// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@80	1522	/// 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.
alpar@25	1524	///
kpeter@80	1525	/// The simplest way of using this map is through the notMap()
kpeter@80	1526	/// function.
alpar@25	1527	///
kpeter@80	1528	/// \sa NotWriteMap
kpeter@80	1529	template <typename M>
alpar@25	1530	class NotMap : public MapBase<typename M::Key, bool> {
kpeter@80	1531	const M &_m;
alpar@25	1532	public:
kpeter@559	1533	///\e
kpeter@559	1534	typedef typename M::Key Key;
kpeter@559	1535	///\e
kpeter@559	1536	typedef bool Value;
alpar@25	1537
alpar@25	1538	/// Constructor
kpeter@80	1539	NotMap(const M &m) : _m(m) {}
kpeter@559	1540	///\e
kpeter@80	1541	Value operator[](const Key &k) const { return !_m[k]; }
alpar@25	1542	};
alpar@25	1543
kpeter@80	1544	/// Logical 'not' of a map (read-write version)
kpeter@80	1545
kpeter@80	1546	/// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80	1547	/// logical negation of the values of the given map.
kpeter@80	1548	/// Its \c Key is inherited from \c M and its \c Value is \c bool.
kpeter@80	1549	/// It makes also possible to write the map. When a value is set,
kpeter@80	1550	/// the opposite value is set to the original map.
kpeter@29	1551	///
kpeter@80	1552	/// The simplest way of using this map is through the notWriteMap()
kpeter@80	1553	/// function.
kpeter@80	1554	///
kpeter@80	1555	/// \sa NotMap
kpeter@80	1556	template <typename M>
alpar@25	1557	class NotWriteMap : public MapBase<typename M::Key, bool> {
kpeter@80	1558	M &_m;
alpar@25	1559	public:
kpeter@559	1560	///\e
kpeter@559	1561	typedef typename M::Key Key;
kpeter@559	1562	///\e
kpeter@559	1563	typedef bool Value;
alpar@25	1564
alpar@25	1565	/// Constructor
kpeter@80	1566	NotWriteMap(M &m) : _m(m) {}
kpeter@559	1567	///\e
kpeter@80	1568	Value operator[](const Key &k) const { return !_m[k]; }
kpeter@559	1569	///\e
kpeter@80	1570	void set(const Key &k, bool v) { _m.set(k, !v); }
alpar@25	1571	};
kpeter@80	1572
kpeter@301	1573	/// Returns a \c NotMap class
kpeter@301	1574
kpeter@301	1575	/// This function just returns a \c NotMap class.
kpeter@80	1576	///
kpeter@80	1577	/// For example, if \c m is a map with \c bool values, then
kpeter@80	1578	/// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80	1579	///
kpeter@80	1580	/// \relates NotMap
kpeter@80	1581	template <typename M>
alpar@25	1582	inline NotMap<M> notMap(const M &m) {
alpar@25	1583	return NotMap<M>(m);
alpar@25	1584	}
kpeter@80	1585
kpeter@301	1586	/// Returns a \c NotWriteMap class
kpeter@301	1587
kpeter@301	1588	/// This function just returns a \c NotWriteMap class.
kpeter@80	1589	///
kpeter@80	1590	/// For example, if \c m is a map with \c bool values, then
kpeter@80	1591	/// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80	1592	/// Moreover it makes also possible to write the map.
kpeter@80	1593	///
kpeter@80	1594	/// \relates NotWriteMap
kpeter@80	1595	template <typename M>
kpeter@80	1596	inline NotWriteMap<M> notWriteMap(M &m) {
alpar@25	1597	return NotWriteMap<M>(m);
alpar@25	1598	}
alpar@25	1599
kpeter@82	1600
kpeter@82	1601	/// Combination of two maps using the \c == operator
kpeter@82	1602
kpeter@82	1603	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1604	/// the keys for which the corresponding values of the two maps are
kpeter@82	1605	/// equal.
kpeter@82	1606	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1607	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1608	///
kpeter@82	1609	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1610	/// \code
kpeter@82	1611	/// EqualMap<M1,M2> em(m1,m2);
kpeter@82	1612	/// \endcode
kpeter@82	1613	/// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
kpeter@82	1614	///
kpeter@82	1615	/// The simplest way of using this map is through the equalMap()
kpeter@82	1616	/// function.
kpeter@82	1617	///
kpeter@82	1618	/// \sa LessMap
kpeter@82	1619	template<typename M1, typename M2>
kpeter@82	1620	class EqualMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1621	const M1 &_m1;
kpeter@82	1622	const M2 &_m2;
kpeter@82	1623	public:
kpeter@559	1624	///\e
kpeter@559	1625	typedef typename M1::Key Key;
kpeter@559	1626	///\e
kpeter@559	1627	typedef bool Value;
kpeter@82	1628
kpeter@82	1629	/// Constructor
kpeter@82	1630	EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	1631	///\e
kpeter@82	1632	Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
kpeter@82	1633	};
kpeter@82	1634
kpeter@301	1635	/// Returns an \c EqualMap class
kpeter@301	1636
kpeter@301	1637	/// This function just returns an \c EqualMap class.
kpeter@82	1638	///
kpeter@82	1639	/// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82	1640	/// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1641	/// <tt>m1[x]==m2[x]</tt>.
kpeter@82	1642	///
kpeter@82	1643	/// \relates EqualMap
kpeter@82	1644	template<typename M1, typename M2>
kpeter@82	1645	inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
kpeter@82	1646	return EqualMap<M1, M2>(m1,m2);
kpeter@82	1647	}
kpeter@82	1648
kpeter@82	1649
kpeter@82	1650	/// Combination of two maps using the \c < operator
kpeter@82	1651
kpeter@82	1652	/// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82	1653	/// the keys for which the corresponding value of the first map is
kpeter@82	1654	/// less then the value of the second map.
kpeter@82	1655	/// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82	1656	/// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82	1657	///
kpeter@82	1658	/// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82	1659	/// \code
kpeter@82	1660	/// LessMap<M1,M2> lm(m1,m2);
kpeter@82	1661	/// \endcode
kpeter@82	1662	/// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
kpeter@82	1663	///
kpeter@82	1664	/// The simplest way of using this map is through the lessMap()
kpeter@82	1665	/// function.
kpeter@82	1666	///
kpeter@82	1667	/// \sa EqualMap
kpeter@82	1668	template<typename M1, typename M2>
kpeter@82	1669	class LessMap : public MapBase<typename M1::Key, bool> {
kpeter@82	1670	const M1 &_m1;
kpeter@82	1671	const M2 &_m2;
kpeter@82	1672	public:
kpeter@559	1673	///\e
kpeter@559	1674	typedef typename M1::Key Key;
kpeter@559	1675	///\e
kpeter@559	1676	typedef bool Value;
kpeter@82	1677
kpeter@82	1678	/// Constructor
kpeter@82	1679	LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559	1680	///\e
kpeter@82	1681	Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
kpeter@82	1682	};
kpeter@82	1683
kpeter@301	1684	/// Returns an \c LessMap class
kpeter@301	1685
kpeter@301	1686	/// This function just returns an \c LessMap class.
kpeter@82	1687	///
kpeter@82	1688	/// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82	1689	/// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
kpeter@82	1690	/// <tt>m1[x]<m2[x]</tt>.
kpeter@82	1691	///
kpeter@82	1692	/// \relates LessMap
kpeter@82	1693	template<typename M1, typename M2>
kpeter@82	1694	inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
kpeter@82	1695	return LessMap<M1, M2>(m1,m2);
kpeter@82	1696	}
kpeter@82	1697
alpar@104	1698	namespace _maps_bits {
alpar@104	1699
alpar@104	1700	template <typename _Iterator, typename Enable = void>
alpar@104	1701	struct IteratorTraits {
alpar@104	1702	typedef typename std::iterator_traits<_Iterator>::value_type Value;
alpar@104	1703	};
alpar@104	1704
alpar@104	1705	template <typename _Iterator>
alpar@104	1706	struct IteratorTraits<_Iterator,
alpar@104	1707	typename exists<typename _Iterator::container_type>::type>
alpar@104	1708	{
alpar@104	1709	typedef typename _Iterator::container_type::value_type Value;
alpar@104	1710	};
alpar@104	1711
alpar@104	1712	}
alpar@104	1713
kpeter@314	1714	/// @}
kpeter@314	1715
kpeter@314	1716	/// \addtogroup maps
kpeter@314	1717	/// @{
kpeter@314	1718
alpar@104	1719	/// \brief Writable bool map for logging each \c true assigned element
alpar@104	1720	///
kpeter@159	1721	/// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104	1722	/// each \c true assigned element, i.e it copies subsequently each
alpar@104	1723	/// keys set to \c true to the given iterator.
kpeter@159	1724	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1725	/// that were marked \c true by an algorithm.
alpar@104	1726	///
kpeter@159	1727	/// There are several algorithms that provide solutions through bool
kpeter@159	1728	/// maps and most of them assign \c true at most once for each key.
kpeter@159	1729	/// In these cases it is a natural request to store each \c true
kpeter@159	1730	/// assigned elements (in order of the assignment), which can be
kpeter@167	1731	/// easily done with LoggerBoolMap.
kpeter@159	1732	///
kpeter@167	1733	/// The simplest way of using this map is through the loggerBoolMap()
kpeter@159	1734	/// function.
kpeter@159	1735	///
kpeter@559	1736	/// \tparam IT The type of the iterator.
kpeter@559	1737	/// \tparam KEY The key type of the map. The default value set
kpeter@159	1738	/// according to the iterator type should work in most cases.
alpar@104	1739	///
alpar@104	1740	/// \note The container of the iterator must contain enough space
kpeter@159	1741	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1742	#ifdef DOXYGEN
kpeter@559	1743	template <typename IT, typename KEY>
kpeter@159	1744	#else
kpeter@559	1745	template <typename IT,
kpeter@559	1746	typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
kpeter@159	1747	#endif
kpeter@559	1748	class LoggerBoolMap : public MapBase<KEY, bool> {
alpar@104	1749	public:
kpeter@559	1750
kpeter@559	1751	///\e
kpeter@559	1752	typedef KEY Key;
kpeter@559	1753	///\e
alpar@104	1754	typedef bool Value;
kpeter@559	1755	///\e
kpeter@559	1756	typedef IT Iterator;
alpar@104	1757
alpar@104	1758	/// Constructor
kpeter@167	1759	LoggerBoolMap(Iterator it)
alpar@104	1760	: _begin(it), _end(it) {}
alpar@104	1761
alpar@104	1762	/// Gives back the given iterator set for the first key
alpar@104	1763	Iterator begin() const {
alpar@104	1764	return _begin;
alpar@104	1765	}
alpar@104	1766
alpar@104	1767	/// Gives back the the 'after the last' iterator
alpar@104	1768	Iterator end() const {
alpar@104	1769	return _end;
alpar@104	1770	}
alpar@104	1771
alpar@104	1772	/// The set function of the map
kpeter@159	1773	void set(const Key& key, Value value) {
alpar@104	1774	if (value) {
alpar@209	1775	*_end++ = key;
alpar@104	1776	}
alpar@104	1777	}
alpar@104	1778
alpar@104	1779	private:
alpar@104	1780	Iterator _begin;
kpeter@159	1781	Iterator _end;
alpar@104	1782	};
alpar@209	1783
kpeter@301	1784	/// Returns a \c LoggerBoolMap class
kpeter@301	1785
kpeter@301	1786	/// This function just returns a \c LoggerBoolMap class.
kpeter@159	1787	///
kpeter@159	1788	/// The most important usage of it is storing certain nodes or arcs
kpeter@159	1789	/// that were marked \c true by an algorithm.
kpeter@159	1790	/// For example it makes easier to store the nodes in the processing
kpeter@159	1791	/// order of Dfs algorithm, as the following examples show.
kpeter@159	1792	/// \code
kpeter@159	1793	/// std::vector<Node> v;
kpeter@167	1794	/// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@159	1795	/// \endcode
kpeter@159	1796	/// \code
kpeter@159	1797	/// std::vector<Node> v(countNodes(g));
kpeter@167	1798	/// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
kpeter@159	1799	/// \endcode
kpeter@159	1800	///
kpeter@159	1801	/// \note The container of the iterator must contain enough space
kpeter@159	1802	/// for the elements or the iterator should be an inserter iterator.
kpeter@159	1803	///
kpeter@167	1804	/// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@159	1805	/// it cannot be used when a readable map is needed, for example as
kpeter@301	1806	/// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
kpeter@159	1807	///
kpeter@167	1808	/// \relates LoggerBoolMap
kpeter@159	1809	template<typename Iterator>
kpeter@167	1810	inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167	1811	return LoggerBoolMap<Iterator>(it);
kpeter@159	1812	}
alpar@104	1813
kpeter@314	1814	/// @}
kpeter@314	1815
kpeter@314	1816	/// \addtogroup graph_maps
kpeter@314	1817	/// @{
kpeter@314	1818
kpeter@559	1819	/// \brief Provides an immutable and unique id for each item in a graph.
kpeter@559	1820	///
kpeter@559	1821	/// IdMap provides a unique and immutable id for each item of the
deba@693	1822	/// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
kpeter@559	1823	/// - \b unique: different items get different ids,
kpeter@559	1824	/// - \b immutable: the id of an item does not change (even if you
kpeter@559	1825	/// delete other nodes).
kpeter@559	1826	///
kpeter@559	1827	/// Using this map you get access (i.e. can read) the inner id values of
kpeter@559	1828	/// the items stored in the graph, which is returned by the \c id()
kpeter@559	1829	/// function of the graph. This map can be inverted with its member
deba@220	1830	/// class \c InverseMap or with the \c operator() member.
deba@220	1831	///
kpeter@559	1832	/// \tparam GR The graph type.
kpeter@559	1833	/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559	1834	/// \c GR::Edge).
kpeter@559	1835	///
alpar@572	1836	/// \see RangeIdMap
kpeter@559	1837	template <typename GR, typename K>
kpeter@559	1838	class IdMap : public MapBase<K, int> {
deba@220	1839	public:
kpeter@559	1840	/// The graph type of IdMap.
kpeter@559	1841	typedef GR Graph;
kpeter@617	1842	typedef GR Digraph;
kpeter@559	1843	/// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559	1844	typedef K Item;
kpeter@559	1845	/// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559	1846	typedef K Key;
kpeter@559	1847	/// The value type of IdMap.
deba@220	1848	typedef int Value;
deba@220	1849
deba@220	1850	/// \brief Constructor.
deba@220	1851	///
deba@220	1852	/// Constructor of the map.
deba@220	1853	explicit IdMap(const Graph& graph) : _graph(&graph) {}
deba@220	1854
deba@220	1855	/// \brief Gives back the \e id of the item.
deba@220	1856	///
deba@220	1857	/// Gives back the immutable and unique \e id of the item.
deba@220	1858	int operator[](const Item& item) const { return _graph->id(item);}
deba@220	1859
kpeter@559	1860	/// \brief Gives back the \e item by its id.
deba@220	1861	///
kpeter@559	1862	/// Gives back the \e item by its id.
deba@220	1863	Item operator()(int id) { return _graph->fromId(id, Item()); }
deba@220	1864
deba@220	1865	private:
deba@220	1866	const Graph* _graph;
deba@220	1867
deba@220	1868	public:
deba@220	1869
kpeter@559	1870	/// \brief This class represents the inverse of its owner (IdMap).
deba@220	1871	///
kpeter@559	1872	/// This class represents the inverse of its owner (IdMap).
deba@220	1873	/// \see inverse()
deba@220	1874	class InverseMap {
deba@220	1875	public:
deba@220	1876
deba@220	1877	/// \brief Constructor.
deba@220	1878	///
deba@220	1879	/// Constructor for creating an id-to-item map.
deba@220	1880	explicit InverseMap(const Graph& graph) : _graph(&graph) {}
deba@220	1881
deba@220	1882	/// \brief Constructor.
deba@220	1883	///
deba@220	1884	/// Constructor for creating an id-to-item map.
deba@220	1885	explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
deba@220	1886
deba@220	1887	/// \brief Gives back the given item from its id.
deba@220	1888	///
deba@220	1889	/// Gives back the given item from its id.
deba@220	1890	Item operator[](int id) const { return _graph->fromId(id, Item());}
deba@220	1891
deba@220	1892	private:
deba@220	1893	const Graph* _graph;
deba@220	1894	};
deba@220	1895
deba@220	1896	/// \brief Gives back the inverse of the map.
deba@220	1897	///
deba@220	1898	/// Gives back the inverse of the IdMap.
deba@220	1899	InverseMap inverse() const { return InverseMap(*_graph);}
deba@220	1900	};
deba@220	1901
deba@220	1902
alpar@572	1903	/// \brief General cross reference graph map type.
kpeter@559	1904
kpeter@559	1905	/// This class provides simple invertable graph maps.
kpeter@559	1906	/// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
deba@220	1907	/// and if a key is set to a new value then store it
deba@220	1908	/// in the inverse map.
deba@220	1909	///
deba@220	1910	/// The values of the map can be accessed
deba@220	1911	/// with stl compatible forward iterator.
deba@220	1912	///
kpeter@559	1913	/// \tparam GR The graph type.
kpeter@559	1914	/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559	1915	/// \c GR::Edge).
kpeter@559	1916	/// \tparam V The value type of the map.
deba@220	1917	///
deba@220	1918	/// \see IterableValueMap
kpeter@559	1919	template <typename GR, typename K, typename V>
alpar@572	1920	class CrossRefMap
kpeter@559	1921	: protected ItemSetTraits<GR, K>::template Map<V>::Type {
deba@220	1922	private:
deba@220	1923
kpeter@559	1924	typedef typename ItemSetTraits<GR, K>::
kpeter@559	1925	template Map<V>::Type Map;
kpeter@559	1926
kpeter@559	1927	typedef std::map<V, K> Container;
deba@220	1928	Container _inv_map;
deba@220	1929
deba@220	1930	public:
deba@220	1931
alpar@572	1932	/// The graph type of CrossRefMap.
kpeter@559	1933	typedef GR Graph;
kpeter@617	1934	typedef GR Digraph;
alpar@572	1935	/// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559	1936	typedef K Item;
alpar@572	1937	/// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559	1938	typedef K Key;
alpar@572	1939	/// The value type of CrossRefMap.
kpeter@559	1940	typedef V Value;
deba@220	1941
deba@220	1942	/// \brief Constructor.
deba@220	1943	///
alpar@572	1944	/// Construct a new CrossRefMap for the given graph.
alpar@572	1945	explicit CrossRefMap(const Graph& graph) : Map(graph) {}
deba@220	1946
deba@220	1947	/// \brief Forward iterator for values.
deba@220	1948	///
deba@220	1949	/// This iterator is an stl compatible forward
deba@220	1950	/// iterator on the values of the map. The values can
kpeter@559	1951	/// be accessed in the <tt>[beginValue, endValue)</tt> range.
deba@220	1952	class ValueIterator
deba@220	1953	: public std::iterator<std::forward_iterator_tag, Value> {
alpar@572	1954	friend class CrossRefMap;
deba@220	1955	private:
deba@220	1956	ValueIterator(typename Container::const_iterator _it)
deba@220	1957	: it(_it) {}
deba@220	1958	public:
deba@220	1959
deba@220	1960	ValueIterator() {}
deba@220	1961
deba@220	1962	ValueIterator& operator++() { ++it; return *this; }
deba@220	1963	ValueIterator operator++(int) {
deba@220	1964	ValueIterator tmp(*this);
deba@220	1965	operator++();
deba@220	1966	return tmp;
deba@220	1967	}
deba@220	1968
deba@220	1969	const Value& operator*() const { return it->first; }
deba@220	1970	const Value* operator->() const { return &(it->first); }
deba@220	1971
deba@220	1972	bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@220	1973	bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@220	1974
deba@220	1975	private:
deba@220	1976	typename Container::const_iterator it;
deba@220	1977	};
deba@220	1978
deba@220	1979	/// \brief Returns an iterator to the first value.
deba@220	1980	///
deba@220	1981	/// Returns an stl compatible iterator to the
deba@220	1982	/// first value of the map. The values of the
kpeter@559	1983	/// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220	1984	/// range.
deba@220	1985	ValueIterator beginValue() const {
deba@220	1986	return ValueIterator(_inv_map.begin());
deba@220	1987	}
deba@220	1988
deba@220	1989	/// \brief Returns an iterator after the last value.
deba@220	1990	///
deba@220	1991	/// Returns an stl compatible iterator after the
deba@220	1992	/// last value of the map. The values of the
kpeter@559	1993	/// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220	1994	/// range.
deba@220	1995	ValueIterator endValue() const {
deba@220	1996	return ValueIterator(_inv_map.end());
deba@220	1997	}
deba@220	1998
kpeter@559	1999	/// \brief Sets the value associated with the given key.
deba@220	2000	///
kpeter@559	2001	/// Sets the value associated with the given key.
deba@220	2002	void set(const Key& key, const Value& val) {
deba@220	2003	Value oldval = Map::operator[](key);
deba@220	2004	typename Container::iterator it = _inv_map.find(oldval);
deba@220	2005	if (it != _inv_map.end() && it->second == key) {
deba@220	2006	_inv_map.erase(it);
deba@220	2007	}
deba@693	2008	_inv_map.insert(std::make_pair(val, key));
deba@220	2009	Map::set(key, val);
deba@220	2010	}
deba@220	2011
kpeter@559	2012	/// \brief Returns the value associated with the given key.
deba@220	2013	///
kpeter@559	2014	/// Returns the value associated with the given key.
deba@220	2015	typename MapTraits<Map>::ConstReturnValue
deba@220	2016	operator[](const Key& key) const {
deba@220	2017	return Map::operator[](key);
deba@220	2018	}
deba@220	2019
deba@220	2020	/// \brief Gives back the item by its value.
deba@220	2021	///
deba@220	2022	/// Gives back the item by its value.
deba@220	2023	Key operator()(const Value& key) const {
deba@220	2024	typename Container::const_iterator it = _inv_map.find(key);
deba@220	2025	return it != _inv_map.end() ? it->second : INVALID;
deba@220	2026	}
deba@220	2027
deba@220	2028	protected:
deba@220	2029
kpeter@559	2030	/// \brief Erase the key from the map and the inverse map.
deba@220	2031	///
kpeter@559	2032	/// Erase the key from the map and the inverse map. It is called by the
deba@220	2033	/// \c AlterationNotifier.
deba@220	2034	virtual void erase(const Key& key) {
deba@220	2035	Value val = Map::operator[](key);
deba@220	2036	typename Container::iterator it = _inv_map.find(val);
deba@220	2037	if (it != _inv_map.end() && it->second == key) {
deba@220	2038	_inv_map.erase(it);
deba@220	2039	}
deba@220	2040	Map::erase(key);
deba@220	2041	}
deba@220	2042
kpeter@559	2043	/// \brief Erase more keys from the map and the inverse map.
deba@220	2044	///
kpeter@559	2045	/// Erase more keys from the map and the inverse map. It is called by the
deba@220	2046	/// \c AlterationNotifier.
deba@220	2047	virtual void erase(const std::vector<Key>& keys) {
deba@220	2048	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	2049	Value val = Map::operator[](keys[i]);
deba@220	2050	typename Container::iterator it = _inv_map.find(val);
deba@220	2051	if (it != _inv_map.end() && it->second == keys[i]) {
deba@220	2052	_inv_map.erase(it);
deba@220	2053	}
deba@220	2054	}
deba@220	2055	Map::erase(keys);
deba@220	2056	}
deba@220	2057
kpeter@559	2058	/// \brief Clear the keys from the map and the inverse map.
deba@220	2059	///
kpeter@559	2060	/// Clear the keys from the map and the inverse map. It is called by the
deba@220	2061	/// \c AlterationNotifier.
deba@220	2062	virtual void clear() {
deba@220	2063	_inv_map.clear();
deba@220	2064	Map::clear();
deba@220	2065	}
deba@220	2066
deba@220	2067	public:
deba@220	2068
deba@220	2069	/// \brief The inverse map type.
deba@220	2070	///
deba@220	2071	/// The inverse of this map. The subscript operator of the map
kpeter@559	2072	/// gives back the item that was last assigned to the value.
deba@220	2073	class InverseMap {
deba@220	2074	public:
kpeter@559	2075	/// \brief Constructor
deba@220	2076	///
deba@220	2077	/// Constructor of the InverseMap.
alpar@572	2078	explicit InverseMap(const CrossRefMap& inverted)
deba@220	2079	: _inverted(inverted) {}
deba@220	2080
deba@220	2081	/// The value type of the InverseMap.
alpar@572	2082	typedef typename CrossRefMap::Key Value;
deba@220	2083	/// The key type of the InverseMap.
alpar@572	2084	typedef typename CrossRefMap::Value Key;
deba@220	2085
deba@220	2086	/// \brief Subscript operator.
deba@220	2087	///
kpeter@559	2088	/// Subscript operator. It gives back the item
kpeter@559	2089	/// that was last assigned to the given value.
deba@220	2090	Value operator[](const Key& key) const {
deba@220	2091	return _inverted(key);
deba@220	2092	}
deba@220	2093
deba@220	2094	private:
alpar@572	2095	const CrossRefMap& _inverted;
deba@220	2096	};
deba@220	2097
kpeter@559	2098	/// \brief It gives back the read-only inverse map.
deba@220	2099	///
kpeter@559	2100	/// It gives back the read-only inverse map.
deba@220	2101	InverseMap inverse() const {
deba@220	2102	return InverseMap(*this);
deba@220	2103	}
deba@220	2104
deba@220	2105	};
deba@220	2106
alpar@572	2107	/// \brief Provides continuous and unique ID for the
alpar@572	2108	/// items of a graph.
deba@220	2109	///
alpar@572	2110	/// RangeIdMap provides a unique and continuous
alpar@572	2111	/// ID for each item of a given type (\c Node, \c Arc or
kpeter@559	2112	/// \c Edge) in a graph. This id is
kpeter@559	2113	/// - \b unique: different items get different ids,
kpeter@559	2114	/// - \b continuous: the range of the ids is the set of integers
kpeter@559	2115	/// between 0 and \c n-1, where \c n is the number of the items of
alpar@572	2116	/// this type (\c Node, \c Arc or \c Edge).
alpar@572	2117	/// - So, the ids can change when deleting an item of the same type.
deba@220	2118	///
kpeter@559	2119	/// Thus this id is not (necessarily) the same as what can get using
kpeter@559	2120	/// the \c id() function of the graph or \ref IdMap.
kpeter@559	2121	/// This map can be inverted with its member class \c InverseMap,
kpeter@559	2122	/// or with the \c operator() member.
kpeter@559	2123	///
kpeter@559	2124	/// \tparam GR The graph type.
kpeter@559	2125	/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559	2126	/// \c GR::Edge).
kpeter@559	2127	///
kpeter@559	2128	/// \see IdMap
kpeter@559	2129	template <typename GR, typename K>
alpar@572	2130	class RangeIdMap
kpeter@559	2131	: protected ItemSetTraits<GR, K>::template Map<int>::Type {
kpeter@559	2132
kpeter@559	2133	typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
deba@220	2134
deba@220	2135	public:
alpar@572	2136	/// The graph type of RangeIdMap.
kpeter@559	2137	typedef GR Graph;
kpeter@617	2138	typedef GR Digraph;
alpar@572	2139	/// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559	2140	typedef K Item;
alpar@572	2141	/// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559	2142	typedef K Key;
alpar@572	2143	/// The value type of RangeIdMap.
kpeter@559	2144	typedef int Value;
deba@220	2145
deba@220	2146	/// \brief Constructor.
deba@220	2147	///
alpar@572	2148	/// Constructor.
alpar@572	2149	explicit RangeIdMap(const Graph& gr) : Map(gr) {
deba@220	2150	Item it;
deba@220	2151	const typename Map::Notifier* nf = Map::notifier();
deba@220	2152	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2153	Map::set(it, _inv_map.size());
deba@220	2154	_inv_map.push_back(it);
deba@220	2155	}
deba@220	2156	}
deba@220	2157
deba@220	2158	protected:
deba@220	2159
kpeter@559	2160	/// \brief Adds a new key to the map.
deba@220	2161	///
deba@220	2162	/// Add a new key to the map. It is called by the
deba@220	2163	/// \c AlterationNotifier.
deba@220	2164	virtual void add(const Item& item) {
deba@220	2165	Map::add(item);
deba@220	2166	Map::set(item, _inv_map.size());
deba@220	2167	_inv_map.push_back(item);
deba@220	2168	}
deba@220	2169
deba@220	2170	/// \brief Add more new keys to the map.
deba@220	2171	///
deba@220	2172	/// Add more new keys to the map. It is called by the
deba@220	2173	/// \c AlterationNotifier.
deba@220	2174	virtual void add(const std::vector<Item>& items) {
deba@220	2175	Map::add(items);
deba@220	2176	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2177	Map::set(items[i], _inv_map.size());
deba@220	2178	_inv_map.push_back(items[i]);
deba@220	2179	}
deba@220	2180	}
deba@220	2181
deba@220	2182	/// \brief Erase the key from the map.
deba@220	2183	///
deba@220	2184	/// Erase the key from the map. It is called by the
deba@220	2185	/// \c AlterationNotifier.
deba@220	2186	virtual void erase(const Item& item) {
deba@220	2187	Map::set(_inv_map.back(), Map::operator[](item));
deba@220	2188	_inv_map[Map::operator[](item)] = _inv_map.back();
deba@220	2189	_inv_map.pop_back();
deba@220	2190	Map::erase(item);
deba@220	2191	}
deba@220	2192
deba@220	2193	/// \brief Erase more keys from the map.
deba@220	2194	///
deba@220	2195	/// Erase more keys from the map. It is called by the
deba@220	2196	/// \c AlterationNotifier.
deba@220	2197	virtual void erase(const std::vector<Item>& items) {
deba@220	2198	for (int i = 0; i < int(items.size()); ++i) {
deba@220	2199	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@220	2200	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@220	2201	_inv_map.pop_back();
deba@220	2202	}
deba@220	2203	Map::erase(items);
deba@220	2204	}
deba@220	2205
deba@220	2206	/// \brief Build the unique map.
deba@220	2207	///
deba@220	2208	/// Build the unique map. It is called by the
deba@220	2209	/// \c AlterationNotifier.
deba@220	2210	virtual void build() {
deba@220	2211	Map::build();
deba@220	2212	Item it;
deba@220	2213	const typename Map::Notifier* nf = Map::notifier();
deba@220	2214	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	2215	Map::set(it, _inv_map.size());
deba@220	2216	_inv_map.push_back(it);
deba@220	2217	}
deba@220	2218	}
deba@220	2219
deba@220	2220	/// \brief Clear the keys from the map.
deba@220	2221	///
deba@220	2222	/// Clear the keys from the map. It is called by the
deba@220	2223	/// \c AlterationNotifier.
deba@220	2224	virtual void clear() {
deba@220	2225	_inv_map.clear();
deba@220	2226	Map::clear();
deba@220	2227	}
deba@220	2228
deba@220	2229	public:
deba@220	2230
deba@220	2231	/// \brief Returns the maximal value plus one.
deba@220	2232	///
deba@220	2233	/// Returns the maximal value plus one in the map.
deba@220	2234	unsigned int size() const {
deba@220	2235	return _inv_map.size();
deba@220	2236	}
deba@220	2237
deba@220	2238	/// \brief Swaps the position of the two items in the map.
deba@220	2239	///
deba@220	2240	/// Swaps the position of the two items in the map.
deba@220	2241	void swap(const Item& p, const Item& q) {
deba@220	2242	int pi = Map::operator[](p);
deba@220	2243	int qi = Map::operator[](q);
deba@220	2244	Map::set(p, qi);
deba@220	2245	_inv_map[qi] = p;
deba@220	2246	Map::set(q, pi);
deba@220	2247	_inv_map[pi] = q;
deba@220	2248	}
deba@220	2249
alpar@572	2250	/// \brief Gives back the \e RangeId of the item
deba@220	2251	///
alpar@572	2252	/// Gives back the \e RangeId of the item.
deba@220	2253	int operator[](const Item& item) const {
deba@220	2254	return Map::operator[](item);
deba@220	2255	}
deba@220	2256
alpar@572	2257	/// \brief Gives back the item belonging to a \e RangeId
deba@693	2258	///
alpar@572	2259	/// Gives back the item belonging to a \e RangeId.
deba@220	2260	Item operator()(int id) const {
deba@220	2261	return _inv_map[id];
deba@220	2262	}
deba@220	2263
deba@220	2264	private:
deba@220	2265
deba@220	2266	typedef std::vector<Item> Container;
deba@220	2267	Container _inv_map;
deba@220	2268
deba@220	2269	public:
kpeter@559	2270
alpar@572	2271	/// \brief The inverse map type of RangeIdMap.
deba@220	2272	///
alpar@572	2273	/// The inverse map type of RangeIdMap.
deba@220	2274	class InverseMap {
deba@220	2275	public:
kpeter@559	2276	/// \brief Constructor
deba@220	2277	///
deba@220	2278	/// Constructor of the InverseMap.
alpar@572	2279	explicit InverseMap(const RangeIdMap& inverted)
deba@220	2280	: _inverted(inverted) {}
deba@220	2281
deba@220	2282
deba@220	2283	/// The value type of the InverseMap.
alpar@572	2284	typedef typename RangeIdMap::Key Value;
deba@220	2285	/// The key type of the InverseMap.
alpar@572	2286	typedef typename RangeIdMap::Value Key;
deba@220	2287
deba@220	2288	/// \brief Subscript operator.
deba@220	2289	///
deba@220	2290	/// Subscript operator. It gives back the item
kpeter@559	2291	/// that the descriptor currently belongs to.
deba@220	2292	Value operator[](const Key& key) const {
deba@220	2293	return _inverted(key);
deba@220	2294	}
deba@220	2295
deba@220	2296	/// \brief Size of the map.
deba@220	2297	///
deba@220	2298	/// Returns the size of the map.
deba@220	2299	unsigned int size() const {
deba@220	2300	return _inverted.size();
deba@220	2301	}
deba@220	2302
deba@220	2303	private:
alpar@572	2304	const RangeIdMap& _inverted;
deba@220	2305	};
deba@220	2306
deba@220	2307	/// \brief Gives back the inverse of the map.
deba@220	2308	///
deba@220	2309	/// Gives back the inverse of the map.
deba@220	2310	const InverseMap inverse() const {
deba@220	2311	return InverseMap(*this);
deba@220	2312	}
deba@220	2313	};
deba@220	2314
deba@693	2315	/// \brief Dynamic iterable bool map.
deba@693	2316	///
deba@693	2317	/// This class provides a special graph map type which can store for
deba@693	2318	/// each graph item(node, arc, edge, etc.) a bool value. For both
deba@693	2319	/// the true and the false values it is possible to iterate on the
deba@693	2320	/// keys.
deba@693	2321	///
deba@693	2322	/// \param GR The graph type.
deba@693	2323	/// \param ITEM One of the graph's item types, the key of the map.
deba@693	2324	template <typename GR, typename ITEM>
deba@693	2325	class IterableBoolMap
deba@693	2326	: protected ItemSetTraits<GR, ITEM>::template Map<int>::Type {
deba@693	2327	private:
deba@693	2328	typedef GR Graph;
deba@693	2329
deba@693	2330	typedef typename ItemSetTraits<Graph, ITEM>::ItemIt KeyIt;
deba@693	2331	typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent;
deba@693	2332
deba@693	2333	std::vector<ITEM> _array;
deba@693	2334	int _sep;
deba@693	2335
deba@693	2336	public:
deba@693	2337
deba@693	2338	/// Indicates that the map if reference map.
deba@693	2339	typedef True ReferenceMapTag;
deba@693	2340
deba@693	2341	/// The key type
deba@693	2342	typedef ITEM Key;
deba@693	2343	/// The value type
deba@693	2344	typedef bool Value;
deba@693	2345	/// The const reference type.
deba@693	2346	typedef const Value& ConstReference;
deba@693	2347
deba@693	2348	private:
deba@693	2349
deba@693	2350	int position(const Key& key) const {
deba@693	2351	return Parent::operator[](key);
deba@693	2352	}
deba@693	2353
deba@693	2354	public:
deba@693	2355
deba@693	2356	/// \brief Refernce to the value of the map.
deba@693	2357	///
deba@693	2358	/// This class is similar to the bool type. It can be converted to
deba@693	2359	/// bool and it provides the same operators.
deba@693	2360	class Reference {
deba@693	2361	friend class IterableBoolMap;
deba@693	2362	private:
deba@693	2363	Reference(IterableBoolMap& map, const Key& key)
deba@693	2364	: _key(key), _map(map) {}
deba@693	2365	public:
deba@693	2366
deba@693	2367	Reference& operator=(const Reference& value) {
deba@693	2368	_map.set(_key, static_cast<bool>(value));
deba@693	2369	return *this;
deba@693	2370	}
deba@693	2371
deba@693	2372	operator bool() const {
deba@693	2373	return static_cast<const IterableBoolMap&>(_map)[_key];
deba@693	2374	}
deba@693	2375
deba@693	2376	Reference& operator=(bool value) {
deba@693	2377	_map.set(_key, value);
deba@693	2378	return *this;
deba@693	2379	}
deba@693	2380	Reference& operator&=(bool value) {
deba@693	2381	_map.set(_key, _map[_key] & value);
deba@693	2382	return *this;
deba@693	2383	}
deba@693	2384	Reference& operator\|=(bool value) {
deba@693	2385	_map.set(_key, _map[_key] \| value);
deba@693	2386	return *this;
deba@693	2387	}
deba@693	2388	Reference& operator^=(bool value) {
deba@693	2389	_map.set(_key, _map[_key] ^ value);
deba@693	2390	return *this;
deba@693	2391	}
deba@693	2392	private:
deba@693	2393	Key _key;
deba@693	2394	IterableBoolMap& _map;
deba@693	2395	};
deba@693	2396
deba@693	2397	/// \brief Constructor of the map with a default value.
deba@693	2398	///
deba@693	2399	/// Constructor of the map with a default value.
deba@693	2400	explicit IterableBoolMap(const Graph& graph, bool def = false)
deba@693	2401	: Parent(graph) {
deba@693	2402	typename Parent::Notifier* nf = Parent::notifier();
deba@693	2403	Key it;
deba@693	2404	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@693	2405	Parent::set(it, _array.size());
deba@693	2406	_array.push_back(it);
deba@693	2407	}
deba@693	2408	_sep = (def ? _array.size() : 0);
deba@693	2409	}
deba@693	2410
deba@693	2411	/// \brief Const subscript operator of the map.
deba@693	2412	///
deba@693	2413	/// Const subscript operator of the map.
deba@693	2414	bool operator[](const Key& key) const {
deba@693	2415	return position(key) < _sep;
deba@693	2416	}
deba@693	2417
deba@693	2418	/// \brief Subscript operator of the map.
deba@693	2419	///
deba@693	2420	/// Subscript operator of the map.
deba@693	2421	Reference operator[](const Key& key) {
deba@693	2422	return Reference(*this, key);
deba@693	2423	}
deba@693	2424
deba@693	2425	/// \brief Set operation of the map.
deba@693	2426	///
deba@693	2427	/// Set operation of the map.
deba@693	2428	void set(const Key& key, bool value) {
deba@693	2429	int pos = position(key);
deba@693	2430	if (value) {
deba@693	2431	if (pos < _sep) return;
deba@693	2432	Key tmp = _array[_sep];
deba@693	2433	_array[_sep] = key;
deba@693	2434	Parent::set(key, _sep);
deba@693	2435	_array[pos] = tmp;
deba@693	2436	Parent::set(tmp, pos);
deba@693	2437	++_sep;
deba@693	2438	} else {
deba@693	2439	if (pos >= _sep) return;
deba@693	2440	--_sep;
deba@693	2441	Key tmp = _array[_sep];
deba@693	2442	_array[_sep] = key;
deba@693	2443	Parent::set(key, _sep);
deba@693	2444	_array[pos] = tmp;
deba@693	2445	Parent::set(tmp, pos);
deba@693	2446	}
deba@693	2447	}
deba@693	2448
deba@693	2449	/// \brief Set all items.
deba@693	2450	///
deba@693	2451	/// Set all items in the map.
deba@693	2452	/// \note Constant time operation.
deba@693	2453	void setAll(bool value) {
deba@693	2454	_sep = (value ? _array.size() : 0);
deba@693	2455	}
deba@693	2456
deba@693	2457	/// \brief Returns the number of the keys mapped to true.
deba@693	2458	///
deba@693	2459	/// Returns the number of the keys mapped to true.
deba@693	2460	int trueNum() const {
deba@693	2461	return _sep;
deba@693	2462	}
deba@693	2463
deba@693	2464	/// \brief Returns the number of the keys mapped to false.
deba@693	2465	///
deba@693	2466	/// Returns the number of the keys mapped to false.
deba@693	2467	int falseNum() const {
deba@693	2468	return _array.size() - _sep;
deba@693	2469	}
deba@693	2470
deba@693	2471	/// \brief Iterator for the keys mapped to true.
deba@693	2472	///
deba@693	2473	/// Iterator for the keys mapped to true. It works
deba@693	2474	/// like a graph item iterator in the map, it can be converted
deba@693	2475	/// the key type of the map, incremented with \c ++ operator, and
deba@693	2476	/// if the iterator leave the last valid key it will be equal to
deba@693	2477	/// \c INVALID.
deba@693	2478	class TrueIt : public Key {
deba@693	2479	public:
deba@693	2480	typedef Key Parent;
deba@693	2481
deba@693	2482	/// \brief Creates an iterator.
deba@693	2483	///
deba@693	2484	/// Creates an iterator. It iterates on the
deba@693	2485	/// keys which mapped to true.
deba@693	2486	/// \param map The IterableIntMap
deba@693	2487	explicit TrueIt(const IterableBoolMap& map)
deba@693	2488	: Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
deba@693	2489	_map(&map) {}
deba@693	2490
deba@693	2491	/// \brief Invalid constructor \& conversion.
deba@693	2492	///
deba@693	2493	/// This constructor initializes the key to be invalid.
deba@693	2494	/// \sa Invalid for more details.
deba@693	2495	TrueIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693	2496
deba@693	2497	/// \brief Increment operator.
deba@693	2498	///
deba@693	2499	/// Increment Operator.
deba@693	2500	TrueIt& operator++() {
deba@693	2501	int pos = _map->position(*this);
deba@693	2502	Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
deba@693	2503	return *this;
deba@693	2504	}
deba@693	2505
deba@693	2506
deba@693	2507	private:
deba@693	2508	const IterableBoolMap* _map;
deba@693	2509	};
deba@693	2510
deba@693	2511	/// \brief Iterator for the keys mapped to false.
deba@693	2512	///
deba@693	2513	/// Iterator for the keys mapped to false. It works
deba@693	2514	/// like a graph item iterator in the map, it can be converted
deba@693	2515	/// the key type of the map, incremented with \c ++ operator, and
deba@693	2516	/// if the iterator leave the last valid key it will be equal to
deba@693	2517	/// \c INVALID.
deba@693	2518	class FalseIt : public Key {
deba@693	2519	public:
deba@693	2520	typedef Key Parent;
deba@693	2521
deba@693	2522	/// \brief Creates an iterator.
deba@693	2523	///
deba@693	2524	/// Creates an iterator. It iterates on the
deba@693	2525	/// keys which mapped to false.
deba@693	2526	/// \param map The IterableIntMap
deba@693	2527	explicit FalseIt(const IterableBoolMap& map)
deba@693	2528	: Parent(map._sep < int(map._array.size()) ?
deba@693	2529	map._array.back() : INVALID), _map(&map) {}
deba@693	2530
deba@693	2531	/// \brief Invalid constructor \& conversion.
deba@693	2532	///
deba@693	2533	/// This constructor initializes the key to be invalid.
deba@693	2534	/// \sa Invalid for more details.
deba@693	2535	FalseIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693	2536
deba@693	2537	/// \brief Increment operator.
deba@693	2538	///
deba@693	2539	/// Increment Operator.
deba@693	2540	FalseIt& operator++() {
deba@693	2541	int pos = _map->position(*this);
deba@693	2542	Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
deba@693	2543	return *this;
deba@693	2544	}
deba@693	2545
deba@693	2546	private:
deba@693	2547	const IterableBoolMap* _map;
deba@693	2548	};
deba@693	2549
deba@693	2550	/// \brief Iterator for the keys mapped to a given value.
deba@693	2551	///
deba@693	2552	/// Iterator for the keys mapped to a given value. It works
deba@693	2553	/// like a graph item iterator in the map, it can be converted
deba@693	2554	/// the key type of the map, incremented with \c ++ operator, and
deba@693	2555	/// if the iterator leave the last valid key it will be equal to
deba@693	2556	/// \c INVALID.
deba@693	2557	class ItemIt : public Key {
deba@693	2558	public:
deba@693	2559	typedef Key Parent;
deba@693	2560
deba@693	2561	/// \brief Creates an iterator.
deba@693	2562	///
deba@693	2563	/// Creates an iterator. It iterates on the
deba@693	2564	/// keys which mapped to false.
deba@693	2565	/// \param map The IterableIntMap
deba@693	2566	/// \param value Which elements should be iterated.
deba@693	2567	ItemIt(const IterableBoolMap& map, bool value)
deba@693	2568	: Parent(value ?
deba@693	2569	(map._sep > 0 ?
deba@693	2570	map._array[map._sep - 1] : INVALID) :
deba@693	2571	(map._sep < int(map._array.size()) ?
deba@693	2572	map._array.back() : INVALID)), _map(&map) {}
deba@693	2573
deba@693	2574	/// \brief Invalid constructor \& conversion.
deba@693	2575	///
deba@693	2576	/// This constructor initializes the key to be invalid.
deba@693	2577	/// \sa Invalid for more details.
deba@693	2578	ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693	2579
deba@693	2580	/// \brief Increment operator.
deba@693	2581	///
deba@693	2582	/// Increment Operator.
deba@693	2583	ItemIt& operator++() {
deba@693	2584	int pos = _map->position(*this);
deba@693	2585	int _sep = pos >= _map->_sep ? _map->_sep : 0;
deba@693	2586	Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
deba@693	2587	return *this;
deba@693	2588	}
deba@693	2589
deba@693	2590	private:
deba@693	2591	const IterableBoolMap* _map;
deba@693	2592	};
deba@693	2593
deba@693	2594	protected:
deba@693	2595
deba@693	2596	virtual void add(const Key& key) {
deba@693	2597	Parent::add(key);
deba@693	2598	Parent::set(key, _array.size());
deba@693	2599	_array.push_back(key);
deba@693	2600	}
deba@693	2601
deba@693	2602	virtual void add(const std::vector<Key>& keys) {
deba@693	2603	Parent::add(keys);
deba@693	2604	for (int i = 0; i < int(keys.size()); ++i) {
deba@693	2605	Parent::set(keys[i], _array.size());
deba@693	2606	_array.push_back(keys[i]);
deba@693	2607	}
deba@693	2608	}
deba@693	2609
deba@693	2610	virtual void erase(const Key& key) {
deba@693	2611	int pos = position(key);
deba@693	2612	if (pos < _sep) {
deba@693	2613	--_sep;
deba@693	2614	Parent::set(_array[_sep], pos);
deba@693	2615	_array[pos] = _array[_sep];
deba@693	2616	Parent::set(_array.back(), _sep);
deba@693	2617	_array[_sep] = _array.back();
deba@693	2618	_array.pop_back();
deba@693	2619	} else {
deba@693	2620	Parent::set(_array.back(), pos);
deba@693	2621	_array[pos] = _array.back();
deba@693	2622	_array.pop_back();
deba@693	2623	}
deba@693	2624	Parent::erase(key);
deba@693	2625	}
deba@693	2626
deba@693	2627	virtual void erase(const std::vector<Key>& keys) {
deba@693	2628	for (int i = 0; i < int(keys.size()); ++i) {
deba@693	2629	int pos = position(keys[i]);
deba@693	2630	if (pos < _sep) {
deba@693	2631	--_sep;
deba@693	2632	Parent::set(_array[_sep], pos);
deba@693	2633	_array[pos] = _array[_sep];
deba@693	2634	Parent::set(_array.back(), _sep);
deba@693	2635	_array[_sep] = _array.back();
deba@693	2636	_array.pop_back();
deba@693	2637	} else {
deba@693	2638	Parent::set(_array.back(), pos);
deba@693	2639	_array[pos] = _array.back();
deba@693	2640	_array.pop_back();
deba@693	2641	}
deba@693	2642	}
deba@693	2643	Parent::erase(keys);
deba@693	2644	}
deba@693	2645
deba@693	2646	virtual void build() {
deba@693	2647	Parent::build();
deba@693	2648	typename Parent::Notifier* nf = Parent::notifier();
deba@693	2649	Key it;
deba@693	2650	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@693	2651	Parent::set(it, _array.size());
deba@693	2652	_array.push_back(it);
deba@693	2653	}
deba@693	2654	_sep = 0;
deba@693	2655	}
deba@693	2656
deba@693	2657	virtual void clear() {
deba@693	2658	_array.clear();
deba@693	2659	_sep = 0;
deba@693	2660	Parent::clear();
deba@693	2661	}
deba@693	2662
deba@693	2663	};
deba@693	2664
deba@693	2665
deba@693	2666	namespace _maps_bits {
deba@693	2667	template <typename Item>
deba@693	2668	struct IterableIntMapNode {
deba@693	2669	IterableIntMapNode() : value(-1) {}
deba@693	2670	IterableIntMapNode(int _value) : value(_value) {}
deba@693	2671	Item prev, next;
deba@693	2672	int value;
deba@693	2673	};
deba@693	2674	}
deba@693	2675
deba@693	2676	///\ingroup graph_maps
deba@693	2677	///
deba@693	2678	/// \brief Dynamic iterable integer map.
deba@693	2679	///
deba@693	2680	/// This class provides a special graph map type which can store
deba@693	2681	/// for each graph item(node, edge, etc.) an integer value. For each
deba@693	2682	/// non negative value it is possible to iterate on the keys which
deba@693	2683	/// mapped to the given value.
deba@693	2684	///
deba@693	2685	/// \note The size of the data structure depends on the highest
deba@693	2686	/// value in the map.
deba@693	2687	///
deba@693	2688	/// \param GR The graph type.
deba@693	2689	/// \param ITEM One of the graph's item type, the key of the map.
deba@693	2690	template <typename GR, typename ITEM>
deba@693	2691	class IterableIntMap
deba@693	2692	: protected ItemSetTraits<GR, ITEM>::
deba@693	2693	template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type {
deba@693	2694	public:
deba@693	2695	typedef typename ItemSetTraits<GR, ITEM>::
deba@693	2696	template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type Parent;
deba@693	2697
deba@693	2698	/// The key type
deba@693	2699	typedef ITEM Key;
deba@693	2700	/// The value type
deba@693	2701	typedef int Value;
deba@693	2702	/// The graph type
deba@693	2703	typedef GR Graph;
deba@693	2704
deba@693	2705	/// \brief Constructor of the map.
deba@693	2706	///
deba@693	2707	/// Constructor of the map. It set all values to -1.
deba@693	2708	explicit IterableIntMap(const Graph& graph)
deba@693	2709	: Parent(graph) {}
deba@693	2710
deba@693	2711	/// \brief Constructor of the map with a given value.
deba@693	2712	///
deba@693	2713	/// Constructor of the map with a given value.
deba@693	2714	explicit IterableIntMap(const Graph& graph, int value)
deba@693	2715	: Parent(graph, _maps_bits::IterableIntMapNode<ITEM>(value)) {
deba@693	2716	if (value >= 0) {
deba@693	2717	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693	2718	lace(it);
deba@693	2719	}
deba@693	2720	}
deba@693	2721	}
deba@693	2722
deba@693	2723	private:
deba@693	2724
deba@693	2725	void unlace(const Key& key) {
deba@693	2726	typename Parent::Value& node = Parent::operator[](key);
deba@693	2727	if (node.value < 0) return;
deba@693	2728	if (node.prev != INVALID) {
deba@693	2729	Parent::operator[](node.prev).next = node.next;
deba@693	2730	} else {
deba@693	2731	_first[node.value] = node.next;
deba@693	2732	}
deba@693	2733	if (node.next != INVALID) {
deba@693	2734	Parent::operator[](node.next).prev = node.prev;
deba@693	2735	}
deba@693	2736	while (!_first.empty() && _first.back() == INVALID) {
deba@693	2737	_first.pop_back();
deba@693	2738	}
deba@693	2739	}
deba@693	2740
deba@693	2741	void lace(const Key& key) {
deba@693	2742	typename Parent::Value& node = Parent::operator[](key);
deba@693	2743	if (node.value < 0) return;
deba@693	2744	if (node.value >= int(_first.size())) {
deba@693	2745	_first.resize(node.value + 1, INVALID);
deba@693	2746	}
deba@693	2747	node.prev = INVALID;
deba@693	2748	node.next = _first[node.value];
deba@693	2749	if (node.next != INVALID) {
deba@693	2750	Parent::operator[](node.next).prev = key;
deba@693	2751	}
deba@693	2752	_first[node.value] = key;
deba@693	2753	}
deba@693	2754
deba@693	2755	public:
deba@693	2756
deba@693	2757	/// Indicates that the map if reference map.
deba@693	2758	typedef True ReferenceMapTag;
deba@693	2759
deba@693	2760	/// \brief Refernce to the value of the map.
deba@693	2761	///
deba@693	2762	/// This class is similar to the int type. It can
deba@693	2763	/// be converted to int and it has the same operators.
deba@693	2764	class Reference {
deba@693	2765	friend class IterableIntMap;
deba@693	2766	private:
deba@693	2767	Reference(IterableIntMap& map, const Key& key)
deba@693	2768	: _key(key), _map(map) {}
deba@693	2769	public:
deba@693	2770
deba@693	2771	Reference& operator=(const Reference& value) {
deba@693	2772	_map.set(_key, static_cast<const int&>(value));
deba@693	2773	return *this;
deba@693	2774	}
deba@693	2775
deba@693	2776	operator const int&() const {
deba@693	2777	return static_cast<const IterableIntMap&>(_map)[_key];
deba@693	2778	}
deba@693	2779
deba@693	2780	Reference& operator=(int value) {
deba@693	2781	_map.set(_key, value);
deba@693	2782	return *this;
deba@693	2783	}
deba@693	2784	Reference& operator++() {
deba@693	2785	_map.set(_key, _map[_key] + 1);
deba@693	2786	return *this;
deba@693	2787	}
deba@693	2788	int operator++(int) {
deba@693	2789	int value = _map[_key];
deba@693	2790	_map.set(_key, value + 1);
deba@693	2791	return value;
deba@693	2792	}
deba@693	2793	Reference& operator--() {
deba@693	2794	_map.set(_key, _map[_key] - 1);
deba@693	2795	return *this;
deba@693	2796	}
deba@693	2797	int operator--(int) {
deba@693	2798	int value = _map[_key];
deba@693	2799	_map.set(_key, value - 1);
deba@693	2800	return value;
deba@693	2801	}
deba@693	2802	Reference& operator+=(int value) {
deba@693	2803	_map.set(_key, _map[_key] + value);
deba@693	2804	return *this;
deba@693	2805	}
deba@693	2806	Reference& operator-=(int value) {
deba@693	2807	_map.set(_key, _map[_key] - value);
deba@693	2808	return *this;
deba@693	2809	}
deba@693	2810	Reference& operator*=(int value) {
deba@693	2811	_map.set(_key, _map[_key] * value);
deba@693	2812	return *this;
deba@693	2813	}
deba@693	2814	Reference& operator/=(int value) {
deba@693	2815	_map.set(_key, _map[_key] / value);
deba@693	2816	return *this;
deba@693	2817	}
deba@693	2818	Reference& operator%=(int value) {
deba@693	2819	_map.set(_key, _map[_key] % value);
deba@693	2820	return *this;
deba@693	2821	}
deba@693	2822	Reference& operator&=(int value) {
deba@693	2823	_map.set(_key, _map[_key] & value);
deba@693	2824	return *this;
deba@693	2825	}
deba@693	2826	Reference& operator\|=(int value) {
deba@693	2827	_map.set(_key, _map[_key] \| value);
deba@693	2828	return *this;
deba@693	2829	}
deba@693	2830	Reference& operator^=(int value) {
deba@693	2831	_map.set(_key, _map[_key] ^ value);
deba@693	2832	return *this;
deba@693	2833	}
deba@693	2834	Reference& operator<<=(int value) {
deba@693	2835	_map.set(_key, _map[_key] << value);
deba@693	2836	return *this;
deba@693	2837	}
deba@693	2838	Reference& operator>>=(int value) {
deba@693	2839	_map.set(_key, _map[_key] >> value);
deba@693	2840	return *this;
deba@693	2841	}
deba@693	2842
deba@693	2843	private:
deba@693	2844	Key _key;
deba@693	2845	IterableIntMap& _map;
deba@693	2846	};
deba@693	2847
deba@693	2848	/// The const reference type.
deba@693	2849	typedef const Value& ConstReference;
deba@693	2850
deba@693	2851	/// \brief Gives back the maximal value plus one.
deba@693	2852	///
deba@693	2853	/// Gives back the maximal value plus one.
deba@693	2854	int size() const {
deba@693	2855	return _first.size();
deba@693	2856	}
deba@693	2857
deba@693	2858	/// \brief Set operation of the map.
deba@693	2859	///
deba@693	2860	/// Set operation of the map.
deba@693	2861	void set(const Key& key, const Value& value) {
deba@693	2862	unlace(key);
deba@693	2863	Parent::operator[](key).value = value;
deba@693	2864	lace(key);
deba@693	2865	}
deba@693	2866
deba@693	2867	/// \brief Const subscript operator of the map.
deba@693	2868	///
deba@693	2869	/// Const subscript operator of the map.
deba@693	2870	const Value& operator[](const Key& key) const {
deba@693	2871	return Parent::operator[](key).value;
deba@693	2872	}
deba@693	2873
deba@693	2874	/// \brief Subscript operator of the map.
deba@693	2875	///
deba@693	2876	/// Subscript operator of the map.
deba@693	2877	Reference operator[](const Key& key) {
deba@693	2878	return Reference(*this, key);
deba@693	2879	}
deba@693	2880
deba@693	2881	/// \brief Iterator for the keys with the same value.
deba@693	2882	///
deba@693	2883	/// Iterator for the keys with the same value. It works
deba@693	2884	/// like a graph item iterator in the map, it can be converted
deba@693	2885	/// the item type of the map, incremented with \c ++ operator, and
deba@693	2886	/// if the iterator leave the last valid item it will be equal to
deba@693	2887	/// \c INVALID.
deba@693	2888	class ItemIt : public ITEM {
deba@693	2889	public:
deba@693	2890	typedef ITEM Parent;
deba@693	2891
deba@693	2892	/// \brief Invalid constructor \& conversion.
deba@693	2893	///
deba@693	2894	/// This constructor initializes the item to be invalid.
deba@693	2895	/// \sa Invalid for more details.
deba@693	2896	ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693	2897
deba@693	2898	/// \brief Creates an iterator with a value.
deba@693	2899	///
deba@693	2900	/// Creates an iterator with a value. It iterates on the
deba@693	2901	/// keys which have the given value.
deba@693	2902	/// \param map The IterableIntMap
deba@693	2903	/// \param value The value
deba@693	2904	ItemIt(const IterableIntMap& map, int value) : _map(&map) {
deba@693	2905	if (value < 0 \|\| value >= int(_map->_first.size())) {
deba@693	2906	Parent::operator=(INVALID);
deba@693	2907	} else {
deba@693	2908	Parent::operator=(_map->_first[value]);
deba@693	2909	}
deba@693	2910	}
deba@693	2911
deba@693	2912	/// \brief Increment operator.
deba@693	2913	///
deba@693	2914	/// Increment Operator.
deba@693	2915	ItemIt& operator++() {
deba@693	2916	Parent::operator=(_map->IterableIntMap::Parent::
deba@693	2917	operator[](static_cast<Parent&>(*this)).next);
deba@693	2918	return *this;
deba@693	2919	}
deba@693	2920
deba@693	2921
deba@693	2922	private:
deba@693	2923	const IterableIntMap* _map;
deba@693	2924	};
deba@693	2925
deba@693	2926	protected:
deba@693	2927
deba@693	2928	virtual void erase(const Key& key) {
deba@693	2929	unlace(key);
deba@693	2930	Parent::erase(key);
deba@693	2931	}
deba@693	2932
deba@693	2933	virtual void erase(const std::vector<Key>& keys) {
deba@693	2934	for (int i = 0; i < int(keys.size()); ++i) {
deba@693	2935	unlace(keys[i]);
deba@693	2936	}
deba@693	2937	Parent::erase(keys);
deba@693	2938	}
deba@693	2939
deba@693	2940	virtual void clear() {
deba@693	2941	_first.clear();
deba@693	2942	Parent::clear();
deba@693	2943	}
deba@693	2944
deba@693	2945	private:
deba@693	2946	std::vector<ITEM> _first;
deba@693	2947	};
deba@693	2948
deba@693	2949	namespace _maps_bits {
deba@693	2950	template <typename Item, typename Value>
deba@693	2951	struct IterableValueMapNode {
deba@693	2952	IterableValueMapNode(Value _value = Value()) : value(_value) {}
deba@693	2953	Item prev, next;
deba@693	2954	Value value;
deba@693	2955	};
deba@693	2956	}
deba@693	2957
deba@693	2958	///\ingroup graph_maps
deba@693	2959	///
deba@693	2960	/// \brief Dynamic iterable map for comparable values.
deba@693	2961	///
deba@693	2962	/// This class provides a special graph map type which can store
deba@693	2963	/// for each graph item(node, edge, etc.) a value. For each
deba@693	2964	/// value it is possible to iterate on the keys which mapped to the
deba@693	2965	/// given value. The type stores for each value a linked list with
deba@693	2966	/// the items which mapped to the value, and the values are stored
deba@693	2967	/// in balanced binary tree. The values of the map can be accessed
deba@693	2968	/// with stl compatible forward iterator.
deba@693	2969	///
deba@693	2970	/// This type is not reference map so it cannot be modified with
deba@693	2971	/// the subscription operator.
deba@693	2972	///
deba@693	2973	/// \see InvertableMap
deba@693	2974	///
deba@693	2975	/// \param GR The graph type.
deba@693	2976	/// \param ITEM One of the graph's item type, the key of the map.
deba@693	2977	/// \param VAL Any comparable value type.
deba@693	2978	template <typename GR, typename ITEM, typename VAL>
deba@693	2979	class IterableValueMap
deba@693	2980	: protected ItemSetTraits<GR, ITEM>::
deba@693	2981	template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type {
deba@693	2982	public:
deba@693	2983	typedef typename ItemSetTraits<GR, ITEM>::
deba@693	2984	template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type Parent;
deba@693	2985
deba@693	2986	/// The key type
deba@693	2987	typedef ITEM Key;
deba@693	2988	/// The value type
deba@693	2989	typedef VAL Value;
deba@693	2990	/// The graph type
deba@693	2991	typedef GR Graph;
deba@693	2992
deba@693	2993	public:
deba@693	2994
deba@693	2995	/// \brief Constructor of the Map with a given value.
deba@693	2996	///
deba@693	2997	/// Constructor of the Map with a given value.
deba@693	2998	explicit IterableValueMap(const Graph& graph,
deba@693	2999	const Value& value = Value())
deba@693	3000	: Parent(graph, _maps_bits::IterableValueMapNode<ITEM, VAL>(value)) {
deba@693	3001	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693	3002	lace(it);
deba@693	3003	}
deba@693	3004	}
deba@693	3005
deba@693	3006	protected:
deba@693	3007
deba@693	3008	void unlace(const Key& key) {
deba@693	3009	typename Parent::Value& node = Parent::operator[](key);
deba@693	3010	if (node.prev != INVALID) {
deba@693	3011	Parent::operator[](node.prev).next = node.next;
deba@693	3012	} else {
deba@693	3013	if (node.next != INVALID) {
deba@693	3014	_first[node.value] = node.next;
deba@693	3015	} else {
deba@693	3016	_first.erase(node.value);
deba@693	3017	}
deba@693	3018	}
deba@693	3019	if (node.next != INVALID) {
deba@693	3020	Parent::operator[](node.next).prev = node.prev;
deba@693	3021	}
deba@693	3022	}
deba@693	3023
deba@693	3024	void lace(const Key& key) {
deba@693	3025	typename Parent::Value& node = Parent::operator[](key);
deba@693	3026	typename std::map<Value, Key>::iterator it = _first.find(node.value);
deba@693	3027	if (it == _first.end()) {
deba@693	3028	node.prev = node.next = INVALID;
deba@693	3029	if (node.next != INVALID) {
deba@693	3030	Parent::operator[](node.next).prev = key;
deba@693	3031	}
deba@693	3032	_first.insert(std::make_pair(node.value, key));
deba@693	3033	} else {
deba@693	3034	node.prev = INVALID;
deba@693	3035	node.next = it->second;
deba@693	3036	if (node.next != INVALID) {
deba@693	3037	Parent::operator[](node.next).prev = key;
deba@693	3038	}
deba@693	3039	it->second = key;
deba@693	3040	}
deba@693	3041	}
deba@693	3042
deba@693	3043	public:
deba@693	3044
deba@693	3045	/// \brief Forward iterator for values.
deba@693	3046	///
deba@693	3047	/// This iterator is an stl compatible forward
deba@693	3048	/// iterator on the values of the map. The values can
deba@693	3049	/// be accessed in the [beginValue, endValue) range.
deba@693	3050	///
deba@693	3051	class ValueIterator
deba@693	3052	: public std::iterator<std::forward_iterator_tag, Value> {
deba@693	3053	friend class IterableValueMap;
deba@693	3054	private:
deba@693	3055	ValueIterator(typename std::map<Value, Key>::const_iterator _it)
deba@693	3056	: it(_it) {}
deba@693	3057	public:
deba@693	3058
deba@693	3059	ValueIterator() {}
deba@693	3060
deba@693	3061	ValueIterator& operator++() { ++it; return *this; }
deba@693	3062	ValueIterator operator++(int) {
deba@693	3063	ValueIterator tmp(*this);
deba@693	3064	operator++();
deba@693	3065	return tmp;
deba@693	3066	}
deba@693	3067
deba@693	3068	const Value& operator*() const { return it->first; }
deba@693	3069	const Value* operator->() const { return &(it->first); }
deba@693	3070
deba@693	3071	bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@693	3072	bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@693	3073
deba@693	3074	private:
deba@693	3075	typename std::map<Value, Key>::const_iterator it;
deba@693	3076	};
deba@693	3077
deba@693	3078	/// \brief Returns an iterator to the first value.
deba@693	3079	///
deba@693	3080	/// Returns an stl compatible iterator to the
deba@693	3081	/// first value of the map. The values of the
deba@693	3082	/// map can be accessed in the [beginValue, endValue)
deba@693	3083	/// range.
deba@693	3084	ValueIterator beginValue() const {
deba@693	3085	return ValueIterator(_first.begin());
deba@693	3086	}
deba@693	3087
deba@693	3088	/// \brief Returns an iterator after the last value.
deba@693	3089	///
deba@693	3090	/// Returns an stl compatible iterator after the
deba@693	3091	/// last value of the map. The values of the
deba@693	3092	/// map can be accessed in the [beginValue, endValue)
deba@693	3093	/// range.
deba@693	3094	ValueIterator endValue() const {
deba@693	3095	return ValueIterator(_first.end());
deba@693	3096	}
deba@693	3097
deba@693	3098	/// \brief Set operation of the map.
deba@693	3099	///
deba@693	3100	/// Set operation of the map.
deba@693	3101	void set(const Key& key, const Value& value) {
deba@693	3102	unlace(key);
deba@693	3103	Parent::operator[](key).value = value;
deba@693	3104	lace(key);
deba@693	3105	}
deba@693	3106
deba@693	3107	/// \brief Const subscript operator of the map.
deba@693	3108	///
deba@693	3109	/// Const subscript operator of the map.
deba@693	3110	const Value& operator[](const Key& key) const {
deba@693	3111	return Parent::operator[](key).value;
deba@693	3112	}
deba@693	3113
deba@693	3114	/// \brief Iterator for the keys with the same value.
deba@693	3115	///
deba@693	3116	/// Iterator for the keys with the same value. It works
deba@693	3117	/// like a graph item iterator in the map, it can be converted
deba@693	3118	/// the item type of the map, incremented with \c ++ operator, and
deba@693	3119	/// if the iterator leave the last valid item it will be equal to
deba@693	3120	/// \c INVALID.
deba@693	3121	class ItemIt : public ITEM {
deba@693	3122	public:
deba@693	3123	typedef ITEM Parent;
deba@693	3124
deba@693	3125	/// \brief Invalid constructor \& conversion.
deba@693	3126	///
deba@693	3127	/// This constructor initializes the item to be invalid.
deba@693	3128	/// \sa Invalid for more details.
deba@693	3129	ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693	3130
deba@693	3131	/// \brief Creates an iterator with a value.
deba@693	3132	///
deba@693	3133	/// Creates an iterator with a value. It iterates on the
deba@693	3134	/// keys which have the given value.
deba@693	3135	/// \param map The IterableValueMap
deba@693	3136	/// \param value The value
deba@693	3137	ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
deba@693	3138	typename std::map<Value, Key>::const_iterator it =
deba@693	3139	map._first.find(value);
deba@693	3140	if (it == map._first.end()) {
deba@693	3141	Parent::operator=(INVALID);
deba@693	3142	} else {
deba@693	3143	Parent::operator=(it->second);
deba@693	3144	}
deba@693	3145	}
deba@693	3146
deba@693	3147	/// \brief Increment operator.
deba@693	3148	///
deba@693	3149	/// Increment Operator.
deba@693	3150	ItemIt& operator++() {
deba@693	3151	Parent::operator=(_map->IterableValueMap::Parent::
deba@693	3152	operator[](static_cast<Parent&>(*this)).next);
deba@693	3153	return *this;
deba@693	3154	}
deba@693	3155
deba@693	3156
deba@693	3157	private:
deba@693	3158	const IterableValueMap* _map;
deba@693	3159	};
deba@693	3160
deba@693	3161	protected:
deba@693	3162
deba@693	3163	virtual void add(const Key& key) {
deba@693	3164	Parent::add(key);
deba@693	3165	unlace(key);
deba@693	3166	}
deba@693	3167
deba@693	3168	virtual void add(const std::vector<Key>& keys) {
deba@693	3169	Parent::add(keys);
deba@693	3170	for (int i = 0; i < int(keys.size()); ++i) {
deba@693	3171	lace(keys[i]);
deba@693	3172	}
deba@693	3173	}
deba@693	3174
deba@693	3175	virtual void erase(const Key& key) {
deba@693	3176	unlace(key);
deba@693	3177	Parent::erase(key);
deba@693	3178	}
deba@693	3179
deba@693	3180	virtual void erase(const std::vector<Key>& keys) {
deba@693	3181	for (int i = 0; i < int(keys.size()); ++i) {
deba@693	3182	unlace(keys[i]);
deba@693	3183	}
deba@693	3184	Parent::erase(keys);
deba@693	3185	}
deba@693	3186
deba@693	3187	virtual void build() {
deba@693	3188	Parent::build();
deba@693	3189	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693	3190	lace(it);
deba@693	3191	}
deba@693	3192	}
deba@693	3193
deba@693	3194	virtual void clear() {
deba@693	3195	_first.clear();
deba@693	3196	Parent::clear();
deba@693	3197	}
deba@693	3198
deba@693	3199	private:
deba@693	3200	std::map<Value, Key> _first;
deba@693	3201	};
deba@693	3202
kpeter@559	3203	/// \brief Map of the source nodes of arcs in a digraph.
deba@220	3204	///
kpeter@559	3205	/// SourceMap provides access for the source node of each arc in a digraph,
kpeter@559	3206	/// which is returned by the \c source() function of the digraph.
kpeter@559	3207	/// \tparam GR The digraph type.
deba@220	3208	/// \see TargetMap
kpeter@559	3209	template <typename GR>
deba@220	3210	class SourceMap {
deba@220	3211	public:
deba@220	3212
kpeter@559	3213	///\e
kpeter@559	3214	typedef typename GR::Arc Key;
kpeter@559	3215	///\e
kpeter@559	3216	typedef typename GR::Node Value;
deba@220	3217
deba@220	3218	/// \brief Constructor
deba@220	3219	///
kpeter@559	3220	/// Constructor.
kpeter@313	3221	/// \param digraph The digraph that the map belongs to.
kpeter@559	3222	explicit SourceMap(const GR& digraph) : _graph(digraph) {}
kpeter@559	3223
kpeter@559	3224	/// \brief Returns the source node of the given arc.
deba@220	3225	///
kpeter@559	3226	/// Returns the source node of the given arc.
deba@220	3227	Value operator[](const Key& arc) const {
kpeter@559	3228	return _graph.source(arc);
deba@220	3229	}
deba@220	3230
deba@220	3231	private:
kpeter@559	3232	const GR& _graph;
deba@220	3233	};
deba@220	3234
kpeter@301	3235	/// \brief Returns a \c SourceMap class.
deba@220	3236	///
kpeter@301	3237	/// This function just returns an \c SourceMap class.
deba@220	3238	/// \relates SourceMap
kpeter@559	3239	template <typename GR>
kpeter@559	3240	inline SourceMap<GR> sourceMap(const GR& graph) {
kpeter@559	3241	return SourceMap<GR>(graph);
deba@220	3242	}
deba@220	3243
kpeter@559	3244	/// \brief Map of the target nodes of arcs in a digraph.
deba@220	3245	///
kpeter@559	3246	/// TargetMap provides access for the target node of each arc in a digraph,
kpeter@559	3247	/// which is returned by the \c target() function of the digraph.
kpeter@559	3248	/// \tparam GR The digraph type.
deba@220	3249	/// \see SourceMap
kpeter@559	3250	template <typename GR>
deba@220	3251	class TargetMap {
deba@220	3252	public:
deba@220	3253
kpeter@559	3254	///\e
kpeter@559	3255	typedef typename GR::Arc Key;
kpeter@559	3256	///\e
kpeter@559	3257	typedef typename GR::Node Value;
deba@220	3258
deba@220	3259	/// \brief Constructor
deba@220	3260	///
kpeter@559	3261	/// Constructor.
kpeter@313	3262	/// \param digraph The digraph that the map belongs to.
kpeter@559	3263	explicit TargetMap(const GR& digraph) : _graph(digraph) {}
kpeter@559	3264
kpeter@559	3265	/// \brief Returns the target node of the given arc.
deba@220	3266	///
kpeter@559	3267	/// Returns the target node of the given arc.
deba@220	3268	Value operator[](const Key& e) const {
kpeter@559	3269	return _graph.target(e);
deba@220	3270	}
deba@220	3271
deba@220	3272	private:
kpeter@559	3273	const GR& _graph;
deba@220	3274	};
deba@220	3275
kpeter@301	3276	/// \brief Returns a \c TargetMap class.
deba@220	3277	///
kpeter@301	3278	/// This function just returns a \c TargetMap class.
deba@220	3279	/// \relates TargetMap
kpeter@559	3280	template <typename GR>
kpeter@559	3281	inline TargetMap<GR> targetMap(const GR& graph) {
kpeter@559	3282	return TargetMap<GR>(graph);
deba@220	3283	}
deba@220	3284
kpeter@559	3285	/// \brief Map of the "forward" directed arc view of edges in a graph.
deba@220	3286	///
kpeter@559	3287	/// ForwardMap provides access for the "forward" directed arc view of
kpeter@559	3288	/// each edge in a graph, which is returned by the \c direct() function
kpeter@559	3289	/// of the graph with \c true parameter.
kpeter@559	3290	/// \tparam GR The graph type.
deba@220	3291	/// \see BackwardMap
kpeter@559	3292	template <typename GR>
deba@220	3293	class ForwardMap {
deba@220	3294	public:
deba@220	3295
kpeter@559	3296	typedef typename GR::Arc Value;
kpeter@559	3297	typedef typename GR::Edge Key;
deba@220	3298
deba@220	3299	/// \brief Constructor
deba@220	3300	///
kpeter@559	3301	/// Constructor.
kpeter@313	3302	/// \param graph The graph that the map belongs to.
kpeter@559	3303	explicit ForwardMap(const GR& graph) : _graph(graph) {}
kpeter@559	3304
kpeter@559	3305	/// \brief Returns the "forward" directed arc view of the given edge.
deba@220	3306	///
kpeter@559	3307	/// Returns the "forward" directed arc view of the given edge.
deba@220	3308	Value operator[](const Key& key) const {
deba@220	3309	return _graph.direct(key, true);
deba@220	3310	}
deba@220	3311
deba@220	3312	private:
kpeter@559	3313	const GR& _graph;
deba@220	3314	};
deba@220	3315
kpeter@301	3316	/// \brief Returns a \c ForwardMap class.
deba@220	3317	///
kpeter@301	3318	/// This function just returns an \c ForwardMap class.
deba@220	3319	/// \relates ForwardMap
kpeter@559	3320	template <typename GR>
kpeter@559	3321	inline ForwardMap<GR> forwardMap(const GR& graph) {
kpeter@559	3322	return ForwardMap<GR>(graph);
deba@220	3323	}
deba@220	3324
kpeter@559	3325	/// \brief Map of the "backward" directed arc view of edges in a graph.
deba@220	3326	///
kpeter@559	3327	/// BackwardMap provides access for the "backward" directed arc view of
kpeter@559	3328	/// each edge in a graph, which is returned by the \c direct() function
kpeter@559	3329	/// of the graph with \c false parameter.
kpeter@559	3330	/// \tparam GR The graph type.
deba@220	3331	/// \see ForwardMap
kpeter@559	3332	template <typename GR>
deba@220	3333	class BackwardMap {
deba@220	3334	public:
deba@220	3335
kpeter@559	3336	typedef typename GR::Arc Value;
kpeter@559	3337	typedef typename GR::Edge Key;
deba@220	3338
deba@220	3339	/// \brief Constructor
deba@220	3340	///
kpeter@559	3341	/// Constructor.
kpeter@313	3342	/// \param graph The graph that the map belongs to.
kpeter@559	3343	explicit BackwardMap(const GR& graph) : _graph(graph) {}
kpeter@559	3344
kpeter@559	3345	/// \brief Returns the "backward" directed arc view of the given edge.
deba@220	3346	///
kpeter@559	3347	/// Returns the "backward" directed arc view of the given edge.
deba@220	3348	Value operator[](const Key& key) const {
deba@220	3349	return _graph.direct(key, false);
deba@220	3350	}
deba@220	3351
deba@220	3352	private:
kpeter@559	3353	const GR& _graph;
deba@220	3354	};
deba@220	3355
kpeter@301	3356	/// \brief Returns a \c BackwardMap class
kpeter@301	3357
kpeter@301	3358	/// This function just returns a \c BackwardMap class.
deba@220	3359	/// \relates BackwardMap
kpeter@559	3360	template <typename GR>
kpeter@559	3361	inline BackwardMap<GR> backwardMap(const GR& graph) {
kpeter@559	3362	return BackwardMap<GR>(graph);
deba@220	3363	}
deba@220	3364
kpeter@559	3365	/// \brief Map of the in-degrees of nodes in a digraph.
deba@220	3366	///
deba@220	3367	/// This map returns the in-degree of a node. Once it is constructed,
kpeter@559	3368	/// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220	3369	/// in constant time. On the other hand, the values are updated automatically
deba@220	3370	/// whenever the digraph changes.
deba@220	3371	///
deba@693	3372	/// \warning Besides \c addNode() and \c addArc(), a digraph structure
kpeter@559	3373	/// may provide alternative ways to modify the digraph.
kpeter@559	3374	/// The correct behavior of InDegMap is not guarantied if these additional
kpeter@559	3375	/// features are used. For example the functions
kpeter@559	3376	/// \ref ListDigraph::changeSource() "changeSource()",
deba@220	3377	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	3378	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	3379	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	3380	///
deba@220	3381	/// \sa OutDegMap
kpeter@559	3382	template <typename GR>
deba@220	3383	class InDegMap
kpeter@559	3384	: protected ItemSetTraits<GR, typename GR::Arc>
deba@220	3385	::ItemNotifier::ObserverBase {
deba@220	3386
deba@220	3387	public:
deba@693	3388
kpeter@617	3389	/// The graph type of InDegMap
kpeter@617	3390	typedef GR Graph;
kpeter@559	3391	typedef GR Digraph;
kpeter@559	3392	/// The key type
kpeter@559	3393	typedef typename Digraph::Node Key;
kpeter@559	3394	/// The value type
deba@220	3395	typedef int Value;
deba@220	3396
deba@220	3397	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	3398	::ItemNotifier::ObserverBase Parent;
deba@220	3399
deba@220	3400	private:
deba@220	3401
deba@220	3402	class AutoNodeMap
deba@220	3403	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	3404	public:
deba@220	3405
deba@220	3406	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	3407	template Map<int>::Type Parent;
deba@220	3408
deba@220	3409	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	3410
deba@220	3411	virtual void add(const Key& key) {
deba@220	3412	Parent::add(key);
deba@220	3413	Parent::set(key, 0);
deba@220	3414	}
deba@220	3415
deba@220	3416	virtual void add(const std::vector<Key>& keys) {
deba@220	3417	Parent::add(keys);
deba@220	3418	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	3419	Parent::set(keys[i], 0);
deba@220	3420	}
deba@220	3421	}
deba@220	3422
deba@220	3423	virtual void build() {
deba@220	3424	Parent::build();
deba@220	3425	Key it;
deba@220	3426	typename Parent::Notifier* nf = Parent::notifier();
deba@220	3427	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	3428	Parent::set(it, 0);
deba@220	3429	}
deba@220	3430	}
deba@220	3431	};
deba@220	3432
deba@220	3433	public:
deba@220	3434
deba@220	3435	/// \brief Constructor.
deba@220	3436	///
kpeter@559	3437	/// Constructor for creating an in-degree map.
kpeter@559	3438	explicit InDegMap(const Digraph& graph)
kpeter@559	3439	: _digraph(graph), _deg(graph) {
deba@220	3440	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	3441
deba@220	3442	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3443	_deg[it] = countInArcs(_digraph, it);
deba@220	3444	}
deba@220	3445	}
deba@220	3446
kpeter@559	3447	/// \brief Gives back the in-degree of a Node.
kpeter@559	3448	///
deba@220	3449	/// Gives back the in-degree of a Node.
deba@220	3450	int operator[](const Key& key) const {
deba@220	3451	return _deg[key];
deba@220	3452	}
deba@220	3453
deba@220	3454	protected:
deba@220	3455
deba@220	3456	typedef typename Digraph::Arc Arc;
deba@220	3457
deba@220	3458	virtual void add(const Arc& arc) {
deba@220	3459	++_deg[_digraph.target(arc)];
deba@220	3460	}
deba@220	3461
deba@220	3462	virtual void add(const std::vector<Arc>& arcs) {
deba@220	3463	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	3464	++_deg[_digraph.target(arcs[i])];
deba@220	3465	}
deba@220	3466	}
deba@220	3467
deba@220	3468	virtual void erase(const Arc& arc) {
deba@220	3469	--_deg[_digraph.target(arc)];
deba@220	3470	}
deba@220	3471
deba@220	3472	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	3473	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	3474	--_deg[_digraph.target(arcs[i])];
deba@220	3475	}
deba@220	3476	}
deba@220	3477
deba@220	3478	virtual void build() {
deba@220	3479	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3480	_deg[it] = countInArcs(_digraph, it);
deba@220	3481	}
deba@220	3482	}
deba@220	3483
deba@220	3484	virtual void clear() {
deba@220	3485	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3486	_deg[it] = 0;
deba@220	3487	}
deba@220	3488	}
deba@220	3489	private:
deba@220	3490
deba@220	3491	const Digraph& _digraph;
deba@220	3492	AutoNodeMap _deg;
deba@220	3493	};
deba@220	3494
kpeter@559	3495	/// \brief Map of the out-degrees of nodes in a digraph.
deba@220	3496	///
deba@220	3497	/// This map returns the out-degree of a node. Once it is constructed,
kpeter@559	3498	/// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220	3499	/// in constant time. On the other hand, the values are updated automatically
deba@220	3500	/// whenever the digraph changes.
deba@220	3501	///
deba@693	3502	/// \warning Besides \c addNode() and \c addArc(), a digraph structure
kpeter@559	3503	/// may provide alternative ways to modify the digraph.
kpeter@559	3504	/// The correct behavior of OutDegMap is not guarantied if these additional
kpeter@559	3505	/// features are used. For example the functions
kpeter@559	3506	/// \ref ListDigraph::changeSource() "changeSource()",
deba@220	3507	/// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220	3508	/// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220	3509	/// of \ref ListDigraph will \e not update the degree values correctly.
deba@220	3510	///
deba@220	3511	/// \sa InDegMap
kpeter@559	3512	template <typename GR>
deba@220	3513	class OutDegMap
kpeter@559	3514	: protected ItemSetTraits<GR, typename GR::Arc>
deba@220	3515	::ItemNotifier::ObserverBase {
deba@220	3516
deba@220	3517	public:
deba@220	3518
kpeter@617	3519	/// The graph type of OutDegMap
kpeter@617	3520	typedef GR Graph;
kpeter@559	3521	typedef GR Digraph;
kpeter@559	3522	/// The key type
kpeter@559	3523	typedef typename Digraph::Node Key;
kpeter@559	3524	/// The value type
deba@220	3525	typedef int Value;
deba@220	3526
deba@220	3527	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220	3528	::ItemNotifier::ObserverBase Parent;
deba@220	3529
deba@220	3530	private:
deba@220	3531
deba@220	3532	class AutoNodeMap
deba@220	3533	: public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220	3534	public:
deba@220	3535
deba@220	3536	typedef typename ItemSetTraits<Digraph, Key>::
deba@220	3537	template Map<int>::Type Parent;
deba@220	3538
deba@220	3539	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220	3540
deba@220	3541	virtual void add(const Key& key) {
deba@220	3542	Parent::add(key);
deba@220	3543	Parent::set(key, 0);
deba@220	3544	}
deba@220	3545	virtual void add(const std::vector<Key>& keys) {
deba@220	3546	Parent::add(keys);
deba@220	3547	for (int i = 0; i < int(keys.size()); ++i) {
deba@220	3548	Parent::set(keys[i], 0);
deba@220	3549	}
deba@220	3550	}
deba@220	3551	virtual void build() {
deba@220	3552	Parent::build();
deba@220	3553	Key it;
deba@220	3554	typename Parent::Notifier* nf = Parent::notifier();
deba@220	3555	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220	3556	Parent::set(it, 0);
deba@220	3557	}
deba@220	3558	}
deba@220	3559	};
deba@220	3560
deba@220	3561	public:
deba@220	3562
deba@220	3563	/// \brief Constructor.
deba@220	3564	///
kpeter@559	3565	/// Constructor for creating an out-degree map.
kpeter@559	3566	explicit OutDegMap(const Digraph& graph)
kpeter@559	3567	: _digraph(graph), _deg(graph) {
deba@220	3568	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220	3569
deba@220	3570	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3571	_deg[it] = countOutArcs(_digraph, it);
deba@220	3572	}
deba@220	3573	}
deba@220	3574
kpeter@559	3575	/// \brief Gives back the out-degree of a Node.
kpeter@559	3576	///
deba@220	3577	/// Gives back the out-degree of a Node.
deba@220	3578	int operator[](const Key& key) const {
deba@220	3579	return _deg[key];
deba@220	3580	}
deba@220	3581
deba@220	3582	protected:
deba@220	3583
deba@220	3584	typedef typename Digraph::Arc Arc;
deba@220	3585
deba@220	3586	virtual void add(const Arc& arc) {
deba@220	3587	++_deg[_digraph.source(arc)];
deba@220	3588	}
deba@220	3589
deba@220	3590	virtual void add(const std::vector<Arc>& arcs) {
deba@220	3591	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	3592	++_deg[_digraph.source(arcs[i])];
deba@220	3593	}
deba@220	3594	}
deba@220	3595
deba@220	3596	virtual void erase(const Arc& arc) {
deba@220	3597	--_deg[_digraph.source(arc)];
deba@220	3598	}
deba@220	3599
deba@220	3600	virtual void erase(const std::vector<Arc>& arcs) {
deba@220	3601	for (int i = 0; i < int(arcs.size()); ++i) {
deba@220	3602	--_deg[_digraph.source(arcs[i])];
deba@220	3603	}
deba@220	3604	}
deba@220	3605
deba@220	3606	virtual void build() {
deba@220	3607	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3608	_deg[it] = countOutArcs(_digraph, it);
deba@220	3609	}
deba@220	3610	}
deba@220	3611
deba@220	3612	virtual void clear() {
deba@220	3613	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220	3614	_deg[it] = 0;
deba@220	3615	}
deba@220	3616	}
deba@220	3617	private:
deba@220	3618
deba@220	3619	const Digraph& _digraph;
deba@220	3620	AutoNodeMap _deg;
deba@220	3621	};
deba@220	3622
kpeter@559	3623	/// \brief Potential difference map
kpeter@559	3624	///
kpeter@584	3625	/// PotentialDifferenceMap returns the difference between the potentials of
kpeter@584	3626	/// the source and target nodes of each arc in a digraph, i.e. it returns
kpeter@559	3627	/// \code
kpeter@559	3628	/// potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559	3629	/// \endcode
kpeter@559	3630	/// \tparam GR The digraph type.
kpeter@559	3631	/// \tparam POT A node map storing the potentials.
kpeter@559	3632	template <typename GR, typename POT>
kpeter@559	3633	class PotentialDifferenceMap {
kpeter@559	3634	public:
kpeter@559	3635	/// Key type
kpeter@559	3636	typedef typename GR::Arc Key;
kpeter@559	3637	/// Value type
kpeter@559	3638	typedef typename POT::Value Value;
kpeter@559	3639
kpeter@559	3640	/// \brief Constructor
kpeter@559	3641	///
kpeter@559	3642	/// Contructor of the map.
kpeter@559	3643	explicit PotentialDifferenceMap(const GR& gr,
kpeter@559	3644	const POT& potential)
kpeter@559	3645	: _digraph(gr), _potential(potential) {}
kpeter@559	3646
kpeter@559	3647	/// \brief Returns the potential difference for the given arc.
kpeter@559	3648	///
kpeter@559	3649	/// Returns the potential difference for the given arc, i.e.
kpeter@559	3650	/// \code
kpeter@559	3651	/// potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559	3652	/// \endcode
kpeter@559	3653	Value operator[](const Key& arc) const {
kpeter@559	3654	return _potential[_digraph.target(arc)] -
kpeter@559	3655	_potential[_digraph.source(arc)];
kpeter@559	3656	}
kpeter@559	3657
kpeter@559	3658	private:
kpeter@559	3659	const GR& _digraph;
kpeter@559	3660	const POT& _potential;
kpeter@559	3661	};
kpeter@559	3662
kpeter@559	3663	/// \brief Returns a PotentialDifferenceMap.
kpeter@559	3664	///
kpeter@559	3665	/// This function just returns a PotentialDifferenceMap.
kpeter@559	3666	/// \relates PotentialDifferenceMap
kpeter@559	3667	template <typename GR, typename POT>
kpeter@559	3668	PotentialDifferenceMap<GR, POT>
kpeter@559	3669	potentialDifferenceMap(const GR& gr, const POT& potential) {
kpeter@559	3670	return PotentialDifferenceMap<GR, POT>(gr, potential);
kpeter@559	3671	}
kpeter@559	3672
alpar@25	3673	/// @}
alpar@25	3674	}
alpar@25	3675
alpar@25	3676	#endif // LEMON_MAPS_H

author	Balazs Dezso <deba@inf.elte.hu>
	Sat, 27 Jun 2009 13:07:26 +0200
changeset 693	7bda7860e0a8
parent 617	4137ef9aacc6
child 694	71939d63ae77
permissions	-rw-r--r--