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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Sun, 24 May 2015 17:30:50 +0200
changeset 1153	233ad6942a26
parent 1092	dceba191c00d
child 1210	da87dbdf3daf
permissions	-rw-r--r--