pq_mergers.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/containers/pq_mergers.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 1999 Peter Sanders <[email protected]>
 *  Copyright (C) 2003, 2004, 2007 Roman Dementiev <[email protected]>
 *  Copyright (C) 2007-2009 Johannes Singler <[email protected]>
 *  Copyright (C) 2007, 2008 Andreas Beckmann <[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_CONTAINERS_PQ_MERGERS_HEADER
#define STXXL_CONTAINERS_PQ_MERGERS_HEADER

#include <stxxl/bits/containers/pq_helpers.h>

STXXL_BEGIN_NAMESPACE

//! \addtogroup stlcontinternals
//!
//! \{

/*! \internal
 */
namespace priority_queue_local {

/////////////////////////////////////////////////////////////////////
// auxiliary functions

// merge length elements from the two sentinel terminated input
// sequences source0 and source1 to target
// advance source0 and source1 accordingly
// require: at least length nonsentinel elements available in source0, source1
// require: target may overwrite one of the sources as long as
//   *(sourcex + length) is before the end of sourcex
template <class InputIterator, class OutputIterator, class CompareType>
void merge_iterator(
    InputIterator& source0,
    InputIterator& source1,
    OutputIterator target,
    unsigned_type length,
    CompareType& cmp)
{
    OutputIterator done = target + length;

    while (target != done)
    {
        if (cmp(*source0, *source1))
        {
            *target = *source1;
            ++source1;
        }
        else
        {
            *target = *source0;
            ++source0;
        }
        ++target;
    }
}

// merge length elements from the three sentinel terminated input
// sequences source0, source1 and source2 to target
// advance source0, source1 and source2 accordingly
// require: at least length nonsentinel elements available in source0, source1 and source2
// require: target may overwrite one of the sources as long as
//   *(sourcex + length) is before the end of sourcex
template <class InputIterator, class OutputIterator, class CompareType>
void merge3_iterator(
    InputIterator& source0,
    InputIterator& source1,
    InputIterator& source2,
    OutputIterator target,
    unsigned_type length,
    CompareType& cmp)
{
    OutputIterator done = target + length;

    if (cmp(*source1, *source0)) {
        if (cmp(*source2, *source1)) {
            goto s012;
        }
        else {
            if (cmp(*source0, *source2)) {
                goto s201;
            }
            else {
                goto s021;
            }
        }
    } else {
        if (cmp(*source2, *source1)) {
            if (cmp(*source2, *source0)) {
                goto s102;
            }
            else {
                goto s120;
            }
        } else {
            goto s210;
        }
    }

#define Merge3Case(a, b, c)              \
    s ## a ## b ## c :                   \
    if (target == done)                  \
        return;                          \
    *target = *source ## a;              \
    ++target;                            \
    ++source ## a;                       \
    if (cmp(*source ## b, *source ## a)) \
        goto s ## a ## b ## c;           \
    if (cmp(*source ## c, *source ## a)) \
        goto s ## b ## a ## c;           \
    goto s ## b ## c ## a;

    // the order is chosen in such a way that
    // four of the trailing gotos can be eliminated by the optimizer
    Merge3Case(0, 1, 2);
    Merge3Case(1, 2, 0);
    Merge3Case(2, 0, 1);
    Merge3Case(1, 0, 2);
    Merge3Case(0, 2, 1);
    Merge3Case(2, 1, 0);

#undef Merge3Case
}


// merge length elements from the four sentinel terminated input
// sequences source0, source1, source2 and source3 to target
// advance source0, source1, source2 and source3 accordingly
// require: at least length nonsentinel elements available in source0, source1, source2 and source3
// require: target may overwrite one of the sources as long as
//   *(sourcex + length) is before the end of sourcex
template <class InputIterator, class OutputIterator, class CompareType>
void merge4_iterator(
    InputIterator& source0,
    InputIterator& source1,
    InputIterator& source2,
    InputIterator& source3,
    OutputIterator target, unsigned_type length, CompareType& cmp)
{
    OutputIterator done = target + length;

#define StartMerge4(a, b, c, d)                                                                                         \
    if ((!cmp(*source ## a, *source ## b)) && (!cmp(*source ## b, *source ## c)) && (!cmp(*source ## c, *source ## d))) \
        goto s ## a ## b ## c ## d;

    // b>a c>b d>c
    // a<b b<c c<d
    // a<=b b<=c c<=d
    // !(a>b) !(b>c) !(c>d)

    StartMerge4(0, 1, 2, 3);
    StartMerge4(1, 2, 3, 0);
    StartMerge4(2, 3, 0, 1);
    StartMerge4(3, 0, 1, 2);

    StartMerge4(0, 3, 1, 2);
    StartMerge4(3, 1, 2, 0);
    StartMerge4(1, 2, 0, 3);
    StartMerge4(2, 0, 3, 1);

    StartMerge4(0, 2, 3, 1);
    StartMerge4(2, 3, 1, 0);
    StartMerge4(3, 1, 0, 2);
    StartMerge4(1, 0, 2, 3);

    StartMerge4(2, 0, 1, 3);
    StartMerge4(0, 1, 3, 2);
    StartMerge4(1, 3, 2, 0);
    StartMerge4(3, 2, 0, 1);

    StartMerge4(3, 0, 2, 1);
    StartMerge4(0, 2, 1, 3);
    StartMerge4(2, 1, 3, 0);
    StartMerge4(1, 3, 0, 2);

    StartMerge4(1, 0, 3, 2);
    StartMerge4(0, 3, 2, 1);
    StartMerge4(3, 2, 1, 0);
    StartMerge4(2, 1, 0, 3);

#define Merge4Case(a, b, c, d)               \
    s ## a ## b ## c ## d :                  \
    if (target == done)                      \
        return;                              \
    *target = *source ## a;                  \
    ++target;                                \
    ++source ## a;                           \
    if (cmp(*source ## c, *source ## a))     \
    {                                        \
        if (cmp(*source ## b, *source ## a)) \
            goto s ## a ## b ## c ## d;      \
        else                                 \
            goto s ## b ## a ## c ## d;      \
    }                                        \
    else                                     \
    {                                        \
        if (cmp(*source ## d, *source ## a)) \
            goto s ## b ## c ## a ## d;      \
        else                                 \
            goto s ## b ## c ## d ## a;      \
    }

    Merge4Case(0, 1, 2, 3);
    Merge4Case(1, 2, 3, 0);
    Merge4Case(2, 3, 0, 1);
    Merge4Case(3, 0, 1, 2);

    Merge4Case(0, 3, 1, 2);
    Merge4Case(3, 1, 2, 0);
    Merge4Case(1, 2, 0, 3);
    Merge4Case(2, 0, 3, 1);

    Merge4Case(0, 2, 3, 1);
    Merge4Case(2, 3, 1, 0);
    Merge4Case(3, 1, 0, 2);
    Merge4Case(1, 0, 2, 3);

    Merge4Case(2, 0, 1, 3);
    Merge4Case(0, 1, 3, 2);
    Merge4Case(1, 3, 2, 0);
    Merge4Case(3, 2, 0, 1);

    Merge4Case(3, 0, 2, 1);
    Merge4Case(0, 2, 1, 3);
    Merge4Case(2, 1, 3, 0);
    Merge4Case(1, 3, 0, 2);

    Merge4Case(1, 0, 3, 2);
    Merge4Case(0, 3, 2, 1);
    Merge4Case(3, 2, 1, 0);
    Merge4Case(2, 1, 0, 3);

#undef StartMerge4
#undef Merge4Case
}

} // namespace priority_queue_local

//! \}

STXXL_END_NAMESPACE

#endif // !STXXL_CONTAINERS_PQ_MERGERS_HEADER
// vim: et:ts=4:sw=4