deba@2202: /* -*- C++ -*- deba@2202: * deba@2202: * This file is a part of LEMON, a generic C++ optimization library deba@2202: * alpar@2391: * Copyright (C) 2003-2007 deba@2202: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2202: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2202: * deba@2202: * Permission to use, modify and distribute this software is granted deba@2202: * provided that this copyright notice appears in all copies. For deba@2202: * precise terms see the accompanying LICENSE file. deba@2202: * deba@2202: * This software is provided "AS IS" with no warranty of any kind, deba@2202: * express or implied, and with no claim as to its suitability for any deba@2202: * purpose. deba@2202: * deba@2202: */ deba@2202: deba@2202: #ifndef LEMON_BITS_DEBUG_MAP_H deba@2202: #define LEMON_BITS_DEBUG_MAP_H deba@2202: deba@2202: #include deba@2202: #include deba@2202: deba@2202: #include deba@2202: #include deba@2202: #include deba@2202: deba@2202: #include deba@2202: deba@2202: #include alpar@2260: #include deba@2202: deba@2202: ///\ingroup graphbits deba@2202: /// deba@2202: ///\file deba@2202: ///\brief Vector based graph maps for debugging. deba@2202: namespace lemon { deba@2202: deba@2333: #ifndef LEMON_STRICT_DEBUG_MAP deba@2333: #define LEMON_STRICT_DEBUG_MAP false deba@2333: #endif deba@2333: deba@2202: /// \ingroup graphbits deba@2202: /// deba@2202: /// \brief Graph map based on the std::vector storage. deba@2202: /// deba@2202: /// The DebugMap template class is graph map structure what deba@2202: /// automatically updates the map when a key is added to or erased from deba@2202: /// the map. This map also checks some programming failures by example deba@2202: /// multiple addition of items, erasing of not existing item or deba@2202: /// not erased items at the destruction of the map. It helps the deba@2202: /// programmer to avoid segmentation faults and memory leaks. deba@2202: /// deba@2202: /// \param Notifier The AlterationNotifier that will notify this map. deba@2202: /// \param Item The item type of the graph items. deba@2202: /// \param Value The value type of the map. deba@2202: /// deba@2202: /// \author Balazs Dezso deba@2202: template deba@2202: class DebugMap deba@2202: : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { deba@2202: private: deba@2202: deba@2202: /// The container type of the map. deba@2202: typedef std::vector<_Value> Container; deba@2202: deba@2202: /// The container type of the debug flags. deba@2202: typedef std::vector Flag; deba@2202: deba@2202: public: deba@2202: deba@2333: static const bool strictCheck = LEMON_STRICT_DEBUG_MAP; deba@2202: deba@2202: struct MapError { deba@2202: public: deba@2202: virtual ~MapError() {} deba@2202: virtual const char* what() const throw() { deba@2202: return "lemon::DebugMap::MapError"; deba@2202: } deba@2202: }; deba@2202: deba@2202: /// The graph type of the map. deba@2202: typedef _Graph Graph; deba@2202: /// The item type of the map. deba@2202: typedef _Item Item; deba@2202: /// The reference map tag. deba@2202: typedef True ReferenceMapTag; deba@2202: deba@2202: /// The key type of the map. deba@2202: typedef _Item Key; deba@2202: /// The value type of the map. deba@2202: typedef _Value Value; deba@2202: deba@2202: /// The notifier type. deba@2202: typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; deba@2202: deba@2202: /// The map type. deba@2202: typedef DebugMap Map; deba@2202: /// The base class of the map. deba@2202: typedef typename Notifier::ObserverBase Parent; deba@2202: deba@2202: /// The reference type of the map; deba@2202: typedef typename Container::reference Reference; deba@2202: /// The const reference type of the map; deba@2202: typedef typename Container::const_reference ConstReference; deba@2202: deba@2202: deba@2202: /// \brief Constructor to attach the new map into the notifier. deba@2202: /// deba@2202: /// It constructs a map and attachs it into the notifier. deba@2202: /// It adds all the items of the graph to the map. deba@2202: DebugMap(const Graph& graph) { deba@2384: Parent::attach(graph.notifier(Item())); deba@2384: container.resize(Parent::notifier()->maxId() + 1); deba@2384: flag.resize(Parent::notifier()->maxId() + 1, false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: flag[Parent::notifier()->id(it)] = true; deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Constructor uses given value to initialize the map. deba@2202: /// deba@2202: /// It constructs a map uses a given value to initialize the map. deba@2202: /// It adds all the items of the graph to the map. deba@2202: DebugMap(const Graph& graph, const Value& value) { deba@2384: Parent::attach(graph.notifier(Item())); deba@2384: container.resize(Parent::notifier()->maxId() + 1, value); deba@2384: flag.resize(Parent::notifier()->maxId() + 1, false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: flag[Parent::notifier()->id(it)] = true; deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Copy constructor deba@2202: /// deba@2202: /// Copy constructor. deba@2202: DebugMap(const DebugMap& _copy) : Parent() { deba@2202: if (_copy.attached()) { deba@2384: Parent::attach(*_copy.notifier()); deba@2202: container = _copy.container; deba@2202: } deba@2384: flag.resize(Parent::notifier()->maxId() + 1, false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: flag[Parent::notifier()->id(it)] = true; deba@2384: LEMON_ASSERT(_copy.flag[Parent::notifier()->id(it)], MapError()); deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Destructor deba@2202: /// deba@2202: /// Destructor. deba@2202: ~DebugMap() { deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: if (notifier != 0) { deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: LEMON_ASSERT(flag[Parent::notifier()->id(it)], MapError()); deba@2384: flag[Parent::notifier()->id(it)] = false; deba@2202: } deba@2202: } deba@2386: for (int i = 0; i < int(flag.size()); ++i) { deba@2202: LEMON_ASSERT(!flag[i], MapError()); deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Assign operator. deba@2202: /// deba@2202: /// This operator assigns for each item in the map the deba@2202: /// value mapped to the same item in the copied map. deba@2202: /// The parameter map should be indiced with the same deba@2202: /// itemset because this assign operator does not change deba@2202: /// the container of the map. deba@2202: DebugMap& operator=(const DebugMap& cmap) { deba@2202: return operator=(cmap); deba@2202: } deba@2202: deba@2202: deba@2202: /// \brief Template assign operator. deba@2202: /// deba@2202: /// The given parameter should be conform to the ReadMap deba@2202: /// concecpt and could be indiced by the current item set of deba@2202: /// the NodeMap. In this case the value for each item deba@2202: /// is assigned by the value of the given ReadMap. deba@2202: template deba@2202: DebugMap& operator=(const CMap& cmap) { alpar@2260: checkConcept, CMap>(); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2202: set(it, cmap[it]); deba@2202: } deba@2202: return *this; deba@2202: } deba@2202: deba@2202: public: deba@2202: deba@2202: /// \brief The subcript operator. deba@2202: /// deba@2202: /// The subscript operator. The map can be subscripted by the deba@2202: /// actual items of the graph. deba@2202: Reference operator[](const Key& key) { deba@2384: LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError()); deba@2384: return container[Parent::notifier()->id(key)]; deba@2202: } deba@2202: deba@2202: /// \brief The const subcript operator. deba@2202: /// deba@2202: /// The const subscript operator. The map can be subscripted by the deba@2202: /// actual items of the graph. deba@2202: ConstReference operator[](const Key& key) const { deba@2384: LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError()); deba@2384: return container[Parent::notifier()->id(key)]; deba@2202: } deba@2202: deba@2202: deba@2202: /// \brief The setter function of the map. deba@2202: /// deba@2202: /// It the same as operator[](key) = value expression. deba@2202: void set(const Key& key, const Value& value) { deba@2202: (*this)[key] = value; deba@2202: } deba@2202: deba@2202: protected: deba@2202: deba@2202: /// \brief Adds a new key to the map. deba@2202: /// deba@2202: /// It adds a new key to the map. It called by the observer notifier deba@2202: /// and it overrides the add() member function of the observer base. deba@2202: virtual void add(const Key& key) { deba@2384: int id = Parent::notifier()->id(key); deba@2386: if (id >= int(container.size())) { deba@2202: container.resize(id + 1); deba@2202: flag.resize(id + 1, false); deba@2202: } deba@2384: LEMON_ASSERT(!flag[Parent::notifier()->id(key)], MapError()); deba@2384: flag[Parent::notifier()->id(key)] = true; deba@2202: if (strictCheck) { deba@2202: std::vector fl(flag.size(), false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2386: int jd = Parent::notifier()->id(it); deba@2386: fl[jd] = true; deba@2202: } deba@2202: LEMON_ASSERT(fl == flag, MapError()); deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Adds more new keys to the map. deba@2202: /// deba@2202: /// It adds more new keys to the map. It called by the observer notifier deba@2202: /// and it overrides the add() member function of the observer base. deba@2202: virtual void add(const std::vector& keys) { deba@2202: int max = container.size() - 1; deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@2384: int id = Parent::notifier()->id(keys[i]); deba@2202: if (id >= max) { deba@2202: max = id; deba@2202: } deba@2202: } deba@2202: container.resize(max + 1); deba@2202: flag.resize(max + 1, false); deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@2384: LEMON_ASSERT(!flag[Parent::notifier()->id(keys[i])], MapError()); deba@2384: flag[Parent::notifier()->id(keys[i])] = true; deba@2202: } deba@2202: if (strictCheck) { deba@2202: std::vector fl(flag.size(), false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: int id = Parent::notifier()->id(it); deba@2202: fl[id] = true; deba@2202: } deba@2202: LEMON_ASSERT(fl == flag, MapError()); deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Erase a key from the map. deba@2202: /// deba@2202: /// Erase a key from the map. It called by the observer notifier deba@2202: /// and it overrides the erase() member function of the observer base. deba@2202: virtual void erase(const Key& key) { deba@2202: if (strictCheck) { deba@2202: std::vector fl(flag.size(), false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: int id = Parent::notifier()->id(it); deba@2202: fl[id] = true; deba@2202: } deba@2202: LEMON_ASSERT(fl == flag, MapError()); deba@2202: } deba@2384: container[Parent::notifier()->id(key)] = Value(); deba@2384: LEMON_ASSERT(flag[Parent::notifier()->id(key)], MapError()); deba@2384: flag[Parent::notifier()->id(key)] = false; deba@2202: } deba@2202: deba@2202: /// \brief Erase more keys from the map. deba@2202: /// deba@2202: /// Erase more keys from the map. It called by the observer notifier deba@2202: /// and it overrides the erase() member function of the observer base. deba@2202: virtual void erase(const std::vector& keys) { deba@2202: if (strictCheck) { deba@2202: std::vector fl(flag.size(), false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: int id = Parent::notifier()->id(it); deba@2202: fl[id] = true; deba@2202: } deba@2202: LEMON_ASSERT(fl == flag, MapError()); deba@2202: } deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@2384: container[Parent::notifier()->id(keys[i])] = Value(); deba@2384: LEMON_ASSERT(flag[Parent::notifier()->id(keys[i])], MapError()); deba@2384: flag[Parent::notifier()->id(keys[i])] = false; deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Buildes the map. deba@2202: /// deba@2202: /// It buildes the map. It called by the observer notifier deba@2202: /// and it overrides the build() member function of the observer base. deba@2202: virtual void build() { deba@2202: if (strictCheck) { deba@2386: for (int i = 0; i < int(flag.size()); ++i) { deba@2202: LEMON_ASSERT(flag[i], MapError()); deba@2202: } deba@2202: } deba@2384: int size = Parent::notifier()->maxId() + 1; deba@2202: container.reserve(size); deba@2202: container.resize(size); deba@2202: flag.reserve(size); deba@2202: flag.resize(size, false); deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: int id = Parent::notifier()->id(it); deba@2202: LEMON_ASSERT(!flag[id], MapError()); deba@2202: flag[id] = true; deba@2202: } deba@2202: } deba@2202: deba@2202: /// \brief Clear the map. deba@2202: /// deba@2202: /// It erase all items from the map. It called by the observer notifier deba@2202: /// and it overrides the clear() member function of the observer base. deba@2202: virtual void clear() { deba@2384: const typename Parent::Notifier* notifier = Parent::notifier(); deba@2202: Item it; deba@2202: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2384: int id = Parent::notifier()->id(it); deba@2202: LEMON_ASSERT(flag[id], MapError()); deba@2202: flag[id] = false; deba@2202: } deba@2202: if (strictCheck) { deba@2386: for (int i = 0; i < int(flag.size()); ++i) { deba@2202: LEMON_ASSERT(!flag[i], MapError()); deba@2202: } deba@2202: } deba@2202: container.clear(); deba@2202: flag.clear(); deba@2202: } deba@2202: deba@2202: private: deba@2202: deba@2202: Container container; deba@2202: Flag flag; deba@2202: deba@2202: }; deba@2202: deba@2202: } deba@2202: deba@2202: #endif