COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/default_map.h @ 1965:71b3bc042c47

Last change on this file since 1965:71b3bc042c47 was 1965:71b3bc042c47, checked in by Balazs Dezso, 14 years ago

Compilation with G++ -ansi

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