lemon/bits/variant.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 12:22:06 +0200
changeset 613 b1811c363299
parent 431 9dfaf6efc36f
permissions -rw-r--r--
Bug fix in NetworkSimplex (#234)
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