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

author	Alpar Juttner <alpar@cs.elte.hu>
	Tue, 28 Jul 2020 21:23:36 +0200
changeset 1432	da87dbdf3daf
parent 1336	0759d974de81
permissions	-rw-r--r--