COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/debug_map.h @ 2254:50cb2b90daa9

Last change on this file since 2254:50cb2b90daa9 was 2202:09cbc87cb4ab, checked in by Balazs Dezso, 18 years ago

New map type based on array map for debugging purpose

It checks multiple allocation and deallocation of map values and
some consistency.

todo:
clarification of debugging concepts
assertions - exceptions - debug
revision of attic/debug.h

motto:
testing is at least so important as coding

File size: 12.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_DEBUG_MAP_H
20#define LEMON_BITS_DEBUG_MAP_H
21
22#include <vector>
23#include <algorithm>
24
25#include <lemon/bits/traits.h>
26#include <lemon/bits/utility.h>
27#include <lemon/error.h>
28
29#include <lemon/bits/alteration_notifier.h>
30
31#include <lemon/concept_check.h>
32#include <lemon/concept/maps.h>
33
34///\ingroup graphbits
35///
36///\file
37///\brief Vector based graph maps for debugging.
38namespace lemon {
39
40  /// \ingroup graphbits
41  ///
42  /// \brief Graph map based on the std::vector storage.
43  ///
44  /// The DebugMap template class is graph map structure what
45  /// automatically updates the map when a key is added to or erased from
46  /// the map. This map also checks some programming failures by example
47  /// multiple addition of items, erasing of not existing item or
48  /// not erased items at the destruction of the map. It helps the
49  /// programmer to avoid segmentation faults and memory leaks.
50  ///
51  /// \param Notifier The AlterationNotifier that will notify this map.
52  /// \param Item The item type of the graph items.
53  /// \param Value The value type of the map.
54  ///
55  /// \author Balazs Dezso     
56  template <typename _Graph, typename _Item, typename _Value>
57  class DebugMap
58    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
59  private:
60               
61    /// The container type of the map.
62    typedef std::vector<_Value> Container;     
63
64    /// The container type of the debug flags.
65    typedef std::vector<bool> Flag;     
66
67  public:
68
69    static const bool strictCheck = true;
70
71    struct MapError {
72    public:
73      virtual ~MapError() {}
74      virtual const char* what() const throw() {
75        return "lemon::DebugMap::MapError";
76      }
77    };
78
79    /// The graph type of the map.
80    typedef _Graph Graph;
81    /// The item type of the map.
82    typedef _Item Item;
83    /// The reference map tag.
84    typedef True ReferenceMapTag;
85
86    /// The key type of the map.
87    typedef _Item Key;
88    /// The value type of the map.
89    typedef _Value Value;
90
91    /// The notifier type.
92    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
93
94    /// The map type.
95    typedef DebugMap Map;
96    /// The base class of the map.
97    typedef typename Notifier::ObserverBase Parent;
98
99    /// The reference type of the map;
100    typedef typename Container::reference Reference;
101    /// The const reference type of the map;
102    typedef typename Container::const_reference ConstReference;
103
104
105    /// \brief Constructor to attach the new map into the notifier.
106    ///
107    /// It constructs a map and attachs it into the notifier.
108    /// It adds all the items of the graph to the map.
109    DebugMap(const Graph& graph) {
110      Parent::attach(graph.getNotifier(Item()));
111      container.resize(Parent::getNotifier()->maxId() + 1);
112      flag.resize(Parent::getNotifier()->maxId() + 1, false);
113      const typename Parent::Notifier* notifier = Parent::getNotifier();
114      Item it;
115      for (notifier->first(it); it != INVALID; notifier->next(it)) {
116        flag[Parent::getNotifier()->id(it)] = true;
117      }
118    }
119
120    /// \brief Constructor uses given value to initialize the map.
121    ///
122    /// It constructs a map uses a given value to initialize the map.
123    /// It adds all the items of the graph to the map.
124    DebugMap(const Graph& graph, const Value& value) {
125      Parent::attach(graph.getNotifier(Item()));
126      container.resize(Parent::getNotifier()->maxId() + 1, value);
127      flag.resize(Parent::getNotifier()->maxId() + 1, false);
128      const typename Parent::Notifier* notifier = Parent::getNotifier();
129      Item it;
130      for (notifier->first(it); it != INVALID; notifier->next(it)) {
131        flag[Parent::getNotifier()->id(it)] = true;
132      }
133    }
134
135    /// \brief Copy constructor
136    ///
137    /// Copy constructor.
138    DebugMap(const DebugMap& _copy) : Parent() {
139      if (_copy.attached()) {
140        Parent::attach(*_copy.getNotifier());
141        container = _copy.container;
142      }
143      flag.resize(Parent::getNotifier()->maxId() + 1, false);
144      const typename Parent::Notifier* notifier = Parent::getNotifier();
145      Item it;
146      for (notifier->first(it); it != INVALID; notifier->next(it)) {
147        flag[Parent::getNotifier()->id(it)] = true;
148        LEMON_ASSERT(_copy.flag[Parent::getNotifier()->id(it)], MapError());
149      }
150    }
151
152    /// \brief Destructor
153    ///
154    /// Destructor.
155    ~DebugMap() {
156      const typename Parent::Notifier* notifier = Parent::getNotifier();
157      if (notifier != 0) {
158        Item it;
159        for (notifier->first(it); it != INVALID; notifier->next(it)) {
160          LEMON_ASSERT(flag[Parent::getNotifier()->id(it)], MapError());
161          flag[Parent::getNotifier()->id(it)] = false;
162        }
163      }
164      for (int i = 0; i < (int)flag.size(); ++i) {
165        LEMON_ASSERT(!flag[i], MapError());
166      }
167    }
168
169    /// \brief Assign operator.
170    ///
171    /// This operator assigns for each item in the map the
172    /// value mapped to the same item in the copied map. 
173    /// The parameter map should be indiced with the same
174    /// itemset because this assign operator does not change
175    /// the container of the map.
176    DebugMap& operator=(const DebugMap& cmap) {
177      return operator=<DebugMap>(cmap);
178    }
179
180
181    /// \brief Template assign operator.
182    ///
183    /// The given parameter should be conform to the ReadMap
184    /// concecpt and could be indiced by the current item set of
185    /// the NodeMap. In this case the value for each item
186    /// is assigned by the value of the given ReadMap.
187    template <typename CMap>
188    DebugMap& operator=(const CMap& cmap) {
189      checkConcept<concept::ReadMap<Key, _Value>, CMap>();
190      const typename Parent::Notifier* notifier = Parent::getNotifier();
191      Item it;
192      for (notifier->first(it); it != INVALID; notifier->next(it)) {
193        set(it, cmap[it]);
194      }
195      return *this;
196    }
197   
198  public:
199
200    /// \brief The subcript operator.
201    ///
202    /// The subscript operator. The map can be subscripted by the
203    /// actual items of the graph.     
204    Reference operator[](const Key& key) {
205      LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
206      return container[Parent::getNotifier()->id(key)];
207    }
208               
209    /// \brief The const subcript operator.
210    ///
211    /// The const subscript operator. The map can be subscripted by the
212    /// actual items of the graph.
213    ConstReference operator[](const Key& key) const {
214      LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
215      return container[Parent::getNotifier()->id(key)];
216    }
217
218
219    /// \brief The setter function of the map.
220    ///
221    /// It the same as operator[](key) = value expression.
222    void set(const Key& key, const Value& value) {
223      (*this)[key] = value;
224    }
225
226  protected:
227
228    /// \brief Adds a new key to the map.
229    ///         
230    /// It adds a new key to the map. It called by the observer notifier
231    /// and it overrides the add() member function of the observer base.     
232    virtual void add(const Key& key) {
233      int id = Parent::getNotifier()->id(key);
234      if (id >= (int)container.size()) {
235        container.resize(id + 1);
236        flag.resize(id + 1, false);
237      }
238      LEMON_ASSERT(!flag[Parent::getNotifier()->id(key)], MapError());
239      flag[Parent::getNotifier()->id(key)] = true;
240      if (strictCheck) {
241        std::vector<bool> fl(flag.size(), false);
242        const typename Parent::Notifier* notifier = Parent::getNotifier();
243        Item it;
244        for (notifier->first(it); it != INVALID; notifier->next(it)) {
245          int id = Parent::getNotifier()->id(it);
246          fl[id] = true;
247        }
248        LEMON_ASSERT(fl == flag, MapError());
249      }
250    }
251
252    /// \brief Adds more new keys to the map.
253    ///         
254    /// It adds more new keys to the map. It called by the observer notifier
255    /// and it overrides the add() member function of the observer base.     
256    virtual void add(const std::vector<Key>& keys) {
257      int max = container.size() - 1;
258      for (int i = 0; i < (int)keys.size(); ++i) {
259        int id = Parent::getNotifier()->id(keys[i]);
260        if (id >= max) {
261          max = id;
262        }
263      }
264      container.resize(max + 1);
265      flag.resize(max + 1, false);
266      for (int i = 0; i < (int)keys.size(); ++i) {
267        LEMON_ASSERT(!flag[Parent::getNotifier()->id(keys[i])], MapError());
268        flag[Parent::getNotifier()->id(keys[i])] = true;
269      }
270      if (strictCheck) {
271        std::vector<bool> fl(flag.size(), false);
272        const typename Parent::Notifier* notifier = Parent::getNotifier();
273        Item it;
274        for (notifier->first(it); it != INVALID; notifier->next(it)) {
275          int id = Parent::getNotifier()->id(it);
276          fl[id] = true;
277        }
278        LEMON_ASSERT(fl == flag, MapError());
279      }
280    }
281
282    /// \brief Erase a key from the map.
283    ///
284    /// Erase a key from the map. It called by the observer notifier
285    /// and it overrides the erase() member function of the observer base.     
286    virtual void erase(const Key& key) {
287      if (strictCheck) {
288        std::vector<bool> fl(flag.size(), false);
289        const typename Parent::Notifier* notifier = Parent::getNotifier();
290        Item it;
291        for (notifier->first(it); it != INVALID; notifier->next(it)) {
292          int id = Parent::getNotifier()->id(it);
293          fl[id] = true;
294        }
295        LEMON_ASSERT(fl == flag, MapError());
296      }
297      container[Parent::getNotifier()->id(key)] = Value();
298      LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
299      flag[Parent::getNotifier()->id(key)] = false;
300    }
301
302    /// \brief Erase more keys from the map.
303    ///
304    /// Erase more keys from the map. It called by the observer notifier
305    /// and it overrides the erase() member function of the observer base.     
306    virtual void erase(const std::vector<Key>& keys) {
307      if (strictCheck) {
308        std::vector<bool> fl(flag.size(), false);
309        const typename Parent::Notifier* notifier = Parent::getNotifier();
310        Item it;
311        for (notifier->first(it); it != INVALID; notifier->next(it)) {
312          int id = Parent::getNotifier()->id(it);
313          fl[id] = true;
314        }
315        LEMON_ASSERT(fl == flag, MapError());
316      }
317      for (int i = 0; i < (int)keys.size(); ++i) {
318        container[Parent::getNotifier()->id(keys[i])] = Value();
319        LEMON_ASSERT(flag[Parent::getNotifier()->id(keys[i])], MapError());
320        flag[Parent::getNotifier()->id(keys[i])] = false;
321      }
322    }
323   
324    /// \brief Buildes the map.
325    ///
326    /// It buildes the map. It called by the observer notifier
327    /// and it overrides the build() member function of the observer base.
328    virtual void build() {
329      if (strictCheck) {
330        for (int i = 0; i < (int)flag.size(); ++i) {
331          LEMON_ASSERT(flag[i], MapError());
332        }
333      }
334      int size = Parent::getNotifier()->maxId() + 1;
335      container.reserve(size);
336      container.resize(size);
337      flag.reserve(size);
338      flag.resize(size, false);
339      const typename Parent::Notifier* notifier = Parent::getNotifier();
340      Item it;
341      for (notifier->first(it); it != INVALID; notifier->next(it)) {
342        int id = Parent::getNotifier()->id(it);
343        LEMON_ASSERT(!flag[id], MapError());
344        flag[id] = true;
345      }
346    }
347
348    /// \brief Clear the map.
349    ///
350    /// It erase all items from the map. It called by the observer notifier
351    /// and it overrides the clear() member function of the observer base.     
352    virtual void clear() {
353      const typename Parent::Notifier* notifier = Parent::getNotifier();
354      Item it;
355      for (notifier->first(it); it != INVALID; notifier->next(it)) {
356        int id = Parent::getNotifier()->id(it);
357        LEMON_ASSERT(flag[id], MapError());
358        flag[id] = false;
359      }
360      if (strictCheck) {
361        for (int i = 0; i < (int)flag.size(); ++i) {
362          LEMON_ASSERT(!flag[i], MapError());
363        }
364      }
365      container.clear();
366      flag.clear();
367    }
368   
369  private:
370               
371    Container container;
372    Flag flag;
373
374  };
375
376}
377
378#endif
Note: See TracBrowser for help on using the repository browser.