1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_VECTOR_MAP_H
20 #define LEMON_BITS_VECTOR_MAP_H
25 #include <lemon/core.h>
26 #include <lemon/bits/alteration_notifier.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concepts/maps.h>
34 ///\brief Vector based graph maps.
37 /// \ingroup graphbits
39 /// \brief Graph map based on the std::vector storage.
41 /// The VectorMap template class is graph map structure what
42 /// automatically updates the map when a key is added to or erased from
43 /// the map. This map type uses the std::vector to store the values.
45 /// \tparam _Notifier The AlterationNotifier that will notify this map.
46 /// \tparam _Item The item type of the graph items.
47 /// \tparam _Value The value type of the map.
48 /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
49 template <typename _Graph, typename _Item, typename _Value>
51 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
54 /// The container type of the map.
55 typedef std::vector<_Value> Container;
59 /// The graph type of the map.
61 /// The item type of the map.
63 /// The reference map tag.
64 typedef True ReferenceMapTag;
66 /// The key type of the map.
68 /// The value type of the map.
71 /// The notifier type.
72 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
75 typedef VectorMap Map;
76 /// The base class of the map.
77 typedef typename Notifier::ObserverBase Parent;
79 /// The reference type of the map;
80 typedef typename Container::reference Reference;
81 /// The const reference type of the map;
82 typedef typename Container::const_reference ConstReference;
85 /// \brief Constructor to attach the new map into the notifier.
87 /// It constructs a map and attachs it into the notifier.
88 /// It adds all the items of the graph to the map.
89 VectorMap(const Graph& graph) {
90 Parent::attach(graph.notifier(Item()));
91 container.resize(Parent::notifier()->maxId() + 1);
94 /// \brief Constructor uses given value to initialize the map.
96 /// It constructs a map uses a given value to initialize the map.
97 /// It adds all the items of the graph to the map.
98 VectorMap(const Graph& graph, const Value& value) {
99 Parent::attach(graph.notifier(Item()));
100 container.resize(Parent::notifier()->maxId() + 1, value);
104 /// \brief Copy constructor
106 /// Copy constructor.
107 VectorMap(const VectorMap& _copy) : Parent() {
108 if (_copy.attached()) {
109 Parent::attach(*_copy.notifier());
110 container = _copy.container;
114 /// \brief Assign operator.
116 /// This operator assigns for each item in the map the
117 /// value mapped to the same item in the copied map.
118 /// The parameter map should be indiced with the same
119 /// itemset because this assign operator does not change
120 /// the container of the map.
121 VectorMap& operator=(const VectorMap& cmap) {
122 return operator=<VectorMap>(cmap);
126 /// \brief Template assign operator.
128 /// The given parameter should be conform to the ReadMap
129 /// concecpt and could be indiced by the current item set of
130 /// the NodeMap. In this case the value for each item
131 /// is assigned by the value of the given ReadMap.
132 template <typename CMap>
133 VectorMap& operator=(const CMap& cmap) {
134 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
135 const typename Parent::Notifier* nf = Parent::notifier();
137 for (nf->first(it); it != INVALID; nf->next(it)) {
145 /// \brief The subcript operator.
147 /// The subscript operator. The map can be subscripted by the
148 /// actual items of the graph.
149 Reference operator[](const Key& key) {
150 return container[Parent::notifier()->id(key)];
153 /// \brief The const subcript operator.
155 /// The const subscript operator. The map can be subscripted by the
156 /// actual items of the graph.
157 ConstReference operator[](const Key& key) const {
158 return container[Parent::notifier()->id(key)];
162 /// \brief The setter function of the map.
164 /// It the same as operator[](key) = value expression.
165 void set(const Key& key, const Value& value) {
166 (*this)[key] = value;
171 /// \brief Adds a new key to the map.
173 /// It adds a new key to the map. It called by the observer notifier
174 /// and it overrides the add() member function of the observer base.
175 virtual void add(const Key& key) {
176 int id = Parent::notifier()->id(key);
177 if (id >= int(container.size())) {
178 container.resize(id + 1);
182 /// \brief Adds more new keys to the map.
184 /// It adds more new keys to the map. It called by the observer notifier
185 /// and it overrides the add() member function of the observer base.
186 virtual void add(const std::vector<Key>& keys) {
187 int max = container.size() - 1;
188 for (int i = 0; i < int(keys.size()); ++i) {
189 int id = Parent::notifier()->id(keys[i]);
194 container.resize(max + 1);
197 /// \brief Erase a key from the map.
199 /// Erase a key from the map. It called by the observer notifier
200 /// and it overrides the erase() member function of the observer base.
201 virtual void erase(const Key& key) {
202 container[Parent::notifier()->id(key)] = Value();
205 /// \brief Erase more keys from the map.
207 /// Erase more keys from the map. It called by the observer notifier
208 /// and it overrides the erase() member function of the observer base.
209 virtual void erase(const std::vector<Key>& keys) {
210 for (int i = 0; i < int(keys.size()); ++i) {
211 container[Parent::notifier()->id(keys[i])] = Value();
215 /// \brief Buildes the map.
217 /// It buildes the map. It called by the observer notifier
218 /// and it overrides the build() member function of the observer base.
219 virtual void build() {
220 int size = Parent::notifier()->maxId() + 1;
221 container.reserve(size);
222 container.resize(size);
225 /// \brief Clear the map.
227 /// It erase all items from the map. It called by the observer notifier
228 /// and it overrides the clear() member function of the observer base.
229 virtual void clear() {