COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/default_map.h @ 1966:65765fb5eb2f

Last change on this file since 1966:65765fb5eb2f was 1966:65765fb5eb2f, checked in by Balazs Dezso, 14 years ago

Easier checking in DEBUG mode

I hope we should not test ArrayMap? longer

The vector map checks its limits in debug mode what
helps us to find the bad memory accesses in the maps

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