lemon/counter.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 21 Dec 2008 20:45:25 +0100
changeset 438 81d40f1c850c
parent 168 8ceb318224b1
child 440 88ed40ad0d4f
permissions -rw-r--r--
Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@119
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@119
     4
 *
alpar@119
     5
 * Copyright (C) 2003-2008
alpar@119
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@119
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@119
     8
 *
alpar@119
     9
 * Permission to use, modify and distribute this software is granted
alpar@119
    10
 * provided that this copyright notice appears in all copies. For
alpar@119
    11
 * precise terms see the accompanying LICENSE file.
alpar@119
    12
 *
alpar@119
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@119
    14
 * express or implied, and with no claim as to its suitability for any
alpar@119
    15
 * purpose.
alpar@119
    16
 *
alpar@119
    17
 */
alpar@119
    18
alpar@119
    19
#ifndef LEMON_COUNTER_H
alpar@119
    20
#define LEMON_COUNTER_H
alpar@119
    21
alpar@119
    22
#include <string>
alpar@119
    23
#include <iostream>
alpar@119
    24
alpar@119
    25
///\ingroup timecount
alpar@119
    26
///\file
alpar@119
    27
///\brief Tools for counting steps and events
alpar@119
    28
alpar@209
    29
namespace lemon
alpar@119
    30
{
alpar@119
    31
alpar@121
    32
  template<class P> class _NoSubCounter;
alpar@119
    33
alpar@119
    34
  template<class P>
alpar@209
    35
  class _SubCounter
alpar@119
    36
  {
alpar@119
    37
    P &_parent;
alpar@119
    38
    std::string _title;
alpar@119
    39
    std::ostream &_os;
alpar@119
    40
    int count;
alpar@119
    41
  public:
alpar@119
    42
alpar@119
    43
    typedef _SubCounter<_SubCounter<P> > SubCounter;
alpar@121
    44
    typedef _NoSubCounter<_SubCounter<P> > NoSubCounter;
alpar@119
    45
alpar@119
    46
    _SubCounter(P &parent)
alpar@119
    47
      : _parent(parent), _title(), _os(std::cerr), count(0) {}
alpar@119
    48
    _SubCounter(P &parent,std::string title,std::ostream &os=std::cerr)
alpar@119
    49
      : _parent(parent), _title(title), _os(os), count(0) {}
alpar@119
    50
    _SubCounter(P &parent,const char *title,std::ostream &os=std::cerr)
alpar@119
    51
      : _parent(parent), _title(title), _os(os), count(0) {}
alpar@209
    52
    ~_SubCounter() {
alpar@119
    53
      _os << _title << count <<std::endl;
alpar@119
    54
      _parent+=count;
alpar@119
    55
    }
alpar@119
    56
    _SubCounter &operator++() { count++; return *this;}
alpar@119
    57
    int operator++(int) { return count++; }
alpar@119
    58
    _SubCounter &operator--() { count--; return *this;}
alpar@119
    59
    int operator--(int) { return count--; }
alpar@119
    60
    _SubCounter &operator+=(int c) { count+=c; return *this;}
alpar@119
    61
    _SubCounter &operator-=(int c) { count-=c; return *this;}
alpar@119
    62
    operator int() {return count;}
alpar@119
    63
  };
alpar@119
    64
alpar@119
    65
  template<class P>
alpar@209
    66
  class _NoSubCounter
alpar@119
    67
  {
alpar@119
    68
    P &_parent;
alpar@119
    69
  public:
alpar@121
    70
    typedef _NoSubCounter<_NoSubCounter<P> > SubCounter;
alpar@121
    71
    typedef _NoSubCounter<_NoSubCounter<P> > NoSubCounter;
alpar@209
    72
alpar@121
    73
    _NoSubCounter(P &parent) :_parent(parent) {}
alpar@209
    74
    _NoSubCounter(P &parent,std::string,std::ostream &)
alpar@119
    75
      :_parent(parent) {}
alpar@209
    76
    _NoSubCounter(P &parent,std::string)
alpar@119
    77
      :_parent(parent) {}
alpar@121
    78
    _NoSubCounter(P &parent,const char *,std::ostream &)
alpar@119
    79
      :_parent(parent) {}
alpar@121
    80
    _NoSubCounter(P &parent,const char *)
alpar@119
    81
      :_parent(parent) {}
alpar@121
    82
    ~_NoSubCounter() {}
alpar@121
    83
    _NoSubCounter &operator++() { ++_parent; return *this;}
alpar@119
    84
    int operator++(int) { _parent++; return 0;}
alpar@121
    85
    _NoSubCounter &operator--() { --_parent; return *this;}
alpar@119
    86
    int operator--(int) { _parent--; return 0;}
alpar@121
    87
    _NoSubCounter &operator+=(int c) { _parent+=c; return *this;}
alpar@121
    88
    _NoSubCounter &operator-=(int c) { _parent-=c; return *this;}
alpar@119
    89
    operator int() {return 0;}
alpar@119
    90
  };
alpar@119
    91
alpar@119
    92
alpar@119
    93
  /// \addtogroup timecount
alpar@119
    94
  /// @{
alpar@119
    95
kpeter@160
    96
  /// A counter class
alpar@119
    97
kpeter@160
    98
  /// This class makes it easier to count certain events (e.g. for debug
kpeter@160
    99
  /// reasons).
kpeter@160
   100
  /// You can increment or decrement the counter using \c operator++,
kpeter@160
   101
  /// \c operator--, \c operator+= and \c operator-=. You can also
kpeter@160
   102
  /// define subcounters for the different phases of the algorithm or
kpeter@160
   103
  /// for different types of operations.
kpeter@160
   104
  /// A report containing the given title and the value of the counter
alpar@209
   105
  /// is automatically printed on destruction.
kpeter@160
   106
  ///
kpeter@160
   107
  /// The following example shows the usage of counters and subcounters.
kpeter@160
   108
  /// \code
kpeter@160
   109
  /// // Bubble sort
kpeter@160
   110
  /// std::vector<T> v;
kpeter@160
   111
  /// ...
kpeter@160
   112
  /// Counter op("Operations: ");
kpeter@160
   113
  /// Counter::SubCounter as(op, "Assignments: ");
kpeter@160
   114
  /// Counter::SubCounter co(op, "Comparisons: ");
kpeter@160
   115
  /// for (int i = v.size()-1; i > 0; --i) {
kpeter@160
   116
  ///   for (int j = 0; j < i; ++j) {
kpeter@160
   117
  ///     if (v[j] > v[j+1]) {
kpeter@160
   118
  ///       T tmp = v[j];
kpeter@160
   119
  ///       v[j] = v[j+1];
kpeter@160
   120
  ///       v[j+1] = tmp;
kpeter@160
   121
  ///       as += 3;          // three assignments
kpeter@160
   122
  ///     }
kpeter@160
   123
  ///     ++co;               // one comparison
kpeter@160
   124
  ///   }
kpeter@160
   125
  /// }
kpeter@160
   126
  /// \endcode
kpeter@160
   127
  ///
kpeter@160
   128
  /// This code prints out something like that:
kpeter@160
   129
  /// \code
kpeter@160
   130
  /// Comparisons: 45
kpeter@160
   131
  /// Assignments: 57
kpeter@160
   132
  /// Operations: 102
kpeter@160
   133
  /// \endcode
kpeter@160
   134
  ///
kpeter@160
   135
  /// \sa NoCounter
alpar@209
   136
  class Counter
alpar@119
   137
  {
alpar@119
   138
    std::string _title;
alpar@119
   139
    std::ostream &_os;
alpar@119
   140
    int count;
alpar@119
   141
  public:
alpar@119
   142
kpeter@160
   143
    /// SubCounter class
alpar@209
   144
kpeter@160
   145
    /// This class can be used to setup subcounters for a \ref Counter
kpeter@160
   146
    /// to have finer reports. A subcounter provides exactly the same
kpeter@160
   147
    /// operations as the main \ref Counter, but it also increments and
kpeter@160
   148
    /// decrements the value of its parent.
kpeter@160
   149
    /// Subcounters can also have subcounters.
alpar@209
   150
    ///
kpeter@160
   151
    /// The parent counter must be given as the first parameter of the
kpeter@160
   152
    /// constructor. Apart from that a title and an \c ostream object
kpeter@160
   153
    /// can also be given just like for the main \ref Counter.
alpar@119
   154
    ///
kpeter@160
   155
    /// A report containing the given title and the value of the
kpeter@160
   156
    /// subcounter is automatically printed on destruction. If you
kpeter@160
   157
    /// would like to turn off this report, use \ref NoSubCounter
kpeter@160
   158
    /// instead.
alpar@209
   159
    ///
kpeter@160
   160
    /// \sa NoSubCounter
alpar@119
   161
    typedef _SubCounter<Counter> SubCounter;
alpar@119
   162
alpar@209
   163
    /// SubCounter class without printing report on destruction
alpar@209
   164
kpeter@160
   165
    /// This class can be used to setup subcounters for a \ref Counter.
kpeter@160
   166
    /// It is the same as \ref SubCounter but it does not print report
kpeter@160
   167
    /// on destruction. (It modifies the value of its parent, so 'No'
kpeter@160
   168
    /// only means 'do not print'.)
alpar@119
   169
    ///
kpeter@160
   170
    /// Replacing \ref SubCounter "SubCounter"s with \ref NoSubCounter
alpar@209
   171
    /// "NoSubCounter"s makes it possible to turn off reporting
kpeter@160
   172
    /// subcounter values without actually removing the definitions
kpeter@160
   173
    /// and the increment or decrement operators.
kpeter@160
   174
    ///
kpeter@160
   175
    /// \sa SubCounter
alpar@121
   176
    typedef _NoSubCounter<Counter> NoSubCounter;
alpar@119
   177
kpeter@160
   178
    /// Constructor.
alpar@119
   179
    Counter() : _title(), _os(std::cerr), count(0) {}
kpeter@160
   180
    /// Constructor.
alpar@209
   181
    Counter(std::string title,std::ostream &os=std::cerr)
alpar@119
   182
      : _title(title), _os(os), count(0) {}
kpeter@160
   183
    /// Constructor.
alpar@119
   184
    Counter(const char *title,std::ostream &os=std::cerr)
alpar@119
   185
      : _title(title), _os(os), count(0) {}
kpeter@160
   186
    /// Destructor. Prints the given title and the value of the counter.
alpar@119
   187
    ~Counter() {
alpar@119
   188
      _os << _title << count <<std::endl;
alpar@119
   189
    }
alpar@119
   190
    ///\e
alpar@119
   191
    Counter &operator++() { count++; return *this;}
alpar@119
   192
    ///\e
alpar@119
   193
    int operator++(int) { return count++;}
alpar@119
   194
    ///\e
alpar@119
   195
    Counter &operator--() { count--; return *this;}
alpar@119
   196
    ///\e
alpar@119
   197
    int operator--(int) { return count--;}
alpar@119
   198
    ///\e
alpar@119
   199
    Counter &operator+=(int c) { count+=c; return *this;}
alpar@119
   200
    ///\e
alpar@119
   201
    Counter &operator-=(int c) { count-=c; return *this;}
kpeter@160
   202
    /// Resets the counter to the given value.
kpeter@168
   203
kpeter@168
   204
    /// Resets the counter to the given value.
kpeter@168
   205
    /// \note This function does not reset the values of
kpeter@168
   206
    /// \ref SubCounter "SubCounter"s but it resets \ref NoSubCounter
alpar@209
   207
    /// "NoSubCounter"s along with the main counter.
alpar@119
   208
    void reset(int c=0) {count=c;}
kpeter@160
   209
    /// Returns the value of the counter.
alpar@119
   210
    operator int() {return count;}
alpar@119
   211
  };
alpar@119
   212
kpeter@160
   213
  /// 'Do nothing' version of Counter.
alpar@119
   214
kpeter@160
   215
  /// This class can be used in the same way as \ref Counter however it
kpeter@160
   216
  /// does not count at all and does not print report on destruction.
kpeter@160
   217
  ///
kpeter@160
   218
  /// Replacing a \ref Counter with a \ref NoCounter makes it possible
kpeter@160
   219
  /// to turn off all counting and reporting (SubCounters should also
kpeter@160
   220
  /// be replaced with NoSubCounters), so it does not affect the
kpeter@160
   221
  /// efficiency of the program at all.
kpeter@160
   222
  ///
kpeter@160
   223
  /// \sa Counter
alpar@119
   224
  class NoCounter
alpar@119
   225
  {
alpar@119
   226
  public:
alpar@121
   227
    typedef _NoSubCounter<NoCounter> SubCounter;
alpar@121
   228
    typedef _NoSubCounter<NoCounter> NoSubCounter;
alpar@119
   229
alpar@119
   230
    NoCounter() {}
alpar@119
   231
    NoCounter(std::string,std::ostream &) {}
alpar@119
   232
    NoCounter(const char *,std::ostream &) {}
alpar@119
   233
    NoCounter(std::string) {}
alpar@119
   234
    NoCounter(const char *) {}
alpar@119
   235
    NoCounter &operator++() { return *this; }
alpar@119
   236
    int operator++(int) { return 0; }
alpar@119
   237
    NoCounter &operator--() { return *this; }
alpar@119
   238
    int operator--(int) { return 0; }
alpar@119
   239
    NoCounter &operator+=(int) { return *this;}
alpar@119
   240
    NoCounter &operator-=(int) { return *this;}
alpar@119
   241
    void reset(int) {}
alpar@119
   242
    void reset() {}
alpar@119
   243
    operator int() {return 0;}
alpar@119
   244
  };
alpar@119
   245
alpar@119
   246
  ///@}
alpar@119
   247
}
alpar@119
   248
alpar@119
   249
#endif