lemon/concepts/maps.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 600 6ac5d9ae1d3d
parent 440 88ed40ad0d4f
child 706 703ebf476a1d
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@25
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@25
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@25
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25
     8
 *
alpar@25
     9
 * Permission to use, modify and distribute this software is granted
alpar@25
    10
 * provided that this copyright notice appears in all copies. For
alpar@25
    11
 * precise terms see the accompanying LICENSE file.
alpar@25
    12
 *
alpar@25
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@25
    14
 * express or implied, and with no claim as to its suitability for any
alpar@25
    15
 * purpose.
alpar@25
    16
 *
alpar@25
    17
 */
alpar@25
    18
deba@514
    19
#ifndef LEMON_CONCEPTS_MAPS_H
deba@514
    20
#define LEMON_CONCEPTS_MAPS_H
alpar@25
    21
deba@220
    22
#include <lemon/core.h>
alpar@25
    23
#include <lemon/concept_check.h>
alpar@25
    24
kpeter@314
    25
///\ingroup map_concepts
alpar@25
    26
///\file
kpeter@114
    27
///\brief The concept of maps.
alpar@25
    28
alpar@25
    29
namespace lemon {
alpar@25
    30
alpar@25
    31
  namespace concepts {
kpeter@79
    32
kpeter@314
    33
    /// \addtogroup map_concepts
alpar@25
    34
    /// @{
alpar@25
    35
alpar@25
    36
    /// Readable map concept
kpeter@28
    37
kpeter@28
    38
    /// Readable map concept.
kpeter@28
    39
    ///
alpar@25
    40
    template<typename K, typename T>
alpar@25
    41
    class ReadMap
alpar@25
    42
    {
alpar@25
    43
    public:
kpeter@35
    44
      /// The key type of the map.
kpeter@79
    45
      typedef K Key;
alpar@210
    46
      /// \brief The value type of the map.
alpar@210
    47
      /// (The type of objects associated with the keys).
alpar@25
    48
      typedef T Value;
alpar@25
    49
kpeter@79
    50
      /// Returns the value associated with the given key.
alpar@209
    51
      Value operator[](const Key &) const {
kpeter@94
    52
        return *static_cast<Value *>(0);
kpeter@94
    53
      }
alpar@25
    54
alpar@25
    55
      template<typename _ReadMap>
alpar@25
    56
      struct Constraints {
alpar@209
    57
        void constraints() {
alpar@209
    58
          Value val = m[key];
alpar@209
    59
          val = m[key];
alpar@209
    60
          typename _ReadMap::Value own_val = m[own_key];
alpar@209
    61
          own_val = m[own_key];
alpar@25
    62
alpar@209
    63
          ignore_unused_variable_warning(key);
alpar@209
    64
          ignore_unused_variable_warning(val);
alpar@209
    65
          ignore_unused_variable_warning(own_key);
alpar@209
    66
          ignore_unused_variable_warning(own_val);
alpar@209
    67
        }
alpar@209
    68
        const Key& key;
alpar@209
    69
        const typename _ReadMap::Key& own_key;
alpar@209
    70
        const _ReadMap& m;
alpar@25
    71
      };
kpeter@79
    72
alpar@25
    73
    };
alpar@25
    74
alpar@25
    75
alpar@25
    76
    /// Writable map concept
kpeter@79
    77
kpeter@28
    78
    /// Writable map concept.
kpeter@28
    79
    ///
alpar@25
    80
    template<typename K, typename T>
alpar@25
    81
    class WriteMap
alpar@25
    82
    {
alpar@25
    83
    public:
kpeter@35
    84
      /// The key type of the map.
kpeter@79
    85
      typedef K Key;
alpar@210
    86
      /// \brief The value type of the map.
alpar@210
    87
      /// (The type of objects associated with the keys).
alpar@25
    88
      typedef T Value;
alpar@25
    89
kpeter@79
    90
      /// Sets the value associated with the given key.
kpeter@79
    91
      void set(const Key &, const Value &) {}
alpar@25
    92
kpeter@79
    93
      /// Default constructor.
alpar@25
    94
      WriteMap() {}
alpar@25
    95
alpar@25
    96
      template <typename _WriteMap>
alpar@25
    97
      struct Constraints {
alpar@209
    98
        void constraints() {
alpar@209
    99
          m.set(key, val);
alpar@209
   100
          m.set(own_key, own_val);
kpeter@79
   101
alpar@209
   102
          ignore_unused_variable_warning(key);
alpar@209
   103
          ignore_unused_variable_warning(val);
alpar@209
   104
          ignore_unused_variable_warning(own_key);
alpar@209
   105
          ignore_unused_variable_warning(own_val);
alpar@209
   106
        }
alpar@209
   107
        const Key& key;
alpar@209
   108
        const Value& val;
alpar@209
   109
        const typename _WriteMap::Key& own_key;
alpar@209
   110
        const typename _WriteMap::Value& own_val;
alpar@209
   111
        _WriteMap& m;
alpar@25
   112
      };
alpar@25
   113
    };
alpar@25
   114
kpeter@48
   115
    /// Read/writable map concept
kpeter@79
   116
kpeter@28
   117
    /// Read/writable map concept.
kpeter@28
   118
    ///
alpar@25
   119
    template<typename K, typename T>
alpar@25
   120
    class ReadWriteMap : public ReadMap<K,T>,
alpar@209
   121
                         public WriteMap<K,T>
alpar@25
   122
    {
alpar@25
   123
    public:
kpeter@35
   124
      /// The key type of the map.
kpeter@79
   125
      typedef K Key;
alpar@210
   126
      /// \brief The value type of the map.
alpar@210
   127
      /// (The type of objects associated with the keys).
alpar@25
   128
      typedef T Value;
alpar@25
   129
kpeter@79
   130
      /// Returns the value associated with the given key.
alpar@209
   131
      Value operator[](const Key &) const {
kpeter@94
   132
        return *static_cast<Value *>(0);
kpeter@94
   133
      }
kpeter@79
   134
kpeter@79
   135
      /// Sets the value associated with the given key.
kpeter@79
   136
      void set(const Key &, const Value &) {}
alpar@25
   137
alpar@25
   138
      template<typename _ReadWriteMap>
alpar@25
   139
      struct Constraints {
alpar@209
   140
        void constraints() {
alpar@209
   141
          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
alpar@209
   142
          checkConcept<WriteMap<K, T>, _ReadWriteMap >();
alpar@209
   143
        }
alpar@25
   144
      };
alpar@25
   145
    };
kpeter@79
   146
kpeter@79
   147
kpeter@28
   148
    /// Dereferable map concept
kpeter@79
   149
kpeter@28
   150
    /// Dereferable map concept.
kpeter@28
   151
    ///
alpar@25
   152
    template<typename K, typename T, typename R, typename CR>
alpar@25
   153
    class ReferenceMap : public ReadWriteMap<K,T>
alpar@25
   154
    {
alpar@25
   155
    public:
alpar@25
   156
      /// Tag for reference maps.
alpar@25
   157
      typedef True ReferenceMapTag;
kpeter@35
   158
      /// The key type of the map.
kpeter@79
   159
      typedef K Key;
alpar@210
   160
      /// \brief The value type of the map.
alpar@210
   161
      /// (The type of objects associated with the keys).
alpar@25
   162
      typedef T Value;
kpeter@35
   163
      /// The reference type of the map.
alpar@25
   164
      typedef R Reference;
kpeter@35
   165
      /// The const reference type of the map.
alpar@25
   166
      typedef CR ConstReference;
alpar@25
   167
alpar@25
   168
    public:
alpar@25
   169
kpeter@79
   170
      /// Returns a reference to the value associated with the given key.
alpar@209
   171
      Reference operator[](const Key &) {
kpeter@94
   172
        return *static_cast<Value *>(0);
kpeter@94
   173
      }
kpeter@79
   174
kpeter@79
   175
      /// Returns a const reference to the value associated with the given key.
kpeter@94
   176
      ConstReference operator[](const Key &) const {
kpeter@94
   177
        return *static_cast<Value *>(0);
kpeter@94
   178
      }
kpeter@79
   179
kpeter@79
   180
      /// Sets the value associated with the given key.
alpar@25
   181
      void set(const Key &k,const Value &t) { operator[](k)=t; }
alpar@25
   182
alpar@25
   183
      template<typename _ReferenceMap>
kpeter@74
   184
      struct Constraints {
alpar@209
   185
        void constraints() {
alpar@209
   186
          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
alpar@209
   187
          ref = m[key];
alpar@209
   188
          m[key] = val;
alpar@209
   189
          m[key] = ref;
alpar@209
   190
          m[key] = cref;
alpar@209
   191
          own_ref = m[own_key];
alpar@209
   192
          m[own_key] = own_val;
alpar@209
   193
          m[own_key] = own_ref;
alpar@209
   194
          m[own_key] = own_cref;
alpar@209
   195
          m[key] = m[own_key];
alpar@209
   196
          m[own_key] = m[key];
alpar@209
   197
        }
alpar@209
   198
        const Key& key;
alpar@209
   199
        Value& val;
alpar@209
   200
        Reference ref;
alpar@209
   201
        ConstReference cref;
alpar@209
   202
        const typename _ReferenceMap::Key& own_key;
alpar@209
   203
        typename _ReferenceMap::Value& own_val;
alpar@209
   204
        typename _ReferenceMap::Reference own_ref;
alpar@209
   205
        typename _ReferenceMap::ConstReference own_cref;
alpar@209
   206
        _ReferenceMap& m;
alpar@25
   207
      };
alpar@25
   208
    };
alpar@25
   209
alpar@25
   210
    // @}
alpar@25
   211
alpar@25
   212
  } //namespace concepts
kpeter@28
   213
alpar@25
   214
} //namespace lemon
kpeter@28
   215
deba@514
   216
#endif