lemon/tolerance.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 05 Dec 2008 00:22:47 +0100
changeset 420 6a2a33ad261b
parent 209 765619b7cbb2
child 440 88ed40ad0d4f
child 496 7992dcb0d0e6
permissions -rw-r--r--
Add missing 'const' for query functions of algorithms
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@7
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@7
     4
 *
alpar@39
     5
 * Copyright (C) 2003-2008
alpar@7
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@7
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@7
     8
 *
alpar@7
     9
 * Permission to use, modify and distribute this software is granted
alpar@7
    10
 * provided that this copyright notice appears in all copies. For
alpar@7
    11
 * precise terms see the accompanying LICENSE file.
alpar@7
    12
 *
alpar@7
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@7
    14
 * express or implied, and with no claim as to its suitability for any
alpar@7
    15
 * purpose.
alpar@7
    16
 *
alpar@7
    17
 */
alpar@7
    18
alpar@7
    19
#ifndef LEMON_TOLERANCE_H
alpar@7
    20
#define LEMON_TOLERANCE_H
alpar@7
    21
alpar@7
    22
///\ingroup misc
alpar@7
    23
///\file
alpar@7
    24
///\brief A basic tool to handle the anomalies of calculation with
alpar@7
    25
///floating point numbers.
alpar@7
    26
///
alpar@7
    27
alpar@7
    28
