COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/static_map.h @ 1703:eb90e3d6bddc

Last change on this file since 1703:eb90e3d6bddc was 1703:eb90e3d6bddc, checked in by Balazs Dezso, 14 years ago

Proper sized map type

File size: 9.2 KB
Line 
1/* -*- C++ -*-
2 * lemon/static_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_STATIC_MAP_H
18#define LEMON_STATIC_MAP_H
19
20#include <algorithm>
21#include <iostream>
22
23#include <lemon/utility.h>
24#include <lemon/bits/map_iterator.h>
25#include <lemon/bits/alteration_notifier.h>
26#include <lemon/error.h>
27#include <lemon/concept_check.h>
28#include <lemon/concept/maps.h>
29
30/// \ingroup graphmaps
31///
32///\file
33///\brief Static sized graph maps.
34
35namespace lemon {
36
37  /// \ingroup graphmaps
38  ///
39  /// \brief Graph map with static sized storage.
40  ///
41  /// The StaticMap template class is graph map structure what
42  /// does not update automatically the map when a key is added to or
43  /// erased from the map rather it throws an exception. This map factory
44  /// uses the allocators to implement the container functionality.
45  ///
46  /// \param Registry The AlterationNotifier that will notify this map.
47  /// \param Item The item type of the graph items.
48  /// \param Value The value type of the map.
49  ///
50  /// \author Balazs Dezso
51       
52
53  template <typename _Graph, typename _Item, typename _Value>
54  class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
55  public:
56
57    /// \brief Exception class for unsupported exceptions.
58    class UnsupportedOperation : public lemon::LogicError {
59    public:
60      virtual const char* exceptionName() const {
61        return "lemon::StaticMap::UnsupportedOperation";
62      }
63    };
64
65    typedef True AdaptibleTag;
66               
67    /// The graph type of the map.
68    typedef _Graph Graph;
69    /// The key type of the map.
70    typedef _Item Key;
71    /// The id map type of the map.
72    typedef AlterationNotifier<_Item> Registry;
73    /// The value type of the map.
74    typedef _Value Value;
75
76    /// The map type.
77    typedef StaticMap Map;
78    /// The base class of the map.
79    typedef typename Registry::ObserverBase Parent;
80
81  private:
82               
83    typedef std::vector<Value> Container;       
84
85  public:
86
87    /// \brief Constructor to attach the new map into the registry.
88    ///
89    /// It constructs a map and attachs it into the registry.
90    /// It adds all the items of the graph to the map.
91    StaticMap(const Graph& _g) : graph(&_g) {
92      attach(_g.getNotifier(_Item()));
93      build();
94    }
95
96    /// \brief Constructor uses given value to initialize the map.
97    ///
98    /// It constructs a map uses a given value to initialize the map.
99    /// It adds all the items of the graph to the map.     
100    StaticMap(const Graph& _g, const Value& _v) : graph(&_g) {
101      attach(_g.getNotifier(_Item()));
102      unsigned size = graph->maxId(_Item()) + 1;
103      container.reserve(size);
104      container.resize(size, _v);
105    }
106
107    /// \brief Copy constructor
108    ///
109    /// Copy constructor.
110    StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
111      if (_copy.attached()) {
112        attach(*_copy.getRegistry());
113        container = _copy.container;
114      }
115    }
116
117    /// \brief Destrcutor
118    ///
119    /// Destructor.
120    virtual ~StaticMap() {
121      clear();
122      if (attached()) {
123        detach();
124      }
125    }
126
127
128  private:
129
130    StaticMap& operator=(const StaticMap&);
131
132  protected:
133
134    using Parent::attach;
135    using Parent::detach;
136    using Parent::attached;
137
138    const Graph* getGraph() const {
139      return graph;
140    }
141
142  public:
143
144    typedef typename Container::reference Reference;
145    typedef typename Container::pointer Pointer;
146    typedef const Value ConstValue;
147    typedef typename Container::const_reference ConstReference;
148    typedef typename Container::const_pointer ConstPointer;
149
150    /// \brief The subcript operator.
151    ///
152    /// The subscript operator. The map can be subscripted by the
153    /// actual items of the graph.
154     
155    Reference operator[](const Key& key) {
156      return container[graph->id(key)];
157    }
158               
159    /// \brief The const subcript operator.
160    ///
161    /// The const subscript operator. The map can be subscripted by the
162    /// actual items of the graph.
163     
164    ConstReference operator[](const Key& key) const {
165      return container[graph->id(key)];
166    }
167
168
169    /// \brief The setter function of the map.
170    ///
171    /// It the same as operator[](key) = value expression.
172    ///
173    void set(const Key& key, const Value& value) {
174      (*this)[key] = value;
175    }
176
177  protected:
178
179    /// \brief Adds a new key to the map.
180    ///         
181    /// It adds a new key to the map. It called by the observer registry
182    /// and it overrides the add() member function of the observer base.
183     
184    void add(const Key&) {
185      throw UnsupportedOperation();
186    }
187
188    /// \brief Erases a key from the map.
189    ///
190    /// Erase a key from the map. It called by the observer registry
191    /// and it overrides the erase() member function of the observer base.     
192    void erase(const Key&) {
193      throw UnsupportedOperation();
194    }
195
196    /// Buildes the map.
197               
198    /// It buildes the map. It called by the observer registry
199    /// and it overrides the build() member function of the observer base.
200
201    void build() {
202      int size = graph->maxId(_Item()) + 1;
203      container.reserve(size);
204      container.resize(size);
205    }
206
207    /// Clear the map.
208
209    /// It erase all items from the map. It called by the observer registry
210    /// and it overrides the clear() member function of the observer base.     
211    void clear() {
212      container.clear();
213    }
214   
215  private:
216               
217    Container container;
218    const Graph *graph;
219
220  };
221
222  /// \e
223  template <typename _Base>
224  class StaticMappableGraphExtender : public _Base {
225  public:
226
227    typedef StaticMappableGraphExtender<_Base> Graph;
228    typedef _Base Parent;
229
230    typedef typename Parent::Node Node;
231    typedef typename Parent::NodeIt NodeIt;
232
233    typedef typename Parent::Edge Edge;
234    typedef typename Parent::EdgeIt EdgeIt;
235
236   
237    template <typename _Value>
238    class NodeMap
239      : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
240    public:
241      typedef StaticMappableGraphExtender Graph;
242      typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
243
244      NodeMap(const Graph& _g)
245        : Parent(_g) {}
246      NodeMap(const Graph& _g, const _Value& _v)
247        : Parent(_g, _v) {}
248
249      NodeMap& operator=(const NodeMap& cmap) {
250        return operator=<NodeMap>(cmap);
251      }
252
253
254      /// \brief Template assign operator.
255      ///
256      /// The given parameter should be conform to the ReadMap
257      /// concecpt and could be indiced by the current item set of
258      /// the NodeMap. In this case the value for each item
259      /// is assigned by the value of the given ReadMap.
260      template <typename CMap>
261      NodeMap& operator=(const CMap& cmap) {
262        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
263        const typename Parent::Graph* graph = Parent::getGraph();
264        Node it;
265        for (graph->first(it); it != INVALID; graph->next(it)) {
266          Parent::set(it, cmap[it]);
267        }
268        return *this;
269      }
270
271    };
272
273    template <typename _Value>
274    class EdgeMap
275      : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
276    public:
277      typedef StaticMappableGraphExtender Graph;
278      typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
279
280      EdgeMap(const Graph& _g)
281        : Parent(_g) {}
282      EdgeMap(const Graph& _g, const _Value& _v)
283        : Parent(_g, _v) {}
284
285      EdgeMap& operator=(const EdgeMap& cmap) {
286        return operator=<EdgeMap>(cmap);
287      }
288
289      template <typename CMap>
290      EdgeMap& operator=(const CMap& cmap) {
291        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
292        const typename Parent::Graph* graph = Parent::getGraph();
293        Edge it;
294        for (graph->first(it); it != INVALID; graph->next(it)) {
295          Parent::set(it, cmap[it]);
296        }
297        return *this;
298      }
299    };
300   
301  };
302
303  /// \e
304  template <typename _Base>
305  class StaticMappableUndirGraphExtender :
306    public StaticMappableGraphExtender<_Base> {
307  public:
308
309    typedef StaticMappableUndirGraphExtender Graph;
310    typedef StaticMappableGraphExtender<_Base> Parent;
311
312    typedef typename Parent::UndirEdge UndirEdge;
313
314    template <typename _Value>
315    class UndirEdgeMap
316      : public IterableMapExtender<StaticMap<Graph, UndirEdge, _Value> > {
317    public:
318      typedef StaticMappableUndirGraphExtender Graph;
319      typedef IterableMapExtender<
320        StaticMap<Graph, UndirEdge, _Value> > Parent;
321
322      UndirEdgeMap(const Graph& _g)
323        : Parent(_g) {}
324      UndirEdgeMap(const Graph& _g, const _Value& _v)
325        : Parent(_g, _v) {}
326
327      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
328        return operator=<UndirEdgeMap>(cmap);
329      }
330
331      template <typename CMap>
332      UndirEdgeMap& operator=(const CMap& cmap) {
333        checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
334        const typename Parent::Graph* graph = Parent::getGraph();
335        UndirEdge it;
336        for (graph->first(it); it != INVALID; graph->next(it)) {
337          Parent::set(it, cmap[it]);
338        }
339        return *this;
340      }
341    };
342
343
344  };
345
346}
347
348#endif
Note: See TracBrowser for help on using the repository browser.