lemon-1.2: lemon/maps.h@1f8ad32f088b (annotated)

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

author	Alpar Juttner <alpar@cs.elte.hu>
	Tue, 29 Sep 2009 09:25:00 +0200
changeset 732	1f8ad32f088b
parent 725	11404088d1a5
parent 717	684964884a2e
child 786	e20173729589
child 789	8ddb7deabab9
permissions	-rw-r--r--