xapian-core/api/roundestimate.h

   1 /** @file
   2  * @brief Round a bounded estimate to an appropriate number of S.F.
   3  */
   4 /* Copyright 2017,2019 Olly Betts
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  19  */
  20
  21 #ifndef XAPIAN_INCLUDED_ROUNDESTIMATE_H
  22 #define XAPIAN_INCLUDED_ROUNDESTIMATE_H
  23
  24 #include <algorithm>
  25 #include <cmath>
  26 #include "exp10.h"
  27
  28 /** Round a bounded estimate to an appropriate number of S.F.
  29  *
  30  *  The algorithm used looks at the lower and upper bound and where the
  31  *  estimate sits between them and picks a number of significant figures
  32  *  which doesn't suggest much more precision than there is, while still
  33  *  providing a useful estimate.
  34  */
  35 template<typename T>
  36 inline Xapian::doccount
  37 round_estimate(T lb, T ub, T est)
  38 {
  39     using namespace std;
  40
  41     // We round based on the difference between the bounds, or the estimate if
  42     // that's smaller - for example, consider lb=11, est=24, ub=1234 where
  43     // rounding est to a multiple of 10 is reasonable but rounding it to a
  44     // multiple of 1000 isn't.
  45     T scale = min(ub - lb, est);
  46     if (scale <= 10) {
  47         // Estimate is either too close to exact or too small to round.
  48         return est;
  49     }
  50
  51     // Set r to the largest power of 10 <= scale.
  52     T r = T(exp10(int(log10(scale))) + 0.5);
  53
  54     // Set result to est with less significant digits truncated.
  55     T result = est / r * r;
  56     if (result < lb) {
  57         // We have to round up to be above the lower bound.
  58         result += r;
  59     } else if (result > ub - r) {
  60         // We can't round up as it would exceed the upper bound.
  61     } else {
  62         // We can choose which way to round so consider whether we're before or
  63         // after the mid-point of [result, result+r] and round to the nearer
  64         // end of the range.  If we're exactly on the middle, pick the rounding
  65         // direction which puts the rounded estimate closest to the mid-range
  66         // of the bounds.
  67         T d = 2 * (est - result);
  68         if (d > r || (d == r && result - lb <= ub - r - result)) {
  69             result += r;
  70         }
  71     }
  72
  73     return result;
  74 }
  75
  76 #endif // XAPIAN_INCLUDED_ROUNDESTIMATE_H