namespace lemon {
alpar@7
    29
alpar@7
    30
  /// \addtogroup misc
alpar@7
    31
  /// @{
alpar@209
    32
alpar@7
    33
  ///\brief A class to provide a basic way to
alpar@7
    34
  ///handle the comparison of numbers that are obtained
alpar@7
    35
  ///as a result of a probably inexact computation.
alpar@7
    36
  ///
kpeter@49
    37
  ///\ref Tolerance is a class to provide a basic way to
alpar@7
    38
  ///handle the comparison of numbers that are obtained
alpar@7
    39
  ///as a result of a probably inexact computation.
alpar@7
    40
  ///
alpar@209
    41
  ///This is an abstract class, it should be specialized for all
alpar@209
    42
  ///numerical data types. These specialized classes like
kpeter@72
    43
  ///Tolerance<double> may offer additional tuning parameters.
alpar@7
    44
  ///
alpar@7
    45
  ///\sa Tolerance<float>
alpar@7
    46
  ///\sa Tolerance<double>
alpar@7
    47
  ///\sa Tolerance<long double>
alpar@7
    48
  ///\sa Tolerance<int>
alpar@7
    49
  ///\sa Tolerance<long long int>
alpar@7
    50
  ///\sa Tolerance<unsigned int>
alpar@7
    51
  ///\sa Tolerance<unsigned long long int>
alpar@7
    52
alpar@7
    53
  template<class T>
alpar@7
    54
  class Tolerance
alpar@7
    55
  {
alpar@7
    56
  public:
alpar@7
    57
    typedef T Value;
alpar@7
    58
alpar@7
    59
    ///\name Comparisons
kpeter@49
    60
    ///The concept is that these bool functions return \c true only if
alpar@7
    61
    ///the related comparisons hold even if some numerical error appeared
alpar@7
    62
    ///during the computations.
alpar@7
    63
alpar@7
    64
    ///@{
alpar@7
    65
alpar@7
    66
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
    67
    static bool less(Value a,Value b) {return false;}
alpar@7
    68
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
    69
    static bool different(Value a,Value b) {return false;}
alpar@7
    70
    ///Returns \c true if \c a is \e surely positive
alpar@7
    71
    static bool positive(Value a) {return false;}
alpar@7
    72
    ///Returns \c true if \c a is \e surely negative
alpar@7
    73
    static bool negative(Value a) {return false;}
alpar@7
    74
    ///Returns \c true if \c a is \e surely non-zero
alpar@7
    75
    static bool nonZero(Value a) {return false;}
alpar@7
    76
alpar@7
    77
    ///@}
alpar@7
    78
alpar@7
    79
    ///Returns the zero value.
alpar@7
    80
    static Value zero() {return T();}
alpar@7
    81
alpar@7
    82
    //   static bool finite(Value a) {}
alpar@7
    83
    //   static Value big() {}
alpar@7
    84
    //   static Value negativeBig() {}
alpar@7
    85
  };
alpar@7
    86
alpar@7
    87
alpar@42
    88
  ///Float specialization of Tolerance.
alpar@7
    89
alpar@42
    90
  ///Float specialization of Tolerance.
alpar@7
    91
  ///\sa Tolerance
alpar@7
    92
  ///\relates Tolerance
alpar@7
    93
  template<>
alpar@7
    94
  class Tolerance<float>
alpar@7
    95
  {
alpar@7
    96
    static float def_epsilon;
alpar@7
    97
    float _epsilon;
alpar@7
    98
  public:
alpar@7
    99
    ///\e
alpar@7
   100
    typedef float Value;
alpar@7
   101
alpar@7
   102
    ///Constructor setting the epsilon tolerance to the default value.
alpar@7
   103
    Tolerance() : _epsilon(def_epsilon) {}
kpeter@49
   104
    ///Constructor setting the epsilon tolerance to the given value.
alpar@7
   105
    Tolerance(float e) : _epsilon(e) {}
alpar@7
   106
kpeter@49
   107
    ///Returns the epsilon value.
alpar@7
   108
    Value epsilon() const {return _epsilon;}
kpeter@49
   109
    ///Sets the epsilon value.
alpar@7
   110
    void epsilon(Value e) {_epsilon=e;}
alpar@7
   111
kpeter@49
   112
    ///Returns the default epsilon value.
alpar@7
   113
    static Value defaultEpsilon() {return def_epsilon;}
kpeter@49
   114
    ///Sets the default epsilon value.
alpar@7
   115
    static void defaultEpsilon(Value e) {def_epsilon=e;}
alpar@7
   116
alpar@7
   117
    ///\name Comparisons
kpeter@72
   118
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   119
alpar@7
   120
    ///@{
alpar@7
   121
alpar@7
   122
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   123
    bool less(Value a,Value b) const {return a+_epsilon<b;}
alpar@7
   124
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   125
    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
alpar@7
   126
    ///Returns \c true if \c a is \e surely positive
alpar@7
   127
    bool positive(Value a) const { return _epsilon<a; }
alpar@7
   128
    ///Returns \c true if \c a is \e surely negative
alpar@7
   129
    bool negative(Value a) const { return -_epsilon>a; }
alpar@7
   130
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   131
    bool nonZero(Value a) const { return positive(a)||negative(a); }
alpar@7
   132
alpar@7
   133
    ///@}
alpar@7
   134
alpar@7
   135
    ///Returns zero
alpar@7
   136
    static Value zero() {return 0;}
alpar@7
   137
  };
alpar@7
   138
alpar@42
   139
  ///Double specialization of Tolerance.
alpar@7
   140
alpar@42
   141
  ///Double specialization of Tolerance.
alpar@7
   142
  ///\sa Tolerance
alpar@7
   143
  ///\relates Tolerance
alpar@7
   144
  template<>
alpar@7
   145
  class Tolerance<double>
alpar@7
   146
  {
alpar@7
   147
    static double def_epsilon;
alpar@7
   148
    double _epsilon;
alpar@7
   149
  public:
alpar@7
   150
    ///\e
alpar@7
   151
    typedef double Value;
alpar@7
   152
alpar@7
   153
    ///Constructor setting the epsilon tolerance to the default value.
alpar@7
   154
    Tolerance() : _epsilon(def_epsilon) {}
kpeter@49
   155
    ///Constructor setting the epsilon tolerance to the given value.
alpar@7
   156
    Tolerance(double e) : _epsilon(e) {}
alpar@7
   157
kpeter@49
   158
    ///Returns the epsilon value.
alpar@7
   159
    Value epsilon() const {return _epsilon;}
kpeter@49
   160
    ///Sets the epsilon value.
alpar@7
   161
    void epsilon(Value e) {_epsilon=e;}
alpar@7
   162
kpeter@49
   163
    ///Returns the default epsilon value.
alpar@7
   164
    static Value defaultEpsilon() {return def_epsilon;}
kpeter@49
   165
    ///Sets the default epsilon value.
alpar@7
   166
    static void defaultEpsilon(Value e) {def_epsilon=e;}
alpar@7
   167
alpar@7
   168
    ///\name Comparisons
kpeter@72
   169
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   170
alpar@7
   171
    ///@{
alpar@7
   172
alpar@7
   173
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   174
    bool less(Value a,Value b) const {return a+_epsilon<b;}
alpar@7
   175
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   176
    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
alpar@7
   177
    ///Returns \c true if \c a is \e surely positive
alpar@7
   178
    bool positive(Value a) const { return _epsilon<a; }
alpar@7
   179
    ///Returns \c true if \c a is \e surely negative
alpar@7
   180
    bool negative(Value a) const { return -_epsilon>a; }
alpar@7
   181
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   182
    bool nonZero(Value a) const { return positive(a)||negative(a); }
alpar@7
   183
alpar@7
   184
    ///@}
alpar@7
   185
alpar@7
   186
    ///Returns zero
alpar@7
   187
    static Value zero() {return 0;}
alpar@7
   188
  };
alpar@7
   189
alpar@42
   190
  ///Long double specialization of Tolerance.
alpar@7
   191
alpar@42
   192
  ///Long double specialization of Tolerance.
alpar@7
   193
  ///\sa Tolerance
alpar@7
   194
  ///\relates Tolerance
alpar@7
   195
  template<>
alpar@7
   196
  class Tolerance<long double>
alpar@7
   197
  {
alpar@7
   198
    static long double def_epsilon;
alpar@7
   199
    long double _epsilon;
alpar@7
   200
  public:
alpar@7
   201
    ///\e
alpar@7
   202
    typedef long double Value;
alpar@7
   203
alpar@7
   204
    ///Constructor setting the epsilon tolerance to the default value.
alpar@7
   205
    Tolerance() : _epsilon(def_epsilon) {}
kpeter@49
   206
    ///Constructor setting the epsilon tolerance to the given value.
alpar@7
   207
    Tolerance(long double e) : _epsilon(e) {}
alpar@7
   208
kpeter@49
   209
    ///Returns the epsilon value.
alpar@7
   210
    Value epsilon() const {return _epsilon;}
kpeter@49
   211
    ///Sets the epsilon value.
alpar@7
   212
    void epsilon(Value e) {_epsilon=e;}
alpar@7
   213
kpeter@49
   214
    ///Returns the default epsilon value.
alpar@7
   215
    static Value defaultEpsilon() {return def_epsilon;}
kpeter@49
   216
    ///Sets the default epsilon value.
alpar@7
   217
    static void defaultEpsilon(Value e) {def_epsilon=e;}
alpar@7
   218
alpar@7
   219
    ///\name Comparisons
kpeter@72
   220
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   221
alpar@7
   222
    ///@{
alpar@7
   223
alpar@7
   224
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   225
    bool less(Value a,Value b) const {return a+_epsilon<b;}
alpar@7
   226
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   227
    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
alpar@7
   228
    ///Returns \c true if \c a is \e surely positive
alpar@7
   229
    bool positive(Value a) const { return _epsilon<a; }
alpar@7
   230
    ///Returns \c true if \c a is \e surely negative
alpar@7
   231
    bool negative(Value a) const { return -_epsilon>a; }
alpar@7
   232
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   233
    bool nonZero(Value a) const { return positive(a)||negative(a); }
alpar@7
   234
alpar@7
   235
    ///@}
alpar@7
   236
alpar@7
   237
    ///Returns zero
alpar@7
   238
    static Value zero() {return 0;}
alpar@7
   239
  };
alpar@7
   240
alpar@42
   241
  ///Integer specialization of Tolerance.
alpar@7
   242
alpar@42
   243
  ///Integer specialization of Tolerance.
alpar@7
   244
  ///\sa Tolerance
alpar@7
   245
  template<>
alpar@7
   246
  class Tolerance<int>
alpar@7
   247
  {
alpar@7
   248
  public:
alpar@7
   249
    ///\e
alpar@7
   250
    typedef int Value;
alpar@7
   251
alpar@7
   252
    ///\name Comparisons
kpeter@72
   253
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   254
alpar@7
   255
    ///@{
alpar@7
   256
alpar@7
   257
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   258
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   259
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   260
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   261
    ///Returns \c true if \c a is \e surely positive
alpar@7
   262
    static bool positive(Value a) { return 0<a; }
alpar@7
   263
    ///Returns \c true if \c a is \e surely negative
alpar@7
   264
    static bool negative(Value a) { return 0>a; }
alpar@7
   265
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   266
    static bool nonZero(Value a) { return a!=0; }
alpar@7
   267
alpar@7
   268
    ///@}
alpar@7
   269
alpar@7
   270
    ///Returns zero
alpar@7
   271
    static Value zero() {return 0;}
alpar@7
   272
  };
alpar@7
   273
alpar@42
   274
  ///Unsigned integer specialization of Tolerance.
alpar@7
   275
kpeter@72
   276
  ///Unsigned integer specialization of Tolerance.
alpar@7
   277
  ///\sa Tolerance
alpar@7
   278
  template<>
alpar@7
   279
  class Tolerance<unsigned int>
alpar@7
   280
  {
alpar@7
   281
  public:
alpar@7
   282
    ///\e
alpar@7
   283
    typedef unsigned int Value;
alpar@7
   284
alpar@7
   285
    ///\name Comparisons
kpeter@72
   286
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   287
alpar@7
   288
    ///@{
alpar@7
   289
alpar@7
   290
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   291
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   292
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   293
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   294
    ///Returns \c true if \c a is \e surely positive
alpar@7
   295
    static bool positive(Value a) { return 0<a; }
alpar@7
   296
    ///Returns \c true if \c a is \e surely negative
alpar@7
   297
    static bool negative(Value) { return false; }
alpar@7
   298
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   299
    static bool nonZero(Value a) { return a!=0; }
alpar@7
   300
alpar@7
   301
    ///@}
alpar@7
   302
alpar@7
   303
    ///Returns zero
alpar@7
   304
    static Value zero() {return 0;}
alpar@7
   305
  };
alpar@209
   306
alpar@7
   307
alpar@42
   308
  ///Long integer specialization of Tolerance.
alpar@7
   309
alpar@42
   310
  ///Long integer specialization of Tolerance.
alpar@7
   311
  ///\sa Tolerance
alpar@7
   312
  template<>
alpar@7
   313
  class Tolerance<long int>
alpar@7
   314
  {
alpar@7
   315
  public:
alpar@7
   316
    ///\e
alpar@7
   317
    typedef long int Value;
alpar@7
   318
alpar@7
   319
    ///\name Comparisons
kpeter@72
   320
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   321
alpar@7
   322
    ///@{
alpar@7
   323
alpar@7
   324
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   325
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   326
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   327
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   328
    ///Returns \c true if \c a is \e surely positive
alpar@7
   329
    static bool positive(Value a) { return 0<a; }
alpar@7
   330
    ///Returns \c true if \c a is \e surely negative
alpar@7
   331
    static bool negative(Value a) { return 0>a; }
alpar@7
   332
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   333
    static bool nonZero(Value a) { return a!=0;}
alpar@7
   334
alpar@7
   335
    ///@}
alpar@7
   336
alpar@7
   337
    ///Returns zero
alpar@7
   338
    static Value zero() {return 0;}
alpar@7
   339
  };
alpar@7
   340
alpar@42
   341
  ///Unsigned long integer specialization of Tolerance.
alpar@7
   342
kpeter@72
   343
  ///Unsigned long integer specialization of Tolerance.
alpar@7
   344
  ///\sa Tolerance
alpar@7
   345
  template<>
alpar@7
   346
  class Tolerance<unsigned long int>
alpar@7
   347
  {
alpar@7
   348
  public:
alpar@7
   349
    ///\e
alpar@7
   350
    typedef unsigned long int Value;
alpar@7
   351
alpar@7
   352
    ///\name Comparisons
kpeter@72
   353
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   354
alpar@7
   355
    ///@{
alpar@7
   356
alpar@7
   357
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   358
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   359
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   360
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   361
    ///Returns \c true if \c a is \e surely positive
alpar@7
   362
    static bool positive(Value a) { return 0<a; }
alpar@7
   363
    ///Returns \c true if \c a is \e surely negative
alpar@7
   364
    static bool negative(Value) { return false; }
alpar@7
   365
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   366
    static bool nonZero(Value a) { return a!=0;}
alpar@7
   367
alpar@7
   368
    ///@}
alpar@7
   369
alpar@7
   370
    ///Returns zero
alpar@7
   371
    static Value zero() {return 0;}
alpar@7
   372
  };
alpar@7
   373
alpar@7
   374
#if defined __GNUC__ && !defined __STRICT_ANSI__
alpar@7
   375
alpar@42
   376
  ///Long long integer specialization of Tolerance.
alpar@7
   377
kpeter@72
   378
  ///Long long integer specialization of Tolerance.
alpar@7
   379
  ///\warning This class (more exactly, type <tt>long long</tt>)
alpar@7
   380
  ///is not ansi compatible.
alpar@7
   381
  ///\sa Tolerance
alpar@7
   382
  template<>
alpar@7
   383
  class Tolerance<long long int>
alpar@7
   384
  {
alpar@7
   385
  public:
alpar@7
   386
    ///\e
alpar@7
   387
    typedef long long int Value;
alpar@7
   388
alpar@7
   389
    ///\name Comparisons
kpeter@72
   390
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   391
alpar@7
   392
    ///@{
alpar@7
   393
alpar@7
   394
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   395
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   396
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   397
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   398
    ///Returns \c true if \c a is \e surely positive
alpar@7
   399
    static bool positive(Value a) { return 0<a; }
alpar@7
   400
    ///Returns \c true if \c a is \e surely negative
alpar@7
   401
    static bool negative(Value a) { return 0>a; }
alpar@7
   402
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   403
    static bool nonZero(Value a) { return a!=0;}
alpar@7
   404
alpar@7
   405
    ///@}
alpar@7
   406
alpar@7
   407
    ///Returns zero
alpar@7
   408
    static Value zero() {return 0;}
alpar@7
   409
  };
alpar@7
   410
alpar@42
   411
  ///Unsigned long long integer specialization of Tolerance.
alpar@7
   412
kpeter@72
   413
  ///Unsigned long long integer specialization of Tolerance.
alpar@7
   414
  ///\warning This class (more exactly, type <tt>unsigned long long</tt>)
alpar@7
   415
  ///is not ansi compatible.
alpar@7
   416
  ///\sa Tolerance
alpar@7
   417
  template<>
alpar@7
   418
  class Tolerance<unsigned long long int>
alpar@7
   419
  {
alpar@7
   420
  public:
alpar@7
   421
    ///\e
alpar@7
   422
    typedef unsigned long long int Value;
alpar@7
   423
alpar@7
   424
    ///\name Comparisons
kpeter@72
   425
    ///See \ref lemon::Tolerance "Tolerance" for more details.
alpar@7
   426
alpar@7
   427
    ///@{
alpar@7
   428
alpar@7
   429
    ///Returns \c true if \c a is \e surely strictly less than \c b
alpar@7
   430
    static bool less(Value a,Value b) { return a<b;}
alpar@7
   431
    ///Returns \c true if \c a is \e surely different from \c b
alpar@7
   432
    static bool different(Value a,Value b) { return a!=b; }
alpar@7
   433
    ///Returns \c true if \c a is \e surely positive
alpar@7
   434
    static bool positive(Value a) { return 0<a; }
alpar@7
   435
    ///Returns \c true if \c a is \e surely negative
alpar@7
   436
    static bool negative(Value) { return false; }
alpar@7
   437
    ///Returns \c true if \c a is \e surely non-zero
kpeter@16
   438
    static bool nonZero(Value a) { return a!=0;}
alpar@7
   439
alpar@7
   440
    ///@}
alpar@7
   441
alpar@7
   442
    ///Returns zero
alpar@7
   443
    static Value zero() {return 0;}
alpar@7
   444
  };
alpar@7
   445
alpar@7
   446
#endif
alpar@7
   447
alpar@7
   448
  /// @}
alpar@7
   449
alpar@7
   450
} //namespace lemon
alpar@7
   451
alpar@7
   452
#endif //LEMON_TOLERANCE_H