yat/utility/round.h

Code
Comments
Other
Rev Date Author Line
4059 20 Apr 21 peter 1 #ifndef _theplu_yat_utility_round_
4059 20 Apr 21 peter 2 #define _theplu_yat_utility_round_
4059 20 Apr 21 peter 3
4059 20 Apr 21 peter 4 // $Id$
4059 20 Apr 21 peter 5
4059 20 Apr 21 peter 6 /*
4059 20 Apr 21 peter 7   Copyright (C) 2021 Peter Johansson
4059 20 Apr 21 peter 8
4059 20 Apr 21 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
4059 20 Apr 21 peter 10
4059 20 Apr 21 peter 11   The yat library is free software; you can redistribute it and/or
4059 20 Apr 21 peter 12   modify it under the terms of the GNU General Public License as
4059 20 Apr 21 peter 13   published by the Free Software Foundation; either version 3 of the
4059 20 Apr 21 peter 14   License, or (at your option) any later version.
4059 20 Apr 21 peter 15
4059 20 Apr 21 peter 16   The yat library is distributed in the hope that it will be useful,
4059 20 Apr 21 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
4059 20 Apr 21 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4059 20 Apr 21 peter 19   General Public License for more details.
4059 20 Apr 21 peter 20
4059 20 Apr 21 peter 21   You should have received a copy of the GNU General Public License
4059 20 Apr 21 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
4059 20 Apr 21 peter 23 */
4059 20 Apr 21 peter 24
4059 20 Apr 21 peter 25 #include <cmath>
4059 20 Apr 21 peter 26 #include <map>
4059 20 Apr 21 peter 27
4059 20 Apr 21 peter 28 namespace theplu {
4059 20 Apr 21 peter 29 namespace yat {
4059 20 Apr 21 peter 30 namespace utility {
4059 20 Apr 21 peter 31
4059 20 Apr 21 peter 32   /**
4059 20 Apr 21 peter 33      \brief Round a range
4059 20 Apr 21 peter 34
4059 20 Apr 21 peter 35      Round each element in [first, last) to the neighboring integer,
4059 20 Apr 21 peter 36      such that the total difference is minimised, but with the
4059 20 Apr 21 peter 37      condition that the sum of elements in [result,
4059 20 Apr 21 peter 38      result+(last-first)) is equal to the sum of elements in the input
4059 20 Apr 21 peter 39      range [first, last).
4059 20 Apr 21 peter 40
4059 20 Apr 21 peter 41      It is possible to round "in place"; it is permissible for \a
4059 20 Apr 21 peter 42      first and \a result to point to the same value.
4059 20 Apr 21 peter 43
4059 20 Apr 21 peter 44      \since New in yat 0.19
4059 20 Apr 21 peter 45    */
4059 20 Apr 21 peter 46   template<typename InputIterator, typename ForwardIterator>
4059 20 Apr 21 peter 47   void round(InputIterator first, InputIterator last,
4059 20 Apr 21 peter 48              ForwardIterator result)
4059 20 Apr 21 peter 49   {
4059 20 Apr 21 peter 50     std::multimap<double, ForwardIterator> map;
4059 20 Apr 21 peter 51     double result_sum = 0;
4059 20 Apr 21 peter 52     double input_sum = 0;
4059 20 Apr 21 peter 53     for (auto it = first; it != last; ++it) {
4059 20 Apr 21 peter 54       // copy value here in case result and first point to same value
4059 20 Apr 21 peter 55       double x = *it;
4059 20 Apr 21 peter 56       input_sum += x;
4059 20 Apr 21 peter 57       *result = std::floor(x);
4059 20 Apr 21 peter 58       map.insert(std::make_pair(*result - x, result));
4059 20 Apr 21 peter 59       result_sum += *result;
4059 20 Apr 21 peter 60       ++result;
4059 20 Apr 21 peter 61     }
4059 20 Apr 21 peter 62     double rounded_sum = std::round(input_sum);
4059 20 Apr 21 peter 63
4059 20 Apr 21 peter 64     for (auto it = map.begin(); result_sum<rounded_sum; ++it) {
4059 20 Apr 21 peter 65       YAT_ASSERT(it != map.end());
4059 20 Apr 21 peter 66       *it->second += 1.0;
4059 20 Apr 21 peter 67       result_sum += 1.0;
4059 20 Apr 21 peter 68     }
4059 20 Apr 21 peter 69   }
4059 20 Apr 21 peter 70
4059 20 Apr 21 peter 71 }}} // of namespace utility, yat, and theplu
4059 20 Apr 21 peter 72
4059 20 Apr 21 peter 73 #endif

Generated on Sat Oct 14 02:25:52 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)