libstdc++
multiseq_selection.h
Go to the documentation of this file.
1
// -*- C++ -*-
2
3
// Copyright (C) 2007-2017 Free Software Foundation, Inc.
4
//
5
// This file is part of the GNU ISO C++ Library. This library is free
6
// software; you can redistribute it and/or modify it under the terms
7
// of the GNU General Public License as published by the Free Software
8
// Foundation; either version 3, or (at your option) any later
9
// version.
10
11
// This library is distributed in the hope that it will be useful, but
12
// WITHOUT ANY WARRANTY; without even the implied warranty of
13
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14
// General Public License for more details.
15
16
// Under Section 7 of GPL version 3, you are granted additional
17
// permissions described in the GCC Runtime Library Exception, version
18
// 3.1, as published by the Free Software Foundation.
19
20
// You should have received a copy of the GNU General Public License and
21
// a copy of the GCC Runtime Library Exception along with this program;
22
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23
// <http://www.gnu.org/licenses/>.
24
25
/** @file parallel/multiseq_selection.h
26
* @brief Functions to find elements of a certain global __rank in
27
* multiple sorted sequences. Also serves for splitting such
28
* sequence sets.
29
*
30
* The algorithm description can be found in
31
*
32
* P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard.
33
* Merging Multiple Lists on Hierarchical-Memory Multiprocessors.
34
* Journal of Parallel and Distributed Computing, 12(2):171–177, 1991.
35
*
36
* This file is a GNU parallel extension to the Standard C++ Library.
37
*/
38
39
// Written by Johannes Singler.
40
41
#ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H
42
#define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1
43
44
#include <
vector
>
45
#include <
queue
>
46
47
#include <
bits/stl_algo.h
>
48
49
namespace
__gnu_parallel
50
{
51
/** @brief Compare __a pair of types lexicographically, ascending. */
52
template
<
typename
_T1,
typename
_T2,
typename
_Compare>
53
class
_Lexicographic
54
:
public
std::binary_function
<std::pair<_T1, _T2>,
55
std::pair<_T1, _T2>, bool>
56
{
57
private
:
58
_Compare& _M_comp;
59
60
public
:
61
_Lexicographic
(_Compare& __comp) : _M_comp(__comp) { }
62
63
bool
64
operator()(
const
std::pair<_T1, _T2>
& __p1,
65
const
std::pair<_T1, _T2>
& __p2)
const
66
{
67
if
(_M_comp(__p1.
first
, __p2.
first
))
68
return
true
;
69
70
if
(_M_comp(__p2.
first
, __p1.
first
))
71
return
false
;
72
73
// Firsts are equal.
74
return
__p1.
second
< __p2.
second
;
75
}
76
};
77
78
/** @brief Compare __a pair of types lexicographically, descending. */
79
template
<
typename
_T1,
typename
_T2,
typename
_Compare>
80
class
_LexicographicReverse
:
public
std::binary_function
<_T1, _T2, bool>
81
{
82
private
:
83
_Compare& _M_comp;
84
85
public
:
86
_LexicographicReverse
(_Compare& __comp) : _M_comp(__comp) { }
87
88
bool
89
operator()(
const
std::pair<_T1, _T2>
& __p1,
90
const
std::pair<_T1, _T2>
& __p2)
const
91
{
92
if
(_M_comp(__p2.
first
, __p1.
first
))
93
return
true
;
94
95
if
(_M_comp(__p1.
first
, __p2.
first
))
96
return
false
;
97
98
// Firsts are equal.
99
return
__p2.
second
< __p1.
second
;
100
}
101
};
102
103
/**
104
* @brief Splits several sorted sequences at a certain global __rank,
105
* resulting in a splitting point for each sequence.
106
* The sequences are passed via a sequence of random-access
107
* iterator pairs, none of the sequences may be empty. If there
108
* are several equal elements across the split, the ones on the
109
* __left side will be chosen from sequences with smaller number.
110
* @param __begin_seqs Begin of the sequence of iterator pairs.
111
* @param __end_seqs End of the sequence of iterator pairs.
112
* @param __rank The global rank to partition at.
113
* @param __begin_offsets A random-access __sequence __begin where the
114
* __result will be stored in. Each element of the sequence is an
115
* iterator that points to the first element on the greater part of
116
* the respective __sequence.
117