lemon/bits/variant.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 431 9dfaf6efc36f
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.
deba@416
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@414
     2
 *
deba@416
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@414
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@414
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414
     8
 *
deba@414
     9
 * Permission to use, modify and distribute this software is granted
deba@414
    10
 * provided that this copyright notice appears in all copies. For
deba@414
    11
 * precise terms see the accompanying LICENSE file.
deba@414
    12
 *
deba@414
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@414
    14
 * express or implied, and with no claim as to its suitability for any
deba@414
    15
 * purpose.
deba@414
    16
 *
deba@414
    17
 */
deba@414
    18
deba@414
    19
#ifndef LEMON_BITS_VARIANT_H
deba@414
    20
#define LEMON_BITS_VARIANT_H
deba@414
    21
deba@414
    22
#include <lemon/assert.h>
deba@414
    23
kpeter@431
    24
// \file
kpeter@431
    25
// \brief Variant types
deba@414
    26
deba@414
    27
namespace lemon {
deba@414
    28
deba@414
    29
  namespace _variant_bits {
deba@416
    30
deba@414
    31
    template <int left, int right>
deba@414
    32
    struct CTMax {
deba@414
    33
      static const int value = left < right ? right : left;
deba@414
    34
    };
deba@414
    35
deba@414
    36
  }
deba@414
    37
deba@414
    38
kpeter@431
    39
  // \brief Simple Variant type for two types
kpeter@431
    40
  //
kpeter@431
    41
  // Simple Variant type for two types. The Variant type is a type-safe
kpeter@431
    42
  // union. C++ has strong limitations for using unions, for
kpeter@431
    43
  // example you cannot store a type with non-default constructor or
kpeter@431
    44
  // destructor in a union. This class always knowns the current
kpeter@431
    45
  // state of the variant and it cares for the proper construction
kpeter@431
    46
  // and destruction.
deba@414
    47
  template <typename _First, typename _Second>
deba@414
    48
  class BiVariant {
deba@414
    49
  public:
deba@414
    50
kpeter@431
    51
    // \brief The \c First type.
deba@414
    52
    typedef _First First;
kpeter@431
    53
    // \brief The \c Second type.
deba@414
    54
    typedef _Second Second;
deba@414
    55
kpeter@431
    56
    // \brief Constructor
kpeter@431
    57
    //
kpeter@431
    58
    // This constructor initalizes to the default value of the \c First
kpeter@431
    59
    // type.
deba@414
    60
    BiVariant() {
deba@414
    61
      flag = true;
deba@414
    62
      new(reinterpret_cast<First*>(data)) First();
deba@414
    63
    }
deba@414
    64
kpeter@431
    65
    // \brief Constructor
kpeter@431
    66
    //
kpeter@431
    67
    // This constructor initalizes to the given value of the \c First
kpeter@431
    68
    // type.
deba@414
    69
    BiVariant(const First& f) {
deba@414
    70
      flag = true;
deba@414
    71
      new(reinterpret_cast<First*>(data)) First(f);
deba@414
    72
    }
deba@414
    73
kpeter@431
    74
    // \brief Constructor
kpeter@431
    75
    //
kpeter@431
    76
    // This constructor initalizes to the given value of the \c
kpeter@431
    77
    // Second type.
deba@414
    78
    BiVariant(const Second& s) {
deba@414
    79
      flag = false;
deba@414
    80
      new(reinterpret_cast<Second*>(data)) Second(s);
deba@414
    81
    }
deba@414
    82
kpeter@431
    83
    // \brief Copy constructor
kpeter@431
    84
    //
kpeter@431
    85
    // Copy constructor
deba@414
    86
    BiVariant(const BiVariant& bivariant) {
deba@414
    87
      flag = bivariant.flag;
deba@414
    88
      if (flag) {
deba@416
    89
        new(reinterpret_cast<First*>(data)) First(bivariant.first());
deba@414
    90
      } else {
deba@416
    91
        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
deba@414
    92
      }
deba@414
    93
    }
deba@414
    94
kpeter@431
    95
    // \brief Destrcutor
kpeter@431
    96
    //
kpeter@431
    97
    // Destructor
deba@414
    98
    ~BiVariant() {
deba@414
    99
      destroy();
deba@414
   100
    }
deba@414
   101
kpeter@431
   102
    // \brief Set to the default value of the \c First type.
kpeter@431
   103
    //
kpeter@431
   104
    // This function sets the variant to the default value of the \c
kpeter@431
   105
    // First type.
deba@414
   106
    BiVariant& setFirst() {
deba@414
   107
      destroy();
deba@414
   108
      flag = true;
deba@416
   109
      new(reinterpret_cast<First*>(data)) First();
deba@414
   110
      return *this;
deba@414
   111
    }
deba@414
   112
kpeter@431
   113
    // \brief Set to the given value of the \c First type.
kpeter@431
   114
    //
kpeter@431
   115
    // This function sets the variant to the given value of the \c
kpeter@431
   116
    // First type.
deba@414
   117
    BiVariant& setFirst(const First& f) {
deba@414
   118
      destroy();
deba@414
   119
      flag = true;
deba@416
   120
      new(reinterpret_cast<First*>(data)) First(f);
deba@414
   121
      return *this;
deba@414
   122
    }
deba@414
   123
kpeter@431
   124
    // \brief Set to the default value of the \c Second type.
kpeter@431
   125
    //
kpeter@431
   126
    // This function sets the variant to the default value of the \c
kpeter@431
   127
    // Second type.
deba@414
   128
    BiVariant& setSecond() {
deba@414
   129
      destroy();
deba@414
   130
      flag = false;
deba@416
   131
      new(reinterpret_cast<Second*>(data)) Second();
deba@414
   132
      return *this;
deba@414
   133
    }
deba@414
   134
kpeter@431
   135
    // \brief Set to the given value of the \c Second type.
kpeter@431
   136
    //
kpeter@431
   137
    // This function sets the variant to the given value of the \c
kpeter@431
   138
    // Second type.
deba@414
   139
    BiVariant& setSecond(const Second& s) {
deba@414
   140
      destroy();
deba@414
   141
      flag = false;
deba@416
   142
      new(reinterpret_cast<Second*>(data)) Second(s);
deba@414
   143
      return *this;
deba@414
   144
    }
deba@414
   145
kpeter@431
   146
    // \brief Operator form of the \c setFirst()
deba@414
   147
    BiVariant& operator=(const First& f) {
deba@414
   148
      return setFirst(f);
deba@414
   149
    }
deba@414
   150
kpeter@431
   151
    // \brief Operator form of the \c setSecond()
deba@414
   152
    BiVariant& operator=(const Second& s) {
deba@414
   153
      return setSecond(s);
deba@414
   154
    }
deba@414
   155
kpeter@431
   156
    // \brief Assign operator
deba@414
   157
    BiVariant& operator=(const BiVariant& bivariant) {
deba@414
   158
      if (this == &bivariant) return *this;
deba@414
   159
      destroy();
deba@414
   160
      flag = bivariant.flag;
deba@414
   161
      if (flag) {
deba@416
   162
        new(reinterpret_cast<First*>(data)) First(bivariant.first());
deba@414
   163
      } else {
deba@416
   164
        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
deba@414
   165
      }
deba@414
   166
      return *this;
deba@414
   167
    }
deba@414
   168
kpeter@431
   169
    // \brief Reference to the value
kpeter@431
   170
    //
kpeter@431
   171
    // Reference to the value of the \c First type.
kpeter@431
   172
    // \pre The BiVariant should store value of \c First type.
deba@414
   173
    First& first() {
deba@414
   174
      LEMON_DEBUG(flag, "Variant wrong state");
kpeter@431
   175
      return *reinterpret_cast<First*>(data);
deba@414
   176
    }
deba@414
   177
kpeter@431
   178
    // \brief Const reference to the value
kpeter@431
   179
    //
kpeter@431
   180
    // Const reference to the value of the \c First type.
kpeter@431
   181
    // \pre The BiVariant should store value of \c First type.
kpeter@431
   182
    const First& first() const {
deba@414
   183
      LEMON_DEBUG(flag, "Variant wrong state");
kpeter@431
   184
      return *reinterpret_cast<const First*>(data);
deba@414
   185
    }
deba@414
   186
kpeter@431
   187
    // \brief Operator form of the \c first()
deba@414
   188
    operator First&() { return first(); }
kpeter@431
   189
    // \brief Operator form of the const \c first()
deba@414
   190
    operator const First&() const { return first(); }
deba@414
   191
kpeter@431
   192
    // \brief Reference to the value
kpeter@431
   193
    //
kpeter@431
   194
    // Reference to the value of the \c Second type.
kpeter@431
   195
    // \pre The BiVariant should store value of \c Second type.
kpeter@431
   196
    Second& second() {
deba@414
   197
      LEMON_DEBUG(!flag, "Variant wrong state");
kpeter@431
   198
      return *reinterpret_cast<Second*>(data);
deba@414
   199
    }
deba@414
   200
kpeter@431
   201
    // \brief Const reference to the value
kpeter@431
   202
    //
kpeter@431
   203
    // Const reference to the value of the \c Second type.
kpeter@431
   204
    // \pre The BiVariant should store value of \c Second type.
kpeter@431
   205
    const Second& second() const {
deba@414
   206
      LEMON_DEBUG(!flag, "Variant wrong state");
kpeter@431
   207
      return *reinterpret_cast<const Second*>(data);
deba@414
   208
    }
deba@414
   209
kpeter@431
   210
    // \brief Operator form of the \c second()
deba@414
   211
    operator Second&() { return second(); }
kpeter@431
   212
    // \brief Operator form of the const \c second()
deba@414
   213
    operator const Second&() const { return second(); }
deba@414
   214
kpeter@431
   215
    // \brief %True when the variant is in the first state
kpeter@431
   216
    //
kpeter@431
   217
    // %True when the variant stores value of the \c First type.
deba@414
   218
    bool firstState() const { return flag; }
deba@414
   219
kpeter@431
   220
    // \brief %True when the variant is in the second state
kpeter@431
   221
    //
kpeter@431
   222
    // %True when the variant stores value of the \c Second type.
deba@414
   223
    bool secondState() const { return !flag; }
deba@414
   224
deba@414
   225
  private:
deba@414
   226
deba@414
   227
    void destroy() {
deba@414
   228
      if (flag) {
deba@414
   229
        reinterpret_cast<First*>(data)->~First();
deba@414
   230
      } else {
deba@414
   231
        reinterpret_cast<Second*>(data)->~Second();
deba@414
   232
      }
deba@414
   233
    }
deba@416
   234
deba@414
   235
    char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
deba@414
   236
    bool flag;
deba@414
   237
  };
deba@414
   238
deba@414
   239
  namespace _variant_bits {
deba@416
   240
deba@414
   241
    template <int _idx, typename _TypeMap>
deba@414
   242
    struct Memory {
deba@414
   243
deba@414
   244
      typedef typename _TypeMap::template Map<_idx>::Type Current;
deba@414
   245
deba@414
   246
      static void destroy(int index, char* place) {
deba@414
   247
        if (index == _idx) {
deba@414
   248
          reinterpret_cast<Current*>(place)->~Current();
deba@414
   249
        } else {
deba@414
   250
          Memory<_idx - 1, _TypeMap>::destroy(index, place);
deba@414
   251
        }
deba@414
   252
      }
deba@414
   253
deba@414
   254
      static void copy(int index, char* to, const char* from) {
deba@414
   255
        if (index == _idx) {
deba@414
   256
          new (reinterpret_cast<Current*>(to))
deba@414
   257
            Current(reinterpret_cast<const Current*>(from));
deba@414
   258
        } else {
deba@414
   259
          Memory<_idx - 1, _TypeMap>::copy(index, to, from);
deba@414
   260
        }
deba@414
   261
      }
deba@414
   262
deba@414
   263
    };
deba@414
   264
deba@414
   265
    template <typename _TypeMap>
deba@414
   266
    struct Memory<-1, _TypeMap> {
deba@414
   267
deba@414
   268
      static void destroy(int, char*) {
deba@414
   269
        LEMON_DEBUG(false, "Variant wrong index.");
deba@414
   270
      }
deba@414
   271
deba@414
   272
      static void copy(int, char*, const char*) {
deba@414
   273
        LEMON_DEBUG(false, "Variant wrong index.");
deba@414
   274
      }
deba@414
   275
    };
deba@414
   276
deba@414
   277
    template <int _idx, typename _TypeMap>
deba@414
   278
    struct Size {
deba@416
   279
      static const int value =
deba@416
   280
      CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
deba@414
   281
            Size<_idx - 1, _TypeMap>::value>::value;
deba@414
   282
    };
deba@414
   283
deba@414
   284
    template <typename _TypeMap>
deba@414
   285
    struct Size<0, _TypeMap> {
deba@416
   286
      static const int value =
deba@414
   287
      sizeof(typename _TypeMap::template Map<0>::Type);
deba@414
   288
    };
deba@414
   289
deba@414
   290
  }
deba@414
   291
kpeter@431
   292
  // \brief Variant type
kpeter@431
   293
  //
kpeter@431
   294
  // Simple Variant type. The Variant type is a type-safe union.
kpeter@431
   295
  // C++ has strong limitations for using unions, for example you
kpeter@431
   296
  // cannot store type with non-default constructor or destructor in
kpeter@431
   297
  // a union. This class always knowns the current state of the
kpeter@431
   298
  // variant and it cares for the proper construction and
kpeter@431
   299
  // destruction.
kpeter@431
   300
  //
kpeter@431
   301
  // \param _num The number of the types which can be stored in the
kpeter@431
   302
  // variant type.
kpeter@431
   303
  // \param _TypeMap This class describes the types of the Variant. The
kpeter@431
   304
  // _TypeMap::Map<index>::Type should be a valid type for each index
kpeter@431
   305
  // in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
kpeter@431
   306
  // class to define such type mappings up to 10 types.
kpeter@431
   307
  //
kpeter@431
   308
  // And the usage of the class:
kpeter@431
   309
  //\code
kpeter@431
   310
  // typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
kpeter@431
   311
  // MyVariant var;
kpeter@431
   312
  // var.set<0>(12);
kpeter@431
   313
  // std::cout << var.get<0>() << std::endl;
kpeter@431
   314
  // var.set<1>("alpha");
kpeter@431
   315
  // std::cout << var.get<1>() << std::endl;
kpeter@431
   316
  // var.set<2>(0.75);
kpeter@431
   317
  // std::cout << var.get<2>() << std::endl;
kpeter@431
   318
  //\endcode
kpeter@431
   319
  //
kpeter@431
   320
  // The result of course:
kpeter@431
   321
  //\code
kpeter@431
   322
  // 12
kpeter@431
   323
  // alpha
kpeter@431
   324
  // 0.75
kpeter@431
   325
  //\endcode
deba@414
   326
  template <int _num, typename _TypeMap>
deba@414
   327
  class Variant {
deba@414
   328
  public:
deba@414
   329
deba@414
   330
    static const int num = _num;
deba@414
   331
deba@414
   332
    typedef _TypeMap TypeMap;
deba@414
   333
kpeter@431
   334
    // \brief Constructor
kpeter@431
   335
    //
kpeter@431
   336
    // This constructor initalizes to the default value of the \c type
kpeter@431
   337
    // with 0 index.
deba@414
   338
    Variant() {
deba@414
   339
      flag = 0;
deba@416
   340
      new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
deba@414
   341
        typename TypeMap::template Map<0>::Type();
deba@414
   342
    }
deba@414
   343
deba@414
   344
kpeter@431
   345
    // \brief Copy constructor
kpeter@431
   346
    //
kpeter@431
   347
    // Copy constructor
deba@414
   348
    Variant(const Variant& variant) {
deba@414
   349
      flag = variant.flag;
deba@414
   350
      _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data);
deba@414
   351
    }
deba@414
   352
kpeter@431
   353
    // \brief Assign operator
kpeter@431
   354
    //
kpeter@431
   355
    // Assign operator
deba@414
   356
    Variant& operator=(const Variant& variant) {
deba@414
   357
      if (this == &variant) return *this;
deba@414
   358
      _variant_bits::Memory<num - 1, TypeMap>::
deba@414
   359
        destroy(flag, data);
deba@414
   360
      flag = variant.flag;
deba@414
   361
      _variant_bits::Memory<num - 1, TypeMap>::
deba@414
   362
        copy(flag, data, variant.data);
deba@414
   363
      return *this;
deba@414
   364
    }
deba@414
   365
kpeter@431
   366
    // \brief Destrcutor
kpeter@431
   367
    //
kpeter@431
   368
    // Destructor
deba@414
   369
    ~Variant() {
deba@414
   370
      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
deba@414
   371
    }
deba@414
   372
kpeter@431
   373
    // \brief Set to the default value of the type with \c _idx index.
kpeter@431
   374
    //
kpeter@431
   375
    // This function sets the variant to the default value of the
kpeter@431
   376
    // type with \c _idx index.
deba@414
   377
    template <int _idx>
deba@414
   378
    Variant& set() {
deba@414
   379
      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
deba@414
   380
      flag = _idx;
deba@416
   381
      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
deba@414
   382
        typename TypeMap::template Map<_idx>::Type();
deba@414
   383
      return *this;
deba@414
   384
    }
deba@414
   385
kpeter@431
   386
    // \brief Set to the given value of the type with \c _idx index.
kpeter@431
   387
    //
kpeter@431
   388
    // This function sets the variant to the given value of the type
kpeter@431
   389
    // with \c _idx index.
deba@414
   390
    template <int _idx>
deba@414
   391
    Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) {
deba@414
   392
      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
deba@414
   393
      flag = _idx;
deba@416
   394
      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
deba@414
   395
        typename TypeMap::template Map<_idx>::Type(init);
deba@414
   396
      return *this;
deba@414
   397
    }
