[906] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
[1956] | 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). |
---|
[906] | 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 | |
---|
[1999] | 19 | #ifndef LEMON_BITS_VECTOR_MAP_H |
---|
| 20 | #define LEMON_BITS_VECTOR_MAP_H |
---|
[822] | 21 | |
---|
| 22 | #include <vector> |
---|
[946] | 23 | #include <algorithm> |
---|
[822] | 24 | |
---|
[1999] | 25 | #include <lemon/bits/traits.h> |
---|
[1993] | 26 | #include <lemon/bits/utility.h> |
---|
[1999] | 27 | |
---|
[1307] | 28 | #include <lemon/bits/alteration_notifier.h> |
---|
[822] | 29 | |
---|
[1999] | 30 | ///\ingroup graphbits |
---|
[1669] | 31 | /// |
---|
[822] | 32 | ///\file |
---|
| 33 | ///\brief Vector based graph maps. |
---|
[921] | 34 | namespace lemon { |
---|
[1669] | 35 | |
---|
[1996] | 36 | /// \ingroup graphbits |
---|
[1669] | 37 | /// |
---|
| 38 | /// \brief Graph map based on the std::vector storage. |
---|
| 39 | /// |
---|
[946] | 40 | /// The VectorMap template class is graph map structure what |
---|
[1999] | 41 | /// automatically updates the map when a key is added to or erased from |
---|
[946] | 42 | /// the map. This map factory uses the allocators to implement |
---|
| 43 | /// the container functionality. This map factory |
---|
| 44 | /// uses the std::vector to implement the container function. |
---|
| 45 | /// |
---|
[1999] | 46 | /// \param Notifier The AlterationNotifier that will notify this map. |
---|
[1703] | 47 | /// \param Item The item type of the graph items. |
---|
[946] | 48 | /// \param Value The value type of the map. |
---|
| 49 | /// |
---|
[1999] | 50 | /// \author Balazs Dezso |
---|
| 51 | template <typename _Graph, typename _Item, typename _Value> |
---|
| 52 | class VectorMap |
---|
| 53 | : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
---|
[1719] | 54 | private: |
---|
| 55 | |
---|
| 56 | /// The container type of the map. |
---|
| 57 | typedef std::vector<_Value> Container; |
---|
| 58 | |
---|
[822] | 59 | public: |
---|
[1703] | 60 | |
---|
[946] | 61 | /// The graph type of the map. |
---|
| 62 | typedef _Graph Graph; |
---|
[1999] | 63 | /// The item type of the map. |
---|
| 64 | typedef _Item Item; |
---|
[1719] | 65 | /// The reference map tag. |
---|
| 66 | typedef True ReferenceMapTag; |
---|
| 67 | |
---|
[946] | 68 | /// The key type of the map. |
---|
[987] | 69 | typedef _Item Key; |
---|
[946] | 70 | /// The value type of the map. |
---|
| 71 | typedef _Value Value; |
---|
[1719] | 72 | |
---|
[1999] | 73 | /// The notifier type. |
---|
| 74 | typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
---|
[822] | 75 | |
---|
| 76 | /// The map type. |
---|
| 77 | typedef VectorMap Map; |
---|
[946] | 78 | /// The base class of the map. |
---|
[1999] | 79 | typedef typename Notifier::ObserverBase Parent; |
---|
[822] | 80 | |
---|
| 81 | /// The reference type of the map; |
---|
[987] | 82 | typedef typename Container::reference Reference; |
---|
[822] | 83 | /// The const reference type of the map; |
---|
[987] | 84 | typedef typename Container::const_reference ConstReference; |
---|
[822] | 85 | |
---|
[1267] | 86 | |
---|
[1999] | 87 | /// \brief Constructor to attach the new map into the notifier. |
---|
[1703] | 88 | /// |
---|
[1999] | 89 | /// It constructs a map and attachs it into the notifier. |
---|
[946] | 90 | /// It adds all the items of the graph to the map. |
---|
[1999] | 91 | VectorMap(const Graph& graph) { |
---|
| 92 | Parent::attach(graph.getNotifier(Item())); |
---|
| 93 | container.resize(Parent::getNotifier()->maxId() + 1); |
---|
[946] | 94 | } |
---|
[822] | 95 | |
---|
[1703] | 96 | /// \brief Constructor uses given value to initialize the map. |
---|
| 97 | /// |
---|
| 98 | /// It constructs a map uses a given value to initialize the map. |
---|
[946] | 99 | /// It adds all the items of the graph to the map. |
---|
[1999] | 100 | VectorMap(const Graph& graph, const Value& value) { |
---|
| 101 | Parent::attach(graph.getNotifier(Item())); |
---|
| 102 | container.resize(Parent::getNotifier()->maxId() + 1, value); |
---|
[946] | 103 | } |
---|
[822] | 104 | |
---|
[1703] | 105 | /// \brief Copy constructor |
---|
| 106 | /// |
---|
| 107 | /// Copy constructor. |
---|
[1999] | 108 | VectorMap(const VectorMap& _copy) : Parent() { |
---|
[980] | 109 | if (_copy.attached()) { |
---|
[1999] | 110 | Parent::attach(*_copy.getNotifier()); |
---|
[980] | 111 | container = _copy.container; |
---|
[822] | 112 | } |
---|
| 113 | } |
---|
| 114 | |
---|
[1669] | 115 | private: |
---|
| 116 | |
---|
| 117 | VectorMap& operator=(const VectorMap&); |
---|
| 118 | |
---|
| 119 | public: |
---|
| 120 | |
---|
[1703] | 121 | /// \brief The subcript operator. |
---|
| 122 | /// |
---|
[946] | 123 | /// The subscript operator. The map can be subscripted by the |
---|
[1703] | 124 | /// actual items of the graph. |
---|
[987] | 125 | Reference operator[](const Key& key) { |
---|
[1999] | 126 | return container[Parent::getNotifier()->id(key)]; |
---|
[822] | 127 | } |
---|
| 128 | |
---|
[1703] | 129 | /// \brief The const subcript operator. |
---|
| 130 | /// |
---|
[946] | 131 | /// The const subscript operator. The map can be subscripted by the |
---|
| 132 | /// actual items of the graph. |
---|
[987] | 133 | ConstReference operator[](const Key& key) const { |
---|
[1999] | 134 | return container[Parent::getNotifier()->id(key)]; |
---|
[822] | 135 | } |
---|
| 136 | |
---|
[937] | 137 | |
---|
[1703] | 138 | /// \brief The setter function of the map. |
---|
| 139 | /// |
---|
[946] | 140 | /// It the same as operator[](key) = value expression. |
---|
[987] | 141 | void set(const Key& key, const Value& value) { |
---|
[946] | 142 | (*this)[key] = value; |
---|
[822] | 143 | } |
---|
[946] | 144 | |
---|
[1669] | 145 | protected: |
---|
| 146 | |
---|
| 147 | /// \brief Adds a new key to the map. |
---|
| 148 | /// |
---|
[1999] | 149 | /// It adds a new key to the map. It called by the observer notifier |
---|
[1703] | 150 | /// and it overrides the add() member function of the observer base. |
---|
| 151 | virtual void add(const Key& key) { |
---|
[1999] | 152 | int id = Parent::getNotifier()->id(key); |
---|
[822] | 153 | if (id >= (int)container.size()) { |
---|
| 154 | container.resize(id + 1); |
---|
| 155 | } |
---|
| 156 | } |
---|
[937] | 157 | |
---|
[1832] | 158 | /// \brief Adds more new keys to the map. |
---|
| 159 | /// |
---|
[1999] | 160 | /// It adds more new keys to the map. It called by the observer notifier |
---|
[1832] | 161 | /// and it overrides the add() member function of the observer base. |
---|
| 162 | virtual void add(const std::vector<Key>& keys) { |
---|
[1999] | 163 | int max = container.size() - 1; |
---|
[1832] | 164 | for (int i = 0; i < (int)keys.size(); ++i) { |
---|
[1999] | 165 | int id = Parent::getNotifier()->id(keys[i]); |
---|
| 166 | if (id >= max) { |
---|
| 167 | max = id; |
---|
| 168 | } |
---|
[1832] | 169 | } |
---|
[1999] | 170 | container.resize(max + 1); |
---|
[1832] | 171 | } |
---|
| 172 | |
---|
[1703] | 173 | /// \brief Erase a key from the map. |
---|
| 174 | /// |
---|
[1999] | 175 | /// Erase a key from the map. It called by the observer notifier |
---|
[946] | 176 | /// and it overrides the erase() member function of the observer base. |
---|
[1999] | 177 | virtual void erase(const Key& key) { |
---|
| 178 | container[Parent::getNotifier()->id(key)] = Value(); |
---|
| 179 | } |
---|
[822] | 180 | |
---|
[1832] | 181 | /// \brief Erase more keys from the map. |
---|
| 182 | /// |
---|
[1999] | 183 | /// Erase more keys from the map. It called by the observer notifier |
---|
[1832] | 184 | /// and it overrides the erase() member function of the observer base. |
---|
[1999] | 185 | virtual void erase(const std::vector<Key>& keys) { |
---|
| 186 | for (int i = 0; i < (int)keys.size(); ++i) { |
---|
| 187 | container[Parent::getNotifier()->id(keys[i])] = Value(); |
---|
| 188 | } |
---|
| 189 | } |
---|
[1832] | 190 | |
---|
[1703] | 191 | /// \brief Buildes the map. |
---|
| 192 | /// |
---|
[1999] | 193 | /// It buildes the map. It called by the observer notifier |
---|
[946] | 194 | /// and it overrides the build() member function of the observer base. |
---|
[1703] | 195 | virtual void build() { |
---|
[1999] | 196 | int size = Parent::getNotifier()->maxId() + 1; |
---|
| 197 | container.reserve(size); |
---|
| 198 | container.resize(size); |
---|
[946] | 199 | } |
---|
[937] | 200 | |
---|
[1703] | 201 | /// \brief Clear the map. |
---|
| 202 | /// |
---|
[1999] | 203 | /// It erase all items from the map. It called by the observer notifier |
---|
[946] | 204 | /// and it overrides the clear() member function of the observer base. |
---|
[1703] | 205 | virtual void clear() { |
---|
[822] | 206 | container.clear(); |
---|
| 207 | } |
---|
[1267] | 208 | |
---|
[822] | 209 | private: |
---|
| 210 | |
---|
| 211 | Container container; |
---|
| 212 | |
---|
[946] | 213 | }; |
---|
| 214 | |
---|
[822] | 215 | } |
---|
| 216 | |
---|
| 217 | #endif |
---|