equally_split.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/parallel/equally_split.h
 *
 *  Function to split a sequence into parts of almost equal size.
 *  Extracted from MCSTL - http://algo2.iti.uni-karlsruhe.de/singler/mcstl/
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2007 Johannes Singler <[email protected]>
 *  Copyright (C) 2014 Timo Bingmann <[email protected]>
 *
 *  Distributed under the Boost Software License, Version 1.0.
 *  (See accompanying file LICENSE_1_0.txt or copy at
 *  http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_PARALLEL_EQUALLY_SPLIT_HEADER
#define STXXL_PARALLEL_EQUALLY_SPLIT_HEADER

#include <stxxl/bits/namespace.h>
#include <stxxl/bits/parallel/base.h>
#include <stxxl/bits/parallel/types.h>

STXXL_BEGIN_NAMESPACE

namespace parallel {

/*!
 * Split a sequence into parts of almost equal size.
 *
 * The resulting sequence s of length p+1 contains the splitting positions when
 * splitting the range [0,n) into parts of almost equal size (plus minus 1).
 * The first entry is 0, the last one n. There may result empty parts.
 *
 * \param n Number of elements
 * \param p Number of parts
 * \param s Splitters
 * \returns End of splitter sequence, i. e. \c s+p+1
 */
template <typename DiffType, typename DiffTypeOutputIterator>
DiffTypeOutputIterator equally_split(DiffType n, thread_index_t p,
                                     DiffTypeOutputIterator s)
{
    DiffType chunk_length = n / p, split = n % p, start = 0;
    for (thread_index_t i = 0; i < p; i++)
    {
        *s++ = start;
        start += ((DiffType)i < split) ? (chunk_length + 1) : chunk_length;
    }
    *s++ = n;

    return s;
}

} // namespace parallel

STXXL_END_NAMESPACE

#endif // !STXXL_PARALLEL_EQUALLY_SPLIT_HEADER