Update INSTALL file.
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);
103 /// \brief Copy constructor
105 /// Copy constructor.
106 VectorMap(const VectorMap& _copy) : Parent() {
107 if (_copy.attached()) {
108 Parent::attach(*_copy.notifier());
109 container = _copy.container;
113 /// \brief Assign operator.
115 /// This operator assigns for each item in the map the
116 /// value mapped to the same item in the copied map.
117 /// The parameter map should be indiced with the same
118 /// itemset because this assign operator does not change
119 /// the container of the map.
120 VectorMap& operator=(const VectorMap& cmap) {
121 return operator=<VectorMap>(cmap);
125 /// \brief Template assign operator.
127 /// The given parameter should be conform to the ReadMap
128 /// concecpt and could be indiced by the current item set of
129 /// the NodeMap. In this case the value for each item
130 /// is assigned by the value of the given ReadMap.
131 template <typename CMap>
132 VectorMap& operator=(const CMap& cmap) {
133 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
134 const typename Parent::Notifier* nf = Parent::notifier();
136 for (nf->first(it); it != INVALID; nf->next(it)) {
144 /// \brief The subcript operator.
146 /// The subscript operator. The map can be subscripted by the
147 /// actual items of the graph.
148 Reference operator[](const Key& key) {
149 return container[Parent::notifier()->id(key)];
152 /// \brief The const subcript operator.
154 /// The const subscript operator. The map can be subscripted by the
155 /// actual items of the graph.
156 ConstReference operator[](const Key& key) const {
157 return container[Parent::notifier()->id(key)];
161 /// \brief The setter function of the map.
163 /// It the same as operator[](key) = value expression.
164 void set(const Key& key, const Value& value) {
165 (*this)[key] = value;
170 /// \brief Adds a new key to the map.
172 /// It adds a new key to the map. It called by the observer notifier
173 /// and it overrides the add() member function of the observer base.
174 virtual void add(const Key& key) {
175 int id = Parent::notifier()->id(key);
176 if (id >= int(container.size())) {
177 container.resize(id + 1);
181 /// \brief Adds more new keys to the map.
183 /// It adds more new keys to the map. It called by the observer notifier
184 /// and it overrides the add() member function of the observer base.
185 virtual void add(const std::vector<Key>& keys) {
186 int max = container.size() - 1;
187 for (int i = 0; i < int(keys.size()); ++i) {
188 int id = Parent::notifier()->id(keys[i]);
193 container.resize(max + 1);
196 /// \brief Erase a key from the map.
198 /// Erase a key from the map. It called by the observer notifier
199 /// and it overrides the erase() member function of the observer base.
200 virtual void erase(const Key& key) {
201 container[Parent::notifier()->id(key)] = Value();
204 /// \brief Erase more keys from the map.
206 /// Erase more keys from the map. It called by the observer notifier
207 /// and it overrides the erase() member function of the observer base.
208 virtual void erase(const std::vector<Key>& keys) {
209 for (int i = 0; i < int(keys.size()); ++i) {
210 container[Parent::notifier()->id(keys[i])] = Value();
214 /// \brief Buildes the map.
216 /// It buildes the map. It called by the observer notifier
217 /// and it overrides the build() member function of the observer base.
218 virtual void build() {
219 int size = Parent::notifier()->maxId() + 1;
220 container.reserve(size);
221 container.resize(size);
224 /// \brief Clear the map.
226 /// It erase all items from the map. It called by the observer notifier
227 /// and it overrides the clear() member function of the observer base.
228 virtual void clear() {