43 template <typename _Graph, typename _Item> |
47 template <typename _Graph, typename _Item> |
44 class IterableBoolMap |
48 class IterableBoolMap |
45 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent { |
49 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent { |
46 private: |
50 private: |
47 typedef _Graph Graph; |
51 typedef _Graph Graph; |
48 typedef _Item Item; |
52 |
49 |
53 typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt; |
50 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
54 typedef typename ItemSetTraits<Graph, _Item> |
51 typedef typename ItemSetTraits<Graph, Item> |
|
52 ::template Map<int>::Parent Parent; |
55 ::template Map<int>::Parent Parent; |
53 |
56 |
54 std::vector<Item> array; |
57 std::vector<_Item> array; |
55 int sep; |
58 int sep; |
56 |
59 |
57 const Graph& graph; |
60 const Graph& graph; |
58 |
|
59 private: |
|
60 |
|
61 int position(const Item& item) const { |
|
62 return Parent::operator[](item); |
|
63 } |
|
64 |
61 |
65 public: |
62 public: |
66 |
63 |
67 /// Indicates that the map if reference map. |
64 /// Indicates that the map if reference map. |
68 typedef True ReferenceMapTag; |
65 typedef True ReferenceMapTag; |
69 |
66 |
70 /// The key type |
67 /// The key type |
71 typedef Item Key; |
68 typedef _Item Key; |
72 /// The value type |
69 /// The value type |
73 typedef bool Value; |
70 typedef bool Value; |
74 /// The const reference type. |
71 /// The const reference type. |
75 typedef const Value& ConstReference; |
72 typedef const Value& ConstReference; |
76 |
73 |
|
74 private: |
|
75 |
|
76 int position(const Key& key) const { |
|
77 return Parent::operator[](key); |
|
78 } |
|
79 |
|
80 public: |
77 |
81 |
78 /// \brief Refernce to the value of the map. |
82 /// \brief Refernce to the value of the map. |
79 /// |
83 /// |
80 /// This class is near to similar to the bool type. It can |
84 /// This class is near to similar to the bool type. It can |
81 /// be converted to bool and it has the same operators. |
85 /// be converted to bool and it has the same operators. |
119 /// \brief Constructor of the Map with a default value. |
123 /// \brief Constructor of the Map with a default value. |
120 /// |
124 /// |
121 /// Constructor of the Map with a default value. |
125 /// Constructor of the Map with a default value. |
122 IterableBoolMap(const Graph& _graph, bool def = false) |
126 IterableBoolMap(const Graph& _graph, bool def = false) |
123 : Parent(_graph), graph(_graph) { |
127 : Parent(_graph), graph(_graph) { |
124 for (ItemIt it(graph); it != INVALID; ++it) { |
128 for (KeyIt it(graph); it != INVALID; ++it) { |
125 Parent::set(it, array.size()); |
129 Parent::set(it, array.size()); |
126 array.push_back(it); |
130 array.push_back(it); |
127 } |
131 } |
128 sep = (def ? array.size() : 0); |
132 sep = (def ? array.size() : 0); |
129 } |
133 } |
130 |
134 |
131 /// \brief Const subscript operator of the map. |
135 /// \brief Const subscript operator of the map. |
132 /// |
136 /// |
133 /// Const subscript operator of the map. |
137 /// Const subscript operator of the map. |
134 bool operator[](const Item& item) const { |
138 bool operator[](const Key& key) const { |
135 return position(item) < sep; |
139 return position(key) < sep; |
136 } |
140 } |
137 |
141 |
138 /// \brief Subscript operator of the map. |
142 /// \brief Subscript operator of the map. |
139 /// |
143 /// |
140 /// Subscript operator of the map. |
144 /// Subscript operator of the map. |
141 Reference operator[](const Item& item) { |
145 Reference operator[](const Key& key) { |
142 return Reference(*this, item); |
146 return Reference(*this, key); |
143 } |
147 } |
144 |
148 |
145 /// \brief Set operation of the map. |
149 /// \brief Set operation of the map. |
146 /// |
150 /// |
147 /// Set operation of the map. |
151 /// Set operation of the map. |
148 void set(const Item& item, bool value) { |
152 void set(const Key& key, bool value) { |
149 int pos = position(item); |
153 int pos = position(key); |
150 if (value) { |
154 if (value) { |
151 if (pos < sep) return; |
155 if (pos < sep) return; |
152 Item tmp = array[sep]; |
156 Key tmp = array[sep]; |
153 array[sep] = item; |
157 array[sep] = key; |
154 Parent::set(item, sep); |
158 Parent::set(key, sep); |
155 array[pos] = tmp; |
159 array[pos] = tmp; |
156 Parent::set(tmp, pos); |
160 Parent::set(tmp, pos); |
157 ++sep; |
161 ++sep; |
158 } else { |
162 } else { |
159 if (pos >= sep) return; |
163 if (pos >= sep) return; |
160 --sep; |
164 --sep; |
161 Item tmp = array[sep]; |
165 Key tmp = array[sep]; |
162 array[sep] = item; |
166 array[sep] = key; |
163 Parent::set(item, sep); |
167 Parent::set(key, sep); |
164 array[pos] = tmp; |
168 array[pos] = tmp; |
165 Parent::set(tmp, pos); |
169 Parent::set(tmp, pos); |
166 } |
170 } |
167 } |
171 } |
168 |
172 |
169 /// \brief Returns the number of the items mapped to true. |
173 /// \brief Returns the number of the keys mapped to true. |
170 /// |
174 /// |
171 /// Returns the number of the items mapped to true. |
175 /// Returns the number of the keys mapped to true. |
172 int trueNum() const { |
176 int trueNum() const { |
173 return sep; |
177 return sep; |
174 } |
178 } |
175 |
179 |
176 /// \brief Returns the number of the items mapped to false. |
180 /// \brief Returns the number of the keys mapped to false. |
177 /// |
181 /// |
178 /// Returns the number of the items mapped to false. |
182 /// Returns the number of the keys mapped to false. |
179 int falseNum() const { |
183 int falseNum() const { |
180 return array.size() - sep; |
184 return array.size() - sep; |
181 } |
185 } |
182 |
186 |
183 /// \brief Iterator for the keys mapped to true. |
187 /// \brief Iterator for the keys mapped to true. |
184 /// |
188 /// |
185 /// Iterator for the keys mapped to true. It works |
189 /// Iterator for the keys mapped to true. It works |
186 /// like a graph item iterator in the map, it can be converted |
190 /// like a graph item iterator in the map, it can be converted |
187 /// the item type of the map, incremented with \c ++ operator, and |
191 /// the key type of the map, incremented with \c ++ operator, and |
188 /// if the iterator leave the last valid item it will be equal to |
192 /// if the iterator leave the last valid key it will be equal to |
189 /// \c INVALID. |
193 /// \c INVALID. |
190 class TrueIt : public Item { |
194 class TrueIt : public Key { |
191 public: |
195 public: |
192 typedef Item Parent; |
196 typedef Key Parent; |
193 |
197 |
194 /// \brief Creates an iterator. |
198 /// \brief Creates an iterator. |
195 /// |
199 /// |
196 /// Creates an iterator. It iterates on the |
200 /// Creates an iterator. It iterates on the |
197 /// keys which mapped to true. |
201 /// keys which mapped to true. |
222 |
226 |
223 /// \brief Iterator for the keys mapped to false. |
227 /// \brief Iterator for the keys mapped to false. |
224 /// |
228 /// |
225 /// Iterator for the keys mapped to false. It works |
229 /// Iterator for the keys mapped to false. It works |
226 /// like a graph item iterator in the map, it can be converted |
230 /// like a graph item iterator in the map, it can be converted |
227 /// the item type of the map, incremented with \c ++ operator, and |
231 /// the key type of the map, incremented with \c ++ operator, and |
228 /// if the iterator leave the last valid item it will be equal to |
232 /// if the iterator leave the last valid key it will be equal to |
229 /// \c INVALID. |
233 /// \c INVALID. |
230 class FalseIt : public Item { |
234 class FalseIt : public Key { |
231 public: |
235 public: |
232 typedef Item Parent; |
236 typedef Key Parent; |
233 |
237 |
234 /// \brief Creates an iterator. |
238 /// \brief Creates an iterator. |
235 /// |
239 /// |
236 /// Creates an iterator. It iterates on the |
240 /// Creates an iterator. It iterates on the |
237 /// keys which mapped to false. |
241 /// keys which mapped to false. |
238 /// \param map The IterableIntMap |
242 /// \param map The IterableIntMap |
239 FalseIt(const IterableBoolMap& _map) |
243 FalseIt(const IterableBoolMap& _map) |
240 : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID), |
244 : Parent(_map.sep < (int)_map.array.size() ? |
241 map(&_map) {} |
245 _map.array.back() : INVALID), map(&_map) {} |
242 |
246 |
243 /// \brief Invalid constructor \& conversion. |
247 /// \brief Invalid constructor \& conversion. |
244 /// |
248 /// |
245 /// This constructor initializes the item to be invalid. |
249 /// This constructor initializes the key to be invalid. |
246 /// \sa Invalid for more details. |
250 /// \sa Invalid for more details. |
247 FalseIt(Invalid) : Parent(INVALID), map(0) {} |
251 FalseIt(Invalid) : Parent(INVALID), map(0) {} |
248 |
252 |
249 /// \brief Increment operator. |
253 /// \brief Increment operator. |
250 /// |
254 /// |
257 |
261 |
258 private: |
262 private: |
259 const IterableBoolMap* map; |
263 const IterableBoolMap* map; |
260 }; |
264 }; |
261 |
265 |
|
266 /// \brief Iterator for the keys mapped to a given value. |
|
267 /// |
|
268 /// Iterator for the keys mapped to a given value. It works |
|
269 /// like a graph item iterator in the map, it can be converted |
|
270 /// the key type of the map, incremented with \c ++ operator, and |
|
271 /// if the iterator leave the last valid key it will be equal to |
|
272 /// \c INVALID. |
|
273 class ItemIt : public Key { |
|
274 public: |
|
275 typedef Key Parent; |
|
276 |
|
277 /// \brief Creates an iterator. |
|
278 /// |
|
279 /// Creates an iterator. It iterates on the |
|
280 /// keys which mapped to false. |
|
281 /// \param map The IterableIntMap |
|
282 /// \param value Which elements should be iterated. |
|
283 ItemIt(const IterableBoolMap& _map, bool value) |
|
284 : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) : |
|
285 (_map.sep < (int)_map.array.size() ? |
|
286 _map.array.back() : INVALID)), map(&_map) {} |
|
287 |
|
288 /// \brief Invalid constructor \& conversion. |
|
289 /// |
|
290 /// This constructor initializes the key to be invalid. |
|
291 /// \sa Invalid for more details. |
|
292 ItemIt(Invalid) : Parent(INVALID), map(0) {} |
|
293 |
|
294 /// \brief Increment operator. |
|
295 /// |
|
296 /// Increment Operator. |
|
297 ItemIt& operator++() { |
|
298 int pos = map->position(*this); |
|
299 int sep = pos >= map->sep ? map->sep : 0; |
|
300 Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID); |
|
301 return *this; |
|
302 } |
|
303 |
|
304 private: |
|
305 const IterableBoolMap* map; |
|
306 }; |
|
307 |
262 protected: |
308 protected: |
263 |
309 |
264 virtual void add(const Item& item) { |
310 virtual void add(const Key& key) { |
265 Parent::add(item); |
311 Parent::add(key); |
266 Parent::set(item, array.size()); |
312 Parent::set(key, array.size()); |
267 array.push_back(item); |
313 array.push_back(key); |
268 } |
314 } |
269 |
315 |
270 virtual void add(const std::vector<Item>& items) { |
316 virtual void add(const std::vector<Key>& keys) { |
271 Parent::add(items); |
317 Parent::add(keys); |
272 for (int i = 0; i < (int)items.size(); ++i) { |
318 for (int i = 0; i < (int)keys.size(); ++i) { |
273 Parent::set(items[i], array.size()); |
319 Parent::set(keys[i], array.size()); |
274 array.push_back(items[i]); |
320 array.push_back(keys[i]); |
275 } |
321 } |
276 } |
322 } |
277 |
323 |
278 virtual void erase(const Item& item) { |
324 virtual void erase(const Key& key) { |
279 int pos = position(item); |
325 int pos = position(key); |
280 if (pos < sep) { |
326 if (pos < sep) { |
281 --sep; |
327 --sep; |
282 Parent::set(array[sep], pos); |
328 Parent::set(array[sep], pos); |
283 array[pos] = array[sep]; |
329 array[pos] = array[sep]; |
284 Parent::set(array.back(), sep); |
330 Parent::set(array.back(), sep); |
607 |
653 |
608 private: |
654 private: |
609 std::vector<_Item> first; |
655 std::vector<_Item> first; |
610 }; |
656 }; |
611 |
657 |
|
658 namespace _iterable_maps_bits { |
|
659 template <typename Item, typename Value> |
|
660 struct IterableValueMapNode { |
|
661 IterableValueMapNode(Value _value = Value()) : value(_value) {} |
|
662 Item prev, next; |
|
663 Value value; |
|
664 }; |
|
665 } |
|
666 |
|
667 ///\ingroup graph_maps |
|
668 /// |
|
669 /// \brief Dynamic iterable map for comparable values. |
|
670 /// |
|
671 /// This class provides a special graph map type which can store |
|
672 /// for each graph item(node, edge, etc.) a value. For each |
|
673 /// value it is possible to iterate on the keys which mapped to the |
|
674 /// given value. The type stores for each value a linked list with |
|
675 /// the items which mapped to the value, and the values are stored |
|
676 /// in balanced binary tree. The values of the map can be accessed |
|
677 /// with stl compatible forward iterator. |
|
678 /// |
|
679 /// This type is not reference map so it cannot be modified with |
|
680 /// the subscription operator. |
|
681 /// |
|
682 /// \see InvertableMap |
|
683 /// |
|
684 /// \param _Graph The graph type. |
|
685 /// \param _Item One of the graph's item type, the key of the map. |
|
686 /// \param _Value Any comparable value type. |
|
687 template <typename _Graph, typename _Item, typename _Value> |
|
688 class IterableValueMap : protected ItemSetTraits<_Graph, _Item> |
|
689 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> > |
|
690 ::Parent { |
|
691 public: |
|
692 typedef typename ItemSetTraits<_Graph, _Item> |
|
693 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> > |
|
694 ::Parent Parent; |
|
695 |
|
696 /// The key type |
|
697 typedef _Item Key; |
|
698 /// The value type |
|
699 typedef _Value Value; |
|
700 /// The graph type |
|
701 typedef _Graph Graph; |
|
702 |
|
703 /// \brief Constructor of the Map with a given value. |
|
704 /// |
|
705 /// Constructor of the Map with a given value. |
|
706 explicit IterableValueMap(const Graph& graph, |
|
707 const Value& value = Value()) |
|
708 : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item, |
|
709 _Value>(value)) { |
|
710 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { |
|
711 lace(it); |
|
712 } |
|
713 } |
|
714 |
|
715 private: |
|
716 |
|
717 void unlace(const Key& key) { |
|
718 typename Parent::Value& node = Parent::operator[](key); |
|
719 if (node.prev != INVALID) { |
|
720 Parent::operator[](node.prev).next = node.next; |
|
721 } else { |
|
722 if (node.next != INVALID) { |
|
723 first[node.value] = node.next; |
|
724 } else { |
|
725 first.erase(node.value); |
|
726 } |
|
727 } |
|
728 if (node.next != INVALID) { |
|
729 Parent::operator[](node.next).prev = node.prev; |
|
730 } |
|
731 } |
|
732 |
|
733 void lace(const Key& key) { |
|
734 typename Parent::Value& node = Parent::operator[](key); |
|
735 typename std::map<Value, Key>::iterator it = first.find(node.value); |
|
736 if (it == first.end()) { |
|
737 node.prev = node.next = INVALID; |
|
738 if (node.next != INVALID) { |
|
739 Parent::operator[](node.next).prev = key; |
|
740 } |
|
741 first.insert(make_pair(node.value, key)); |
|
742 } else { |
|
743 node.prev = INVALID; |
|
744 node.next = it->second; |
|
745 if (node.next != INVALID) { |
|
746 Parent::operator[](node.next).prev = key; |
|
747 } |
|
748 it->second = key; |
|
749 } |
|
750 } |
|
751 |
|
752 public: |
|
753 |
|
754 /// \brief Forward iterator for values. |
|
755 /// |
|
756 /// This iterator is an stl compatible forward |
|
757 /// iterator on the values of the map. The values can |
|
758 /// be accessed in the [beginValue, endValue) range. |
|
759 /// |
|
760 class ValueIterator |
|
761 : public std::iterator<std::forward_iterator_tag, Value> { |
|
762 friend class IterableValueMap; |
|
763 private: |
|
764 ValueIterator(typename std::map<Value, Key>::const_iterator _it) |
|
765 : it(_it) {} |
|
766 public: |
|
767 |
|
768 ValueIterator() {} |
|
769 |
|
770 ValueIterator& operator++() { ++it; return *this; } |
|
771 ValueIterator operator++(int) { |
|
772 ValueIterator tmp(*this); |
|
773 operator++(); |
|
774 return tmp; |
|
775 } |
|
776 |
|
777 const Value& operator*() const { return it->first; } |
|
778 const Value* operator->() const { return &(it->first); } |
|
779 |
|
780 bool operator==(ValueIterator jt) const { return it == jt.it; } |
|
781 bool operator!=(ValueIterator jt) const { return it != jt.it; } |
|
782 |
|
783 private: |
|
784 typename std::map<Value, Key>::const_iterator it; |
|
785 }; |
|
786 |
|
787 /// \brief Returns an iterator to the first value. |
|
788 /// |
|
789 /// Returns an stl compatible iterator to the |
|
790 /// first value of the map. The values of the |
|
791 /// map can be accessed in the [beginValue, endValue) |
|
792 /// range. |
|
793 ValueIterator beginValue() const { |
|
794 return ValueIterator(first.begin()); |
|
795 } |
|
796 |
|
797 /// \brief Returns an iterator after the last value. |
|
798 /// |
|
799 /// Returns an stl compatible iterator after the |
|
800 /// last value of the map. The values of the |
|
801 /// map can be accessed in the [beginValue, endValue) |
|
802 /// range. |
|
803 ValueIterator endValue() const { |
|
804 return ValueIterator(first.end()); |
|
805 } |
|
806 |
|
807 /// \brief Set operation of the map. |
|
808 /// |
|
809 /// Set operation of the map. |
|
810 void set(const Key& key, const Value& value) { |
|
811 unlace(key); |
|
812 Parent::operator[](key).value = value; |
|
813 lace(key); |
|
814 } |
|
815 |
|
816 /// \brief Const subscript operator of the map. |
|
817 /// |
|
818 /// Const subscript operator of the map. |
|
819 const Value& operator[](const Key& key) const { |
|
820 return Parent::operator[](key).value; |
|
821 } |
|
822 |
|
823 /// \brief Iterator for the keys with the same value. |
|
824 /// |
|
825 /// Iterator for the keys with the same value. It works |
|
826 /// like a graph item iterator in the map, it can be converted |
|
827 /// the item type of the map, incremented with \c ++ operator, and |
|
828 /// if the iterator leave the last valid item it will be equal to |
|
829 /// \c INVALID. |
|
830 class ItemIt : public _Item { |
|
831 public: |
|
832 typedef _Item Parent; |
|
833 |
|
834 /// \brief Invalid constructor \& conversion. |
|
835 /// |
|
836 /// This constructor initializes the item to be invalid. |
|
837 /// \sa Invalid for more details. |
|
838 ItemIt(Invalid) : Parent(INVALID), _map(0) {} |
|
839 |
|
840 /// \brief Creates an iterator with a value. |
|
841 /// |
|
842 /// Creates an iterator with a value. It iterates on the |
|
843 /// keys which have the given value. |
|
844 /// \param map The IterableValueMap |
|
845 /// \param value The value |
|
846 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { |
|
847 typename std::map<Value, Key>::const_iterator it = |
|
848 map.first.find(value); |
|
849 if (it == map.first.end()) { |
|
850 Parent::operator=(INVALID); |
|
851 } else { |
|
852 Parent::operator=(it->second); |
|
853 } |
|
854 } |
|
855 |
|
856 /// \brief Increment operator. |
|
857 /// |
|
858 /// Increment Operator. |
|
859 ItemIt& operator++() { |
|
860 Parent::operator=(_map->IterableValueMap::Parent:: |
|
861 operator[](static_cast<Parent&>(*this)).next); |
|
862 return *this; |
|
863 } |
|
864 |
|
865 |
|
866 private: |
|
867 const IterableValueMap* _map; |
|
868 }; |
|
869 |
|
870 protected: |
|
871 |
|
872 virtual void erase(const Key& key) { |
|
873 unlace(key); |
|
874 Parent::erase(key); |
|
875 } |
|
876 |
|
877 virtual void erase(const std::vector<Key>& keys) { |
|
878 for (int i = 0; i < (int)keys.size(); ++i) { |
|
879 unlace(keys[i]); |
|
880 } |
|
881 Parent::erase(keys); |
|
882 } |
|
883 |
|
884 virtual void clear() { |
|
885 first.clear(); |
|
886 Parent::clear(); |
|
887 } |
|
888 |
|
889 private: |
|
890 std::map<Value, Key> first; |
|
891 }; |
|
892 |
612 /// @} |
893 /// @} |
613 } |
894 } |