111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2007-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file parallel/multiseq_selection.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Functions to find elements of a certain global __rank in 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * multiple sorted sequences. Also serves for splitting such 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * sequence sets. 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The algorithm description can be found in 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Merging Multiple Lists on Hierarchical-Memory Multiprocessors. 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Journal of Parallel and Distributed Computing, 12(2):171–177, 1991. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU parallel extension to the Standard C++ Library. 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Written by Johannes Singler. 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <vector> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <queue> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <bits/stl_algo.h> 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_parallel 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Compare __a pair of types lexicographically, ascending. */ 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _T1, typename _T2, typename _Compare> 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Lexicographic 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public std::binary_function<std::pair<_T1, _T2>, 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_T1, _T2>, bool> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare& _M_comp; 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Lexicographic(_Compare& __comp) : _M_comp(__comp) { } 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(const std::pair<_T1, _T2>& __p1, 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const std::pair<_T1, _T2>& __p2) const 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_comp(__p1.first, __p2.first)) 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_comp(__p2.first, __p1.first)) 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Firsts are equal. 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p1.second < __p2.second; 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Compare __a pair of types lexicographically, descending. */ 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _T1, typename _T2, typename _Compare> 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _LexicographicReverse : public std::binary_function<_T1, _T2, bool> 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare& _M_comp; 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _LexicographicReverse(_Compare& __comp) : _M_comp(__comp) { } 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(const std::pair<_T1, _T2>& __p1, 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const std::pair<_T1, _T2>& __p2) const 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_comp(__p2.first, __p1.first)) 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_comp(__p1.first, __p2.first)) 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Firsts are equal. 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __p2.second < __p1.second; 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Splits several sorted sequences at a certain global __rank, 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * resulting in a splitting point for each sequence. 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The sequences are passed via a sequence of random-access 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterator pairs, none of the sequences may be empty. If there 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * are several equal elements across the split, the ones on the 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * __left side will be chosen from sequences with smaller number. 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin_seqs Begin of the sequence of iterator pairs. 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end_seqs End of the sequence of iterator pairs. 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __rank The global rank to partition at. 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin_offsets A random-access __sequence __begin where the 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * __result will be stored in. Each element of the sequence is an 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterator that points to the first element on the greater part of 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * the respective __sequence. 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp The ordering functor, defaults to std::less<_Tp>. 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RanSeqs, typename _RankType, typename _RankIterator, 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RankType __rank, 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RankIterator __begin_offsets, 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare __comp = std::less< 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename std::iterator_traits<typename 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::iterator_traits<_RanSeqs>::value_type:: 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert first_type>::value_type>()) // std::less<_Tp> 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__end_seqs - __begin_seqs) 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _It; 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RanSeqs>::difference_type 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_It>::difference_type 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_It>::value_type _ValueType; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp); 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp); 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Number of sequences, number of elements in total (possibly 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // including padding). 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0, 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nmax, __n, __r; 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nn += std::distance(__begin_seqs[__i].first, 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_seqs[__i].second); 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT( 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::distance(__begin_seqs[__i].first, 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_seqs[__i].second) > 0); 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__rank == __nn) 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_offsets[__i] = __begin_seqs[__i].second; // Very end. 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Return __m - 1; 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(__m != 0); 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(__nn != 0); 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(__rank >= 0); 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(__rank < __nn); 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __ns = new _DifferenceType[__m]; 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __a = new _DifferenceType[__m]; 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __b = new _DifferenceType[__m]; 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __l; 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nmax = __ns[0]; 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __ns[__i] = std::distance(__begin_seqs[__i].first, 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_seqs[__i].second); 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nmax = std::max(__nmax, __ns[__i]); 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __rd_log2(__nmax) + 1; 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Pad all lists to this length, at least as long as any ns[__i], 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // equality iff __nmax = 2^__k - 1. 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __l = (1ULL << __r) - 1; 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__i] = 0; 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__i] = __l; 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n = __l / 2; 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Invariants: 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define __S(__i) (__begin_seqs[__i].first) 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Initial partition. 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_ValueType, _SeqNumber> > __sample; 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__n < __ns[__i]) //__sequence long enough 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __sample.push_back(std::make_pair(__S(__i)[__n], __i)); 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp); 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) //conceptual infinity 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__n >= __ns[__i]) //__sequence too short, conceptual infinity 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __sample.push_back( 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __localrank = __rank / __l; 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __j; 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__j = 0; 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__j) 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__sample[__j].second] += __n + 1; 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __j < __m; __j++) 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__sample[__j].second] -= __n + 1; 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Further refinement. 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__n > 0) 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n /= 2; 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __lmax_seq = -1; // to avoid warning 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _ValueType* __lmax = 0; // impossible to avoid the warning? 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__lmax) 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax = &(__S(__i)[__a[__i] - 1]); 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax_seq = __i; 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Max, favor rear sequences. 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__comp(__S(__i)[__a[__i] - 1], *__lmax)) 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax = &(__S(__i)[__a[__i] - 1]); 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax_seq = __i; 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __i; 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < __m; __i++) 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __middle = (__b[__i] + __a[__i]) / 2; 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__lmax && __middle < __ns[__i] && 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lcomp(std::make_pair(__S(__i)[__middle], __i), 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(*__lmax, __lmax_seq))) 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]); 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__i] -= __n + 1; 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __leftsize = 0; 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __leftsize += __a[__i] / (__n + 1); 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __skew = __rank / (__n + 1) - __leftsize; 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__skew > 0) 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Move to the left, find smallest. 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::priority_queue<std::pair<_ValueType, _SeqNumber>, 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_ValueType, _SeqNumber> >, 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _LexicographicReverse<_ValueType, _SeqNumber, _Compare> > 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq(__lrcomp); 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__i] < __ns[__i]) 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __skew != 0 && !__pq.empty(); --__skew) 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __source = __pq.top().second; 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.pop(); 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__source] 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = std::min(__a[__source] + __n + 1, __ns[__source]); 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__source] += __n + 1; 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__source] < __ns[__source]) 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push( 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(__S(__source)[__b[__source]], __source)); 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__skew < 0) 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Move to the right, find greatest. 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::priority_queue<std::pair<_ValueType, _SeqNumber>, 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_ValueType, _SeqNumber> >, 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Lexicographic<_ValueType, _SeqNumber, _Compare> > 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq(__lcomp); 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __skew != 0; ++__skew) 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __source = __pq.top().second; 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.pop(); 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__source] -= __n + 1; 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__source] -= __n + 1; 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__source] > 0) 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair( 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __S(__source)[__a[__source] - 1], __source)); 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Postconditions: 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __a[__i] == __b[__i] in most cases, except when __a[__i] has been 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // clamped because of having reached the boundary 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Now return the result, calculate the offset. 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Compare the keys on both edges of the border. 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Maximum of left edge, minimum of right edge. 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType* __maxleft = 0; 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType* __minright = 0; 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__maxleft) 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __maxleft = &(__S(__i)[__a[__i] - 1]); 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Max, favor rear sequences. 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft)) 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __maxleft = &(__S(__i)[__a[__i] - 1]); 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__i] < __ns[__i]) 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__minright) 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minright = &(__S(__i)[__b[__i]]); 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Min, favor fore sequences. 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(__S(__i)[__b[__i]], *__minright)) 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minright = &(__S(__i)[__b[__i]]); 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __seq = 0; 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_offsets[__i] = __S(__i) + __a[__i]; 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __ns; 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __a; 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __b; 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Selects the element at a certain global __rank from several 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * sorted sequences. 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The sequences are passed via a sequence of random-access 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * iterator pairs, none of the sequences may be empty. 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin_seqs Begin of the sequence of iterator pairs. 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end_seqs End of the sequence of iterator pairs. 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __rank The global rank to partition at. 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __offset The rank of the selected element in the global 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * subsequence of elements equal to the selected element. If the 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * selected element is unique, this number is 0. 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp The ordering functor, defaults to std::less. 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _Tp, typename _RanSeqs, typename _RankType, 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Tp 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RankType __rank, 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RankType& __offset, _Compare __comp = std::less<_Tp>()) 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__end_seqs - __begin_seqs) 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _It; 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RanSeqs>::difference_type 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber; 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_It>::difference_type 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType; 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp); 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp); 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Number of sequences, number of elements in total (possibly 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // including padding). 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __m = std::distance(__begin_seqs, __end_seqs); 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __nn = 0; 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __nmax, __n, __r; 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nn += std::distance(__begin_seqs[__i].first, 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_seqs[__i].second); 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn) 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // result undefined if there is no data or __rank is outside bounds 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert throw std::exception(); 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __ns = new _DifferenceType[__m]; 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __a = new _DifferenceType[__m]; 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __b = new _DifferenceType[__m]; 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __l; 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nmax = __ns[0]; 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 42911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 43011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __ns[__i] = std::distance(__begin_seqs[__i].first, 43111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin_seqs[__i].second); 43211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __nmax = std::max(__nmax, __ns[__i]); 43311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 43411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __rd_log2(__nmax) + 1; 43611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Pad all lists to this length, at least as long as any ns[__i], 43811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // equality iff __nmax = 2^__k - 1 43911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __l = __round_up_to_pow2(__r) - 1; 44011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 44211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 44311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__i] = 0; 44411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__i] = __l; 44511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 44611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n = __l / 2; 44711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Invariants: 44911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l 45011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define __S(__i) (__begin_seqs[__i].first) 45211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Initial partition. 45411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_Tp, _SeqNumber> > __sample; 45511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 45711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__n < __ns[__i]) 45811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __sample.push_back(std::make_pair(__S(__i)[__n], __i)); 45911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __gnu_sequential::sort(__sample.begin(), __sample.end(), 46011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lcomp, sequential_tag()); 46111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Conceptual infinity. 46311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; __i++) 46411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__n >= __ns[__i]) 46511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __sample.push_back( 46611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); 46711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __localrank = __rank / __l; 46911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __j; 47111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__j = 0; 47211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); 47311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__j) 47411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__sample[__j].second] += __n + 1; 47511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __j < __m; ++__j) 47611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__sample[__j].second] -= __n + 1; 47711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Further refinement. 47911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__n > 0) 48011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 48111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __n /= 2; 48211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Tp* __lmax = 0; 48411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 48511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 48611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 48711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 48811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__lmax) 48911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax = &(__S(__i)[__a[__i] - 1]); 49011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 49111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 49211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(*__lmax, __S(__i)[__a[__i] - 1])) //max 49311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lmax = &(__S(__i)[__a[__i] - 1]); 49411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 49511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 49611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 49711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __i; 49911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < __m; __i++) 50011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 50111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __middle = (__b[__i] + __a[__i]) / 2; 50211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__lmax && __middle < __ns[__i] 50311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __comp(__S(__i)[__middle], *__lmax)) 50411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]); 50511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 50611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__i] -= __n + 1; 50711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 50811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __leftsize = 0; 51011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 51111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __leftsize += __a[__i] / (__n + 1); 51211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __skew = __rank / (__n + 1) - __leftsize; 51411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__skew > 0) 51611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 51711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Move to the left, find smallest. 51811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::priority_queue<std::pair<_Tp, _SeqNumber>, 51911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_Tp, _SeqNumber> >, 52011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _LexicographicReverse<_Tp, _SeqNumber, _Compare> > 52111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq(__lrcomp); 52211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 52411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__i] < __ns[__i]) 52511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); 52611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __skew != 0 && !__pq.empty(); --__skew) 52811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 52911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __source = __pq.top().second; 53011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.pop(); 53111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__source] 53311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = std::min(__a[__source] + __n + 1, __ns[__source]); 53411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__source] += __n + 1; 53511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__source] < __ns[__source]) 53711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push( 53811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(__S(__source)[__b[__source]], __source)); 53911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 54011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 54111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__skew < 0) 54211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 54311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Move to the right, find greatest. 54411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::priority_queue<std::pair<_Tp, _SeqNumber>, 54511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::vector<std::pair<_Tp, _SeqNumber> >, 54611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp); 54711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 54811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 54911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 55011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); 55111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 55211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (; __skew != 0; ++__skew) 55311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 55411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _SeqNumber __source = __pq.top().second; 55511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.pop(); 55611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 55711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a[__source] -= __n + 1; 55811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __b[__source] -= __n + 1; 55911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 56011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__source] > 0) 56111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pq.push(std::make_pair( 56211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __S(__source)[__a[__source] - 1], __source)); 56311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 56711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Postconditions: 56811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __a[__i] == __b[__i] in most cases, except when __a[__i] has been 56911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // clamped because of having reached the boundary 57011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Now return the result, calculate the offset. 57211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Compare the keys on both edges of the border. 57411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Maximum of left edge, minimum of right edge. 57611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __maxleftset = false, __minrightset = false; 57711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Impossible to avoid the warning? 57911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Tp __maxleft, __minright; 58011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 58111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 58211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__a[__i] > 0) 58311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 58411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__maxleftset) 58511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 58611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __maxleft = __S(__i)[__a[__i] - 1]; 58711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __maxleftset = true; 58811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 58911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 59011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Max. 59211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(__maxleft, __S(__i)[__a[__i] - 1])) 59311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __maxleft = __S(__i)[__a[__i] - 1]; 59411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 59511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 59611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__b[__i] < __ns[__i]) 59711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__minrightset) 59911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 60011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minright = __S(__i)[__b[__i]]; 60111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minrightset = true; 60211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 60411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 60511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Min. 60611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(__S(__i)[__b[__i]], __minright)) 60711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minright = __S(__i)[__b[__i]]; 60811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 61211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Minright is the __splitter, in any case. 61311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 61411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__maxleftset || __comp(__minright, __maxleft)) 61511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 61611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Good luck, everything is split unambiguously. 61711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __offset = 0; 61811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 62011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 62111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We have to calculate an offset. 62211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __offset = 0; 62311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 62411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_SeqNumber __i = 0; __i < __m; ++__i) 62511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 62611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType lb 62711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = std::lower_bound(__S(__i), __S(__i) + __ns[__i], 62811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __minright, 62911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __comp) - __S(__i); 63011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __offset += __a[__i] - lb; 63111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 63411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __ns; 63511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __a; 63611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __b; 63711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 63811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __minright; 63911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 64011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 64111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 64211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef __S 64311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 64411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H */ 645