Changeset 1999:2ff283124dfc in lemon-0.x for lemon/bits/vector_map.h
- Timestamp:
- 03/06/06 11:28:37 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2609
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/vector_map.h
r1996 r1999 17 17 */ 18 18 19 #ifndef LEMON_ VECTOR_MAP_H20 #define LEMON_ VECTOR_MAP_H19 #ifndef LEMON_BITS_VECTOR_MAP_H 20 #define LEMON_BITS_VECTOR_MAP_H 21 21 22 22 #include <vector> 23 23 #include <algorithm> 24 24 25 #include <lemon/bits/traits.h> 25 26 #include <lemon/bits/utility.h> 26 #include <lemon/bits/map_extender.h> 27 27 28 #include <lemon/bits/alteration_notifier.h> 28 #include <lemon/concept_check.h> 29 #include <lemon/concept/maps.h> 30 31 /// \ingroup graphbits 29 30 ///\ingroup graphbits 32 31 /// 33 32 ///\file 34 33 ///\brief Vector based graph maps. 35 36 34 namespace lemon { 37 35 … … 41 39 /// 42 40 /// The VectorMap template class is graph map structure what 43 /// automatically indates the map when a key is added to or erased from41 /// automatically updates the map when a key is added to or erased from 44 42 /// the map. This map factory uses the allocators to implement 45 43 /// the container functionality. This map factory 46 44 /// uses the std::vector to implement the container function. 47 45 /// 48 /// \param RegistryThe AlterationNotifier that will notify this map.46 /// \param Notifier The AlterationNotifier that will notify this map. 49 47 /// \param Item The item type of the graph items. 50 48 /// \param Value The value type of the map. 51 49 /// 52 /// \author Balazs Dezso 53 54 template < 55 typename _Graph, 56 typename _Item, 57 typename _Value 58 > 59 class VectorMap : public AlterationNotifier<_Item>::ObserverBase { 50 /// \author Balazs Dezso 51 template <typename _Graph, typename _Item, typename _Value> 52 class VectorMap 53 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 60 54 private: 61 55 … … 67 61 /// The graph type of the map. 68 62 typedef _Graph Graph; 63 /// The item type of the map. 64 typedef _Item Item; 69 65 /// The reference map tag. 70 66 typedef True ReferenceMapTag; … … 75 71 typedef _Value Value; 76 72 77 typedef AlterationNotifier<_Item> Registry; 73 /// The notifier type. 74 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; 78 75 79 76 /// The map type. 80 77 typedef VectorMap Map; 81 78 /// The base class of the map. 82 typedef typename Registry::ObserverBase Parent;79 typedef typename Notifier::ObserverBase Parent; 83 80 84 81 /// The reference type of the map; 85 82 typedef typename Container::reference Reference; 86 /// The pointer type of the map;87 typedef typename Container::pointer Pointer;88 89 /// The const value type of the map.90 typedef const Value ConstValue;91 83 /// The const reference type of the map; 92 84 typedef typename Container::const_reference ConstReference; 93 /// The pointer type of the map; 94 typedef typename Container::const_pointer ConstPointer; 95 96 97 /// \brief Constructor to attach the new map into the registry. 98 /// 99 /// It constructs a map and attachs it into the registry. 85 86 87 /// \brief Constructor to attach the new map into the notifier. 88 /// 89 /// It constructs a map and attachs it into the notifier. 100 90 /// It adds all the items of the graph to the map. 101 VectorMap(const Graph& _g) : graph(&_g) {102 attach(_g.getNotifier(_Item()));103 build();91 VectorMap(const Graph& graph) { 92 Parent::attach(graph.getNotifier(Item())); 93 container.resize(Parent::getNotifier()->maxId() + 1); 104 94 } 105 95 … … 108 98 /// It constructs a map uses a given value to initialize the map. 109 99 /// It adds all the items of the graph to the map. 110 VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {111 attach(_g.getNotifier(_Item()));112 container.resize( graph->maxId(_Item()) + 1, _v);100 VectorMap(const Graph& graph, const Value& value) { 101 Parent::attach(graph.getNotifier(Item())); 102 container.resize(Parent::getNotifier()->maxId() + 1, value); 113 103 } 114 104 … … 116 106 /// 117 107 /// Copy constructor. 118 VectorMap(const VectorMap& _copy) 119 : Parent(), graph(_copy.getGraph()) { 108 VectorMap(const VectorMap& _copy) : Parent() { 120 109 if (_copy.attached()) { 121 attach(*_copy.getRegistry());110 Parent::attach(*_copy.getNotifier()); 122 111 container = _copy.container; 123 112 } 124 113 } 125 114 126 /// \brief Destrcutor127 ///128 /// Destructor.129 virtual ~VectorMap() {130 if (attached()) {131 detach();132 }133 }134 135 136 115 private: 137 116 138 117 VectorMap& operator=(const VectorMap&); 139 140 protected:141 142 using Parent::attach;143 using Parent::detach;144 using Parent::attached;145 146 const Graph* getGraph() const {147 return graph;148 }149 118 150 119 public: … … 155 124 /// actual items of the graph. 156 125 Reference operator[](const Key& key) { 157 return container[ graph->id(key)];126 return container[Parent::getNotifier()->id(key)]; 158 127 } 159 128 … … 163 132 /// actual items of the graph. 164 133 ConstReference operator[](const Key& key) const { 165 return container[ graph->id(key)];134 return container[Parent::getNotifier()->id(key)]; 166 135 } 167 136 … … 178 147 /// \brief Adds a new key to the map. 179 148 /// 180 /// It adds a new key to the map. It called by the observer registry149 /// It adds a new key to the map. It called by the observer notifier 181 150 /// and it overrides the add() member function of the observer base. 182 151 virtual void add(const Key& key) { 183 int id = graph->id(key);152 int id = Parent::getNotifier()->id(key); 184 153 if (id >= (int)container.size()) { 185 154 container.resize(id + 1); … … 189 158 /// \brief Adds more new keys to the map. 190 159 /// 191 /// It adds more new keys to the map. It called by the observer registry160 /// It adds more new keys to the map. It called by the observer notifier 192 161 /// and it overrides the add() member function of the observer base. 193 162 virtual void add(const std::vector<Key>& keys) { 163 int max = container.size() - 1; 194 164 for (int i = 0; i < (int)keys.size(); ++i) { 195 add(keys[i]); 196 } 165 int id = Parent::getNotifier()->id(keys[i]); 166 if (id >= max) { 167 max = id; 168 } 169 } 170 container.resize(max + 1); 197 171 } 198 172 199 173 /// \brief Erase a key from the map. 200 174 /// 201 /// Erase a key from the map. It called by the observer registry175 /// Erase a key from the map. It called by the observer notifier 202 176 /// and it overrides the erase() member function of the observer base. 203 virtual void erase(const Key&) {} 177 virtual void erase(const Key& key) { 178 container[Parent::getNotifier()->id(key)] = Value(); 179 } 204 180 205 181 /// \brief Erase more keys from the map. 206 182 /// 207 /// Erase more keys from the map. It called by the observer registry183 /// Erase more keys from the map. It called by the observer notifier 208 184 /// and it overrides the erase() member function of the observer base. 209 virtual void erase(const std::vector<Key>&) {} 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 } 210 190 211 191 /// \brief Buildes the map. 212 192 /// 213 /// It buildes the map. It called by the observer registry193 /// It buildes the map. It called by the observer notifier 214 194 /// and it overrides the build() member function of the observer base. 215 195 virtual void build() { 216 container.resize(graph->maxId(_Item()) + 1); 196 int size = Parent::getNotifier()->maxId() + 1; 197 container.reserve(size); 198 container.resize(size); 217 199 } 218 200 219 201 /// \brief Clear the map. 220 202 /// 221 /// It erase all items from the map. It called by the observer registry203 /// It erase all items from the map. It called by the observer notifier 222 204 /// and it overrides the clear() member function of the observer base. 223 205 virtual void clear() { … … 228 210 229 211 Container container; 230 const Graph *graph;231 212 232 213 };
Note: See TracChangeset
for help on using the changeset viewer.