deba@414
   398
kpeter@431
   399
    // \brief Gets the current value of the type with \c _idx index.
kpeter@431
   400
    //
kpeter@431
   401
    // Gets the current value of the type with \c _idx index.
deba@414
   402
    template <int _idx>
deba@414
   403
    const typename TypeMap::template Map<_idx>::Type& get() const {
deba@414
   404
      LEMON_DEBUG(_idx == flag, "Variant wrong index");
deba@414
   405
      return *reinterpret_cast<const typename TypeMap::
deba@416
   406
        template Map<_idx>::Type*>(data);
deba@414
   407
    }
deba@414
   408
kpeter@431
   409
    // \brief Gets the current value of the type with \c _idx index.
kpeter@431
   410
    //
kpeter@431
   411
    // Gets the current value of the type with \c _idx index.
deba@414
   412
    template <int _idx>
deba@414
   413
    typename _TypeMap::template Map<_idx>::Type& get() {
deba@414
   414
      LEMON_DEBUG(_idx == flag, "Variant wrong index");
deba@414
   415
      return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
deba@416
   416
        (data);
deba@414
   417
    }
deba@414
   418
kpeter@431
   419
    // \brief Returns the current state of the variant.
kpeter@431
   420
    //
kpeter@431
   421
    // Returns the current state of the variant.
