COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/default_map.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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