STXXL  1.4-dev
equally_split.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/parallel/equally_split.h
3  *
4  * Function to split a sequence into parts of almost equal size.
5  * Extracted from MCSTL - http://algo2.iti.uni-karlsruhe.de/singler/mcstl/
6  *
7  * Part of the STXXL. See http://stxxl.sourceforge.net
8  *
9  * Copyright (C) 2007 Johannes Singler <[email protected]>
10  * Copyright (C) 2014 Timo Bingmann <[email protected]>
11  *
13  * (See accompanying file LICENSE_1_0.txt or copy at
15  **************************************************************************/
16
19
20 #include <stxxl/bits/namespace.h>
23
25
26 namespace parallel {
27
28 /*!
29  * Split a sequence into parts of almost equal size.
30  *
31  * The resulting sequence s of length p+1 contains the splitting positions when
32  * splitting the range [0,n) into parts of almost equal size (plus minus 1).
33  * The first entry is 0, the last one n. There may result empty parts.
34  *
35  * \param n Number of elements
36  * \param p Number of parts
37  * \param s Splitters
38  * \returns End of splitter sequence, i. e. \c s+p+1
39  */
40 template <typename DiffType, typename DiffTypeOutputIterator>
41 DiffTypeOutputIterator equally_split(DiffType n, thread_index_t p,
42  DiffTypeOutputIterator s)
43 {
44  DiffType chunk_length = n / p, split = n % p, start = 0;
45  for (thread_index_t i = 0; i < p; i++)
46  {
47  *s++ = start;
48  start += ((DiffType)i < split) ? (chunk_length + 1) : chunk_length;
49  }
50  *s++ = n;
51
52  return s;
53 }
54
55 } // namespace parallel
56
58