COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/debug_map.h @ 2260:4274224f8a7d

Last change on this file since 2260:4274224f8a7d was 2260:4274224f8a7d, checked in by Alpar Juttner, 13 years ago

concept -> concepts (namespace & directory)

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/concepts/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<concepts::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.