lemon/tolerance.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 03 Dec 2008 14:23:22 +0100
changeset 419 9afe81e4c543
parent 209 765619b7cbb2
child 440 88ed40ad0d4f
child 496 7992dcb0d0e6
permissions -rw-r--r--
Renamings in connectivity.h and bug fix in DfsVisit (#61)

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