changeset 554 | 538b3dd9a2c0 |
parent 440 | 88ed40ad0d4f |
child 564 | be6646ac5d89 |
28:82bfc715d7c7 | 29:a57b20ae1999 |
---|---|
61 /// |
61 /// |
62 /// \sa ConstMap |
62 /// \sa ConstMap |
63 template<typename K, typename V> |
63 template<typename K, typename V> |
64 class NullMap : public MapBase<K, V> { |
64 class NullMap : public MapBase<K, V> { |
65 public: |
65 public: |
66 typedef MapBase<K, V> Parent; |
66 ///\e |
67 typedef typename Parent::Key Key; |
67 typedef K Key; |
68 typedef typename Parent::Value Value; |
68 ///\e |
69 typedef V Value; |
|
69 |
70 |
70 /// Gives back a default constructed element. |
71 /// Gives back a default constructed element. |
71 Value operator[](const Key&) const { return Value(); } |
72 Value operator[](const Key&) const { return Value(); } |
72 /// Absorbs the value. |
73 /// Absorbs the value. |
73 void set(const Key&, const Value&) {} |
74 void set(const Key&, const Value&) {} |
100 template<typename K, typename V> |
101 template<typename K, typename V> |
101 class ConstMap : public MapBase<K, V> { |
102 class ConstMap : public MapBase<K, V> { |
102 private: |
103 private: |
103 V _value; |
104 V _value; |
104 public: |
105 public: |
105 typedef MapBase<K, V> Parent; |
106 ///\e |
106 typedef typename Parent::Key Key; |
107 typedef K Key; |
107 typedef typename Parent::Value Value; |
108 ///\e |
109 typedef V Value; |
|
108 |
110 |
109 /// Default constructor |
111 /// Default constructor |
110 |
112 |
111 /// Default constructor. |
113 /// Default constructor. |
112 /// The value of the map will be default constructed. |
114 /// The value of the map will be default constructed. |
166 /// \sa NullMap |
168 /// \sa NullMap |
167 /// \sa IdentityMap |
169 /// \sa IdentityMap |
168 template<typename K, typename V, V v> |
170 template<typename K, typename V, V v> |
169 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { |
171 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { |
170 public: |
172 public: |
171 typedef MapBase<K, V> Parent; |
173 ///\e |
172 typedef typename Parent::Key Key; |
174 typedef K Key; |
173 typedef typename Parent::Value Value; |
175 ///\e |
176 typedef V Value; |
|
174 |
177 |
175 /// Constructor. |
178 /// Constructor. |
176 ConstMap() {} |
179 ConstMap() {} |
177 |
180 |
178 /// Gives back the specified value. |
181 /// Gives back the specified value. |
200 /// |
203 /// |
201 /// \sa ConstMap |
204 /// \sa ConstMap |
202 template <typename T> |
205 template <typename T> |
203 class IdentityMap : public MapBase<T, T> { |
206 class IdentityMap : public MapBase<T, T> { |
204 public: |
207 public: |
205 typedef MapBase<T, T> Parent; |
208 ///\e |
206 typedef typename Parent::Key Key; |
209 typedef T Key; |
207 typedef typename Parent::Value Value; |
210 ///\e |
211 typedef T Value; |
|
208 |
212 |
209 /// Gives back the given value without any modification. |
213 /// Gives back the given value without any modification. |
210 Value operator[](const Key &k) const { |
214 Value operator[](const Key &k) const { |
211 return k; |
215 return k; |
212 } |
216 } |
243 typedef std::vector<V> Vector; |
247 typedef std::vector<V> Vector; |
244 Vector _vector; |
248 Vector _vector; |
245 |
249 |
246 public: |
250 public: |
247 |
251 |
248 typedef MapBase<int, V> Parent; |
|
249 /// Key type |
252 /// Key type |
250 typedef typename Parent::Key Key; |
253 typedef int Key; |
251 /// Value type |
254 /// Value type |
252 typedef typename Parent::Value Value; |
255 typedef V Value; |
253 /// Reference type |
256 /// Reference type |
254 typedef typename Vector::reference Reference; |
257 typedef typename Vector::reference Reference; |
255 /// Const reference type |
258 /// Const reference type |
256 typedef typename Vector::const_reference ConstReference; |
259 typedef typename Vector::const_reference ConstReference; |
257 |
260 |
351 /// However keep in mind that it is usually not as efficient as other |
354 /// However keep in mind that it is usually not as efficient as other |
352 /// maps. |
355 /// maps. |
353 /// |
356 /// |
354 /// The simplest way of using this map is through the sparseMap() |
357 /// The simplest way of using this map is through the sparseMap() |
355 /// function. |
358 /// function. |
356 template <typename K, typename V, typename Compare = std::less<K> > |
359 template <typename K, typename V, typename Comp = std::less<K> > |
357 class SparseMap : public MapBase<K, V> { |
360 class SparseMap : public MapBase<K, V> { |
358 template <typename K1, typename V1, typename C1> |
361 template <typename K1, typename V1, typename C1> |
359 friend class SparseMap; |
362 friend class SparseMap; |
360 public: |
363 public: |
361 |
364 |
362 typedef MapBase<K, V> Parent; |
|
363 /// Key type |
365 /// Key type |
364 typedef typename Parent::Key Key; |
366 typedef K Key; |
365 /// Value type |
367 /// Value type |
366 typedef typename Parent::Value Value; |
368 typedef V Value; |
367 /// Reference type |
369 /// Reference type |
368 typedef Value& Reference; |
370 typedef Value& Reference; |
369 /// Const reference type |
371 /// Const reference type |
370 typedef const Value& ConstReference; |
372 typedef const Value& ConstReference; |
371 |
373 |
372 typedef True ReferenceMapTag; |
374 typedef True ReferenceMapTag; |
373 |
375 |
374 private: |
376 private: |
375 |
377 |
376 typedef std::map<K, V, Compare> Map; |
378 typedef std::map<K, V, Comp> Map; |
377 Map _map; |
379 Map _map; |
378 Value _value; |
380 Value _value; |
379 |
381 |
380 public: |
382 public: |
381 |
383 |
487 template <typename M1, typename M2> |
489 template <typename M1, typename M2> |
488 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { |
490 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { |
489 const M1 &_m1; |
491 const M1 &_m1; |
490 const M2 &_m2; |
492 const M2 &_m2; |
491 public: |
493 public: |
492 typedef MapBase<typename M2::Key, typename M1::Value> Parent; |
494 ///\e |
493 typedef typename Parent::Key Key; |
495 typedef typename M2::Key Key; |
494 typedef typename Parent::Value Value; |
496 ///\e |
497 typedef typename M1::Value Value; |
|
495 |
498 |
496 /// Constructor |
499 /// Constructor |
497 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
500 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
498 |
501 |
499 /// \e |
502 ///\e |
500 typename MapTraits<M1>::ConstReturnValue |
503 typename MapTraits<M1>::ConstReturnValue |
501 operator[](const Key &k) const { return _m1[_m2[k]]; } |
504 operator[](const Key &k) const { return _m1[_m2[k]]; } |
502 }; |
505 }; |
503 |
506 |
504 /// Returns a \c ComposeMap class |
507 /// Returns a \c ComposeMap class |
543 class CombineMap : public MapBase<typename M1::Key, V> { |
546 class CombineMap : public MapBase<typename M1::Key, V> { |
544 const M1 &_m1; |
547 const M1 &_m1; |
545 const M2 &_m2; |
548 const M2 &_m2; |
546 F _f; |
549 F _f; |
547 public: |
550 public: |
548 typedef MapBase<typename M1::Key, V> Parent; |
551 ///\e |
549 typedef typename Parent::Key Key; |
552 typedef typename M1::Key Key; |
550 typedef typename Parent::Value Value; |
553 ///\e |
554 typedef V Value; |
|
551 |
555 |
552 /// Constructor |
556 /// Constructor |
553 CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) |
557 CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) |
554 : _m1(m1), _m2(m2), _f(f) {} |
558 : _m1(m1), _m2(m2), _f(f) {} |
555 /// \e |
559 ///\e |
556 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } |
560 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } |
557 }; |
561 }; |
558 |
562 |
559 /// Returns a \c CombineMap class |
563 /// Returns a \c CombineMap class |
560 |
564 |
613 typename K = typename F::argument_type, |
617 typename K = typename F::argument_type, |
614 typename V = typename F::result_type> |
618 typename V = typename F::result_type> |
615 class FunctorToMap : public MapBase<K, V> { |
619 class FunctorToMap : public MapBase<K, V> { |
616 F _f; |
620 F _f; |
617 public: |
621 public: |
618 typedef MapBase<K, V> Parent; |
622 ///\e |
619 typedef typename Parent::Key Key; |
623 typedef K Key; |
620 typedef typename Parent::Value Value; |
624 ///\e |
625 typedef V Value; |
|
621 |
626 |
622 /// Constructor |
627 /// Constructor |
623 FunctorToMap(const F &f = F()) : _f(f) {} |
628 FunctorToMap(const F &f = F()) : _f(f) {} |
624 /// \e |
629 ///\e |
625 Value operator[](const Key &k) const { return _f(k); } |
630 Value operator[](const Key &k) const { return _f(k); } |
626 }; |
631 }; |
627 |
632 |
628 /// Returns a \c FunctorToMap class |
633 /// Returns a \c FunctorToMap class |
629 |
634 |
667 ///\sa FunctorToMap |
672 ///\sa FunctorToMap |
668 template <typename M> |
673 template <typename M> |
669 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> { |
674 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> { |
670 const M &_m; |
675 const M &_m; |
671 public: |
676 public: |
672 typedef MapBase<typename M::Key, typename M::Value> Parent; |
677 ///\e |
673 typedef typename Parent::Key Key; |
678 typedef typename M::Key Key; |
674 typedef typename Parent::Value Value; |
679 ///\e |
675 |
680 typedef typename M::Value Value; |
676 typedef typename Parent::Key argument_type; |
681 |
677 typedef typename Parent::Value result_type; |
682 typedef typename M::Key argument_type; |
683 typedef typename M::Value result_type; |
|
678 |
684 |
679 /// Constructor |
685 /// Constructor |
680 MapToFunctor(const M &m) : _m(m) {} |
686 MapToFunctor(const M &m) : _m(m) {} |
681 /// \e |
687 ///\e |
682 Value operator()(const Key &k) const { return _m[k]; } |
688 Value operator()(const Key &k) const { return _m[k]; } |
683 /// \e |
689 ///\e |
684 Value operator[](const Key &k) const { return _m[k]; } |
690 Value operator[](const Key &k) const { return _m[k]; } |
685 }; |
691 }; |
686 |
692 |
687 /// Returns a \c MapToFunctor class |
693 /// Returns a \c MapToFunctor class |
688 |
694 |
707 /// function. |
713 /// function. |
708 template <typename M, typename V> |
714 template <typename M, typename V> |
709 class ConvertMap : public MapBase<typename M::Key, V> { |
715 class ConvertMap : public MapBase<typename M::Key, V> { |
710 const M &_m; |
716 const M &_m; |
711 public: |
717 public: |
712 typedef MapBase<typename M::Key, V> Parent; |
718 ///\e |
713 typedef typename Parent::Key Key; |
719 typedef typename M::Key Key; |
714 typedef typename Parent::Value Value; |
720 ///\e |
721 typedef V Value; |
|
715 |
722 |
716 /// Constructor |
723 /// Constructor |
717 |
724 |
718 /// Constructor. |
725 /// Constructor. |
719 /// \param m The underlying map. |
726 /// \param m The underlying map. |
720 ConvertMap(const M &m) : _m(m) {} |
727 ConvertMap(const M &m) : _m(m) {} |
721 |
728 |
722 /// \e |
729 ///\e |
723 Value operator[](const Key &k) const { return _m[k]; } |
730 Value operator[](const Key &k) const { return _m[k]; } |
724 }; |
731 }; |
725 |
732 |
726 /// Returns a \c ConvertMap class |
733 /// Returns a \c ConvertMap class |
727 |
734 |
749 template<typename M1, typename M2> |
756 template<typename M1, typename M2> |
750 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { |
757 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { |
751 M1 &_m1; |
758 M1 &_m1; |
752 M2 &_m2; |
759 M2 &_m2; |
753 public: |
760 public: |
754 typedef MapBase<typename M1::Key, typename M1::Value> Parent; |
761 ///\e |
755 typedef typename Parent::Key Key; |
762 typedef typename M1::Key Key; |
756 typedef typename Parent::Value Value; |
763 ///\e |
764 typedef typename M1::Value Value; |
|
757 |
765 |
758 /// Constructor |
766 /// Constructor |
759 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} |
767 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} |
760 /// Returns the value associated with the given key in the first map. |
768 /// Returns the value associated with the given key in the first map. |
761 Value operator[](const Key &k) const { return _m1[k]; } |
769 Value operator[](const Key &k) const { return _m1[k]; } |
795 template<typename M1, typename M2> |
803 template<typename M1, typename M2> |
796 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { |
804 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { |
797 const M1 &_m1; |
805 const M1 &_m1; |
798 const M2 &_m2; |
806 const M2 &_m2; |
799 public: |
807 public: |
800 typedef MapBase<typename M1::Key, typename M1::Value> Parent; |
808 ///\e |
801 typedef typename Parent::Key Key; |
809 typedef typename M1::Key Key; |
802 typedef typename Parent::Value Value; |
810 ///\e |
811 typedef typename M1::Value Value; |
|
803 |
812 |
804 /// Constructor |
813 /// Constructor |
805 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
814 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
806 /// \e |
815 ///\e |
807 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } |
816 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } |
808 }; |
817 }; |
809 |
818 |
810 /// Returns an \c AddMap class |
819 /// Returns an \c AddMap class |
811 |
820 |
843 template<typename M1, typename M2> |
852 template<typename M1, typename M2> |
844 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { |
853 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { |
845 const M1 &_m1; |
854 const M1 &_m1; |
846 const M2 &_m2; |
855 const M2 &_m2; |
847 public: |
856 public: |
848 typedef MapBase<typename M1::Key, typename M1::Value> Parent; |
857 ///\e |
849 typedef typename Parent::Key Key; |
858 typedef typename M1::Key Key; |
850 typedef typename Parent::Value Value; |
859 ///\e |
860 typedef typename M1::Value Value; |
|
851 |
861 |
852 /// Constructor |
862 /// Constructor |
853 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
863 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
854 /// \e |
864 ///\e |
855 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } |
865 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } |
856 }; |
866 }; |
857 |
867 |
858 /// Returns a \c SubMap class |
868 /// Returns a \c SubMap class |
859 |
869 |
892 template<typename M1, typename M2> |
902 template<typename M1, typename M2> |
893 class MulMap : public MapBase<typename M1::Key, typename M1::Value> { |
903 class MulMap : public MapBase<typename M1::Key, typename M1::Value> { |
894 const M1 &_m1; |
904 const M1 &_m1; |
895 const M2 &_m2; |
905 const M2 &_m2; |
896 public: |
906 public: |
897 typedef MapBase<typename M1::Key, typename M1::Value> Parent; |
907 ///\e |
898 typedef typename Parent::Key Key; |
908 typedef typename M1::Key Key; |
899 typedef typename Parent::Value Value; |
909 ///\e |
910 typedef typename M1::Value Value; |
|
900 |
911 |
901 /// Constructor |
912 /// Constructor |
902 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} |
913 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} |
903 /// \e |
914 ///\e |
904 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } |
915 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } |
905 }; |
916 }; |
906 |
917 |
907 /// Returns a \c MulMap class |
918 /// Returns a \c MulMap class |
908 |
919 |
940 template<typename M1, typename M2> |
951 template<typename M1, typename M2> |
941 class DivMap : public MapBase<typename M1::Key, typename M1::Value> { |
952 class DivMap : public MapBase<typename M1::Key, typename M1::Value> { |
942 const M1 &_m1; |
953 const M1 &_m1; |
943 const M2 &_m2; |
954 const M2 &_m2; |
944 public: |
955 public: |
945 typedef MapBase<typename M1::Key, typename M1::Value> Parent; |
956 ///\e |
946 typedef typename Parent::Key Key; |
957 typedef typename M1::Key Key; |
947 typedef typename Parent::Value Value; |
958 ///\e |
959 typedef typename M1::Value Value; |
|
948 |
960 |
949 /// Constructor |
961 /// Constructor |
950 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} |
962 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} |
951 /// \e |
963 ///\e |
952 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } |
964 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } |
953 }; |
965 }; |
954 |
966 |
955 /// Returns a \c DivMap class |
967 /// Returns a \c DivMap class |
956 |
968 |
990 template<typename M, typename C = typename M::Value> |
1002 template<typename M, typename C = typename M::Value> |
991 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { |
1003 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { |
992 const M &_m; |
1004 const M &_m; |
993 C _v; |
1005 C _v; |
994 public: |
1006 public: |
995 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1007 ///\e |
996 typedef typename Parent::Key Key; |
1008 typedef typename M::Key Key; |
997 typedef typename Parent::Value Value; |
1009 ///\e |
1010 typedef typename M::Value Value; |
|
998 |
1011 |
999 /// Constructor |
1012 /// Constructor |
1000 |
1013 |
1001 /// Constructor. |
1014 /// Constructor. |
1002 /// \param m The undelying map. |
1015 /// \param m The undelying map. |
1003 /// \param v The constant value. |
1016 /// \param v The constant value. |
1004 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} |
1017 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} |
1005 /// \e |
1018 ///\e |
1006 Value operator[](const Key &k) const { return _m[k]+_v; } |
1019 Value operator[](const Key &k) const { return _m[k]+_v; } |
1007 }; |
1020 }; |
1008 |
1021 |
1009 /// Shifts a map with a constant (read-write version). |
1022 /// Shifts a map with a constant (read-write version). |
1010 |
1023 |
1020 template<typename M, typename C = typename M::Value> |
1033 template<typename M, typename C = typename M::Value> |
1021 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1034 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1022 M &_m; |
1035 M &_m; |
1023 C _v; |
1036 C _v; |
1024 public: |
1037 public: |
1025 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1038 ///\e |
1026 typedef typename Parent::Key Key; |
1039 typedef typename M::Key Key; |
1027 typedef typename Parent::Value Value; |
1040 ///\e |
1041 typedef typename M::Value Value; |
|
1028 |
1042 |
1029 /// Constructor |
1043 /// Constructor |
1030 |
1044 |
1031 /// Constructor. |
1045 /// Constructor. |
1032 /// \param m The undelying map. |
1046 /// \param m The undelying map. |
1033 /// \param v The constant value. |
1047 /// \param v The constant value. |
1034 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} |
1048 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} |
1035 /// \e |
1049 ///\e |
1036 Value operator[](const Key &k) const { return _m[k]+_v; } |
1050 Value operator[](const Key &k) const { return _m[k]+_v; } |
1037 /// \e |
1051 ///\e |
1038 void set(const Key &k, const Value &v) { _m.set(k, v-_v); } |
1052 void set(const Key &k, const Value &v) { _m.set(k, v-_v); } |
1039 }; |
1053 }; |
1040 |
1054 |
1041 /// Returns a \c ShiftMap class |
1055 /// Returns a \c ShiftMap class |
1042 |
1056 |
1091 template<typename M, typename C = typename M::Value> |
1105 template<typename M, typename C = typename M::Value> |
1092 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { |
1106 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { |
1093 const M &_m; |
1107 const M &_m; |
1094 C _v; |
1108 C _v; |
1095 public: |
1109 public: |
1096 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1110 ///\e |
1097 typedef typename Parent::Key Key; |
1111 typedef typename M::Key Key; |
1098 typedef typename Parent::Value Value; |
1112 ///\e |
1113 typedef typename M::Value Value; |
|
1099 |
1114 |
1100 /// Constructor |
1115 /// Constructor |
1101 |
1116 |
1102 /// Constructor. |
1117 /// Constructor. |
1103 /// \param m The undelying map. |
1118 /// \param m The undelying map. |
1104 /// \param v The constant value. |
1119 /// \param v The constant value. |
1105 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} |
1120 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} |
1106 /// \e |
1121 ///\e |
1107 Value operator[](const Key &k) const { return _v*_m[k]; } |
1122 Value operator[](const Key &k) const { return _v*_m[k]; } |
1108 }; |
1123 }; |
1109 |
1124 |
1110 /// Scales a map with a constant (read-write version). |
1125 /// Scales a map with a constant (read-write version). |
1111 |
1126 |
1122 template<typename M, typename C = typename M::Value> |
1137 template<typename M, typename C = typename M::Value> |
1123 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1138 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1124 M &_m; |
1139 M &_m; |
1125 C _v; |
1140 C _v; |
1126 public: |
1141 public: |
1127 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1142 ///\e |
1128 typedef typename Parent::Key Key; |
1143 typedef typename M::Key Key; |
1129 typedef typename Parent::Value Value; |
1144 ///\e |
1145 typedef typename M::Value Value; |
|
1130 |
1146 |
1131 /// Constructor |
1147 /// Constructor |
1132 |
1148 |
1133 /// Constructor. |
1149 /// Constructor. |
1134 /// \param m The undelying map. |
1150 /// \param m The undelying map. |
1135 /// \param v The constant value. |
1151 /// \param v The constant value. |
1136 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} |
1152 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} |
1137 /// \e |
1153 ///\e |
1138 Value operator[](const Key &k) const { return _v*_m[k]; } |
1154 Value operator[](const Key &k) const { return _v*_m[k]; } |
1139 /// \e |
1155 ///\e |
1140 void set(const Key &k, const Value &v) { _m.set(k, v/_v); } |
1156 void set(const Key &k, const Value &v) { _m.set(k, v/_v); } |
1141 }; |
1157 }; |
1142 |
1158 |
1143 /// Returns a \c ScaleMap class |
1159 /// Returns a \c ScaleMap class |
1144 |
1160 |
1191 /// \sa NegWriteMap |
1207 /// \sa NegWriteMap |
1192 template<typename M> |
1208 template<typename M> |
1193 class NegMap : public MapBase<typename M::Key, typename M::Value> { |
1209 class NegMap : public MapBase<typename M::Key, typename M::Value> { |
1194 const M& _m; |
1210 const M& _m; |
1195 public: |
1211 public: |
1196 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1212 ///\e |
1197 typedef typename Parent::Key Key; |
1213 typedef typename M::Key Key; |
1198 typedef typename Parent::Value Value; |
1214 ///\e |
1215 typedef typename M::Value Value; |
|
1199 |
1216 |
1200 /// Constructor |
1217 /// Constructor |
1201 NegMap(const M &m) : _m(m) {} |
1218 NegMap(const M &m) : _m(m) {} |
1202 /// \e |
1219 ///\e |
1203 Value operator[](const Key &k) const { return -_m[k]; } |
1220 Value operator[](const Key &k) const { return -_m[k]; } |
1204 }; |
1221 }; |
1205 |
1222 |
1206 /// Negative of a map (read-write version) |
1223 /// Negative of a map (read-write version) |
1207 |
1224 |
1226 /// \sa NegMap |
1243 /// \sa NegMap |
1227 template<typename M> |
1244 template<typename M> |
1228 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1245 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { |
1229 M &_m; |
1246 M &_m; |
1230 public: |
1247 public: |
1231 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1248 ///\e |
1232 typedef typename Parent::Key Key; |
1249 typedef typename M::Key Key; |
1233 typedef typename Parent::Value Value; |
1250 ///\e |
1251 typedef typename M::Value Value; |
|
1234 |
1252 |
1235 /// Constructor |
1253 /// Constructor |
1236 NegWriteMap(M &m) : _m(m) {} |
1254 NegWriteMap(M &m) : _m(m) {} |
1237 /// \e |
1255 ///\e |
1238 Value operator[](const Key &k) const { return -_m[k]; } |
1256 Value operator[](const Key &k) const { return -_m[k]; } |
1239 /// \e |
1257 ///\e |
1240 void set(const Key &k, const Value &v) { _m.set(k, -v); } |
1258 void set(const Key &k, const Value &v) { _m.set(k, -v); } |
1241 }; |
1259 }; |
1242 |
1260 |
1243 /// Returns a \c NegMap class |
1261 /// Returns a \c NegMap class |
1244 |
1262 |
1280 /// function. |
1298 /// function. |
1281 template<typename M> |
1299 template<typename M> |
1282 class AbsMap : public MapBase<typename M::Key, typename M::Value> { |
1300 class AbsMap : public MapBase<typename M::Key, typename M::Value> { |
1283 const M &_m; |
1301 const M &_m; |
1284 public: |
1302 public: |
1285 typedef MapBase<typename M::Key, typename M::Value> Parent; |
1303 ///\e |
1286 typedef typename Parent::Key Key; |
1304 typedef typename M::Key Key; |
1287 typedef typename Parent::Value Value; |
1305 ///\e |
1306 typedef typename M::Value Value; |
|
1288 |
1307 |
1289 /// Constructor |
1308 /// Constructor |
1290 AbsMap(const M &m) : _m(m) {} |
1309 AbsMap(const M &m) : _m(m) {} |
1291 /// \e |
1310 ///\e |
1292 Value operator[](const Key &k) const { |
1311 Value operator[](const Key &k) const { |
1293 Value tmp = _m[k]; |
1312 Value tmp = _m[k]; |
1294 return tmp >= 0 ? tmp : -tmp; |
1313 return tmp >= 0 ? tmp : -tmp; |
1295 } |
1314 } |
1296 |
1315 |
1335 /// \sa FalseMap |
1354 /// \sa FalseMap |
1336 /// \sa ConstMap |
1355 /// \sa ConstMap |
1337 template <typename K> |
1356 template <typename K> |
1338 class TrueMap : public MapBase<K, bool> { |
1357 class TrueMap : public MapBase<K, bool> { |
1339 public: |
1358 public: |
1340 typedef MapBase<K, bool> Parent; |
1359 ///\e |
1341 typedef typename Parent::Key Key; |
1360 typedef K Key; |
1342 typedef typename Parent::Value Value; |
1361 ///\e |
1362 typedef bool Value; |
|
1343 |
1363 |
1344 /// Gives back \c true. |
1364 /// Gives back \c true. |
1345 Value operator[](const Key&) const { return true; } |
1365 Value operator[](const Key&) const { return true; } |
1346 }; |
1366 }; |
1347 |
1367 |
1372 /// \sa TrueMap |
1392 /// \sa TrueMap |
1373 /// \sa ConstMap |
1393 /// \sa ConstMap |
1374 template <typename K> |
1394 template <typename K> |
1375 class FalseMap : public MapBase<K, bool> { |
1395 class FalseMap : public MapBase<K, bool> { |
1376 public: |
1396 public: |
1377 typedef MapBase<K, bool> Parent; |
1397 ///\e |
1378 typedef typename Parent::Key Key; |
1398 typedef K Key; |
1379 typedef typename Parent::Value Value; |
1399 ///\e |
1400 typedef bool Value; |
|
1380 |
1401 |
1381 /// Gives back \c false. |
1402 /// Gives back \c false. |
1382 Value operator[](const Key&) const { return false; } |
1403 Value operator[](const Key&) const { return false; } |
1383 }; |
1404 }; |
1384 |
1405 |
1417 template<typename M1, typename M2> |
1438 template<typename M1, typename M2> |
1418 class AndMap : public MapBase<typename M1::Key, bool> { |
1439 class AndMap : public MapBase<typename M1::Key, bool> { |
1419 const M1 &_m1; |
1440 const M1 &_m1; |
1420 const M2 &_m2; |
1441 const M2 &_m2; |
1421 public: |
1442 public: |
1422 typedef MapBase<typename M1::Key, bool> Parent; |
1443 ///\e |
1423 typedef typename Parent::Key Key; |
1444 typedef typename M1::Key Key; |
1424 typedef typename Parent::Value Value; |
1445 ///\e |
1446 typedef bool Value; |
|
1425 |
1447 |
1426 /// Constructor |
1448 /// Constructor |
1427 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1449 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1428 /// \e |
1450 ///\e |
1429 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } |
1451 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } |
1430 }; |
1452 }; |
1431 |
1453 |
1432 /// Returns an \c AndMap class |
1454 /// Returns an \c AndMap class |
1433 |
1455 |
1465 template<typename M1, typename M2> |
1487 template<typename M1, typename M2> |
1466 class OrMap : public MapBase<typename M1::Key, bool> { |
1488 class OrMap : public MapBase<typename M1::Key, bool> { |
1467 const M1 &_m1; |
1489 const M1 &_m1; |
1468 const M2 &_m2; |
1490 const M2 &_m2; |
1469 public: |
1491 public: |
1470 typedef MapBase<typename M1::Key, bool> Parent; |
1492 ///\e |
1471 typedef typename Parent::Key Key; |
1493 typedef typename M1::Key Key; |
1472 typedef typename Parent::Value Value; |
1494 ///\e |
1495 typedef bool Value; |
|
1473 |
1496 |
1474 /// Constructor |
1497 /// Constructor |
1475 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1498 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1476 /// \e |
1499 ///\e |
1477 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } |
1500 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } |
1478 }; |
1501 }; |
1479 |
1502 |
1480 /// Returns an \c OrMap class |
1503 /// Returns an \c OrMap class |
1481 |
1504 |
1504 /// \sa NotWriteMap |
1527 /// \sa NotWriteMap |
1505 template <typename M> |
1528 template <typename M> |
1506 class NotMap : public MapBase<typename M::Key, bool> { |
1529 class NotMap : public MapBase<typename M::Key, bool> { |
1507 const M &_m; |
1530 const M &_m; |
1508 public: |
1531 public: |
1509 typedef MapBase<typename M::Key, bool> Parent; |
1532 ///\e |
1510 typedef typename Parent::Key Key; |
1533 typedef typename M::Key Key; |
1511 typedef typename Parent::Value Value; |
1534 ///\e |
1535 typedef bool Value; |
|
1512 |
1536 |
1513 /// Constructor |
1537 /// Constructor |
1514 NotMap(const M &m) : _m(m) {} |
1538 NotMap(const M &m) : _m(m) {} |
1515 /// \e |
1539 ///\e |
1516 Value operator[](const Key &k) const { return !_m[k]; } |
1540 Value operator[](const Key &k) const { return !_m[k]; } |
1517 }; |
1541 }; |
1518 |
1542 |
1519 /// Logical 'not' of a map (read-write version) |
1543 /// Logical 'not' of a map (read-write version) |
1520 |
1544 |
1530 /// \sa NotMap |
1554 /// \sa NotMap |
1531 template <typename M> |
1555 template <typename M> |
1532 class NotWriteMap : public MapBase<typename M::Key, bool> { |
1556 class NotWriteMap : public MapBase<typename M::Key, bool> { |
1533 M &_m; |
1557 M &_m; |
1534 public: |
1558 public: |
1535 typedef MapBase<typename M::Key, bool> Parent; |
1559 ///\e |
1536 typedef typename Parent::Key Key; |
1560 typedef typename M::Key Key; |
1537 typedef typename Parent::Value Value; |
1561 ///\e |
1562 typedef bool Value; |
|
1538 |
1563 |
1539 /// Constructor |
1564 /// Constructor |
1540 NotWriteMap(M &m) : _m(m) {} |
1565 NotWriteMap(M &m) : _m(m) {} |
1541 /// \e |
1566 ///\e |
1542 Value operator[](const Key &k) const { return !_m[k]; } |
1567 Value operator[](const Key &k) const { return !_m[k]; } |
1543 /// \e |
1568 ///\e |
1544 void set(const Key &k, bool v) { _m.set(k, !v); } |
1569 void set(const Key &k, bool v) { _m.set(k, !v); } |
1545 }; |
1570 }; |
1546 |
1571 |
1547 /// Returns a \c NotMap class |
1572 /// Returns a \c NotMap class |
1548 |
1573 |
1593 template<typename M1, typename M2> |
1618 template<typename M1, typename M2> |
1594 class EqualMap : public MapBase<typename M1::Key, bool> { |
1619 class EqualMap : public MapBase<typename M1::Key, bool> { |
1595 const M1 &_m1; |
1620 const M1 &_m1; |
1596 const M2 &_m2; |
1621 const M2 &_m2; |
1597 public: |
1622 public: |
1598 typedef MapBase<typename M1::Key, bool> Parent; |
1623 ///\e |
1599 typedef typename Parent::Key Key; |
1624 typedef typename M1::Key Key; |
1600 typedef typename Parent::Value Value; |
1625 ///\e |
1626 typedef bool Value; |
|
1601 |
1627 |
1602 /// Constructor |
1628 /// Constructor |
1603 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1629 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1604 /// \e |
1630 ///\e |
1605 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } |
1631 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } |
1606 }; |
1632 }; |
1607 |
1633 |
1608 /// Returns an \c EqualMap class |
1634 /// Returns an \c EqualMap class |
1609 |
1635 |
1641 template<typename M1, typename M2> |
1667 template<typename M1, typename M2> |
1642 class LessMap : public MapBase<typename M1::Key, bool> { |
1668 class LessMap : public MapBase<typename M1::Key, bool> { |
1643 const M1 &_m1; |
1669 const M1 &_m1; |
1644 const M2 &_m2; |
1670 const M2 &_m2; |
1645 public: |
1671 public: |
1646 typedef MapBase<typename M1::Key, bool> Parent; |
1672 ///\e |
1647 typedef typename Parent::Key Key; |
1673 typedef typename M1::Key Key; |
1648 typedef typename Parent::Value Value; |
1674 ///\e |
1675 typedef bool Value; |
|
1649 |
1676 |
1650 /// Constructor |
1677 /// Constructor |
1651 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1678 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
1652 /// \e |
1679 ///\e |
1653 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } |
1680 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } |
1654 }; |
1681 }; |
1655 |
1682 |
1656 /// Returns an \c LessMap class |
1683 /// Returns an \c LessMap class |
1657 |
1684 |
1703 /// easily done with LoggerBoolMap. |
1730 /// easily done with LoggerBoolMap. |
1704 /// |
1731 /// |
1705 /// The simplest way of using this map is through the loggerBoolMap() |
1732 /// The simplest way of using this map is through the loggerBoolMap() |
1706 /// function. |
1733 /// function. |
1707 /// |
1734 /// |
1708 /// \tparam It The type of the iterator. |
1735 /// \tparam IT The type of the iterator. |
1709 /// \tparam Ke The key type of the map. The default value set |
1736 /// \tparam KEY The key type of the map. The default value set |
1710 /// according to the iterator type should work in most cases. |
1737 /// according to the iterator type should work in most cases. |
1711 /// |
1738 /// |
1712 /// \note The container of the iterator must contain enough space |
1739 /// \note The container of the iterator must contain enough space |
1713 /// for the elements or the iterator should be an inserter iterator. |
1740 /// for the elements or the iterator should be an inserter iterator. |
1714 #ifdef DOXYGEN |
1741 #ifdef DOXYGEN |
1715 template <typename It, typename Ke> |
1742 template <typename IT, typename KEY> |
1716 #else |
1743 #else |
1717 template <typename It, |
1744 template <typename IT, |
1718 typename Ke=typename _maps_bits::IteratorTraits<It>::Value> |
1745 typename KEY = typename _maps_bits::IteratorTraits<IT>::Value> |
1719 #endif |
1746 #endif |
1720 class LoggerBoolMap { |
1747 class LoggerBoolMap : public MapBase<KEY, bool> { |
1721 public: |
1748 public: |
1722 typedef It Iterator; |
1749 |
1723 |
1750 ///\e |
1724 typedef Ke Key; |
1751 typedef KEY Key; |
1752 ///\e |
|
1725 typedef bool Value; |
1753 typedef bool Value; |
1754 ///\e |
|
1755 typedef IT Iterator; |
|
1726 |
1756 |
1727 /// Constructor |
1757 /// Constructor |
1728 LoggerBoolMap(Iterator it) |
1758 LoggerBoolMap(Iterator it) |
1729 : _begin(it), _end(it) {} |
1759 : _begin(it), _end(it) {} |
1730 |
1760 |
1783 /// @} |
1813 /// @} |
1784 |
1814 |
1785 /// \addtogroup graph_maps |
1815 /// \addtogroup graph_maps |
1786 /// @{ |
1816 /// @{ |
1787 |
1817 |
1788 /// Provides an immutable and unique id for each item in the graph. |
1818 /// \brief Provides an immutable and unique id for each item in a graph. |
1789 |
1819 /// |
1790 /// The IdMap class provides a unique and immutable id for each item of the |
1820 /// IdMap provides a unique and immutable id for each item of the |
1791 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: |
1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is |
1792 /// different items (nodes) get different ids <li>\b immutable: the id of an |
1822 /// - \b unique: different items get different ids, |
1793 /// item (node) does not change (even if you delete other nodes). </ul> |
1823 /// - \b immutable: the id of an item does not change (even if you |
1794 /// Through this map you get access (i.e. can read) the inner id values of |
1824 /// delete other nodes). |
1795 /// the items stored in the graph. This map can be inverted with its member |
1825 /// |
1826 /// Using this map you get access (i.e. can read) the inner id values of |
|
1827 /// the items stored in the graph, which is returned by the \c id() |
|
1828 /// function of the graph. This map can be inverted with its member |
|
1796 /// class \c InverseMap or with the \c operator() member. |
1829 /// class \c InverseMap or with the \c operator() member. |
1797 /// |
1830 /// |
1798 template <typename _Graph, typename _Item> |
1831 /// \tparam GR The graph type. |
1799 class IdMap { |
1832 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or |
1800 public: |
1833 /// \c GR::Edge). |
1801 typedef _Graph Graph; |
1834 /// |
1835 /// \see DescriptorMap |
|
1836 template <typename GR, typename K> |
|
1837 class IdMap : public MapBase<K, int> { |
|
1838 public: |
|
1839 /// The graph type of IdMap. |
|
1840 typedef GR Graph; |
|
1841 /// The key type of IdMap (\c Node, \c Arc or \c Edge). |
|
1842 typedef K Item; |
|
1843 /// The key type of IdMap (\c Node, \c Arc or \c Edge). |
|
1844 typedef K Key; |
|
1845 /// The value type of IdMap. |
|
1802 typedef int Value; |
1846 typedef int Value; |
1803 typedef _Item Item; |
|
1804 typedef _Item Key; |
|
1805 |
1847 |
1806 /// \brief Constructor. |
1848 /// \brief Constructor. |
1807 /// |
1849 /// |
1808 /// Constructor of the map. |
1850 /// Constructor of the map. |
1809 explicit IdMap(const Graph& graph) : _graph(&graph) {} |
1851 explicit IdMap(const Graph& graph) : _graph(&graph) {} |
1811 /// \brief Gives back the \e id of the item. |
1853 /// \brief Gives back the \e id of the item. |
1812 /// |
1854 /// |
1813 /// Gives back the immutable and unique \e id of the item. |
1855 /// Gives back the immutable and unique \e id of the item. |
1814 int operator[](const Item& item) const { return _graph->id(item);} |
1856 int operator[](const Item& item) const { return _graph->id(item);} |
1815 |
1857 |
1816 /// \brief Gives back the item by its id. |
1858 /// \brief Gives back the \e item by its id. |
1817 /// |
1859 /// |
1818 /// Gives back the item by its id. |
1860 /// Gives back the \e item by its id. |
1819 Item operator()(int id) { return _graph->fromId(id, Item()); } |
1861 Item operator()(int id) { return _graph->fromId(id, Item()); } |
1820 |
1862 |
1821 private: |
1863 private: |
1822 const Graph* _graph; |
1864 const Graph* _graph; |
1823 |
1865 |
1824 public: |
1866 public: |
1825 |
1867 |
1826 /// \brief The class represents the inverse of its owner (IdMap). |
1868 /// \brief This class represents the inverse of its owner (IdMap). |
1827 /// |
1869 /// |
1828 /// The class represents the inverse of its owner (IdMap). |
1870 /// This class represents the inverse of its owner (IdMap). |
1829 /// \see inverse() |
1871 /// \see inverse() |
1830 class InverseMap { |
1872 class InverseMap { |
1831 public: |
1873 public: |
1832 |
1874 |
1833 /// \brief Constructor. |
1875 /// \brief Constructor. |
1841 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} |
1883 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} |
1842 |
1884 |
1843 /// \brief Gives back the given item from its id. |
1885 /// \brief Gives back the given item from its id. |
1844 /// |
1886 /// |
1845 /// Gives back the given item from its id. |
1887 /// Gives back the given item from its id. |
1846 /// |
|
1847 Item operator[](int id) const { return _graph->fromId(id, Item());} |
1888 Item operator[](int id) const { return _graph->fromId(id, Item());} |
1848 |
1889 |
1849 private: |
1890 private: |
1850 const Graph* _graph; |
1891 const Graph* _graph; |
1851 }; |
1892 }; |
1852 |
1893 |
1853 /// \brief Gives back the inverse of the map. |
1894 /// \brief Gives back the inverse of the map. |
1854 /// |
1895 /// |
1855 /// Gives back the inverse of the IdMap. |
1896 /// Gives back the inverse of the IdMap. |
1856 InverseMap inverse() const { return InverseMap(*_graph);} |
1897 InverseMap inverse() const { return InverseMap(*_graph);} |
1857 |
1898 }; |
1858 }; |
1899 |
1859 |
1900 |
1860 |
1901 /// \brief General invertable graph map type. |
1861 /// \brief General invertable graph-map type. |
1902 |
1862 |
1903 /// This class provides simple invertable graph maps. |
1863 /// This type provides simple invertable graph-maps. |
1904 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" |
1864 /// The InvertableMap wraps an arbitrary ReadWriteMap |
|
1865 /// and if a key is set to a new value then store it |
1905 /// and if a key is set to a new value then store it |
1866 /// in the inverse map. |
1906 /// in the inverse map. |
1867 /// |
1907 /// |
1868 /// The values of the map can be accessed |
1908 /// The values of the map can be accessed |
1869 /// with stl compatible forward iterator. |
1909 /// with stl compatible forward iterator. |
1870 /// |
1910 /// |
1871 /// \tparam _Graph The graph type. |
1911 /// \tparam GR The graph type. |
1872 /// \tparam _Item The item type of the graph. |
1912 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or |
1873 /// \tparam _Value The value type of the map. |
1913 /// \c GR::Edge). |
1914 /// \tparam V The value type of the map. |
|
1874 /// |
1915 /// |
1875 /// \see IterableValueMap |
1916 /// \see IterableValueMap |
1876 template <typename _Graph, typename _Item, typename _Value> |
1917 template <typename GR, typename K, typename V> |
1877 class InvertableMap |
1918 class InvertableMap |
1878 : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type { |
1919 : protected ItemSetTraits<GR, K>::template Map<V>::Type { |
1879 private: |
1920 private: |
1880 |
1921 |
1881 typedef typename ItemSetTraits<_Graph, _Item>:: |
1922 typedef typename ItemSetTraits<GR, K>:: |
1882 template Map<_Value>::Type Map; |
1923 template Map<V>::Type Map; |
1883 typedef _Graph Graph; |
1924 |
1884 |
1925 typedef std::map<V, K> Container; |
1885 typedef std::map<_Value, _Item> Container; |
|
1886 Container _inv_map; |
1926 Container _inv_map; |
1887 |
1927 |
1888 public: |
1928 public: |
1889 |
1929 |
1890 /// The key type of InvertableMap (Node, Arc, Edge). |
1930 /// The graph type of InvertableMap. |
1891 typedef typename Map::Key Key; |
1931 typedef GR Graph; |
1892 /// The value type of the InvertableMap. |
1932 /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). |
1893 typedef typename Map::Value Value; |
1933 typedef K Item; |
1934 /// The key type of InvertableMap (\c Node, \c Arc or \c Edge). |
|
1935 typedef K Key; |
|
1936 /// The value type of InvertableMap. |
|
1937 typedef V Value; |
|
1894 |
1938 |
1895 /// \brief Constructor. |
1939 /// \brief Constructor. |
1896 /// |
1940 /// |
1897 /// Construct a new InvertableMap for the graph. |
1941 /// Construct a new InvertableMap for the given graph. |
1898 /// |
|
1899 explicit InvertableMap(const Graph& graph) : Map(graph) {} |
1942 explicit InvertableMap(const Graph& graph) : Map(graph) {} |
1900 |
1943 |
1901 /// \brief Forward iterator for values. |
1944 /// \brief Forward iterator for values. |
1902 /// |
1945 /// |
1903 /// This iterator is an stl compatible forward |
1946 /// This iterator is an stl compatible forward |
1904 /// iterator on the values of the map. The values can |
1947 /// iterator on the values of the map. The values can |
1905 /// be accessed in the [beginValue, endValue) range. |
1948 /// be accessed in the <tt>[beginValue, endValue)</tt> range. |
1906 /// |
|
1907 class ValueIterator |
1949 class ValueIterator |
1908 : public std::iterator<std::forward_iterator_tag, Value> { |
1950 : public std::iterator<std::forward_iterator_tag, Value> { |
1909 friend class InvertableMap; |
1951 friend class InvertableMap; |
1910 private: |
1952 private: |
1911 ValueIterator(typename Container::const_iterator _it) |
1953 ValueIterator(typename Container::const_iterator _it) |
1933 |
1975 |
1934 /// \brief Returns an iterator to the first value. |
1976 /// \brief Returns an iterator to the first value. |
1935 /// |
1977 /// |
1936 /// Returns an stl compatible iterator to the |
1978 /// Returns an stl compatible iterator to the |
1937 /// first value of the map. The values of the |
1979 /// first value of the map. The values of the |
1938 /// map can be accessed in the [beginValue, endValue) |
1980 /// map can be accessed in the <tt>[beginValue, endValue)</tt> |
1939 /// range. |
1981 /// range. |
1940 ValueIterator beginValue() const { |
1982 ValueIterator beginValue() const { |
1941 return ValueIterator(_inv_map.begin()); |
1983 return ValueIterator(_inv_map.begin()); |
1942 } |
1984 } |
1943 |
1985 |
1944 /// \brief Returns an iterator after the last value. |
1986 /// \brief Returns an iterator after the last value. |
1945 /// |
1987 /// |
1946 /// Returns an stl compatible iterator after the |
1988 /// Returns an stl compatible iterator after the |
1947 /// last value of the map. The values of the |
1989 /// last value of the map. The values of the |
1948 /// map can be accessed in the [beginValue, endValue) |
1990 /// map can be accessed in the <tt>[beginValue, endValue)</tt> |
1949 /// range. |
1991 /// range. |
1950 ValueIterator endValue() const { |
1992 ValueIterator endValue() const { |
1951 return ValueIterator(_inv_map.end()); |
1993 return ValueIterator(_inv_map.end()); |
1952 } |
1994 } |
1953 |
1995 |
1954 /// \brief The setter function of the map. |
1996 /// \brief Sets the value associated with the given key. |
1955 /// |
1997 /// |
1956 /// Sets the mapped value. |
1998 /// Sets the value associated with the given key. |
1957 void set(const Key& key, const Value& val) { |
1999 void set(const Key& key, const Value& val) { |
1958 Value oldval = Map::operator[](key); |
2000 Value oldval = Map::operator[](key); |
1959 typename Container::iterator it = _inv_map.find(oldval); |
2001 typename Container::iterator it = _inv_map.find(oldval); |
1960 if (it != _inv_map.end() && it->second == key) { |
2002 if (it != _inv_map.end() && it->second == key) { |
1961 _inv_map.erase(it); |
2003 _inv_map.erase(it); |
1962 } |
2004 } |
1963 _inv_map.insert(make_pair(val, key)); |
2005 _inv_map.insert(make_pair(val, key)); |
1964 Map::set(key, val); |
2006 Map::set(key, val); |
1965 } |
2007 } |
1966 |
2008 |
1967 /// \brief The getter function of the map. |
2009 /// \brief Returns the value associated with the given key. |
1968 /// |
2010 /// |
1969 /// It gives back the value associated with the key. |
2011 /// Returns the value associated with the given key. |
1970 typename MapTraits<Map>::ConstReturnValue |
2012 typename MapTraits<Map>::ConstReturnValue |
1971 operator[](const Key& key) const { |
2013 operator[](const Key& key) const { |
1972 return Map::operator[](key); |
2014 return Map::operator[](key); |
1973 } |
2015 } |
1974 |
2016 |
1980 return it != _inv_map.end() ? it->second : INVALID; |
2022 return it != _inv_map.end() ? it->second : INVALID; |
1981 } |
2023 } |
1982 |
2024 |
1983 protected: |
2025 protected: |
1984 |
2026 |
1985 /// \brief Erase the key from the map. |
2027 /// \brief Erase the key from the map and the inverse map. |
1986 /// |
2028 /// |
1987 /// Erase the key to the map. It is called by the |
2029 /// Erase the key from the map and the inverse map. It is called by the |
1988 /// \c AlterationNotifier. |
2030 /// \c AlterationNotifier. |
1989 virtual void erase(const Key& key) { |
2031 virtual void erase(const Key& key) { |
1990 Value val = Map::operator[](key); |
2032 Value val = Map::operator[](key); |
1991 typename Container::iterator it = _inv_map.find(val); |
2033 typename Container::iterator it = _inv_map.find(val); |
1992 if (it != _inv_map.end() && it->second == key) { |
2034 if (it != _inv_map.end() && it->second == key) { |
1993 _inv_map.erase(it); |
2035 _inv_map.erase(it); |
1994 } |
2036 } |
1995 Map::erase(key); |
2037 Map::erase(key); |
1996 } |
2038 } |
1997 |
2039 |
1998 /// \brief Erase more keys from the map. |
2040 /// \brief Erase more keys from the map and the inverse map. |
1999 /// |
2041 /// |
2000 /// Erase more keys from the map. It is called by the |
2042 /// Erase more keys from the map and the inverse map. It is called by the |
2001 /// \c AlterationNotifier. |
2043 /// \c AlterationNotifier. |
2002 virtual void erase(const std::vector<Key>& keys) { |
2044 virtual void erase(const std::vector<Key>& keys) { |
2003 for (int i = 0; i < int(keys.size()); ++i) { |
2045 for (int i = 0; i < int(keys.size()); ++i) { |
2004 Value val = Map::operator[](keys[i]); |
2046 Value val = Map::operator[](keys[i]); |
2005 typename Container::iterator it = _inv_map.find(val); |
2047 typename Container::iterator it = _inv_map.find(val); |
2008 } |
2050 } |
2009 } |
2051 } |
2010 Map::erase(keys); |
2052 Map::erase(keys); |
2011 } |
2053 } |
2012 |
2054 |
2013 /// \brief Clear the keys from the map and inverse map. |
2055 /// \brief Clear the keys from the map and the inverse map. |
2014 /// |
2056 /// |
2015 /// Clear the keys from the map and inverse map. It is called by the |
2057 /// Clear the keys from the map and the inverse map. It is called by the |
2016 /// \c AlterationNotifier. |
2058 /// \c AlterationNotifier. |
2017 virtual void clear() { |
2059 virtual void clear() { |
2018 _inv_map.clear(); |
2060 _inv_map.clear(); |
2019 Map::clear(); |
2061 Map::clear(); |
2020 } |
2062 } |
2022 public: |
2064 public: |
2023 |
2065 |
2024 /// \brief The inverse map type. |
2066 /// \brief The inverse map type. |
2025 /// |
2067 /// |
2026 /// The inverse of this map. The subscript operator of the map |
2068 /// The inverse of this map. The subscript operator of the map |
2027 /// gives back always the item what was last assigned to the value. |
2069 /// gives back the item that was last assigned to the value. |
2028 class InverseMap { |
2070 class InverseMap { |
2029 public: |
2071 public: |
2030 /// \brief Constructor of the InverseMap. |
2072 /// \brief Constructor |
2031 /// |
2073 /// |
2032 /// Constructor of the InverseMap. |
2074 /// Constructor of the InverseMap. |
2033 explicit InverseMap(const InvertableMap& inverted) |
2075 explicit InverseMap(const InvertableMap& inverted) |
2034 : _inverted(inverted) {} |
2076 : _inverted(inverted) {} |
2035 |
2077 |
2038 /// The key type of the InverseMap. |
2080 /// The key type of the InverseMap. |
2039 typedef typename InvertableMap::Value Key; |
2081 typedef typename InvertableMap::Value Key; |
2040 |
2082 |
2041 /// \brief Subscript operator. |
2083 /// \brief Subscript operator. |
2042 /// |
2084 /// |
2043 /// Subscript operator. It gives back always the item |
2085 /// Subscript operator. It gives back the item |
2044 /// what was last assigned to the value. |
2086 /// that was last assigned to the given value. |
2045 Value operator[](const Key& key) const { |
2087 Value operator[](const Key& key) const { |
2046 return _inverted(key); |
2088 return _inverted(key); |
2047 } |
2089 } |
2048 |
2090 |
2049 private: |
2091 private: |
2050 const InvertableMap& _inverted; |
2092 const InvertableMap& _inverted; |
2051 }; |
2093 }; |
2052 |
2094 |
2053 /// \brief It gives back the just readable inverse map. |
2095 /// \brief It gives back the read-only inverse map. |
2054 /// |
2096 /// |
2055 /// It gives back the just readable inverse map. |
2097 /// It gives back the read-only inverse map. |
2056 InverseMap inverse() const { |
2098 InverseMap inverse() const { |
2057 return InverseMap(*this); |
2099 return InverseMap(*this); |
2058 } |
2100 } |
2059 |
2101 |
2060 }; |
2102 }; |
2061 |
2103 |
2062 /// \brief Provides a mutable, continuous and unique descriptor for each |
2104 /// \brief Provides a mutable, continuous and unique descriptor for each |
2063 /// item in the graph. |
2105 /// item in a graph. |
2064 /// |
2106 /// |
2065 /// The DescriptorMap class provides a unique and continuous (but mutable) |
2107 /// DescriptorMap provides a unique and continuous (but mutable) |
2066 /// descriptor (id) for each item of the same type (e.g. node) in the |
2108 /// descriptor (id) for each item of the same type (\c Node, \c Arc or |
2067 /// graph. This id is <ul><li>\b unique: different items (nodes) get |
2109 /// \c Edge) in a graph. This id is |
2068 /// different ids <li>\b continuous: the range of the ids is the set of |
2110 /// - \b unique: different items get different ids, |
2069 /// integers between 0 and \c n-1, where \c n is the number of the items of |
2111 /// - \b continuous: the range of the ids is the set of integers |
2070 /// this type (e.g. nodes) (so the id of a node can change if you delete an |
2112 /// between 0 and \c n-1, where \c n is the number of the items of |
2071 /// other node, i.e. this id is mutable). </ul> This map can be inverted |
2113 /// this type (\c Node, \c Arc or \c Edge). So the id of an item can |
2072 /// with its member class \c InverseMap, or with the \c operator() member. |
2114 /// change if you delete an other item of the same type, i.e. this |
2073 /// |
2115 /// id is mutable. |
2074 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. |
2116 /// |
2075 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or |
2117 /// Thus this id is not (necessarily) the same as what can get using |
2076 /// Edge. |
2118 /// the \c id() function of the graph or \ref IdMap. |
2077 template <typename _Graph, typename _Item> |
2119 /// This map can be inverted with its member class \c InverseMap, |
2120 /// or with the \c operator() member. |
|
2121 /// |
|
2122 /// \tparam GR The graph type. |
|
2123 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or |
|
2124 /// \c GR::Edge). |
|
2125 /// |
|
2126 /// \see IdMap |
|
2127 template <typename GR, typename K> |
|
2078 class DescriptorMap |
2128 class DescriptorMap |
2079 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type { |
2129 : protected ItemSetTraits<GR, K>::template Map<int>::Type { |
2080 |
2130 |
2081 typedef _Item Item; |
2131 typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map; |
2082 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map; |
2132 |
2083 |
2133 public: |
2084 public: |
2134 /// The graph type of DescriptorMap. |
2085 /// The graph class of DescriptorMap. |
2135 typedef GR Graph; |
2086 typedef _Graph Graph; |
2136 /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). |
2087 |
2137 typedef K Item; |
2088 /// The key type of DescriptorMap (Node, Arc, Edge). |
2138 /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge). |
2089 typedef typename Map::Key Key; |
2139 typedef K Key; |
2090 /// The value type of DescriptorMap. |
2140 /// The value type of DescriptorMap. |
2091 typedef typename Map::Value Value; |
2141 typedef int Value; |
2092 |
2142 |
2093 /// \brief Constructor. |
2143 /// \brief Constructor. |
2094 /// |
2144 /// |
2095 /// Constructor for descriptor map. |
2145 /// Constructor for descriptor map. |
2096 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { |
2146 explicit DescriptorMap(const Graph& gr) : Map(gr) { |
2097 Item it; |
2147 Item it; |
2098 const typename Map::Notifier* nf = Map::notifier(); |
2148 const typename Map::Notifier* nf = Map::notifier(); |
2099 for (nf->first(it); it != INVALID; nf->next(it)) { |
2149 for (nf->first(it); it != INVALID; nf->next(it)) { |
2100 Map::set(it, _inv_map.size()); |
2150 Map::set(it, _inv_map.size()); |
2101 _inv_map.push_back(it); |
2151 _inv_map.push_back(it); |
2102 } |
2152 } |
2103 } |
2153 } |
2104 |
2154 |
2105 protected: |
2155 protected: |
2106 |
2156 |
2107 /// \brief Add a new key to the map. |
2157 /// \brief Adds a new key to the map. |
2108 /// |
2158 /// |
2109 /// Add a new key to the map. It is called by the |
2159 /// Add a new key to the map. It is called by the |
2110 /// \c AlterationNotifier. |
2160 /// \c AlterationNotifier. |
2111 virtual void add(const Item& item) { |
2161 virtual void add(const Item& item) { |
2112 Map::add(item); |
2162 Map::add(item); |
2212 |
2262 |
2213 typedef std::vector<Item> Container; |
2263 typedef std::vector<Item> Container; |
2214 Container _inv_map; |
2264 Container _inv_map; |
2215 |
2265 |
2216 public: |
2266 public: |
2267 |
|
2217 /// \brief The inverse map type of DescriptorMap. |
2268 /// \brief The inverse map type of DescriptorMap. |
2218 /// |
2269 /// |
2219 /// The inverse map type of DescriptorMap. |
2270 /// The inverse map type of DescriptorMap. |
2220 class InverseMap { |
2271 class InverseMap { |
2221 public: |
2272 public: |
2222 /// \brief Constructor of the InverseMap. |
2273 /// \brief Constructor |
2223 /// |
2274 /// |
2224 /// Constructor of the InverseMap. |
2275 /// Constructor of the InverseMap. |
2225 explicit InverseMap(const DescriptorMap& inverted) |
2276 explicit InverseMap(const DescriptorMap& inverted) |
2226 : _inverted(inverted) {} |
2277 : _inverted(inverted) {} |
2227 |
2278 |
2232 typedef typename DescriptorMap::Value Key; |
2283 typedef typename DescriptorMap::Value Key; |
2233 |
2284 |
2234 /// \brief Subscript operator. |
2285 /// \brief Subscript operator. |
2235 /// |
2286 /// |
2236 /// Subscript operator. It gives back the item |
2287 /// Subscript operator. It gives back the item |
2237 /// that the descriptor belongs to currently. |
2288 /// that the descriptor currently belongs to. |
2238 Value operator[](const Key& key) const { |
2289 Value operator[](const Key& key) const { |
2239 return _inverted(key); |
2290 return _inverted(key); |
2240 } |
2291 } |
2241 |
2292 |
2242 /// \brief Size of the map. |
2293 /// \brief Size of the map. |
2256 const InverseMap inverse() const { |
2307 const InverseMap inverse() const { |
2257 return InverseMap(*this); |
2308 return InverseMap(*this); |
2258 } |
2309 } |
2259 }; |
2310 }; |
2260 |
2311 |
2261 /// \brief Returns the source of the given arc. |
2312 /// \brief Map of the source nodes of arcs in a digraph. |
2262 /// |
2313 /// |
2263 /// The SourceMap gives back the source Node of the given arc. |
2314 /// SourceMap provides access for the source node of each arc in a digraph, |
2315 /// which is returned by the \c source() function of the digraph. |
|
2316 /// \tparam GR The digraph type. |
|
2264 /// \see TargetMap |
2317 /// \see TargetMap |
2265 template <typename Digraph> |
2318 template <typename GR> |
2266 class SourceMap { |
2319 class SourceMap { |
2267 public: |
2320 public: |
2268 |
2321 |
2269 typedef typename Digraph::Node Value; |
2322 ///\e |
2270 typedef typename Digraph::Arc Key; |
2323 typedef typename GR::Arc Key; |
2324 ///\e |
|
2325 typedef typename GR::Node Value; |
|
2271 |
2326 |
2272 /// \brief Constructor |
2327 /// \brief Constructor |
2273 /// |
2328 /// |
2274 /// Constructor |
2329 /// Constructor. |
2275 /// \param digraph The digraph that the map belongs to. |
2330 /// \param digraph The digraph that the map belongs to. |
2276 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} |
2331 explicit SourceMap(const GR& digraph) : _graph(digraph) {} |
2277 |
2332 |
2278 /// \brief The subscript operator. |
2333 /// \brief Returns the source node of the given arc. |
2279 /// |
2334 /// |
2280 /// The subscript operator. |
2335 /// Returns the source node of the given arc. |
2281 /// \param arc The arc |
|
2282 /// \return The source of the arc |
|
2283 Value operator[](const Key& arc) const { |
2336 Value operator[](const Key& arc) const { |
2284 return _digraph.source(arc); |
2337 return _graph.source(arc); |
2285 } |
2338 } |
2286 |
2339 |
2287 private: |
2340 private: |
2288 const Digraph& _digraph; |
2341 const GR& _graph; |
2289 }; |
2342 }; |
2290 |
2343 |
2291 /// \brief Returns a \c SourceMap class. |
2344 /// \brief Returns a \c SourceMap class. |
2292 /// |
2345 /// |
2293 /// This function just returns an \c SourceMap class. |
2346 /// This function just returns an \c SourceMap class. |
2294 /// \relates SourceMap |
2347 /// \relates SourceMap |
2295 template <typename Digraph> |
2348 template <typename GR> |
2296 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) { |
2349 inline SourceMap<GR> sourceMap(const GR& graph) { |
2297 return SourceMap<Digraph>(digraph); |
2350 return SourceMap<GR>(graph); |
2298 } |
2351 } |
2299 |
2352 |
2300 /// \brief Returns the target of the given arc. |
2353 /// \brief Map of the target nodes of arcs in a digraph. |
2301 /// |
2354 /// |
2302 /// The TargetMap gives back the target Node of the given arc. |
2355 /// TargetMap provides access for the target node of each arc in a digraph, |
2356 /// which is returned by the \c target() function of the digraph. |
|
2357 /// \tparam GR The digraph type. |
|
2303 /// \see SourceMap |
2358 /// \see SourceMap |
2304 template <typename Digraph> |
2359 template <typename GR> |
2305 class TargetMap { |
2360 class TargetMap { |
2306 public: |
2361 public: |
2307 |
2362 |
2308 typedef typename Digraph::Node Value; |
2363 ///\e |
2309 typedef typename Digraph::Arc Key; |
2364 typedef typename GR::Arc Key; |
2365 ///\e |
|
2366 typedef typename GR::Node Value; |
|
2310 |
2367 |
2311 /// \brief Constructor |
2368 /// \brief Constructor |
2312 /// |
2369 /// |
2313 /// Constructor |
2370 /// Constructor. |
2314 /// \param digraph The digraph that the map belongs to. |
2371 /// \param digraph The digraph that the map belongs to. |
2315 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} |
2372 explicit TargetMap(const GR& digraph) : _graph(digraph) {} |
2316 |
2373 |
2317 /// \brief The subscript operator. |
2374 /// \brief Returns the target node of the given arc. |
2318 /// |
2375 /// |
2319 /// The subscript operator. |
2376 /// Returns the target node of the given arc. |
2320 /// \param e The arc |
|
2321 /// \return The target of the arc |
|
2322 Value operator[](const Key& e) const { |
2377 Value operator[](const Key& e) const { |
2323 return _digraph.target(e); |
2378 return _graph.target(e); |
2324 } |
2379 } |
2325 |
2380 |
2326 private: |
2381 private: |
2327 const Digraph& _digraph; |
2382 const GR& _graph; |
2328 }; |
2383 }; |
2329 |
2384 |
2330 /// \brief Returns a \c TargetMap class. |
2385 /// \brief Returns a \c TargetMap class. |
2331 /// |
2386 /// |
2332 /// This function just returns a \c TargetMap class. |
2387 /// This function just returns a \c TargetMap class. |
2333 /// \relates TargetMap |
2388 /// \relates TargetMap |
2334 template <typename Digraph> |
2389 template <typename GR> |
2335 inline TargetMap<Digraph> targetMap(const Digraph& digraph) { |
2390 inline TargetMap<GR> targetMap(const GR& graph) { |
2336 return TargetMap<Digraph>(digraph); |
2391 return TargetMap<GR>(graph); |
2337 } |
2392 } |
2338 |
2393 |
2339 /// \brief Returns the "forward" directed arc view of an edge. |
2394 /// \brief Map of the "forward" directed arc view of edges in a graph. |
2340 /// |
2395 /// |
2341 /// Returns the "forward" directed arc view of an edge. |
2396 /// ForwardMap provides access for the "forward" directed arc view of |
2397 /// each edge in a graph, which is returned by the \c direct() function |
|
2398 /// of the graph with \c true parameter. |
|
2399 /// \tparam GR The graph type. |
|
2342 /// \see BackwardMap |
2400 /// \see BackwardMap |
2343 template <typename Graph> |
2401 template <typename GR> |
2344 class ForwardMap { |
2402 class ForwardMap { |
2345 public: |
2403 public: |
2346 |
2404 |
2347 typedef typename Graph::Arc Value; |
2405 typedef typename GR::Arc Value; |
2348 typedef typename Graph::Edge Key; |
2406 typedef typename GR::Edge Key; |
2349 |
2407 |
2350 /// \brief Constructor |
2408 /// \brief Constructor |
2351 /// |
2409 /// |
2352 /// Constructor |
2410 /// Constructor. |
2353 /// \param graph The graph that the map belongs to. |
2411 /// \param graph The graph that the map belongs to. |
2354 explicit ForwardMap(const Graph& graph) : _graph(graph) {} |
2412 explicit ForwardMap(const GR& graph) : _graph(graph) {} |
2355 |
2413 |
2356 /// \brief The subscript operator. |
2414 /// \brief Returns the "forward" directed arc view of the given edge. |
2357 /// |
2415 /// |
2358 /// The subscript operator. |
2416 /// Returns the "forward" directed arc view of the given edge. |
2359 /// \param key An edge |
|
2360 /// \return The "forward" directed arc view of edge |
|
2361 Value operator[](const Key& key) const { |
2417 Value operator[](const Key& key) const { |
2362 return _graph.direct(key, true); |
2418 return _graph.direct(key, true); |
2363 } |
2419 } |
2364 |
2420 |
2365 private: |
2421 private: |
2366 const Graph& _graph; |
2422 const GR& _graph; |
2367 }; |
2423 }; |
2368 |
2424 |
2369 /// \brief Returns a \c ForwardMap class. |
2425 /// \brief Returns a \c ForwardMap class. |
2370 /// |
2426 /// |
2371 /// This function just returns an \c ForwardMap class. |
2427 /// This function just returns an \c ForwardMap class. |
2372 /// \relates ForwardMap |
2428 /// \relates ForwardMap |
2373 template <typename Graph> |
2429 template <typename GR> |
2374 inline ForwardMap<Graph> forwardMap(const Graph& graph) { |
2430 inline ForwardMap<GR> forwardMap(const GR& graph) { |
2375 return ForwardMap<Graph>(graph); |
2431 return ForwardMap<GR>(graph); |
2376 } |
2432 } |
2377 |
2433 |
2378 /// \brief Returns the "backward" directed arc view of an edge. |
2434 /// \brief Map of the "backward" directed arc view of edges in a graph. |
2379 /// |
2435 /// |
2380 /// Returns the "backward" directed arc view of an edge. |
2436 /// BackwardMap provides access for the "backward" directed arc view of |
2437 /// each edge in a graph, which is returned by the \c direct() function |
|
2438 /// of the graph with \c false parameter. |
|
2439 /// \tparam GR The graph type. |
|
2381 /// \see ForwardMap |
2440 /// \see ForwardMap |
2382 template <typename Graph> |
2441 template <typename GR> |
2383 class BackwardMap { |
2442 class BackwardMap { |
2384 public: |
2443 public: |
2385 |
2444 |
2386 typedef typename Graph::Arc Value; |
2445 typedef typename GR::Arc Value; |
2387 typedef typename Graph::Edge Key; |
2446 typedef typename GR::Edge Key; |
2388 |
2447 |
2389 /// \brief Constructor |
2448 /// \brief Constructor |
2390 /// |
2449 /// |
2391 /// Constructor |
2450 /// Constructor. |
2392 /// \param graph The graph that the map belongs to. |
2451 /// \param graph The graph that the map belongs to. |
2393 explicit BackwardMap(const Graph& graph) : _graph(graph) {} |
2452 explicit BackwardMap(const GR& graph) : _graph(graph) {} |
2394 |
2453 |
2395 /// \brief The subscript operator. |
2454 /// \brief Returns the "backward" directed arc view of the given edge. |
2396 /// |
2455 /// |
2397 /// The subscript operator. |
2456 /// Returns the "backward" directed arc view of the given edge. |
2398 /// \param key An edge |
|
2399 /// \return The "backward" directed arc view of edge |
|
2400 Value operator[](const Key& key) const { |
2457 Value operator[](const Key& key) const { |
2401 return _graph.direct(key, false); |
2458 return _graph.direct(key, false); |
2402 } |
2459 } |
2403 |
2460 |
2404 private: |
2461 private: |
2405 const Graph& _graph; |
2462 const GR& _graph; |
2406 }; |
2463 }; |
2407 |
2464 |
2408 /// \brief Returns a \c BackwardMap class |
2465 /// \brief Returns a \c BackwardMap class |
2409 |
2466 |
2410 /// This function just returns a \c BackwardMap class. |
2467 /// This function just returns a \c BackwardMap class. |
2411 /// \relates BackwardMap |
2468 /// \relates BackwardMap |
2412 template <typename Graph> |
2469 template <typename GR> |
2413 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
2470 inline BackwardMap<GR> backwardMap(const GR& graph) { |
2414 return BackwardMap<Graph>(graph); |
2471 return BackwardMap<GR>(graph); |
2415 } |
2472 } |
2416 |
2473 |
2417 /// \brief Potential difference map |
2474 /// \brief Map of the in-degrees of nodes in a digraph. |
2418 /// |
|
2419 /// If there is an potential map on the nodes then we |
|
2420 /// can get an arc map as we get the substraction of the |
|
2421 /// values of the target and source. |
|
2422 template <typename Digraph, typename NodeMap> |
|
2423 class PotentialDifferenceMap { |
|
2424 public: |
|
2425 typedef typename Digraph::Arc Key; |
|
2426 typedef typename NodeMap::Value Value; |
|
2427 |
|
2428 /// \brief Constructor |
|
2429 /// |
|
2430 /// Contructor of the map |
|
2431 explicit PotentialDifferenceMap(const Digraph& digraph, |
|
2432 const NodeMap& potential) |
|
2433 : _digraph(digraph), _potential(potential) {} |
|
2434 |
|
2435 /// \brief Const subscription operator |
|
2436 /// |
|
2437 /// Const subscription operator |
|
2438 Value operator[](const Key& arc) const { |
|
2439 return _potential[_digraph.target(arc)] - |
|
2440 _potential[_digraph.source(arc)]; |
|
2441 } |
|
2442 |
|
2443 private: |
|
2444 const Digraph& _digraph; |
|
2445 const NodeMap& _potential; |
|
2446 }; |
|
2447 |
|
2448 /// \brief Returns a PotentialDifferenceMap. |
|
2449 /// |
|
2450 /// This function just returns a PotentialDifferenceMap. |
|
2451 /// \relates PotentialDifferenceMap |
|
2452 template <typename Digraph, typename NodeMap> |
|
2453 PotentialDifferenceMap<Digraph, NodeMap> |
|
2454 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { |
|
2455 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential); |
|
2456 } |
|
2457 |
|
2458 /// \brief Map of the node in-degrees. |
|
2459 /// |
2475 /// |
2460 /// This map returns the in-degree of a node. Once it is constructed, |
2476 /// This map returns the in-degree of a node. Once it is constructed, |
2461 /// the degrees are stored in a standard NodeMap, so each query is done |
2477 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2462 /// in constant time. On the other hand, the values are updated automatically |
2478 /// in constant time. On the other hand, the values are updated automatically |
2463 /// whenever the digraph changes. |
2479 /// whenever the digraph changes. |
2464 /// |
2480 /// |
2465 /// \warning Besides addNode() and addArc(), a digraph structure may provide |
2481 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2466 /// alternative ways to modify the digraph. The correct behavior of InDegMap |
2482 /// may provide alternative ways to modify the digraph. |
2467 /// is not guarantied if these additional features are used. For example |
2483 /// The correct behavior of InDegMap is not guarantied if these additional |
2468 /// the functions \ref ListDigraph::changeSource() "changeSource()", |
2484 /// features are used. For example the functions |
2485 /// \ref ListDigraph::changeSource() "changeSource()", |
|
2469 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2486 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2470 /// \ref ListDigraph::reverseArc() "reverseArc()" |
2487 /// \ref ListDigraph::reverseArc() "reverseArc()" |
2471 /// of \ref ListDigraph will \e not update the degree values correctly. |
2488 /// of \ref ListDigraph will \e not update the degree values correctly. |
2472 /// |
2489 /// |
2473 /// \sa OutDegMap |
2490 /// \sa OutDegMap |
2474 |
2491 template <typename GR> |
2475 template <typename _Digraph> |
|
2476 class InDegMap |
2492 class InDegMap |
2477 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> |
2493 : protected ItemSetTraits<GR, typename GR::Arc> |
2478 ::ItemNotifier::ObserverBase { |
2494 ::ItemNotifier::ObserverBase { |
2479 |
2495 |
2480 public: |
2496 public: |
2481 |
2497 |
2482 typedef _Digraph Digraph; |
2498 /// The digraph type |
2499 typedef GR Digraph; |
|
2500 /// The key type |
|
2501 typedef typename Digraph::Node Key; |
|
2502 /// The value type |
|
2483 typedef int Value; |
2503 typedef int Value; |
2484 typedef typename Digraph::Node Key; |
|
2485 |
2504 |
2486 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
2505 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
2487 ::ItemNotifier::ObserverBase Parent; |
2506 ::ItemNotifier::ObserverBase Parent; |
2488 |
2507 |
2489 private: |
2508 private: |
2521 |
2540 |
2522 public: |
2541 public: |
2523 |
2542 |
2524 /// \brief Constructor. |
2543 /// \brief Constructor. |
2525 /// |
2544 /// |
2526 /// Constructor for creating in-degree map. |
2545 /// Constructor for creating an in-degree map. |
2527 explicit InDegMap(const Digraph& digraph) |
2546 explicit InDegMap(const Digraph& graph) |
2528 : _digraph(digraph), _deg(digraph) { |
2547 : _digraph(graph), _deg(graph) { |
2529 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
2548 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
2530 |
2549 |
2531 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
2550 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
2532 _deg[it] = countInArcs(_digraph, it); |
2551 _deg[it] = countInArcs(_digraph, it); |
2533 } |
2552 } |
2534 } |
2553 } |
2535 |
2554 |
2555 /// \brief Gives back the in-degree of a Node. |
|
2556 /// |
|
2536 /// Gives back the in-degree of a Node. |
2557 /// Gives back the in-degree of a Node. |
2537 int operator[](const Key& key) const { |
2558 int operator[](const Key& key) const { |
2538 return _deg[key]; |
2559 return _deg[key]; |
2539 } |
2560 } |
2540 |
2561 |
2577 |
2598 |
2578 const Digraph& _digraph; |
2599 const Digraph& _digraph; |
2579 AutoNodeMap _deg; |
2600 AutoNodeMap _deg; |
2580 }; |
2601 }; |
2581 |
2602 |
2582 /// \brief Map of the node out-degrees. |
2603 /// \brief Map of the out-degrees of nodes in a digraph. |
2583 /// |
2604 /// |
2584 /// This map returns the out-degree of a node. Once it is constructed, |
2605 /// This map returns the out-degree of a node. Once it is constructed, |
2585 /// the degrees are stored in a standard NodeMap, so each query is done |
2606 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2586 /// in constant time. On the other hand, the values are updated automatically |
2607 /// in constant time. On the other hand, the values are updated automatically |
2587 /// whenever the digraph changes. |
2608 /// whenever the digraph changes. |
2588 /// |
2609 /// |
2589 /// \warning Besides addNode() and addArc(), a digraph structure may provide |
2610 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2590 /// alternative ways to modify the digraph. The correct behavior of OutDegMap |
2611 /// may provide alternative ways to modify the digraph. |
2591 /// is not guarantied if these additional features are used. For example |
2612 /// The correct behavior of OutDegMap is not guarantied if these additional |
2592 /// the functions \ref ListDigraph::changeSource() "changeSource()", |
2613 /// features are used. For example the functions |
2614 /// \ref ListDigraph::changeSource() "changeSource()", |
|
2593 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2615 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2594 /// \ref ListDigraph::reverseArc() "reverseArc()" |
2616 /// \ref ListDigraph::reverseArc() "reverseArc()" |
2595 /// of \ref ListDigraph will \e not update the degree values correctly. |
2617 /// of \ref ListDigraph will \e not update the degree values correctly. |
2596 /// |
2618 /// |
2597 /// \sa InDegMap |
2619 /// \sa InDegMap |
2598 |
2620 template <typename GR> |
2599 template <typename _Digraph> |
|
2600 class OutDegMap |
2621 class OutDegMap |
2601 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> |
2622 : protected ItemSetTraits<GR, typename GR::Arc> |
2602 ::ItemNotifier::ObserverBase { |
2623 ::ItemNotifier::ObserverBase { |
2603 |
2624 |
2604 public: |
2625 public: |
2605 |
2626 |
2606 typedef _Digraph Digraph; |
2627 /// The digraph type |
2628 typedef GR Digraph; |
|
2629 /// The key type |
|
2630 typedef typename Digraph::Node Key; |
|
2631 /// The value type |
|
2607 typedef int Value; |
2632 typedef int Value; |
2608 typedef typename Digraph::Node Key; |
|
2609 |
2633 |
2610 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
2634 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
2611 ::ItemNotifier::ObserverBase Parent; |
2635 ::ItemNotifier::ObserverBase Parent; |
2612 |
2636 |
2613 private: |
2637 private: |
2643 |
2667 |
2644 public: |
2668 public: |
2645 |
2669 |
2646 /// \brief Constructor. |
2670 /// \brief Constructor. |
2647 /// |
2671 /// |
2648 /// Constructor for creating out-degree map. |
2672 /// Constructor for creating an out-degree map. |
2649 explicit OutDegMap(const Digraph& digraph) |
2673 explicit OutDegMap(const Digraph& graph) |
2650 : _digraph(digraph), _deg(digraph) { |
2674 : _digraph(graph), _deg(graph) { |
2651 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
2675 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
2652 |
2676 |
2653 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
2677 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
2654 _deg[it] = countOutArcs(_digraph, it); |
2678 _deg[it] = countOutArcs(_digraph, it); |
2655 } |
2679 } |
2656 } |
2680 } |
2657 |
2681 |
2682 /// \brief Gives back the out-degree of a Node. |
|
2683 /// |
|
2658 /// Gives back the out-degree of a Node. |
2684 /// Gives back the out-degree of a Node. |
2659 int operator[](const Key& key) const { |
2685 int operator[](const Key& key) const { |
2660 return _deg[key]; |
2686 return _deg[key]; |
2661 } |
2687 } |
2662 |
2688 |
2699 |
2725 |
2700 const Digraph& _digraph; |
2726 const Digraph& _digraph; |
2701 AutoNodeMap _deg; |
2727 AutoNodeMap _deg; |
2702 }; |
2728 }; |
2703 |
2729 |
2730 /// \brief Potential difference map |
|
2731 /// |
|
2732 /// PotentialMap returns the difference between the potentials of the |
|
2733 /// source and target nodes of each arc in a digraph, i.e. it returns |
|
2734 /// \code |
|
2735 /// potential[gr.target(arc)] - potential[gr.source(arc)]. |
|
2736 /// \endcode |
|
2737 /// \tparam GR The digraph type. |
|
2738 /// \tparam POT A node map storing the potentials. |
|
2739 template <typename GR, typename POT> |
|
2740 class PotentialDifferenceMap { |
|
2741 public: |
|
2742 /// Key type |
|
2743 typedef typename GR::Arc Key; |
|
2744 /// Value type |
|
2745 typedef typename POT::Value Value; |
|
2746 |
|
2747 /// \brief Constructor |
|
2748 /// |
|
2749 /// Contructor of the map. |
|
2750 explicit PotentialDifferenceMap(const GR& gr, |
|
2751 const POT& potential) |
|
2752 : _digraph(gr), _potential(potential) {} |
|
2753 |
|
2754 /// \brief Returns the potential difference for the given arc. |
|
2755 /// |
|
2756 /// Returns the potential difference for the given arc, i.e. |
|
2757 /// \code |
|
2758 /// potential[gr.target(arc)] - potential[gr.source(arc)]. |
|
2759 /// \endcode |
|
2760 Value operator[](const Key& arc) const { |
|
2761 return _potential[_digraph.target(arc)] - |
|
2762 _potential[_digraph.source(arc)]; |
|
2763 } |
|
2764 |
|
2765 private: |
|
2766 const GR& _digraph; |
|
2767 const POT& _potential; |
|
2768 }; |
|
2769 |
|
2770 /// \brief Returns a PotentialDifferenceMap. |
|
2771 /// |
|
2772 /// This function just returns a PotentialDifferenceMap. |
|
2773 /// \relates PotentialDifferenceMap |
|
2774 template <typename GR, typename POT> |
|
2775 PotentialDifferenceMap<GR, POT> |
|
2776 potentialDifferenceMap(const GR& gr, const POT& potential) { |
|
2777 return PotentialDifferenceMap<GR, POT>(gr, potential); |
|
2778 } |
|
2779 |
|
2704 /// @} |
2780 /// @} |
2705 } |
2781 } |
2706 |
2782 |
2707 #endif // LEMON_MAPS_H |
2783 #endif // LEMON_MAPS_H |