I only corrected bugs to make things compile: some featured not implemented here yet.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_DEBUG_MAP_H
20 #define LEMON_BITS_DEBUG_MAP_H
25 #include <lemon/bits/traits.h>
26 #include <lemon/bits/utility.h>
27 #include <lemon/error.h>
29 #include <lemon/bits/alteration_notifier.h>
31 #include <lemon/concept_check.h>
32 #include <lemon/concepts/maps.h>
37 ///\brief Vector based graph maps for debugging.
40 #ifndef LEMON_STRICT_DEBUG_MAP
41 #define LEMON_STRICT_DEBUG_MAP false
44 /// \ingroup graphbits
46 /// \brief Graph map based on the std::vector storage.
48 /// The DebugMap template class is graph map structure what
49 /// automatically updates the map when a key is added to or erased from
50 /// the map. This map also checks some programming failures by example
51 /// multiple addition of items, erasing of not existing item or
52 /// not erased items at the destruction of the map. It helps the
53 /// programmer to avoid segmentation faults and memory leaks.
55 /// \param Notifier The AlterationNotifier that will notify this map.
56 /// \param Item The item type of the graph items.
57 /// \param Value The value type of the map.
59 /// \author Balazs Dezso
60 template <typename _Graph, typename _Item, typename _Value>
62 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
65 /// The container type of the map.
66 typedef std::vector<_Value> Container;
68 /// The container type of the debug flags.
69 typedef std::vector<bool> Flag;
73 static const bool strictCheck = LEMON_STRICT_DEBUG_MAP;
77 virtual ~MapError() {}
78 virtual const char* what() const throw() {
79 return "lemon::DebugMap::MapError";
83 /// The graph type of the map.
85 /// The item type of the map.
87 /// The reference map tag.
88 typedef True ReferenceMapTag;
90 /// The key type of the map.
92 /// The value type of the map.
95 /// The notifier type.
96 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
100 /// The base class of the map.
101 typedef typename Notifier::ObserverBase Parent;
103 /// The reference type of the map;
104 typedef typename Container::reference Reference;
105 /// The const reference type of the map;
106 typedef typename Container::const_reference ConstReference;
109 /// \brief Constructor to attach the new map into the notifier.
111 /// It constructs a map and attachs it into the notifier.
112 /// It adds all the items of the graph to the map.
113 DebugMap(const Graph& graph) {
114 Parent::attach(graph.notifier(Item()));
115 container.resize(Parent::notifier()->maxId() + 1);
116 flag.resize(Parent::notifier()->maxId() + 1, false);
117 const typename Parent::Notifier* notifier = Parent::notifier();
119 for (notifier->first(it); it != INVALID; notifier->next(it)) {
120 flag[Parent::notifier()->id(it)] = true;
124 /// \brief Constructor uses given value to initialize the map.
126 /// It constructs a map uses a given value to initialize the map.
127 /// It adds all the items of the graph to the map.
128 DebugMap(const Graph& graph, const Value& value) {
129 Parent::attach(graph.notifier(Item()));
130 container.resize(Parent::notifier()->maxId() + 1, value);
131 flag.resize(Parent::notifier()->maxId() + 1, false);
132 const typename Parent::Notifier* notifier = Parent::notifier();
134 for (notifier->first(it); it != INVALID; notifier->next(it)) {
135 flag[Parent::notifier()->id(it)] = true;
139 /// \brief Copy constructor
141 /// Copy constructor.
142 DebugMap(const DebugMap& _copy) : Parent() {
143 if (_copy.attached()) {
144 Parent::attach(*_copy.notifier());
145 container = _copy.container;
147 flag.resize(Parent::notifier()->maxId() + 1, false);
148 const typename Parent::Notifier* notifier = Parent::notifier();
150 for (notifier->first(it); it != INVALID; notifier->next(it)) {
151 flag[Parent::notifier()->id(it)] = true;
152 LEMON_ASSERT(_copy.flag[Parent::notifier()->id(it)], MapError());
156 /// \brief Destructor
160 const typename Parent::Notifier* notifier = Parent::notifier();
163 for (notifier->first(it); it != INVALID; notifier->next(it)) {
164 LEMON_ASSERT(flag[Parent::notifier()->id(it)], MapError());
165 flag[Parent::notifier()->id(it)] = false;
168 for (int i = 0; i < int(flag.size()); ++i) {
169 LEMON_ASSERT(!flag[i], MapError());
173 /// \brief Assign operator.
175 /// This operator assigns for each item in the map the
176 /// value mapped to the same item in the copied map.
177 /// The parameter map should be indiced with the same
178 /// itemset because this assign operator does not change
179 /// the container of the map.
180 DebugMap& operator=(const DebugMap& cmap) {
181 return operator=<DebugMap>(cmap);
185 /// \brief Template assign operator.
187 /// The given parameter should be conform to the ReadMap
188 /// concecpt and could be indiced by the current item set of
189 /// the NodeMap. In this case the value for each item
190 /// is assigned by the value of the given ReadMap.
191 template <typename CMap>
192 DebugMap& operator=(const CMap& cmap) {
193 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
194 const typename Parent::Notifier* notifier = Parent::notifier();
196 for (notifier->first(it); it != INVALID; notifier->next(it)) {
204 /// \brief The subcript operator.
206 /// The subscript operator. The map can be subscripted by the
207 /// actual items of the graph.
208 Reference operator[](const Key& key) {
209 LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError());
210 return container[Parent::notifier()->id(key)];
213 /// \brief The const subcript operator.
215 /// The const subscript operator. The map can be subscripted by the
216 /// actual items of the graph.
217 ConstReference operator[](const Key& key) const {
218 LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError());
219 return container[Parent::notifier()->id(key)];
223 /// \brief The setter function of the map.
225 /// It the same as operator[](key) = value expression.
226 void set(const Key& key, const Value& value) {
227 (*this)[key] = value;
232 /// \brief Adds a new key to the map.
234 /// It adds a new key to the map. It called by the observer notifier
235 /// and it overrides the add() member function of the observer base.
236 virtual void add(const Key& key) {
237 int id = Parent::notifier()->id(key);
238 if (id >= int(container.size())) {
239 container.resize(id + 1);
240 flag.resize(id + 1, false);
242 LEMON_ASSERT(!flag[Parent::notifier()->id(key)], MapError());
243 flag[Parent::notifier()->id(key)] = true;
245 std::vector<bool> fl(flag.size(), false);
246 const typename Parent::Notifier* notifier = Parent::notifier();
248 for (notifier->first(it); it != INVALID; notifier->next(it)) {
249 int jd = Parent::notifier()->id(it);
252 LEMON_ASSERT(fl == flag, MapError());
256 /// \brief Adds more new keys to the map.
258 /// It adds more new keys to the map. It called by the observer notifier
259 /// and it overrides the add() member function of the observer base.
260 virtual void add(const std::vector<Key>& keys) {
261 int max = container.size() - 1;
262 for (int i = 0; i < int(keys.size()); ++i) {
263 int id = Parent::notifier()->id(keys[i]);
268 container.resize(max + 1);
269 flag.resize(max + 1, false);
270 for (int i = 0; i < int(keys.size()); ++i) {
271 LEMON_ASSERT(!flag[Parent::notifier()->id(keys[i])], MapError());
272 flag[Parent::notifier()->id(keys[i])] = true;
275 std::vector<bool> fl(flag.size(), false);
276 const typename Parent::Notifier* notifier = Parent::notifier();
278 for (notifier->first(it); it != INVALID; notifier->next(it)) {
279 int id = Parent::notifier()->id(it);
282 LEMON_ASSERT(fl == flag, MapError());
286 /// \brief Erase a key from the map.
288 /// Erase a key from the map. It called by the observer notifier
289 /// and it overrides the erase() member function of the observer base.
290 virtual void erase(const Key& key) {
292 std::vector<bool> fl(flag.size(), false);
293 const typename Parent::Notifier* notifier = Parent::notifier();
295 for (notifier->first(it); it != INVALID; notifier->next(it)) {
296 int id = Parent::notifier()->id(it);
299 LEMON_ASSERT(fl == flag, MapError());
301 container[Parent::notifier()->id(key)] = Value();
302 LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError());
303 flag[Parent::notifier()->id(key)] = false;
306 /// \brief Erase more keys from the map.
308 /// Erase more keys from the map. It called by the observer notifier
309 /// and it overrides the erase() member function of the observer base.
310 virtual void erase(const std::vector<Key>& keys) {
312 std::vector<bool> fl(flag.size(), false);
313 const typename Parent::Notifier* notifier = Parent::notifier();
315 for (notifier->first(it); it != INVALID; notifier->next(it)) {
316 int id = Parent::notifier()->id(it);
319 LEMON_ASSERT(fl == flag, MapError());
321 for (int i = 0; i < int(keys.size()); ++i) {
322 container[Parent::notifier()->id(keys[i])] = Value();
323 LEMON_ASSERT(flag[Parent::notifier()->id(keys[i])], MapError());
324 flag[Parent::notifier()->id(keys[i])] = false;
328 /// \brief Buildes the map.
330 /// It buildes the map. It called by the observer notifier
331 /// and it overrides the build() member function of the observer base.
332 virtual void build() {
334 for (int i = 0; i < int(flag.size()); ++i) {
335 LEMON_ASSERT(flag[i], MapError());
338 int size = Parent::notifier()->maxId() + 1;
339 container.reserve(size);
340 container.resize(size);
342 flag.resize(size, false);
343 const typename Parent::Notifier* notifier = Parent::notifier();
345 for (notifier->first(it); it != INVALID; notifier->next(it)) {
346 int id = Parent::notifier()->id(it);
347 LEMON_ASSERT(!flag[id], MapError());
352 /// \brief Clear the map.
354 /// It erase all items from the map. It called by the observer notifier
355 /// and it overrides the clear() member function of the observer base.
356 virtual void clear() {
357 const typename Parent::Notifier* notifier = Parent::notifier();
359 for (notifier->first(it); it != INVALID; notifier->next(it)) {
360 int id = Parent::notifier()->id(it);
361 LEMON_ASSERT(flag[id], MapError());
365 for (int i = 0; i < int(flag.size()); ++i) {
366 LEMON_ASSERT(!flag[i], MapError());