--- /dev/null
+// -*- C++ -*-
+
+// Copyright (C) 2007, 2008, 2009, 2010, 2011 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
+{
+ /** @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;
+ }
+ };
+
+ /**
+ * @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;
+
+ // Pad all lists to this length, at least as long as any ns[__i],
+ // equality iff __nmax = 2^__k - 1.
+ __l = (1ULL << __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<_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 */
projects / cross.git / blobdiff