src/lemon/default_map.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1022 567f392d1d2e
child 1267 a93f94dbe3d3
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/lemon/default_map.h - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
alpar@921
    17
#ifndef LEMON_DEFAULT_MAP_H
alpar@921
    18
#define LEMON_DEFAULT_MAP_H
deba@822
    19
deba@822
    20
alpar@921
    21
#include <lemon/array_map.h>
alpar@921
    22
#include <lemon/vector_map.h>
deba@822
    23
deba@822
    24
///\ingroup graphmaps
deba@822
    25
///\file
klao@946
    26
///\brief Graph maps that construct and destruct
deba@822
    27
///their elements dynamically.
deba@822
    28
alpar@921
    29
namespace lemon {
deba@822
    30
deba@822
    31
/// \addtogroup graphmaps
deba@822
    32
/// @{
deba@822
    33
deba@822
    34
  /** The ArrayMap template class is graph map structure what
deba@822
    35
   *  automatically updates the map when a key is added to or erased from
alpar@987
    36
   *  the map. This map uses the VectorMap if the Value is a primitive
deba@822
    37
   *  type and the ArrayMap for the other cases.
deba@822
    38
   *
deba@822
    39
   *  The template parameter is the MapRegistry that the maps
alpar@987
    40
   *  will belong to and the Value.
deba@822
    41
   */
deba@822
    42
deba@822
    43
deba@822
    44
deba@980
    45
  template <typename _Graph, typename _Item, typename _ItemIt, typename _Value>
klao@946
    46
  struct DefaultMapSelector {
deba@980
    47
    typedef ArrayMap<_Graph, _Item, _ItemIt, _Value> Map;
klao@946
    48
  };
deba@822
    49
klao@946
    50
  // bool
deba@980
    51
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    52
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, bool> {
deba@980
    53
    typedef VectorMap<_Graph, _Item, bool> Map;
klao@946
    54
  };
deba@822
    55
klao@946
    56
  // char
deba@980
    57
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    58
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, char> {
deba@980
    59
    typedef VectorMap<_Graph, _Item, char> Map;
klao@946
    60
  };
deba@822
    61
deba@980
    62
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    63
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed char> {
deba@980
    64
    typedef VectorMap<_Graph, _Item, signed char> Map;
klao@946
    65
  };
deba@822
    66
deba@980
    67
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    68
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned char> {
deba@980
    69
    typedef VectorMap<_Graph, _Item, unsigned char> Map;
klao@946
    70
  };
deba@822
    71
deba@822
    72
klao@946
    73
  // int
deba@980
    74
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    75
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed int> {
deba@980
    76
    typedef VectorMap<_Graph, _Item, signed int> Map;
klao@946
    77
  };
deba@822
    78
deba@980
    79
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    80
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned int> {
deba@980
    81
    typedef VectorMap<_Graph, _Item, unsigned int> Map;
klao@946
    82
  };
deba@822
    83
deba@822
    84
klao@946
    85
  // short
deba@980
    86
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    87
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed short> {
deba@980
    88
    typedef VectorMap<_Graph, _Item, signed short> Map;
klao@946
    89
  };
deba@822
    90
deba@980
    91
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    92
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned short> {
deba@980
    93
    typedef VectorMap<_Graph, _Item, unsigned short> Map;
klao@946
    94
  };
klao@946
    95
klao@946
    96
klao@946
    97
  // long
deba@980
    98
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
    99
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed long> {
deba@980
   100
    typedef VectorMap<_Graph, _Item, signed long> Map;
klao@946
   101
  };
klao@946
   102
deba@980
   103
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
   104
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned long> {
deba@980
   105
    typedef VectorMap<_Graph, _Item, unsigned long> Map;
klao@946
   106
  };
klao@946
   107
klao@946
   108
  // \todo handling long long type
klao@946
   109
klao@946
   110
klao@946
   111
  // float
deba@980
   112
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
   113
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, float> {
deba@980
   114
    typedef VectorMap<_Graph, _Item, float> Map;
klao@946
   115
  };
klao@946
   116
klao@946
   117
klao@946
   118
  // double
deba@980
   119
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
   120
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, double> {
deba@980
   121
    typedef VectorMap<_Graph, _Item,  double> Map;
klao@946
   122
  };
klao@946
   123
klao@946
   124
klao@946
   125
  // long double
deba@980
   126
  template <typename _Graph, typename _Item, typename _ItemIt>
deba@980
   127
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, long double> {
deba@980
   128
    typedef VectorMap<_Graph, _Item, long double> Map;
klao@946
   129
  };
klao@946
   130
klao@946
   131
klao@946
   132
  // pointer
deba@980
   133
  template <typename _Graph, typename _Item, typename _ItemIt, typename _Ptr>
deba@980
   134
  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _Ptr*> {
deba@980
   135
    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
klao@946
   136
  };
klao@946
   137
klao@946
   138
klao@946
   139
klao@946
   140
  template <typename _Graph, 
klao@946
   141
	    typename _Item,
klao@946
   142
	    typename _ItemIt,
klao@946
   143
	    typename _Value>
deba@980
   144
  class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map {
klao@946
   145
  public:
deba@980
   146
    typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map Parent;
deba@980
   147
    typedef DefaultMap<_Graph, _Item, _ItemIt, _Value> Map;
klao@946
   148
    
klao@946
   149
    typedef typename Parent::Graph Graph;
alpar@987
   150
    typedef typename Parent::Value Value;
klao@946
   151
deba@980
   152
    DefaultMap(const Graph& _g) : Parent(_g) {}
alpar@987
   153
    DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
klao@946
   154
  };
klao@946
   155
klao@946
   156
klao@946
   157
klao@946
   158
  template <typename _Base> 
klao@946
   159
  class DefaultMappableGraphExtender : public _Base {
klao@946
   160
  public:
klao@946
   161
klao@946
   162
    typedef DefaultMappableGraphExtender<_Base> Graph;
klao@946
   163
    typedef _Base Parent;
klao@946
   164
klao@946
   165
    typedef typename Parent::Node Node;
klao@946
   166
    typedef typename Parent::NodeIt NodeIt;
klao@946
   167
klao@946
   168
    typedef typename Parent::Edge Edge;
klao@946
   169
    typedef typename Parent::EdgeIt EdgeIt;
klao@946
   170
klao@946
   171
    
klao@946
   172
    template <typename _Value>
deba@980
   173
    class NodeMap : public DefaultMap<Graph, Node, NodeIt, _Value> {
klao@946
   174
    public:
klao@1022
   175
      typedef DefaultMappableGraphExtender Graph;
deba@980
   176
      typedef DefaultMap<Graph, Node, NodeIt, _Value> Parent;
klao@946
   177
deba@980
   178
      NodeMap(const Graph& _g) 
deba@980
   179
	: Parent(_g) {}
klao@1022
   180
      NodeMap(const Graph& _g, const _Value& _v) 
deba@980
   181
	: Parent(_g, _v) {}
klao@946
   182
    };
klao@946
   183
klao@946
   184
    template <typename _Value>
deba@980
   185
    class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, _Value> {
klao@946
   186
    public:
klao@1022
   187
      typedef DefaultMappableGraphExtender Graph;
deba@980
   188
      typedef DefaultMap<Graph, Edge, EdgeIt, _Value> Parent;
klao@946
   189
deba@980
   190
      EdgeMap(const Graph& _g) 
deba@980
   191
	: Parent(_g) {}
klao@1022
   192
      EdgeMap(const Graph& _g, const _Value& _v) 
deba@980
   193
	: Parent(_g, _v) {}
klao@946
   194
    };
klao@946
   195
    
klao@946
   196
  };
klao@946
   197
klao@1022
   198
  template <typename _Base> 
klao@1022
   199
  class MappableUndirGraphExtender : 
klao@1022
   200
    public DefaultMappableGraphExtender<_Base> {
klao@1022
   201
  public:
klao@1022
   202
klao@1022
   203
    typedef MappableUndirGraphExtender Graph;
klao@1022
   204
    typedef DefaultMappableGraphExtender<_Base> Parent;
klao@1022
   205
klao@1022
   206
    typedef typename Parent::UndirEdge UndirEdge;
klao@1022
   207
    typedef typename Parent::UndirEdgeIt UndirEdgeIt;
klao@1022
   208
klao@1022
   209
    template <typename _Value>
klao@1022
   210
    class UndirEdgeMap :
klao@1022
   211
      public DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> {
klao@1022
   212
    public:
klao@1022
   213
      typedef MappableUndirGraphExtender Graph;
klao@1022
   214
      typedef DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> Parent;
klao@1022
   215
klao@1022
   216
      UndirEdgeMap(const Graph& _g) 
klao@1022
   217
	: Parent(_g) {}
klao@1022
   218
      UndirEdgeMap(const Graph& _g, const _Value& _v) 
klao@1022
   219
	: Parent(_g, _v) {}
klao@1022
   220
    };
klao@1022
   221
klao@1022
   222
klao@1022
   223
  };
deba@822
   224
deba@822
   225
}
deba@822
   226
deba@822
   227
#endif