1.1 --- a/lemon/bits/array_map.h Mon Mar 06 09:38:19 2006 +0000
1.2 +++ b/lemon/bits/array_map.h Mon Mar 06 10:28:37 2006 +0000
1.3 @@ -20,15 +20,13 @@
1.4 #define LEMON_BITS_ARRAY_MAP_H
1.5
1.6 #include <memory>
1.7 -#include <lemon/bits/map_extender.h>
1.8 +
1.9 +#include <lemon/bits/traits.h>
1.10 #include <lemon/bits/alteration_notifier.h>
1.11 -#include <lemon/concept_check.h>
1.12 -#include <lemon/concept/maps.h>
1.13
1.14 /// \ingroup graphbits
1.15 /// \file
1.16 -/// \brief Graph maps that construct and destruct
1.17 -/// their elements dynamically.
1.18 +/// \brief Graph map based on the array storage.
1.19
1.20 namespace lemon {
1.21
1.22 @@ -37,22 +35,20 @@
1.23 /// \brief Graph map based on the array storage.
1.24 ///
1.25 /// The ArrayMap template class is graph map structure what
1.26 - /// automatically indates the map when a key is added to or erased from
1.27 + /// automatically updates the map when a key is added to or erased from
1.28 /// the map. This map uses the allocators to implement
1.29 /// the container functionality.
1.30 ///
1.31 - /// The template parameter is the AlterationNotifier that the maps
1.32 - /// will belong to and the Value.
1.33 -
1.34 - template <typename _Graph,
1.35 - typename _Item,
1.36 - typename _Value>
1.37 - class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
1.38 -
1.39 - typedef _Item Item;
1.40 + /// The template parameter is the Graph the current Item type and
1.41 + /// the Value type of the map.
1.42 + template <typename _Graph, typename _Item, typename _Value>
1.43 + class ArrayMap
1.44 + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
1.45 public:
1.46 /// The graph type of the maps.
1.47 typedef _Graph Graph;
1.48 + /// The item type of the map.
1.49 + typedef _Item Item;
1.50 /// The reference map tag.
1.51 typedef True ReferenceMapTag;
1.52
1.53 @@ -60,37 +56,33 @@
1.54 typedef _Item Key;
1.55 /// The value type of the map.
1.56 typedef _Value Value;
1.57 +
1.58 /// The const reference type of the map.
1.59 typedef const _Value& ConstReference;
1.60 /// The reference type of the map.
1.61 typedef _Value& Reference;
1.62
1.63 - typedef const Value ConstValue;
1.64 - typedef Value* Pointer;
1.65 - typedef const Value* ConstPointer;
1.66 -
1.67 - typedef AlterationNotifier<_Item> Registry;
1.68 + /// The notifier type.
1.69 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
1.70
1.71 /// The MapBase of the Map which imlements the core regisitry function.
1.72 - typedef typename Registry::ObserverBase Parent;
1.73 + typedef typename Notifier::ObserverBase Parent;
1.74
1.75 -
1.76 -
1.77 private:
1.78 typedef std::allocator<Value> Allocator;
1.79
1.80 -
1.81 public:
1.82
1.83 /// \brief Graph initialized map constructor.
1.84 ///
1.85 /// Graph initialized map constructor.
1.86 - ArrayMap(const Graph& _g) : graph(&_g) {
1.87 + ArrayMap(const Graph& graph) {
1.88 + Parent::attach(graph.getNotifier(Item()));
1.89 + allocate_memory();
1.90 + Notifier* notifier = Parent::getNotifier();
1.91 Item it;
1.92 - attach(_g.getNotifier(Item()));
1.93 - allocate_memory();
1.94 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.95 - int id = graph->id(it);;
1.96 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.97 + int id = notifier->id(it);;
1.98 allocator.construct(&(values[id]), Value());
1.99 }
1.100 }
1.101 @@ -98,29 +90,31 @@
1.102 /// \brief Constructor to use default value to initialize the map.
1.103 ///
1.104 /// It constructs a map and initialize all of the the map.
1.105 - ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
1.106 + ArrayMap(const Graph& graph, const Value& value) {
1.107 + Parent::attach(graph.getNotifier(Item()));
1.108 + allocate_memory();
1.109 + Notifier* notifier = Parent::getNotifier();
1.110 Item it;
1.111 - attach(_g.getNotifier(_Item()));
1.112 - allocate_memory();
1.113 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.114 - int id = graph->id(it);;
1.115 - allocator.construct(&(values[id]), _v);
1.116 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.117 + int id = notifier->id(it);;
1.118 + allocator.construct(&(values[id]), value);
1.119 }
1.120 }
1.121
1.122 /// \brief Constructor to copy a map of the same map type.
1.123 ///
1.124 /// Constructor to copy a map of the same map type.
1.125 - ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
1.126 + ArrayMap(const ArrayMap& copy) : Parent() {
1.127 if (copy.attached()) {
1.128 - attach(*copy.getRegistry());
1.129 + attach(*copy.getNotifier());
1.130 }
1.131 capacity = copy.capacity;
1.132 if (capacity == 0) return;
1.133 values = allocator.allocate(capacity);
1.134 + Notifier* notifier = Parent::getNotifier();
1.135 Item it;
1.136 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.137 - int id = graph->id(it);;
1.138 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.139 + int id = notifier->id(it);;
1.140 allocator.construct(&(values[id]), copy.values[id]);
1.141 }
1.142 }
1.143 @@ -145,11 +139,6 @@
1.144 using Parent::detach;
1.145 using Parent::attached;
1.146
1.147 - const Graph* getGraph() {
1.148 - return graph;
1.149 - }
1.150 -
1.151 -
1.152 public:
1.153
1.154 /// \brief The subscript operator.
1.155 @@ -157,7 +146,7 @@
1.156 /// The subscript operator. The map can be subscripted by the
1.157 /// actual keys of the graph.
1.158 Value& operator[](const Key& key) {
1.159 - int id = graph->id(key);
1.160 + int id = Parent::getNotifier()->id(key);
1.161 return values[id];
1.162 }
1.163
1.164 @@ -166,7 +155,7 @@
1.165 /// The const subscript operator. The map can be subscripted by the
1.166 /// actual keys of the graph.
1.167 const Value& operator[](const Key& key) const {
1.168 - int id = graph->id(key);
1.169 + int id = Parent::getNotifier()->id(key);
1.170 return values[id];
1.171 }
1.172
1.173 @@ -180,10 +169,13 @@
1.174
1.175 protected:
1.176
1.177 - /// Add a new key to the map. It called by the map registry.
1.178 -
1.179 + /// \brief Adds a new key to the map.
1.180 + ///
1.181 + /// It adds a new key to the map. It called by the observer notifier
1.182 + /// and it overrides the add() member function of the observer base.
1.183 virtual void add(const Key& key) {
1.184 - int id = graph->id(key);
1.185 + Notifier* notifier = Parent::getNotifier();
1.186 + int id = notifier->id(key);
1.187 if (id >= capacity) {
1.188 int new_capacity = (capacity == 0 ? 1 : capacity);
1.189 while (new_capacity <= id) {
1.190 @@ -191,8 +183,8 @@
1.191 }
1.192 Value* new_values = allocator.allocate(new_capacity);
1.193 Item it;
1.194 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.195 - int jd = graph->id(it);;
1.196 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.197 + int jd = notifier->id(it);;
1.198 if (id != jd) {
1.199 allocator.construct(&(new_values[jd]), values[jd]);
1.200 allocator.destroy(&(values[jd]));
1.201 @@ -205,10 +197,15 @@
1.202 allocator.construct(&(values[id]), Value());
1.203 }
1.204
1.205 + /// \brief Adds more new keys to the map.
1.206 + ///
1.207 + /// It adds more new keys to the map. It called by the observer notifier
1.208 + /// and it overrides the add() member function of the observer base.
1.209 virtual void add(const std::vector<Key>& keys) {
1.210 + Notifier* notifier = Parent::getNotifier();
1.211 int max_id = -1;
1.212 for (int i = 0; i < (int)keys.size(); ++i) {
1.213 - int id = graph->id(keys[i]);
1.214 + int id = notifier->id(keys[i]);
1.215 if (id > max_id) {
1.216 max_id = id;
1.217 }
1.218 @@ -220,11 +217,11 @@
1.219 }
1.220 Value* new_values = allocator.allocate(new_capacity);
1.221 Item it;
1.222 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.223 - int id = graph->id(it);
1.224 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.225 + int id = notifier->id(it);
1.226 bool found = false;
1.227 for (int i = 0; i < (int)keys.size(); ++i) {
1.228 - int jd = graph->id(keys[i]);
1.229 + int jd = notifier->id(keys[i]);
1.230 if (id == jd) {
1.231 found = true;
1.232 break;
1.233 @@ -239,39 +236,55 @@
1.234 capacity = new_capacity;
1.235 }
1.236 for (int i = 0; i < (int)keys.size(); ++i) {
1.237 - int id = graph->id(keys[i]);
1.238 + int id = notifier->id(keys[i]);
1.239 allocator.construct(&(values[id]), Value());
1.240 }
1.241 }
1.242
1.243 - /// Erase a key from the map. It called by the map registry.
1.244 -
1.245 + /// \brief Erase a key from the map.
1.246 + ///
1.247 + /// Erase a key from the map. It called by the observer notifier
1.248 + /// and it overrides the erase() member function of the observer base.
1.249 virtual void erase(const Key& key) {
1.250 - int id = graph->id(key);
1.251 + int id = Parent::getNotifier()->id(key);
1.252 allocator.destroy(&(values[id]));
1.253 }
1.254
1.255 + /// \brief Erase more keys from the map.
1.256 + ///
1.257 + /// Erase more keys from the map. It called by the observer notifier
1.258 + /// and it overrides the erase() member function of the observer base.
1.259 virtual void erase(const std::vector<Key>& keys) {
1.260 for (int i = 0; i < (int)keys.size(); ++i) {
1.261 - int id = graph->id(keys[i]);
1.262 + int id = Parent::getNotifier()->id(keys[i]);
1.263 allocator.destroy(&(values[id]));
1.264 }
1.265 }
1.266
1.267 + /// \brief Buildes the map.
1.268 + ///
1.269 + /// It buildes the map. It called by the observer notifier
1.270 + /// and it overrides the build() member function of the observer base.
1.271 virtual void build() {
1.272 + Notifier* notifier = Parent::getNotifier();
1.273 allocate_memory();
1.274 Item it;
1.275 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.276 - int id = graph->id(it);;
1.277 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.278 + int id = notifier->id(it);;
1.279 allocator.construct(&(values[id]), Value());
1.280 }
1.281 }
1.282
1.283 + /// \brief Clear the map.
1.284 + ///
1.285 + /// It erase all items from the map. It called by the observer notifier
1.286 + /// and it overrides the clear() member function of the observer base.
1.287 virtual void clear() {
1.288 + Notifier* notifier = Parent::getNotifier();
1.289 if (capacity != 0) {
1.290 Item it;
1.291 - for (graph->first(it); it != INVALID; graph->next(it)) {
1.292 - int id = graph->id(it);
1.293 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.294 + int id = notifier->id(it);
1.295 allocator.destroy(&(values[id]));
1.296 }
1.297 allocator.deallocate(values, capacity);
1.298 @@ -282,7 +295,7 @@
1.299 private:
1.300
1.301 void allocate_memory() {
1.302 - int max_id = graph->maxId(_Item());
1.303 + int max_id = Parent::getNotifier()->maxId();
1.304 if (max_id == -1) {
1.305 capacity = 0;
1.306 values = 0;
1.307 @@ -295,7 +308,6 @@
1.308 values = allocator.allocate(capacity);
1.309 }
1.310
1.311 - const Graph* graph;
1.312 int capacity;
1.313 Value* values;
1.314 Allocator allocator;