| // -*- C++ -*- | |
| // Copyright (C) 2007-2026 Free Software Foundation, Inc. | |
| // | |
| // This file is part of the GNU ISO C++ Library. This library is free | |
| // software; you can redistribute it and/or modify it under the terms | |
| // of the GNU General Public License as published by the Free Software | |
| // Foundation; either version 3, or (at your option) any later | |
| // version. | |
| // This library is distributed in the hope that it will be useful, but | |
| // WITHOUT ANY WARRANTY; without even the implied warranty of | |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| // General Public License for more details. | |
| // Under Section 7 of GPL version 3, you are granted additional | |
| // permissions described in the GCC Runtime Library Exception, version | |
| // 3.1, as published by the Free Software Foundation. | |
| // You should have received a copy of the GNU General Public License and | |
| // a copy of the GCC Runtime Library Exception along with this program; | |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
| // <http://www.gnu.org/licenses/>. | |
| /** @file parallel/multiseq_selection.h | |
| * @brief Functions to find elements of a certain global __rank in | |
| * multiple sorted sequences. Also serves for splitting such | |
| * sequence sets. | |
| * | |
| * The algorithm description can be found in | |
| * | |
| * P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. | |
| * Merging Multiple Lists on Hierarchical-Memory Multiprocessors. | |
| * Journal of Parallel and Distributed Computing, 12(2):171-177, 1991. | |
| * | |
| * This file is a GNU parallel extension to the Standard C++ Library. | |
| */ | |
| // Written by Johannes Singler. | |
| #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H | |
| #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 | |
| #include <vector> | |
| #include <queue> | |
| #include <bits/stl_algo.h> | |
| namespace __gnu_parallel | |
| { | |
| #pragma GCC diagnostic push | |
| #pragma GCC diagnostic ignored "-Wdeprecated-declarations" // *nary_function | |
| /** @brief Compare __a pair of types lexicographically, ascending. */ | |
| template<typename _T1, typename _T2, typename _Compare> | |
| class _Lexicographic | |
| : public std::binary_function<std::pair<_T1, _T2>, | |
| std::pair<_T1, _T2>, bool> | |
| { | |
| private: | |
| _Compare& _M_comp; | |
| public: | |
| _Lexicographic(_Compare& __comp) : _M_comp(__comp) { } | |
| bool | |
| operator()(const std::pair<_T1, _T2>& __p1, | |
| const std::pair<_T1, _T2>& __p2) const | |
| { | |
| if (_M_comp(__p1.first, __p2.first)) | |
| return true; | |
| if (_M_comp(__p2.first, __p1.first)) | |
| return false; | |
| // Firsts are equal. | |
| return __p1.second < __p2.second; | |
| } | |
| }; | |
| /** @brief Compare __a pair of types lexicographically, descending. */ | |
| template<typename _T1, typename _T2, typename _Compare> | |
| class _LexicographicReverse : public std::binary_function<_T1, _T2, bool> | |
| { | |
| private: | |
| _Compare& _M_comp; | |
| public: | |
| _LexicographicReverse(_Compare& __comp) : _M_comp(__comp) { } | |
| bool | |
| operator()(const std::pair<_T1, _T2>& __p1, | |
| const std::pair<_T1, _T2>& __p2) const | |
| { | |
| if (_M_comp(__p2.first, __p1.first)) | |
| return true; | |
| if (_M_comp(__p1.first, __p2.first)) | |
| return false; | |
| // Firsts are equal. | |
| return __p2.second < __p1.second; | |
| } | |
| }; | |
| #pragma GCC diagnostic pop // -Wdeprecated-declarations | |
| /** | |
| * @brief Splits several sorted sequences at a certain global __rank, | |
| * resulting in a splitting point for each sequence. | |
| * The sequences are passed via a sequence of random-access | |
| * iterator pairs, none of the sequences may be empty. If there | |
| * are several equal elements across the split, the ones on the | |
| * __left side will be chosen from sequences with smaller number. | |
| * @param __begin_seqs Begin of the sequence of iterator pairs. | |
| * @param __end_seqs End of the sequence of iterator pairs. | |
| * @param __rank The global rank to partition at. | |
| * @param __begin_offsets A random-access __sequence __begin where the | |
| * __result will be stored in. Each element of the sequence is an | |
| * iterator that points to the first element on the greater part of | |
| * the respective __sequence. | |
| * @param __comp The ordering functor, defaults to std::less<_Tp>. | |
| */ | |
| template<typename _RanSeqs, typename _RankType, typename _RankIterator, | |
| typename _Compare> | |
| void | |
| multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, | |
| _RankType __rank, | |
| _RankIterator __begin_offsets, | |
| _Compare __comp = std::less< | |
| typename std::iterator_traits<typename | |
| std::iterator_traits<_RanSeqs>::value_type:: | |
| first_type>::value_type>()) // std::less<_Tp> | |
| { | |
| _GLIBCXX_CALL(__end_seqs - __begin_seqs) | |
| typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type | |
| _It; | |
| typedef typename std::iterator_traits<_RanSeqs>::difference_type | |
| _SeqNumber; | |
| typedef typename std::iterator_traits<_It>::difference_type | |
| _DifferenceType; | |
| typedef typename std::iterator_traits<_It>::value_type _ValueType; | |
| _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp); | |
| _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp); | |
| // Number of sequences, number of elements in total (possibly | |
| // including padding). | |
| _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0, | |
| __nmax, __n, __r; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| { | |
| __nn += std::distance(__begin_seqs[__i].first, | |
| __begin_seqs[__i].second); | |
| _GLIBCXX_PARALLEL_ASSERT( | |
| std::distance(__begin_seqs[__i].first, | |
| __begin_seqs[__i].second) > 0); | |
| } | |
| if (__rank == __nn) | |
| { | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| __begin_offsets[__i] = __begin_seqs[__i].second; // Very end. | |
| // Return __m - 1; | |
| return; | |
| } | |
| _GLIBCXX_PARALLEL_ASSERT(__m != 0); | |
| _GLIBCXX_PARALLEL_ASSERT(__nn != 0); | |
| _GLIBCXX_PARALLEL_ASSERT(__rank >= 0); | |
| _GLIBCXX_PARALLEL_ASSERT(__rank < __nn); | |
| _DifferenceType* __ns = new _DifferenceType[__m]; | |
| _DifferenceType* __a = new _DifferenceType[__m]; | |
| _DifferenceType* __b = new _DifferenceType[__m]; | |
| _DifferenceType __l; | |
| __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); | |
| __nmax = __ns[0]; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| { | |
| __ns[__i] = std::distance(__begin_seqs[__i].first, | |
| __begin_seqs[__i].second); | |
| __nmax = std::max(__nmax, __ns[__i]); | |
| } | |
| __r = __rd_log2(__nmax) + 1; | |
| #pragma GCC diagnostic push | |
| #pragma GCC diagnostic ignored "-Wlong-long" // LL literal | |
| // Pad all lists to this length, at least as long as any ns[__i], | |
| // equality iff __nmax = 2^__k - 1. | |
| __l = (1ULL << __r) - 1; | |
| #pragma GCC diagnostic pop | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| { | |
| __a[__i] = 0; | |
| __b[__i] = __l; | |
| } | |
| __n = __l / 2; | |
| // Invariants: | |
| // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l | |
| #define __S(__i) (__begin_seqs[__i].first) | |
| // Initial partition. | |
| std::vector<std::pair<_ValueType, _SeqNumber> > __sample; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| if (__n < __ns[__i]) //__sequence long enough | |
| __sample.push_back(std::make_pair(__S(__i)[__n], __i)); | |
| __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp); | |
| for (_SeqNumber __i = 0; __i < __m; __i++) //conceptual infinity | |
| if (__n >= __ns[__i]) //__sequence too short, conceptual infinity | |
| __sample.push_back( | |
| std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); | |
| _DifferenceType __localrank = __rank / __l; | |
| _SeqNumber __j; | |
| for (__j = 0; | |
| __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); | |
| ++__j) | |
| __a[__sample[__j].second] += __n + 1; | |
| for (; __j < __m; __j++) | |
| __b[__sample[__j].second] -= __n + 1; | |
| // Further refinement. | |
| while (__n > 0) | |
| { | |
| __n /= 2; | |
| _SeqNumber __lmax_seq = -1; // to avoid warning | |
| const _ValueType* __lmax = 0; // impossible to avoid the warning? | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| { | |
| if (__a[__i] > 0) | |
| { | |
| if (!__lmax) | |
| { | |
| __lmax = &(__S(__i)[__a[__i] - 1]); | |
| __lmax_seq = __i; | |
| } | |
| else | |
| { | |
| // Max, favor rear sequences. | |
| if (!__comp(__S(__i)[__a[__i] - 1], *__lmax)) | |
| { | |
| __lmax = &(__S(__i)[__a[__i] - 1]); | |
| __lmax_seq = __i; | |
| } | |
| } | |
| } | |
| } | |
| _SeqNumber __i; | |
| for (__i = 0; __i < __m; __i++) | |
| { | |
| _DifferenceType __middle = (__b[__i] + __a[__i]) / 2; | |
| if (__lmax && __middle < __ns[__i] && | |
| __lcomp(std::make_pair(__S(__i)[__middle], __i), | |
| std::make_pair(*__lmax, __lmax_seq))) | |
| __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]); | |
| else | |
| __b[__i] -= __n + 1; | |
| } | |
| _DifferenceType __leftsize = 0; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| __leftsize += __a[__i] / (__n + 1); | |
| _DifferenceType __skew = __rank / (__n + 1) - __leftsize; | |
| if (__skew > 0) | |
| { | |
| // Move to the left, find smallest. | |
| std::priority_queue<std::pair<_ValueType, _SeqNumber>, | |
| std::vector<std::pair<_ValueType, _SeqNumber> >, | |
| _LexicographicReverse<_ValueType, _SeqNumber, _Compare> > | |
| __pq(__lrcomp); | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| if (__b[__i] < __ns[__i]) | |
| __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); | |
| for (; __skew != 0 && !__pq.empty(); --__skew) | |
| { | |
| _SeqNumber __source = __pq.top().second; | |
| __pq.pop(); | |
| __a[__source] | |
| = std::min(__a[__source] + __n + 1, __ns[__source]); | |
| __b[__source] += __n + 1; | |
| if (__b[__source] < __ns[__source]) | |
| __pq.push( | |
| std::make_pair(__S(__source)[__b[__source]], __source)); | |
| } | |
| } | |
| else if (__skew < 0) | |
| { | |
| // Move to the right, find greatest. | |
| std::priority_queue<std::pair<_ValueType, _SeqNumber>, | |
| std::vector<std::pair<_ValueType, _SeqNumber> >, | |
| _Lexicographic<_ValueType, _SeqNumber, _Compare> > | |
| __pq(__lcomp); | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| if (__a[__i] > 0) | |
| __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); | |
| for (; __skew != 0; ++__skew) | |
| { | |
| _SeqNumber __source = __pq.top().second; | |
| __pq.pop(); | |
| __a[__source] -= __n + 1; | |
| __b[__source] -= __n + 1; | |
| if (__a[__source] > 0) | |
| __pq.push(std::make_pair( | |
| __S(__source)[__a[__source] - 1], __source)); | |
| } | |
| } | |
| } | |
| // Postconditions: | |
| // __a[__i] == __b[__i] in most cases, except when __a[__i] has been | |
| // clamped because of having reached the boundary | |
| // Now return the result, calculate the offset. | |
| // Compare the keys on both edges of the border. | |
| // Maximum of left edge, minimum of right edge. | |
| _ValueType* __maxleft = 0; | |
| _ValueType* __minright = 0; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| { | |
| if (__a[__i] > 0) | |
| { | |
| if (!__maxleft) | |
| __maxleft = &(__S(__i)[__a[__i] - 1]); | |
| else | |
| { | |
| // Max, favor rear sequences. | |
| if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft)) | |
| __maxleft = &(__S(__i)[__a[__i] - 1]); | |
| } | |
| } | |
| if (__b[__i] < __ns[__i]) | |
| { | |
| if (!__minright) | |
| __minright = &(__S(__i)[__b[__i]]); | |
| else | |
| { | |
| // Min, favor fore sequences. | |
| if (__comp(__S(__i)[__b[__i]], *__minright)) | |
| __minright = &(__S(__i)[__b[__i]]); | |
| } | |
| } | |
| } | |
| _SeqNumber __seq = 0; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| __begin_offsets[__i] = __S(__i) + __a[__i]; | |
| delete[] __ns; | |
| delete[] __a; | |
| delete[] __b; | |
| } | |
| /** | |
| * @brief Selects the element at a certain global __rank from several | |
| * sorted sequences. | |
| * | |
| * The sequences are passed via a sequence of random-access | |
| * iterator pairs, none of the sequences may be empty. | |
| * @param __begin_seqs Begin of the sequence of iterator pairs. | |
| * @param __end_seqs End of the sequence of iterator pairs. | |
| * @param __rank The global rank to partition at. | |
| * @param __offset The rank of the selected element in the global | |
| * subsequence of elements equal to the selected element. If the | |
| * selected element is unique, this number is 0. | |
| * @param __comp The ordering functor, defaults to std::less. | |
| */ | |
| template<typename _Tp, typename _RanSeqs, typename _RankType, | |
| typename _Compare> | |
| _Tp | |
| multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, | |
| _RankType __rank, | |
| _RankType& __offset, _Compare __comp = std::less<_Tp>()) | |
| { | |
| _GLIBCXX_CALL(__end_seqs - __begin_seqs) | |
| typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type | |
| _It; | |
| typedef typename std::iterator_traits<_RanSeqs>::difference_type | |
| _SeqNumber; | |
| typedef typename std::iterator_traits<_It>::difference_type | |
| _DifferenceType; | |
| _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp); | |
| _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp); | |
| // Number of sequences, number of elements in total (possibly | |
| // including padding). | |
| _DifferenceType __m = std::distance(__begin_seqs, __end_seqs); | |
| _DifferenceType __nn = 0; | |
| _DifferenceType __nmax, __n, __r; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| __nn += std::distance(__begin_seqs[__i].first, | |
| __begin_seqs[__i].second); | |
| if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn) | |
| { | |
| // result undefined if there is no data or __rank is outside bounds | |
| throw std::exception(); | |
| } | |
| _DifferenceType* __ns = new _DifferenceType[__m]; | |
| _DifferenceType* __a = new _DifferenceType[__m]; | |
| _DifferenceType* __b = new _DifferenceType[__m]; | |
| _DifferenceType __l; | |
| __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); | |
| __nmax = __ns[0]; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| { | |
| __ns[__i] = std::distance(__begin_seqs[__i].first, | |
| __begin_seqs[__i].second); | |
| __nmax = std::max(__nmax, __ns[__i]); | |
| } | |
| __r = __rd_log2(__nmax) + 1; | |
| // Pad all lists to this length, at least as long as any ns[__i], | |
| // equality iff __nmax = 2^__k - 1 | |
| __l = __round_up_to_pow2(__r) - 1; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| { | |
| __a[__i] = 0; | |
| __b[__i] = __l; | |
| } | |
| __n = __l / 2; | |
| // Invariants: | |
| // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l | |
| #define __S(__i) (__begin_seqs[__i].first) | |
| // Initial partition. | |
| std::vector<std::pair<_Tp, _SeqNumber> > __sample; | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| if (__n < __ns[__i]) | |
| __sample.push_back(std::make_pair(__S(__i)[__n], __i)); | |
| __gnu_sequential::sort(__sample.begin(), __sample.end(), | |
| __lcomp, sequential_tag()); | |
| // Conceptual infinity. | |
| for (_SeqNumber __i = 0; __i < __m; __i++) | |
| if (__n >= __ns[__i]) | |
| __sample.push_back( | |
| std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); | |
| _DifferenceType __localrank = __rank / __l; | |
| _SeqNumber __j; | |
| for (__j = 0; | |
| __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); | |
| ++__j) | |
| __a[__sample[__j].second] += __n + 1; | |
| for (; __j < __m; ++__j) | |
| __b[__sample[__j].second] -= __n + 1; | |
| // Further refinement. | |
| while (__n > 0) | |
| { | |
| __n /= 2; | |
| const _Tp* __lmax = 0; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| { | |
| if (__a[__i] > 0) | |
| { | |
| if (!__lmax) | |
| __lmax = &(__S(__i)[__a[__i] - 1]); | |
| else | |
| { | |
| if (__comp(*__lmax, __S(__i)[__a[__i] - 1])) //max | |
| __lmax = &(__S(__i)[__a[__i] - 1]); | |
| } | |
| } | |
| } | |
| _SeqNumber __i; | |
| for (__i = 0; __i < __m; __i++) | |
| { | |
| _DifferenceType __middle = (__b[__i] + __a[__i]) / 2; | |
| if (__lmax && __middle < __ns[__i] | |
| && __comp(__S(__i)[__middle], *__lmax)) | |
| __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]); | |
| else | |
| __b[__i] -= __n + 1; | |
| } | |
| _DifferenceType __leftsize = 0; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| __leftsize += __a[__i] / (__n + 1); | |
| _DifferenceType __skew = __rank / (__n + 1) - __leftsize; | |
| if (__skew > 0) | |
| { | |
| // Move to the left, find smallest. | |
| std::priority_queue<std::pair<_Tp, _SeqNumber>, | |
| std::vector<std::pair<_Tp, _SeqNumber> >, | |
| _LexicographicReverse<_Tp, _SeqNumber, _Compare> > | |
| __pq(__lrcomp); | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| if (__b[__i] < __ns[__i]) | |
| __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); | |
| for (; __skew != 0 && !__pq.empty(); --__skew) | |
| { | |
| _SeqNumber __source = __pq.top().second; | |
| __pq.pop(); | |
| __a[__source] | |
| = std::min(__a[__source] + __n + 1, __ns[__source]); | |
| __b[__source] += __n + 1; | |
| if (__b[__source] < __ns[__source]) | |
| __pq.push( | |
| std::make_pair(__S(__source)[__b[__source]], __source)); | |
| } | |
| } | |
| else if (__skew < 0) | |
| { | |
| // Move to the right, find greatest. | |
| std::priority_queue<std::pair<_Tp, _SeqNumber>, | |
| std::vector<std::pair<_Tp, _SeqNumber> >, | |
| _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp); | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| if (__a[__i] > 0) | |
| __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); | |
| for (; __skew != 0; ++__skew) | |
| { | |
| _SeqNumber __source = __pq.top().second; | |
| __pq.pop(); | |
| __a[__source] -= __n + 1; | |
| __b[__source] -= __n + 1; | |
| if (__a[__source] > 0) | |
| __pq.push(std::make_pair( | |
| __S(__source)[__a[__source] - 1], __source)); | |
| } | |
| } | |
| } | |
| // Postconditions: | |
| // __a[__i] == __b[__i] in most cases, except when __a[__i] has been | |
| // clamped because of having reached the boundary | |
| // Now return the result, calculate the offset. | |
| // Compare the keys on both edges of the border. | |
| // Maximum of left edge, minimum of right edge. | |
| bool __maxleftset = false, __minrightset = false; | |
| // Impossible to avoid the warning? | |
| _Tp __maxleft, __minright; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| { | |
| if (__a[__i] > 0) | |
| { | |
| if (!__maxleftset) | |
| { | |
| __maxleft = __S(__i)[__a[__i] - 1]; | |
| __maxleftset = true; | |
| } | |
| else | |
| { | |
| // Max. | |
| if (__comp(__maxleft, __S(__i)[__a[__i] - 1])) | |
| __maxleft = __S(__i)[__a[__i] - 1]; | |
| } | |
| } | |
| if (__b[__i] < __ns[__i]) | |
| { | |
| if (!__minrightset) | |
| { | |
| __minright = __S(__i)[__b[__i]]; | |
| __minrightset = true; | |
| } | |
| else | |
| { | |
| // Min. | |
| if (__comp(__S(__i)[__b[__i]], __minright)) | |
| __minright = __S(__i)[__b[__i]]; | |
| } | |
| } | |
| } | |
| // Minright is the __splitter, in any case. | |
| if (!__maxleftset || __comp(__minright, __maxleft)) | |
| { | |
| // Good luck, everything is split unambiguously. | |
| __offset = 0; | |
| } | |
| else | |
| { | |
| // We have to calculate an offset. | |
| __offset = 0; | |
| for (_SeqNumber __i = 0; __i < __m; ++__i) | |
| { | |
| _DifferenceType lb | |
| = std::lower_bound(__S(__i), __S(__i) + __ns[__i], | |
| __minright, | |
| __comp) - __S(__i); | |
| __offset += __a[__i] - lb; | |
| } | |
| } | |
| delete[] __ns; | |
| delete[] __a; | |
| delete[] __b; | |
| return __minright; | |
| } | |
| } | |
| #undef __S | |
| #endif /* _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H */ |