statistics/detail/rank.hpp

0001 //  (C) Copyright Matt Borland 2022
0002 //  Use, modification and distribution are subject to the
0003 //  Boost Software License, Version 1.0. (See accompanying file
0004 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_MATH_STATISTICS_DETAIL_RANK_HPP
0007 #define BOOST_MATH_STATISTICS_DETAIL_RANK_HPP
0008
0009 #include <cstdint>
0010 #include <vector>
0011 #include <numeric>
0012 #include <utility>
0013 #include <iterator>
0014 #include <algorithm>
0015 #include <boost/math/tools/config.hpp>
0016
0017 #ifdef BOOST_MATH_EXEC_COMPATIBLE
0018 #include <execution>
0019 #endif
0020
0021 namespace boost { namespace math { namespace statistics { namespace detail {
0022
0023 struct pair_equal
0024 {
0025     template <typename T1, typename T2>
0026     bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
0027     {
0028         return a.first == b.first;
0029     }
0030 };
0031
0032 }}}} // Namespaces
0033
0034 #ifndef BOOST_MATH_EXEC_COMPATIBLE
0035
0036 namespace boost { namespace math { namespace statistics { namespace detail {
0037
0038 template <typename ForwardIterator, typename T = typename std::iterator_traits<ForwardIterator>::value_type>
0039 auto rank(ForwardIterator first, ForwardIterator last) -> std::vector<std::size_t>
0040 {
0041     std::size_t elements = std::distance(first, last);
0042
0043     std::vector<std::pair<T, std::size_t>> rank_vector(elements);
0044     std::size_t i = 0;
0045     while (first != last)
0046     {
0047         rank_vector[i] = std::make_pair(*first, i);
0048         ++i;
0049         ++first;
0050     }
0051
0052     std::sort(rank_vector.begin(), rank_vector.end());
0053
0054     // Remove duplicates
0055     rank_vector.erase(std::unique(rank_vector.begin(), rank_vector.end(), pair_equal()), rank_vector.end());
0056     elements = rank_vector.size();
0057
0058     std::pair<T, std::size_t> rank;
0059     std::vector<std::size_t> result(elements);
0060     for (i = 0; i < elements; ++i)
0061     {
0062         if (rank_vector[i].first != rank.first)
0063         {
0064             rank = std::make_pair(rank_vector[i].first, i);
0065         }
0066         result[rank_vector[i].second] = rank.second;
0067     }
0068
0069     return result;
0070 }
0071
0072 template <typename Container>
0073 inline auto rank(const Container& c) -> std::vector<std::size_t>
0074 {
0075     return rank(std::begin(c), std::end(c));
0076 }
0077
0078 }}}} // Namespaces
0079
0080 #else
0081
0082 namespace boost::math::statistics::detail {
0083
0084 template <typename ExecutionPolicy, typename ForwardIterator, typename T = typename std::iterator_traits<ForwardIterator>::value_type>
0085 auto rank(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last)
0086 {
0087     std::size_t elements = std::distance(first, last);
0088
0089     std::vector<std::pair<T, std::size_t>> rank_vector(elements);
0090     std::size_t i = 0;
0091     while (first != last)
0092     {
0093         rank_vector[i] = std::make_pair(*first, i);
0094         ++i;
0095         ++first;
0096     }
0097
0098     std::sort(exec, rank_vector.begin(), rank_vector.end());
0099
0100     // Remove duplicates
0101     rank_vector.erase(std::unique(exec, rank_vector.begin(), rank_vector.end(), pair_equal()), rank_vector.end());
0102     elements = rank_vector.size();
0103
0104     std::pair<T, std::size_t> rank;
0105     std::vector<std::size_t> result(elements);
0106     for (i = 0; i < elements; ++i)
0107     {
0108         if (rank_vector[i].first != rank.first)
0109         {
0110             rank = std::make_pair(rank_vector[i].first, i);
0111         }
0112         result[rank_vector[i].second] = rank.second;
0113     }
0114
0115     return result;
0116 }
0117
0118 template <typename ExecutionPolicy, typename Container>
0119 inline auto rank(ExecutionPolicy&& exec, const Container& c)
0120 {
0121     return rank(exec, std::cbegin(c), std::cend(c));
0122 }
0123
0124 template <typename ForwardIterator, typename T = typename std::iterator_traits<ForwardIterator>::value_type>
0125 inline auto rank(ForwardIterator first, ForwardIterator last)
0126 {
0127     return rank(std::execution::seq, first, last);
0128 }
0129
0130 template <typename Container>
0131 inline auto rank(const Container& c)
0132 {
0133     return rank(std::execution::seq, std::cbegin(c), std::cend(c));
0134 }
0135
0136 } // Namespaces
0137
0138 #endif // BOOST_MATH_EXEC_COMPATIBLE
0139
0140 #endif // BOOST_MATH_STATISTICS_DETAIL_RANK_HPP