deba@414
   422
    int state() const {
deba@414
   423
      return flag;
deba@414
   424
    }
deba@414
   425
deba@414
   426
  private:
deba@416
   427
deba@414
   428
    char data[_variant_bits::Size<num - 1, TypeMap>::value];
deba@414
   429
    int flag;
deba@414
   430
  };
deba@414
   431
deba@414
   432
  namespace _variant_bits {
deba@414
   433
deba@414
   434
    template <int _index, typename _List>
deba@414
   435
    struct Get {
deba@414
   436
      typedef typename Get<_index - 1, typename _List::Next>::Type Type;
deba@414
   437
    };
deba@414
   438
deba@414
   439
    template <typename _List>
deba@414
   440
    struct Get<0, _List> {
deba@414
   441
      typedef typename _List::Type Type;
deba@414
   442
    };
deba@414
   443
deba@414
   444
    struct List {};
deba@416
   445
deba@414
   446
    template <typename _Type, typename _List>
deba@414
   447
    struct Insert {
deba@414
   448
      typedef _List Next;
deba@414
   449
      typedef _Type Type;
deba@414
   450
    };
deba@414
   451
deba@416
   452
    template <int _idx, typename _T0, typename _T1, typename _T2,
kpeter@430
   453
              typename _T3, typename _T4, typename _T5, typename _T6,
deba@414
   454
              typename _T7, typename _T8, typename _T9>
deba@414
   455
    struct Mapper {
deba@414
   456
      typedef List L10;
deba@414
   457
      typedef Insert<_T9, L10> L9;
deba@414
   458
      typedef Insert<_T8, L9> L8;
deba@414
   459
      typedef Insert<_T7, L8> L7;
deba@414
   460
      typedef Insert<_T6, L7> L6;
deba@414
   461
      typedef Insert<_T5, L6> L5;
deba@414
   462
      typedef Insert<_T4, L5> L4;
deba@414
   463
      typedef Insert<_T3, L4> L3;
deba@414
   464
      typedef Insert<_T2, L3> L2;
deba@414
   465
      typedef Insert<_T1, L2> L1;
deba@414
   466
      typedef Insert<_T0, L1> L0;
deba@414
   467
      typedef typename Get<_idx, L0>::Type Type;
deba@414
   468
    };
deba@416
   469
deba@414
   470
  }
deba@414
   471
kpeter@431
   472
  // \brief Helper class for Variant
kpeter@431
   473
  //
kpeter@431
   474
  // Helper class to define type mappings for Variant. This class
kpeter@431
   475
  // converts the template parameters to be mappable by integer.
kpeter@431
   476
  // \see Variant
deba@414
   477
  template <
deba@416
   478
    typename _T0,
deba@414
   479
    typename _T1 = void, typename _T2 = void, typename _T3 = void,
kpeter@430
   480
    typename _T4 = void, typename _T5 = void, typename _T6 = void,
deba@414
   481
    typename _T7 = void, typename _T8 = void, typename _T9 = void>
deba@414
   482
  struct VariantTypeMap {
deba@414
   483
    template <int _idx>
deba@414
   484
    struct Map {
deba@414
   485
      typedef typename _variant_bits::
deba@414
   486
      Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type
deba@414
   487
      Type;
deba@414
   488
    };
deba@414
   489
  };
deba@416
   490
deba@414
   491
}
deba@414
   492
deba@414
   493
deba@414
   494
#endif