COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/static_map.h @ 1961:8e19ca944727

Last change on this file since 1961:8e19ca944727 was 1961:8e19ca944727, checked in by Balazs Dezso, 14 years ago

Bug fix

File size: 16.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_STATIC_MAP_H
20#define LEMON_STATIC_MAP_H
21
22#include <algorithm>
23#include <iostream>
24
25#include <lemon/utility.h>
26#include <lemon/bits/map_extender.h>
27#include <lemon/bits/alteration_notifier.h>
28#include <lemon/error.h>
29#include <lemon/concept_check.h>
30#include <lemon/concept/maps.h>
31
32/// \ingroup graphmaps
33///
34///\file
35///\brief Static sized graph maps.
36
37namespace lemon {
38
39  /// \ingroup graphmaps
40  ///
41  /// \brief Graph map with static sized storage.
42  ///
43  /// The StaticMap template class is graph map structure what
44  /// does not indate automatically the map when a key is added to or
45  /// erased from the map rather it throws an exception. This map factory
46  /// uses the allocators to implement the container functionality.
47  ///
48  /// \param Registry The AlterationNotifier that will notify this map.
49  /// \param Item The item type of the graph items.
50  /// \param Value The value type of the map.
51  ///
52  /// \author Balazs Dezso
53       
54
55  template <typename _Graph, typename _Item, typename _Value>
56  class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
57  public:
58
59    /// \brief Exception class for unsinported exceptions.
60    class UnsinportedOperation : public lemon::LogicError {
61    public:
62      virtual const char* exceptionName() const {
63        return "lemon::StaticMap::UnsinportedOperation";
64      }
65    };
66
67  private:
68               
69    typedef std::vector<_Value> Container;     
70
71  public:
72
73    /// The graph type of the map.
74    typedef _Graph Graph;
75    /// The reference map tag.
76    typedef True ReferenceMapTag;
77
78    /// The key type of the map.
79    typedef _Item Key;
80    /// The value type of the map.
81    typedef _Value Value;
82    /// The const reference type of the map.
83    typedef typename Container::const_reference ConstReference;
84    /// The reference type of the map.
85    typedef typename Container::reference Reference;
86
87    typedef const Value ConstValue;
88    typedef Value* Pointer;
89    typedef const Value* ConstPointer;
90
91    typedef AlterationNotifier<_Item> Registry;
92
93    /// The map type.
94    typedef StaticMap Map;
95    /// The base class of the map.
96    typedef typename Registry::ObserverBase Parent;
97
98    /// \brief Constructor to attach the new map into the registry.
99    ///
100    /// It constructs a map and attachs it into the registry.
101    /// It adds all the items of the graph to the map.
102    StaticMap(const Graph& _g) : graph(&_g) {
103      attach(_g.getNotifier(_Item()));
104      build();
105    }
106
107    /// \brief Constructor uses given value to initialize the map.
108    ///
109    /// It constructs a map uses a given value to initialize the map.
110    /// It adds all the items of the graph to the map.     
111    StaticMap(const Graph& _g, const Value& _v) : graph(&_g) {
112      attach(_g.getNotifier(_Item()));
113      unsigned size = graph->maxId(_Item()) + 1;
114      container.reserve(size);
115      container.resize(size, _v);
116    }
117
118    /// \brief Copy constructor
119    ///
120    /// Copy constructor.
121    StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
122      if (_copy.attached()) {
123        attach(*_copy.getRegistry());
124        container = _copy.container;
125      }
126    }
127
128    /// \brief Destrcutor
129    ///
130    /// Destructor.
131    virtual ~StaticMap() {
132      clear();
133      if (attached()) {
134        detach();
135      }
136    }
137
138
139  private:
140
141    StaticMap& operator=(const StaticMap&);
142
143  protected:
144
145    using Parent::attach;
146    using Parent::detach;
147    using Parent::attached;
148
149    const Graph* getGraph() const {
150      return graph;
151    }
152
153  public:
154
155    /// \brief The subcript operator.
156    ///
157    /// The subscript operator. The map can be subscripted by the
158    /// actual items of the graph.
159     
160    Reference operator[](const Key& key) {
161      return container[graph->id(key)];
162    }
163               
164    /// \brief The const subcript operator.
165    ///
166    /// The const subscript operator. The map can be subscripted by the
167    /// actual items of the graph.
168     
169    ConstReference operator[](const Key& key) const {
170      return container[graph->id(key)];
171    }
172
173
174    /// \brief The setter function of the map.
175    ///
176    /// It the same as operator[](key) = value expression.
177    ///
178    void set(const Key& key, const Value& value) {
179      (*this)[key] = value;
180    }
181
182  protected:
183
184    /// \brief Adds a new key to the map.
185    ///         
186    /// It adds a new key to the map. It called by the observer registry
187    /// and it overrides the add() member function of the observer base.
188     
189    void add(const Key&) {
190      throw UnsinportedOperation();
191    }
192
193    /// \brief Erases a key from the map.
194    ///
195    /// Erase a key from the map. It called by the observer registry
196    /// and it overrides the erase() member function of the observer base.     
197    void erase(const Key&) {
198      throw UnsinportedOperation();
199    }
200
201    /// Buildes the map.
202               
203    /// It buildes the map. It called by the observer registry
204    /// and it overrides the build() member function of the observer base.
205
206    void build() {
207      int size = graph->maxId(_Item()) + 1;
208      container.reserve(size);
209      container.resize(size);
210    }
211
212    /// Clear the map.
213
214    /// It erase all items from the map. It called by the observer registry
215    /// and it overrides the clear() member function of the observer base.     
216    void clear() {
217      container.clear();
218    }
219   
220  private:
221               
222    Container container;
223    const Graph *graph;
224
225  };
226
227  /// \e
228  template <typename _Base>
229  class StaticMappableGraphExtender : public _Base {
230  public:
231
232    typedef StaticMappableGraphExtender<_Base> Graph;
233    typedef _Base Parent;
234
235    typedef typename Parent::Node Node;
236    typedef typename Parent::NodeIt NodeIt;
237
238    typedef typename Parent::Edge Edge;
239    typedef typename Parent::EdgeIt EdgeIt;
240
241   
242    template <typename _Value>
243    class NodeMap
244      : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
245    public:
246      typedef StaticMappableGraphExtender Graph;
247      typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
248
249      NodeMap(const Graph& _g)
250        : Parent(_g) {}
251      NodeMap(const Graph& _g, const _Value& _v)
252        : Parent(_g, _v) {}
253
254      NodeMap& operator=(const NodeMap& cmap) {
255        return operator=<NodeMap>(cmap);
256      }
257
258
259      /// \brief Template assign operator.
260      ///
261      /// The given parameter should be conform to the ReadMap
262      /// concecpt and could be indiced by the current item set of
263      /// the NodeMap. In this case the value for each item
264      /// is assigned by the value of the given ReadMap.
265      template <typename CMap>
266      NodeMap& operator=(const CMap& cmap) {
267        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
268        const typename Parent::Graph* graph = Parent::getGraph();
269        Node it;
270        for (graph->first(it); it != INVALID; graph->next(it)) {
271          Parent::set(it, cmap[it]);
272        }
273        return *this;
274      }
275
276    };
277
278    template <typename _Value>
279    class EdgeMap
280      : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
281    public:
282      typedef StaticMappableGraphExtender Graph;
283      typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
284
285      EdgeMap(const Graph& _g)
286        : Parent(_g) {}
287      EdgeMap(const Graph& _g, const _Value& _v)
288        : Parent(_g, _v) {}
289
290      EdgeMap& operator=(const EdgeMap& cmap) {
291        return operator=<EdgeMap>(cmap);
292      }
293
294      template <typename CMap>
295      EdgeMap& operator=(const CMap& cmap) {
296        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
297        const typename Parent::Graph* graph = Parent::getGraph();
298        Edge it;
299        for (graph->first(it); it != INVALID; graph->next(it)) {
300          Parent::set(it, cmap[it]);
301        }
302        return *this;
303      }
304    };
305   
306  };
307
308  /// \e
309  template <typename _Base>
310  class StaticMappableUGraphExtender :
311    public StaticMappableGraphExtender<_Base> {
312  public:
313
314    typedef StaticMappableUGraphExtender Graph;
315    typedef StaticMappableGraphExtender<_Base> Parent;
316
317    typedef typename Parent::UEdge UEdge;
318
319    template <typename _Value>
320    class UEdgeMap
321      : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
322    public:
323      typedef StaticMappableUGraphExtender Graph;
324      typedef IterableMapExtender<
325        StaticMap<Graph, UEdge, _Value> > Parent;
326
327      UEdgeMap(const Graph& _g)
328        : Parent(_g) {}
329      UEdgeMap(const Graph& _g, const _Value& _v)
330        : Parent(_g, _v) {}
331
332      UEdgeMap& operator=(const UEdgeMap& cmap) {
333        return operator=<UEdgeMap>(cmap);
334      }
335
336      template <typename CMap>
337      UEdgeMap& operator=(const CMap& cmap) {
338        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
339        const typename Parent::Graph* graph = Parent::getGraph();
340        UEdge it;
341        for (graph->first(it); it != INVALID; graph->next(it)) {
342          Parent::set(it, cmap[it]);
343        }
344        return *this;
345      }
346    };
347
348  };
349
350  template <typename _Base>
351  class StaticMappableBpUGraphExtender : public _Base {
352  public:
353
354    typedef _Base Parent;
355    typedef StaticMappableBpUGraphExtender Graph;
356
357    typedef typename Parent::Node Node;
358    typedef typename Parent::ANode ANode;
359    typedef typename Parent::BNode BNode;
360    typedef typename Parent::Edge Edge;
361    typedef typename Parent::UEdge UEdge;
362   
363    template <typename _Value>
364    class ANodeMap
365      : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
366    public:
367      typedef StaticMappableBpUGraphExtender Graph;
368      typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >
369      Parent;
370   
371      ANodeMap(const Graph& _g)
372        : Parent(_g) {}
373      ANodeMap(const Graph& _g, const _Value& _v)
374        : Parent(_g, _v) {}
375   
376      ANodeMap& operator=(const ANodeMap& cmap) {
377        return operator=<ANodeMap>(cmap);
378      }
379   
380
381      /// \brief Template assign operator.
382      ///
383      /// The given parameter should be conform to the ReadMap
384      /// concept and could be indiced by the current item set of
385      /// the ANodeMap. In this case the value for each item
386      /// is assigned by the value of the given ReadMap.
387      template <typename CMap>
388      ANodeMap& operator=(const CMap& cmap) {
389        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
390        const typename Parent::Graph* graph = Parent::getGraph();
391        ANode it;
392        for (graph->first(it); it != INVALID; graph->next(it)) {
393          Parent::set(it, cmap[it]);
394        }
395        return *this;
396      }
397   
398    };
399
400    template <typename _Value>
401    class BNodeMap
402      : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {
403    public:
404      typedef StaticMappableBpUGraphExtender Graph;
405      typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >
406      Parent;
407   
408      BNodeMap(const Graph& _g)
409        : Parent(_g) {}
410      BNodeMap(const Graph& _g, const _Value& _v)
411        : Parent(_g, _v) {}
412   
413      BNodeMap& operator=(const BNodeMap& cmap) {
414        return operator=<BNodeMap>(cmap);
415      }
416   
417
418      /// \brief Template assign operator.
419      ///
420      /// The given parameter should be conform to the ReadMap
421      /// concept and could be indiced by the current item set of
422      /// the BNodeMap. In this case the value for each item
423      /// is assigned by the value of the given ReadMap.
424      template <typename CMap>
425      BNodeMap& operator=(const CMap& cmap) {
426        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
427        const typename Parent::Graph* graph = Parent::getGraph();
428        BNode it;
429        for (graph->first(it); it != INVALID; graph->next(it)) {
430          Parent::set(it, cmap[it]);
431        }
432        return *this;
433      }
434   
435    };
436
437  protected:
438
439    template <typename _Value>
440    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
441    public:
442      typedef StaticMappableBpUGraphExtender Graph;
443
444      typedef Node Key;
445      typedef _Value Value;
446
447      /// The reference type of the map;
448      typedef typename BNodeMap<_Value>::Reference Reference;
449      /// The pointer type of the map;
450      typedef typename BNodeMap<_Value>::Pointer Pointer;
451     
452      /// The const value type of the map.
453      typedef const Value ConstValue;
454      /// The const reference type of the map;
455      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
456      /// The pointer type of the map;
457      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
458
459      typedef True ReferenceMapTag;
460
461      NodeMapBase(const Graph& _g)
462        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
463        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
464      }
465      NodeMapBase(const Graph& _g, const _Value& _v)
466        : graph(&_g), bNodeMap(_g, _v),
467          aNodeMap(_g, _v) {
468        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
469      }
470
471      virtual ~NodeMapBase() {     
472        if (Parent::NodeNotifier::ObserverBase::attached()) {
473          Parent::NodeNotifier::ObserverBase::detach();
474        }
475      }
476   
477      ConstReference operator[](const Key& node) const {
478        if (Parent::aNode(node)) {
479          return aNodeMap[node];
480        } else {
481          return bNodeMap[node];
482        }
483      }
484
485      Reference operator[](const Key& node) {
486        if (Parent::aNode(node)) {
487          return aNodeMap[node];
488        } else {
489          return bNodeMap[node];
490        }
491      }
492
493      void set(const Key& node, const Value& value) {
494        if (Parent::aNode(node)) {
495          aNodeMap.set(node, value);
496        } else {
497          bNodeMap.set(node, value);
498        }
499      }
500
501    protected:
502     
503      virtual void add(const Node&) {}
504      virtual void add(const std::vector<Node>&) {}
505      virtual void erase(const Node&) {}
506      virtual void erase(const std::vector<Node>&) {}
507      virtual void clear() {}
508      virtual void build() {}
509
510      const Graph* getGraph() const { return graph; }
511     
512    private:
513      const Graph* graph;
514      BNodeMap<_Value> bNodeMap;
515      ANodeMap<_Value> aNodeMap;
516    };
517   
518  public:
519
520    template <typename _Value>
521    class NodeMap
522      : public IterableMapExtender<NodeMapBase<_Value> > {
523    public:
524      typedef StaticMappableBpUGraphExtender Graph;
525      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
526   
527      NodeMap(const Graph& _g)
528        : Parent(_g) {}
529      NodeMap(const Graph& _g, const _Value& _v)
530        : Parent(_g, _v) {}
531   
532      NodeMap& operator=(const NodeMap& cmap) {
533        return operator=<NodeMap>(cmap);
534      }
535   
536
537      /// \brief Template assign operator.
538      ///
539      /// The given parameter should be conform to the ReadMap
540      /// concept and could be indiced by the current item set of
541      /// the NodeMap. In this case the value for each item
542      /// is assigned by the value of the given ReadMap.
543      template <typename CMap>
544      NodeMap& operator=(const CMap& cmap) {
545        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
546        const typename Parent::Graph* graph = Parent::getGraph();
547        Node it;
548        for (graph->first(it); it != INVALID; graph->next(it)) {
549          Parent::set(it, cmap[it]);
550        }
551        return *this;
552      }
553   
554    };
555
556
557
558    template <typename _Value>
559    class EdgeMap
560      : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
561    public:
562      typedef StaticMappableBpUGraphExtender Graph;
563      typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
564   
565      EdgeMap(const Graph& _g)
566        : Parent(_g) {}
567      EdgeMap(const Graph& _g, const _Value& _v)
568        : Parent(_g, _v) {}
569   
570      EdgeMap& operator=(const EdgeMap& cmap) {
571        return operator=<EdgeMap>(cmap);
572      }
573   
574      template <typename CMap>
575      EdgeMap& operator=(const CMap& cmap) {
576        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
577        const typename Parent::Graph* graph = Parent::getGraph();
578        Edge it;
579        for (graph->first(it); it != INVALID; graph->next(it)) {
580          Parent::set(it, cmap[it]);
581        }
582        return *this;
583      }
584    };
585
586    template <typename _Value>
587    class UEdgeMap
588      : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
589    public:
590      typedef StaticMappableBpUGraphExtender Graph;
591      typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >
592      Parent;
593   
594      UEdgeMap(const Graph& _g)
595        : Parent(_g) {}
596      UEdgeMap(const Graph& _g, const _Value& _v)
597        : Parent(_g, _v) {}
598   
599      UEdgeMap& operator=(const UEdgeMap& cmap) {
600        return operator=<UEdgeMap>(cmap);
601      }
602   
603      template <typename CMap>
604      UEdgeMap& operator=(const CMap& cmap) {
605        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
606        const typename Parent::Graph* graph = Parent::getGraph();
607        UEdge it;
608        for (graph->first(it); it != INVALID; graph->next(it)) {
609          Parent::set(it, cmap[it]);
610        }
611        return *this;
612      }
613    };
614 
615  };
616
617}
618
619#endif
Note: See TracBrowser for help on using the repository browser.