COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/default_map.h @ 1820:22099ef840d7

Last change on this file since 1820:22099ef840d7 was 1820:22099ef840d7, checked in by Balazs Dezso, 14 years ago

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

File size: 14.7 KB
Line 
1/* -*- C++ -*-
2 * lemon/default_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_DEFAULT_MAP_H
18#define LEMON_DEFAULT_MAP_H
19
20
21#include <lemon/bits/array_map.h>
22#include <lemon/bits/vector_map.h>
23
24///\ingroup graphmapfactory
25///\file
26///\brief Graph maps that construct and destruct
27///their elements dynamically.
28
29namespace lemon {
30
31
32  template <typename _Graph, typename _Item, typename _Value>
33  struct DefaultMapSelector {
34    typedef ArrayMap<_Graph, _Item, _Value> Map;
35  };
36
37  // bool
38  template <typename _Graph, typename _Item>
39  struct DefaultMapSelector<_Graph, _Item, bool> {
40    typedef VectorMap<_Graph, _Item, bool> Map;
41  };
42
43  // char
44  template <typename _Graph, typename _Item>
45  struct DefaultMapSelector<_Graph, _Item, char> {
46    typedef VectorMap<_Graph, _Item, char> Map;
47  };
48
49  template <typename _Graph, typename _Item>
50  struct DefaultMapSelector<_Graph, _Item, signed char> {
51    typedef VectorMap<_Graph, _Item, signed char> Map;
52  };
53
54  template <typename _Graph, typename _Item>
55  struct DefaultMapSelector<_Graph, _Item, unsigned char> {
56    typedef VectorMap<_Graph, _Item, unsigned char> Map;
57  };
58
59
60  // int
61  template <typename _Graph, typename _Item>
62  struct DefaultMapSelector<_Graph, _Item, signed int> {
63    typedef VectorMap<_Graph, _Item, signed int> Map;
64  };
65
66  template <typename _Graph, typename _Item>
67  struct DefaultMapSelector<_Graph, _Item, unsigned int> {
68    typedef VectorMap<_Graph, _Item, unsigned int> Map;
69  };
70
71
72  // short
73  template <typename _Graph, typename _Item>
74  struct DefaultMapSelector<_Graph, _Item, signed short> {
75    typedef VectorMap<_Graph, _Item, signed short> Map;
76  };
77
78  template <typename _Graph, typename _Item>
79  struct DefaultMapSelector<_Graph, _Item, unsigned short> {
80    typedef VectorMap<_Graph, _Item, unsigned short> Map;
81  };
82
83
84  // long
85  template <typename _Graph, typename _Item>
86  struct DefaultMapSelector<_Graph, _Item, signed long> {
87    typedef VectorMap<_Graph, _Item, signed long> Map;
88  };
89
90  template <typename _Graph, typename _Item>
91  struct DefaultMapSelector<_Graph, _Item, unsigned long> {
92    typedef VectorMap<_Graph, _Item, unsigned long> Map;
93  };
94
95  // \todo handling long long type
96
97
98  // float
99  template <typename _Graph, typename _Item>
100  struct DefaultMapSelector<_Graph, _Item, float> {
101    typedef VectorMap<_Graph, _Item, float> Map;
102  };
103
104
105  // double
106  template <typename _Graph, typename _Item>
107  struct DefaultMapSelector<_Graph, _Item, double> {
108    typedef VectorMap<_Graph, _Item,  double> Map;
109  };
110
111
112  // long double
113  template <typename _Graph, typename _Item>
114  struct DefaultMapSelector<_Graph, _Item, long double> {
115    typedef VectorMap<_Graph, _Item, long double> Map;
116  };
117
118
119  // pointer
120  template <typename _Graph, typename _Item, typename _Ptr>
121  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
122    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
123  };
124
125  /// \e
126  template <
127    typename _Graph,
128    typename _Item,
129    typename _Value>
130  class DefaultMap
131    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
132  public:
133    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
134    typedef DefaultMap<_Graph, _Item, _Value> Map;
135   
136    typedef typename Parent::Graph Graph;
137    typedef typename Parent::Value Value;
138
139    DefaultMap(const Graph& _g) : Parent(_g) {}
140    DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
141
142  };
143
144
145  /// \e
146  template <typename _Base>
147  class MappableGraphExtender : public _Base {
148  public:
149
150    typedef MappableGraphExtender<_Base> Graph;
151    typedef _Base Parent;
152
153    typedef typename Parent::Node Node;
154    typedef typename Parent::NodeIt NodeIt;
155
156    typedef typename Parent::Edge Edge;
157    typedef typename Parent::EdgeIt EdgeIt;
158
159   
160    template <typename _Value>
161    class NodeMap
162      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
163    public:
164      typedef MappableGraphExtender Graph;
165      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
166
167      NodeMap(const Graph& _g)
168        : Parent(_g) {}
169      NodeMap(const Graph& _g, const _Value& _v)
170        : Parent(_g, _v) {}
171
172      NodeMap& operator=(const NodeMap& cmap) {
173        return operator=<NodeMap>(cmap);
174      }
175
176
177      /// \brief Template assign operator.
178      ///
179      /// The given parameter should be conform to the ReadMap
180      /// concecpt and could be indiced by the current item set of
181      /// the NodeMap. In this case the value for each item
182      /// is assigned by the value of the given ReadMap.
183      template <typename CMap>
184      NodeMap& operator=(const CMap& cmap) {
185        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
186        const typename Parent::Graph* graph = Parent::getGraph();
187        Node it;
188        for (graph->first(it); it != INVALID; graph->next(it)) {
189          Parent::set(it, cmap[it]);
190        }
191        return *this;
192      }
193
194    };
195
196    template <typename _Value>
197    class EdgeMap
198      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
199    public:
200      typedef MappableGraphExtender Graph;
201      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
202
203      EdgeMap(const Graph& _g)
204        : Parent(_g) {}
205      EdgeMap(const Graph& _g, const _Value& _v)
206        : Parent(_g, _v) {}
207
208      EdgeMap& operator=(const EdgeMap& cmap) {
209        return operator=<EdgeMap>(cmap);
210      }
211
212      template <typename CMap>
213      EdgeMap& operator=(const CMap& cmap) {
214        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
215        const typename Parent::Graph* graph = Parent::getGraph();
216        Edge it;
217        for (graph->first(it); it != INVALID; graph->next(it)) {
218          Parent::set(it, cmap[it]);
219        }
220        return *this;
221      }
222    };
223   
224  };
225
226  /// \e
227  template <typename _Base>
228  class MappableUndirGraphExtender :
229    public MappableGraphExtender<_Base> {
230  public:
231
232    typedef MappableUndirGraphExtender Graph;
233    typedef MappableGraphExtender<_Base> Parent;
234
235    typedef typename Parent::UndirEdge UndirEdge;
236
237    template <typename _Value>
238    class UndirEdgeMap
239      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
240    public:
241      typedef MappableUndirGraphExtender Graph;
242      typedef IterableMapExtender<
243        DefaultMap<Graph, UndirEdge, _Value> > Parent;
244
245      UndirEdgeMap(const Graph& _g)
246        : Parent(_g) {}
247      UndirEdgeMap(const Graph& _g, const _Value& _v)
248        : Parent(_g, _v) {}
249
250      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
251        return operator=<UndirEdgeMap>(cmap);
252      }
253
254      template <typename CMap>
255      UndirEdgeMap& operator=(const CMap& cmap) {
256        checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
257        const typename Parent::Graph* graph = Parent::getGraph();
258        UndirEdge it;
259        for (graph->first(it); it != INVALID; graph->next(it)) {
260          Parent::set(it, cmap[it]);
261        }
262        return *this;
263      }
264    };
265
266
267  };
268
269
270  template <typename _Base>
271  class MappableUndirBipartiteGraphExtender : public _Base {
272  public:
273
274    typedef _Base Parent;
275    typedef MappableUndirBipartiteGraphExtender Graph;
276
277    typedef typename Parent::Node Node;
278    typedef typename Parent::UpperNode UpperNode;
279    typedef typename Parent::LowerNode LowerNode;
280    typedef typename Parent::Edge Edge;
281    typedef typename Parent::UndirEdge UndirEdge;
282   
283    template <typename _Value>
284    class UpperNodeMap
285      : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {
286    public:
287      typedef MappableUndirBipartiteGraphExtender Graph;
288      typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> >
289      Parent;
290   
291      UpperNodeMap(const Graph& _g)
292        : Parent(_g) {}
293      UpperNodeMap(const Graph& _g, const _Value& _v)
294        : Parent(_g, _v) {}
295   
296      UpperNodeMap& operator=(const UpperNodeMap& cmap) {
297        return operator=<UpperNodeMap>(cmap);
298      }
299   
300
301      /// \brief Template assign operator.
302      ///
303      /// The given parameter should be conform to the ReadMap
304      /// concept and could be indiced by the current item set of
305      /// the UpperNodeMap. In this case the value for each item
306      /// is assigned by the value of the given ReadMap.
307      template <typename CMap>
308      UpperNodeMap& operator=(const CMap& cmap) {
309        checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
310        const typename Parent::Graph* graph = Parent::getGraph();
311        UpperNode it;
312        for (graph->first(it); it != INVALID; graph->next(it)) {
313          Parent::set(it, cmap[it]);
314        }
315        return *this;
316      }
317   
318    };
319
320    template <typename _Value>
321    class LowerNodeMap
322      : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {
323    public:
324      typedef MappableUndirBipartiteGraphExtender Graph;
325      typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> >
326      Parent;
327   
328      LowerNodeMap(const Graph& _g)
329        : Parent(_g) {}
330      LowerNodeMap(const Graph& _g, const _Value& _v)
331        : Parent(_g, _v) {}
332   
333      LowerNodeMap& operator=(const LowerNodeMap& cmap) {
334        return operator=<LowerNodeMap>(cmap);
335      }
336   
337
338      /// \brief Template assign operator.
339      ///
340      /// The given parameter should be conform to the ReadMap
341      /// concept and could be indiced by the current item set of
342      /// the LowerNodeMap. In this case the value for each item
343      /// is assigned by the value of the given ReadMap.
344      template <typename CMap>
345      LowerNodeMap& operator=(const CMap& cmap) {
346        checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
347        const typename Parent::Graph* graph = Parent::getGraph();
348        LowerNode it;
349        for (graph->first(it); it != INVALID; graph->next(it)) {
350          Parent::set(it, cmap[it]);
351        }
352        return *this;
353      }
354   
355    };
356
357  protected:
358
359    template <typename _Value>
360    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
361    public:
362      typedef MappableUndirBipartiteGraphExtender Graph;
363
364      typedef Node Key;
365      typedef _Value Value;
366
367      /// The reference type of the map;
368      typedef typename LowerNodeMap<_Value>::Reference Reference;
369      /// The pointer type of the map;
370      typedef typename LowerNodeMap<_Value>::Pointer Pointer;
371     
372      /// The const value type of the map.
373      typedef const Value ConstValue;
374      /// The const reference type of the map;
375      typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
376      /// The pointer type of the map;
377      typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
378
379      typedef True ReferenceMapTag;
380
381      NodeMapBase(const Graph& _g)
382        : graph(&_g), lowerMap(_g), upperMap(_g) {
383        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
384      }
385      NodeMapBase(const Graph& _g, const _Value& _v)
386        : graph(&_g), lowerMap(_g, _v),
387          upperMap(_g, _v) {
388        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
389      }
390
391      virtual ~NodeMapBase() {     
392        if (Parent::NodeNotifier::ObserverBase::attached()) {
393          Parent::NodeNotifier::ObserverBase::detach();
394        }
395      }
396   
397      ConstReference operator[](const Key& node) const {
398        if (Parent::upper(node)) {
399          return upperMap[node];
400        } else {
401          return lowerMap[node];
402        }
403      }
404
405      Reference operator[](const Key& node) {
406        if (Parent::upper(node)) {
407          return upperMap[node];
408        } else {
409          return lowerMap[node];
410        }
411      }
412
413      void set(const Key& node, const Value& value) {
414        if (Parent::upper(node)) {
415          upperMap.set(node, value);
416        } else {
417          lowerMap.set(node, value);
418        }
419      }
420
421    protected:
422     
423      virtual void add(const Node&) {}
424      virtual void erase(const Node&) {}
425      virtual void clear() {}
426      virtual void build() {}
427
428      const Graph* getGraph() const { return graph; }
429     
430    private:
431      const Graph* graph;
432      LowerNodeMap<_Value> lowerMap;
433      UpperNodeMap<_Value> upperMap;
434    };
435   
436  public:
437
438    template <typename _Value>
439    class NodeMap
440      : public IterableMapExtender<NodeMapBase<_Value> > {
441    public:
442      typedef MappableUndirBipartiteGraphExtender Graph;
443      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
444   
445      NodeMap(const Graph& _g)
446        : Parent(_g) {}
447      NodeMap(const Graph& _g, const _Value& _v)
448        : Parent(_g, _v) {}
449   
450      NodeMap& operator=(const NodeMap& cmap) {
451        return operator=<NodeMap>(cmap);
452      }
453   
454
455      /// \brief Template assign operator.
456      ///
457      /// The given parameter should be conform to the ReadMap
458      /// concept and could be indiced by the current item set of
459      /// the NodeMap. In this case the value for each item
460      /// is assigned by the value of the given ReadMap.
461      template <typename CMap>
462      NodeMap& operator=(const CMap& cmap) {
463        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
464        const typename Parent::Graph* graph = Parent::getGraph();
465        Node it;
466        for (graph->first(it); it != INVALID; graph->next(it)) {
467          Parent::set(it, cmap[it]);
468        }
469        return *this;
470      }
471   
472    };
473
474
475
476    template <typename _Value>
477    class EdgeMap
478      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
479    public:
480      typedef MappableUndirBipartiteGraphExtender Graph;
481      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
482   
483      EdgeMap(const Graph& _g)
484        : Parent(_g) {}
485      EdgeMap(const Graph& _g, const _Value& _v)
486        : Parent(_g, _v) {}
487   
488      EdgeMap& operator=(const EdgeMap& cmap) {
489        return operator=<EdgeMap>(cmap);
490      }
491   
492      template <typename CMap>
493      EdgeMap& operator=(const CMap& cmap) {
494        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
495        const typename Parent::Graph* graph = Parent::getGraph();
496        Edge it;
497        for (graph->first(it); it != INVALID; graph->next(it)) {
498          Parent::set(it, cmap[it]);
499        }
500        return *this;
501      }
502    };
503
504    template <typename _Value>
505    class UndirEdgeMap
506      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
507    public:
508      typedef MappableUndirBipartiteGraphExtender Graph;
509      typedef IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> >
510      Parent;
511   
512      UndirEdgeMap(const Graph& _g)
513        : Parent(_g) {}
514      UndirEdgeMap(const Graph& _g, const _Value& _v)
515        : Parent(_g, _v) {}
516   
517      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
518        return operator=<UndirEdgeMap>(cmap);
519      }
520   
521      template <typename CMap>
522      UndirEdgeMap& operator=(const CMap& cmap) {
523        checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
524        const typename Parent::Graph* graph = Parent::getGraph();
525        UndirEdge it;
526        for (graph->first(it); it != INVALID; graph->next(it)) {
527          Parent::set(it, cmap[it]);
528        }
529        return *this;
530      }
531    };
532 
533  };
534
535}
536
537#endif
Note: See TracBrowser for help on using the repository browser.