COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/default_map.h @ 1910:f95eea8c34b0

Last change on this file since 1910:f95eea8c34b0 was 1910:f95eea8c34b0, checked in by Balazs Dezso, 18 years ago

Bipartite => Bp
Upper => A
Lower => B

+ some bug fix

File size: 16.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/default_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Groin 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///\ingroin 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 MappableEdgeSetExtender : public _Base {
229  public:
230
231    typedef MappableEdgeSetExtender<_Base> Graph;
232    typedef _Base Parent;
233
234    typedef typename Parent::Edge Edge;
235    typedef typename Parent::EdgeIt EdgeIt;
236
237    template <typename _Value>
238    class EdgeMap
239      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
240    public:
241      typedef MappableEdgeSetExtender Graph;
242      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
243
244      EdgeMap(const Graph& _g)
245        : Parent(_g) {}
246      EdgeMap(const Graph& _g, const _Value& _v)
247        : Parent(_g, _v) {}
248
249      EdgeMap& operator=(const EdgeMap& cmap) {
250        return operator=<EdgeMap>(cmap);
251      }
252
253      template <typename CMap>
254      EdgeMap& operator=(const CMap& cmap) {
255        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
256        const typename Parent::Graph* graph = Parent::getGraph();
257        Edge it;
258        for (graph->first(it); it != INVALID; graph->next(it)) {
259          Parent::set(it, cmap[it]);
260        }
261        return *this;
262      }
263    };
264   
265  };
266
267  /// \e
268  template <typename _Base>
269  class MappableUGraphExtender :
270    public MappableGraphExtender<_Base> {
271  public:
272
273    typedef MappableUGraphExtender Graph;
274    typedef MappableGraphExtender<_Base> Parent;
275
276    typedef typename Parent::UEdge UEdge;
277
278    template <typename _Value>
279    class UEdgeMap
280      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
281    public:
282      typedef MappableUGraphExtender Graph;
283      typedef IterableMapExtender<
284        DefaultMap<Graph, UEdge, _Value> > Parent;
285
286      UEdgeMap(const Graph& _g)
287        : Parent(_g) {}
288      UEdgeMap(const Graph& _g, const _Value& _v)
289        : Parent(_g, _v) {}
290
291      UEdgeMap& operator=(const UEdgeMap& cmap) {
292        return operator=<UEdgeMap>(cmap);
293      }
294
295      template <typename CMap>
296      UEdgeMap& operator=(const CMap& cmap) {
297        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
298        const typename Parent::Graph* graph = Parent::getGraph();
299        UEdge it;
300        for (graph->first(it); it != INVALID; graph->next(it)) {
301          Parent::set(it, cmap[it]);
302        }
303        return *this;
304      }
305    };
306
307
308  };
309
310  /// \e
311  template <typename _Base>
312  class MappableUEdgeSetExtender :
313    public MappableEdgeSetExtender<_Base> {
314  public:
315
316    typedef MappableUEdgeSetExtender Graph;
317    typedef MappableEdgeSetExtender<_Base> Parent;
318
319    typedef typename Parent::UEdge UEdge;
320
321    template <typename _Value>
322    class UEdgeMap
323      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
324    public:
325      typedef MappableUEdgeSetExtender Graph;
326      typedef IterableMapExtender<
327        DefaultMap<Graph, UEdge, _Value> > Parent;
328
329      UEdgeMap(const Graph& _g)
330        : Parent(_g) {}
331      UEdgeMap(const Graph& _g, const _Value& _v)
332        : Parent(_g, _v) {}
333
334      UEdgeMap& operator=(const UEdgeMap& cmap) {
335        return operator=<UEdgeMap>(cmap);
336      }
337
338      template <typename CMap>
339      UEdgeMap& operator=(const CMap& cmap) {
340        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
341        const typename Parent::Graph* graph = Parent::getGraph();
342        UEdge it;
343        for (graph->first(it); it != INVALID; graph->next(it)) {
344          Parent::set(it, cmap[it]);
345        }
346        return *this;
347      }
348    };
349
350
351  };
352
353
354  template <typename _Base>
355  class MappableBpUGraphExtender : public _Base {
356  public:
357
358    typedef _Base Parent;
359    typedef MappableBpUGraphExtender Graph;
360
361    typedef typename Parent::Node Node;
362    typedef typename Parent::ANode ANode;
363    typedef typename Parent::BNode BNode;
364    typedef typename Parent::Edge Edge;
365    typedef typename Parent::UEdge UEdge;
366   
367    template <typename _Value>
368    class ANodeMap
369      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
370    public:
371      typedef MappableBpUGraphExtender Graph;
372      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
373      Parent;
374   
375      ANodeMap(const Graph& _g)
376        : Parent(_g) {}
377      ANodeMap(const Graph& _g, const _Value& _v)
378        : Parent(_g, _v) {}
379   
380      ANodeMap& operator=(const ANodeMap& cmap) {
381        return operator=<ANodeMap>(cmap);
382      }
383   
384
385      /// \brief Template assign operator.
386      ///
387      /// The given parameter should be conform to the ReadMap
388      /// concept and could be indiced by the current item set of
389      /// the ANodeMap. In this case the value for each item
390      /// is assigned by the value of the given ReadMap.
391      template <typename CMap>
392      ANodeMap& operator=(const CMap& cmap) {
393        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
394        const typename Parent::Graph* graph = Parent::getGraph();
395        ANode it;
396        for (graph->first(it); it != INVALID; graph->next(it)) {
397          Parent::set(it, cmap[it]);
398        }
399        return *this;
400      }
401   
402    };
403
404    template <typename _Value>
405    class BNodeMap
406      : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
407    public:
408      typedef MappableBpUGraphExtender Graph;
409      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
410      Parent;
411   
412      BNodeMap(const Graph& _g)
413        : Parent(_g) {}
414      BNodeMap(const Graph& _g, const _Value& _v)
415        : Parent(_g, _v) {}
416   
417      BNodeMap& operator=(const BNodeMap& cmap) {
418        return operator=<BNodeMap>(cmap);
419      }
420   
421
422      /// \brief Template assign operator.
423      ///
424      /// The given parameter should be conform to the ReadMap
425      /// concept and could be indiced by the current item set of
426      /// the BNodeMap. In this case the value for each item
427      /// is assigned by the value of the given ReadMap.
428      template <typename CMap>
429      BNodeMap& operator=(const CMap& cmap) {
430        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
431        const typename Parent::Graph* graph = Parent::getGraph();
432        BNode it;
433        for (graph->first(it); it != INVALID; graph->next(it)) {
434          Parent::set(it, cmap[it]);
435        }
436        return *this;
437      }
438   
439    };
440
441  protected:
442
443    template <typename _Value>
444    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
445    public:
446      typedef MappableBpUGraphExtender Graph;
447
448      typedef Node Key;
449      typedef _Value Value;
450
451      /// The reference type of the map;
452      typedef typename BNodeMap<_Value>::Reference Reference;
453      /// The pointer type of the map;
454      typedef typename BNodeMap<_Value>::Pointer Pointer;
455     
456      /// The const value type of the map.
457      typedef const Value ConstValue;
458      /// The const reference type of the map;
459      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
460      /// The pointer type of the map;
461      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
462
463      typedef True ReferenceMapTag;
464
465      NodeMapBase(const Graph& _g)
466        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
467        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
468      }
469      NodeMapBase(const Graph& _g, const _Value& _v)
470        : graph(&_g), bNodeMap(_g, _v),
471          aNodeMap(_g, _v) {
472        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
473      }
474
475      virtual ~NodeMapBase() {     
476        if (Parent::NodeNotifier::ObserverBase::attached()) {
477          Parent::NodeNotifier::ObserverBase::detach();
478        }
479      }
480   
481      ConstReference operator[](const Key& node) const {
482        if (Parent::aNode(node)) {
483          return aNodeMap[node];
484        } else {
485          return bNodeMap[node];
486        }
487      }
488
489      Reference operator[](const Key& node) {
490        if (Parent::aNode(node)) {
491          return aNodeMap[node];
492        } else {
493          return bNodeMap[node];
494        }
495      }
496
497      void set(const Key& node, const Value& value) {
498        if (Parent::aNode(node)) {
499          aNodeMap.set(node, value);
500        } else {
501          bNodeMap.set(node, value);
502        }
503      }
504
505    protected:
506     
507      virtual void add(const Node&) {}
508      virtual void erase(const Node&) {}
509      virtual void clear() {}
510      virtual void build() {}
511
512      const Graph* getGraph() const { return graph; }
513     
514    private:
515      const Graph* graph;
516      BNodeMap<_Value> bNodeMap;
517      ANodeMap<_Value> aNodeMap;
518    };
519   
520  public:
521
522    template <typename _Value>
523    class NodeMap
524      : public IterableMapExtender<NodeMapBase<_Value> > {
525    public:
526      typedef MappableBpUGraphExtender Graph;
527      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
528   
529      NodeMap(const Graph& _g)
530        : Parent(_g) {}
531      NodeMap(const Graph& _g, const _Value& _v)
532        : Parent(_g, _v) {}
533   
534      NodeMap& operator=(const NodeMap& cmap) {
535        return operator=<NodeMap>(cmap);
536      }
537   
538
539      /// \brief Template assign operator.
540      ///
541      /// The given parameter should be conform to the ReadMap
542      /// concept and could be indiced by the current item set of
543      /// the NodeMap. In this case the value for each item
544      /// is assigned by the value of the given ReadMap.
545      template <typename CMap>
546      NodeMap& operator=(const CMap& cmap) {
547        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
548        const typename Parent::Graph* graph = Parent::getGraph();
549        Node it;
550        for (graph->first(it); it != INVALID; graph->next(it)) {
551          Parent::set(it, cmap[it]);
552        }
553        return *this;
554      }
555   
556    };
557
558
559
560    template <typename _Value>
561    class EdgeMap
562      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
563    public:
564      typedef MappableBpUGraphExtender Graph;
565      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
566   
567      EdgeMap(const Graph& _g)
568        : Parent(_g) {}
569      EdgeMap(const Graph& _g, const _Value& _v)
570        : Parent(_g, _v) {}
571   
572      EdgeMap& operator=(const EdgeMap& cmap) {
573        return operator=<EdgeMap>(cmap);
574      }
575   
576      template <typename CMap>
577      EdgeMap& operator=(const CMap& cmap) {
578        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
579        const typename Parent::Graph* graph = Parent::getGraph();
580        Edge it;
581        for (graph->first(it); it != INVALID; graph->next(it)) {
582          Parent::set(it, cmap[it]);
583        }
584        return *this;
585      }
586    };
587
588    template <typename _Value>
589    class UEdgeMap
590      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
591    public:
592      typedef MappableBpUGraphExtender Graph;
593      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
594      Parent;
595   
596      UEdgeMap(const Graph& _g)
597        : Parent(_g) {}
598      UEdgeMap(const Graph& _g, const _Value& _v)
599        : Parent(_g, _v) {}
600   
601      UEdgeMap& operator=(const UEdgeMap& cmap) {
602        return operator=<UEdgeMap>(cmap);
603      }
604   
605      template <typename CMap>
606      UEdgeMap& operator=(const CMap& cmap) {
607        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
608        const typename Parent::Graph* graph = Parent::getGraph();
609        UEdge it;
610        for (graph->first(it); it != INVALID; graph->next(it)) {
611          Parent::set(it, cmap[it]);
612        }
613        return *this;
614      }
615    };
616 
617  };
618
619}
620
621#endif
Note: See TracBrowser for help on using the repository browser.