1.1 --- a/lemon/Makefile.am Wed Sep 06 10:10:48 2006 +0000
1.2 +++ b/lemon/Makefile.am Wed Sep 06 10:19:57 2006 +0000
1.3 @@ -100,6 +100,7 @@
1.4 lemon/bits/array_map.h \
1.5 lemon/bits/base_extender.h \
1.6 lemon/bits/bezier.h \
1.7 + lemon/bits/debug_map.h \
1.8 lemon/bits/default_map.h \
1.9 lemon/bits/edge_set_extender.h \
1.10 lemon/bits/graph_adaptor_extender.h \
2.1 --- a/lemon/bits/array_map.h Wed Sep 06 10:10:48 2006 +0000
2.2 +++ b/lemon/bits/array_map.h Wed Sep 06 10:19:57 2006 +0000
2.3 @@ -41,7 +41,7 @@
2.4 /// the map. This map uses the allocators to implement
2.5 /// the container functionality.
2.6 ///
2.7 - /// The template parameter is the Graph the current Item type and
2.8 + /// The template parameters are the Graph the current Item type and
2.9 /// the Value type of the map.
2.10 template <typename _Graph, typename _Item, typename _Value>
2.11 class ArrayMap
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/bits/debug_map.h Wed Sep 06 10:19:57 2006 +0000
3.3 @@ -0,0 +1,378 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2006
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_BITS_DEBUG_MAP_H
3.23 +#define LEMON_BITS_DEBUG_MAP_H
3.24 +
3.25 +#include <vector>
3.26 +#include <algorithm>
3.27 +
3.28 +#include <lemon/bits/traits.h>
3.29 +#include <lemon/bits/utility.h>
3.30 +#include <lemon/error.h>
3.31 +
3.32 +#include <lemon/bits/alteration_notifier.h>
3.33 +
3.34 +#include <lemon/concept_check.h>
3.35 +#include <lemon/concept/maps.h>
3.36 +
3.37 +///\ingroup graphbits
3.38 +///
3.39 +///\file
3.40 +///\brief Vector based graph maps for debugging.
3.41 +namespace lemon {
3.42 +
3.43 + /// \ingroup graphbits
3.44 + ///
3.45 + /// \brief Graph map based on the std::vector storage.
3.46 + ///
3.47 + /// The DebugMap template class is graph map structure what
3.48 + /// automatically updates the map when a key is added to or erased from
3.49 + /// the map. This map also checks some programming failures by example
3.50 + /// multiple addition of items, erasing of not existing item or
3.51 + /// not erased items at the destruction of the map. It helps the
3.52 + /// programmer to avoid segmentation faults and memory leaks.
3.53 + ///
3.54 + /// \param Notifier The AlterationNotifier that will notify this map.
3.55 + /// \param Item The item type of the graph items.
3.56 + /// \param Value The value type of the map.
3.57 + ///
3.58 + /// \author Balazs Dezso
3.59 + template <typename _Graph, typename _Item, typename _Value>
3.60 + class DebugMap
3.61 + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
3.62 + private:
3.63 +
3.64 + /// The container type of the map.
3.65 + typedef std::vector<_Value> Container;
3.66 +
3.67 + /// The container type of the debug flags.
3.68 + typedef std::vector<bool> Flag;
3.69 +
3.70 + public:
3.71 +
3.72 + static const bool strictCheck = true;
3.73 +
3.74 + struct MapError {
3.75 + public:
3.76 + virtual ~MapError() {}
3.77 + virtual const char* what() const throw() {
3.78 + return "lemon::DebugMap::MapError";
3.79 + }
3.80 + };
3.81 +
3.82 + /// The graph type of the map.
3.83 + typedef _Graph Graph;
3.84 + /// The item type of the map.
3.85 + typedef _Item Item;
3.86 + /// The reference map tag.
3.87 + typedef True ReferenceMapTag;
3.88 +
3.89 + /// The key type of the map.
3.90 + typedef _Item Key;
3.91 + /// The value type of the map.
3.92 + typedef _Value Value;
3.93 +
3.94 + /// The notifier type.
3.95 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
3.96 +
3.97 + /// The map type.
3.98 + typedef DebugMap Map;
3.99 + /// The base class of the map.
3.100 + typedef typename Notifier::ObserverBase Parent;
3.101 +
3.102 + /// The reference type of the map;
3.103 + typedef typename Container::reference Reference;
3.104 + /// The const reference type of the map;
3.105 + typedef typename Container::const_reference ConstReference;
3.106 +
3.107 +
3.108 + /// \brief Constructor to attach the new map into the notifier.
3.109 + ///
3.110 + /// It constructs a map and attachs it into the notifier.
3.111 + /// It adds all the items of the graph to the map.
3.112 + DebugMap(const Graph& graph) {
3.113 + Parent::attach(graph.getNotifier(Item()));
3.114 + container.resize(Parent::getNotifier()->maxId() + 1);
3.115 + flag.resize(Parent::getNotifier()->maxId() + 1, false);
3.116 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.117 + Item it;
3.118 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.119 + flag[Parent::getNotifier()->id(it)] = true;
3.120 + }
3.121 + }
3.122 +
3.123 + /// \brief Constructor uses given value to initialize the map.
3.124 + ///
3.125 + /// It constructs a map uses a given value to initialize the map.
3.126 + /// It adds all the items of the graph to the map.
3.127 + DebugMap(const Graph& graph, const Value& value) {
3.128 + Parent::attach(graph.getNotifier(Item()));
3.129 + container.resize(Parent::getNotifier()->maxId() + 1, value);
3.130 + flag.resize(Parent::getNotifier()->maxId() + 1, false);
3.131 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.132 + Item it;
3.133 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.134 + flag[Parent::getNotifier()->id(it)] = true;
3.135 + }
3.136 + }
3.137 +
3.138 + /// \brief Copy constructor
3.139 + ///
3.140 + /// Copy constructor.
3.141 + DebugMap(const DebugMap& _copy) : Parent() {
3.142 + if (_copy.attached()) {
3.143 + Parent::attach(*_copy.getNotifier());
3.144 + container = _copy.container;
3.145 + }
3.146 + flag.resize(Parent::getNotifier()->maxId() + 1, false);
3.147 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.148 + Item it;
3.149 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.150 + flag[Parent::getNotifier()->id(it)] = true;
3.151 + LEMON_ASSERT(_copy.flag[Parent::getNotifier()->id(it)], MapError());
3.152 + }
3.153 + }
3.154 +
3.155 + /// \brief Destructor
3.156 + ///
3.157 + /// Destructor.
3.158 + ~DebugMap() {
3.159 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.160 + if (notifier != 0) {
3.161 + Item it;
3.162 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.163 + LEMON_ASSERT(flag[Parent::getNotifier()->id(it)], MapError());
3.164 + flag[Parent::getNotifier()->id(it)] = false;
3.165 + }
3.166 + }
3.167 + for (int i = 0; i < (int)flag.size(); ++i) {
3.168 + LEMON_ASSERT(!flag[i], MapError());
3.169 + }
3.170 + }
3.171 +
3.172 + /// \brief Assign operator.
3.173 + ///
3.174 + /// This operator assigns for each item in the map the
3.175 + /// value mapped to the same item in the copied map.
3.176 + /// The parameter map should be indiced with the same
3.177 + /// itemset because this assign operator does not change
3.178 + /// the container of the map.
3.179 + DebugMap& operator=(const DebugMap& cmap) {
3.180 + return operator=<DebugMap>(cmap);
3.181 + }
3.182 +
3.183 +
3.184 + /// \brief Template assign operator.
3.185 + ///
3.186 + /// The given parameter should be conform to the ReadMap
3.187 + /// concecpt and could be indiced by the current item set of
3.188 + /// the NodeMap. In this case the value for each item
3.189 + /// is assigned by the value of the given ReadMap.
3.190 + template <typename CMap>
3.191 + DebugMap& operator=(const CMap& cmap) {
3.192 + checkConcept<concept::ReadMap<Key, _Value>, CMap>();
3.193 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.194 + Item it;
3.195 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.196 + set(it, cmap[it]);
3.197 + }
3.198 + return *this;
3.199 + }
3.200 +
3.201 + public:
3.202 +
3.203 + /// \brief The subcript operator.
3.204 + ///
3.205 + /// The subscript operator. The map can be subscripted by the
3.206 + /// actual items of the graph.
3.207 + Reference operator[](const Key& key) {
3.208 + LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
3.209 + return container[Parent::getNotifier()->id(key)];
3.210 + }
3.211 +
3.212 + /// \brief The const subcript operator.
3.213 + ///
3.214 + /// The const subscript operator. The map can be subscripted by the
3.215 + /// actual items of the graph.
3.216 + ConstReference operator[](const Key& key) const {
3.217 + LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
3.218 + return container[Parent::getNotifier()->id(key)];
3.219 + }
3.220 +
3.221 +
3.222 + /// \brief The setter function of the map.
3.223 + ///
3.224 + /// It the same as operator[](key) = value expression.
3.225 + void set(const Key& key, const Value& value) {
3.226 + (*this)[key] = value;
3.227 + }
3.228 +
3.229 + protected:
3.230 +
3.231 + /// \brief Adds a new key to the map.
3.232 + ///
3.233 + /// It adds a new key to the map. It called by the observer notifier
3.234 + /// and it overrides the add() member function of the observer base.
3.235 + virtual void add(const Key& key) {
3.236 + int id = Parent::getNotifier()->id(key);
3.237 + if (id >= (int)container.size()) {
3.238 + container.resize(id + 1);
3.239 + flag.resize(id + 1, false);
3.240 + }
3.241 + LEMON_ASSERT(!flag[Parent::getNotifier()->id(key)], MapError());
3.242 + flag[Parent::getNotifier()->id(key)] = true;
3.243 + if (strictCheck) {
3.244 + std::vector<bool> fl(flag.size(), false);
3.245 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.246 + Item it;
3.247 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.248 + int id = Parent::getNotifier()->id(it);
3.249 + fl[id] = true;
3.250 + }
3.251 + LEMON_ASSERT(fl == flag, MapError());
3.252 + }
3.253 + }
3.254 +
3.255 + /// \brief Adds more new keys to the map.
3.256 + ///
3.257 + /// It adds more new keys to the map. It called by the observer notifier
3.258 + /// and it overrides the add() member function of the observer base.
3.259 + virtual void add(const std::vector<Key>& keys) {
3.260 + int max = container.size() - 1;
3.261 + for (int i = 0; i < (int)keys.size(); ++i) {
3.262 + int id = Parent::getNotifier()->id(keys[i]);
3.263 + if (id >= max) {
3.264 + max = id;
3.265 + }
3.266 + }
3.267 + container.resize(max + 1);
3.268 + flag.resize(max + 1, false);
3.269 + for (int i = 0; i < (int)keys.size(); ++i) {
3.270 + LEMON_ASSERT(!flag[Parent::getNotifier()->id(keys[i])], MapError());
3.271 + flag[Parent::getNotifier()->id(keys[i])] = true;
3.272 + }
3.273 + if (strictCheck) {
3.274 + std::vector<bool> fl(flag.size(), false);
3.275 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.276 + Item it;
3.277 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.278 + int id = Parent::getNotifier()->id(it);
3.279 + fl[id] = true;
3.280 + }
3.281 + LEMON_ASSERT(fl == flag, MapError());
3.282 + }
3.283 + }
3.284 +
3.285 + /// \brief Erase a key from the map.
3.286 + ///
3.287 + /// Erase a key from the map. It called by the observer notifier
3.288 + /// and it overrides the erase() member function of the observer base.
3.289 + virtual void erase(const Key& key) {
3.290 + if (strictCheck) {
3.291 + std::vector<bool> fl(flag.size(), false);
3.292 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.293 + Item it;
3.294 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.295 + int id = Parent::getNotifier()->id(it);
3.296 + fl[id] = true;
3.297 + }
3.298 + LEMON_ASSERT(fl == flag, MapError());
3.299 + }
3.300 + container[Parent::getNotifier()->id(key)] = Value();
3.301 + LEMON_ASSERT(flag[Parent::getNotifier()->id(key)], MapError());
3.302 + flag[Parent::getNotifier()->id(key)] = false;
3.303 + }
3.304 +
3.305 + /// \brief Erase more keys from the map.
3.306 + ///
3.307 + /// Erase more keys from the map. It called by the observer notifier
3.308 + /// and it overrides the erase() member function of the observer base.
3.309 + virtual void erase(const std::vector<Key>& keys) {
3.310 + if (strictCheck) {
3.311 + std::vector<bool> fl(flag.size(), false);
3.312 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.313 + Item it;
3.314 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.315 + int id = Parent::getNotifier()->id(it);
3.316 + fl[id] = true;
3.317 + }
3.318 + LEMON_ASSERT(fl == flag, MapError());
3.319 + }
3.320 + for (int i = 0; i < (int)keys.size(); ++i) {
3.321 + container[Parent::getNotifier()->id(keys[i])] = Value();
3.322 + LEMON_ASSERT(flag[Parent::getNotifier()->id(keys[i])], MapError());
3.323 + flag[Parent::getNotifier()->id(keys[i])] = false;
3.324 + }
3.325 + }
3.326 +
3.327 + /// \brief Buildes the map.
3.328 + ///
3.329 + /// It buildes the map. It called by the observer notifier
3.330 + /// and it overrides the build() member function of the observer base.
3.331 + virtual void build() {
3.332 + if (strictCheck) {
3.333 + for (int i = 0; i < (int)flag.size(); ++i) {
3.334 + LEMON_ASSERT(flag[i], MapError());
3.335 + }
3.336 + }
3.337 + int size = Parent::getNotifier()->maxId() + 1;
3.338 + container.reserve(size);
3.339 + container.resize(size);
3.340 + flag.reserve(size);
3.341 + flag.resize(size, false);
3.342 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.343 + Item it;
3.344 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.345 + int id = Parent::getNotifier()->id(it);
3.346 + LEMON_ASSERT(!flag[id], MapError());
3.347 + flag[id] = true;
3.348 + }
3.349 + }
3.350 +
3.351 + /// \brief Clear the map.
3.352 + ///
3.353 + /// It erase all items from the map. It called by the observer notifier
3.354 + /// and it overrides the clear() member function of the observer base.
3.355 + virtual void clear() {
3.356 + const typename Parent::Notifier* notifier = Parent::getNotifier();
3.357 + Item it;
3.358 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
3.359 + int id = Parent::getNotifier()->id(it);
3.360 + LEMON_ASSERT(flag[id], MapError());
3.361 + flag[id] = false;
3.362 + }
3.363 + if (strictCheck) {
3.364 + for (int i = 0; i < (int)flag.size(); ++i) {
3.365 + LEMON_ASSERT(!flag[i], MapError());
3.366 + }
3.367 + }
3.368 + container.clear();
3.369 + flag.clear();
3.370 + }
3.371 +
3.372 + private:
3.373 +
3.374 + Container container;
3.375 + Flag flag;
3.376 +
3.377 + };
3.378 +
3.379 +}
3.380 +
3.381 +#endif
4.1 --- a/lemon/bits/default_map.h Wed Sep 06 10:10:48 2006 +0000
4.2 +++ b/lemon/bits/default_map.h Wed Sep 06 10:19:57 2006 +0000
4.3 @@ -22,6 +22,7 @@
4.4
4.5 #include <lemon/bits/array_map.h>
4.6 #include <lemon/bits/vector_map.h>
4.7 +#include <lemon/bits/debug_map.h>
4.8
4.9 ///\ingroup graphbits
4.10 ///\file
4.11 @@ -37,15 +38,6 @@
4.12 typedef ArrayMap<_Graph, _Item, _Value> Map;
4.13 };
4.14
4.15 -#else
4.16 -
4.17 - template <typename _Graph, typename _Item, typename _Value>
4.18 - struct DefaultMapSelector {
4.19 - typedef VectorMap<_Graph, _Item, _Value> Map;
4.20 - };
4.21 -
4.22 -#endif
4.23 -
4.24 // bool
4.25 template <typename _Graph, typename _Item>
4.26 struct DefaultMapSelector<_Graph, _Item, bool> {
4.27 @@ -148,6 +140,15 @@
4.28 typedef VectorMap<_Graph, _Item, _Ptr*> Map;
4.29 };
4.30
4.31 +#else
4.32 +
4.33 + template <typename _Graph, typename _Item, typename _Value>
4.34 + struct DefaultMapSelector {
4.35 + typedef DebugMap<_Graph, _Item, _Value> Map;
4.36 + };
4.37 +
4.38 +#endif
4.39 +
4.40 /// \e
4.41 template <typename _Graph, typename _Item, typename _Value>
4.42 class DefaultMap
5.1 --- a/lemon/bits/vector_map.h Wed Sep 06 10:10:48 2006 +0000
5.2 +++ b/lemon/bits/vector_map.h Wed Sep 06 10:19:57 2006 +0000
5.3 @@ -42,9 +42,7 @@
5.4 ///
5.5 /// The VectorMap template class is graph map structure what
5.6 /// automatically updates the map when a key is added to or erased from
5.7 - /// the map. This map factory uses the allocators to implement
5.8 - /// the container functionality. This map factory
5.9 - /// uses the std::vector to implement the container function.
5.10 + /// the map. This map type uses the std::vector to store the values.
5.11 ///
5.12 /// \param Notifier The AlterationNotifier that will notify this map.
5.13 /// \param Item The item type of the graph items.