base.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/parallel/base.h
 *
 * Sequential helper functions.
 * 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_BASE_HEADER
#define STXXL_PARALLEL_BASE_HEADER

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

#include <functional>
#include <iterator>

STXXL_BEGIN_NAMESPACE

namespace parallel {

/*!
 * Alternative to std::not2, typedefs first_argument_type and
 * second_argument_type not needed.
 */
template <class Predicate, typename first_argument_type, typename second_argument_type>
class binary_negate
 : public std::binary_function<first_argument_type, second_argument_type, bool>
{
protected:
 Predicate pred;

public:
 explicit
 binary_negate(const Predicate& _pred) : pred(_pred) { }

 bool operator () (const first_argument_type& x,
 const second_argument_type& y) const
 {
 return !pred(x, y);
 }
};

/*!
 * Encode two integers into one mcstl::lcas_t.
 *
 * \param a First integer, to be encoded in the most-significant \c lcas_t_bits/2 bits.
 * \param b Second integer, to be encoded in the least-significant \c lcas_t_bits/2 bits.
 * \return mcstl::lcas_t value encoding \c a and \c b.
 * \see decode2
 */
static inline lcas_t encode2(int a, int b) // must all be non-negative, actually
{
 return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
}

/*!
 * Decode two integers from one mcstl::lcas_t.
 *
 * \param x mcstl::lcas_t to decode integers from.
 * \param a First integer, to be decoded from the most-significant \c lcas_t_bits/2 bits of \c x.
 * \param b Second integer, to be encoded in the least-significant \c lcas_t_bits/2 bits of \c x.
 * \see encode2
 */
static inline void decode2(lcas_t x, int& a, int& b)
{
 a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
 b = (int)((x >> 0) & lcas_t_mask);
}

/*!
 * Constructs predicate for equality from strict weak ordering predicate
 */
template <class Comparator, typename T1, typename T2>
class equal_from_less : public std::binary_function<T1, T2, bool>
{
private:
 Comparator& comp;

public:
 equal_from_less(Comparator& _comp) : comp(_comp) { }

 bool operator () (const T1& a, const T2& b)
 {
 //FIXME: wrong in general (T1 != T2)
 return !comp(a, b) && !comp(b, a);
 }
};

/*!
 * Compute the median of three referenced elements, according to \c comp.
 *
 * \param a First iterator.
 * \param b Second iterator.
 * \param c Third iterator.
 * \param comp Comparator.
 */
template <typename RandomAccessIterator, typename Comparator>
RandomAccessIterator
median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
 RandomAccessIterator c, Comparator& comp)
{
 if (comp(*a, *b))
 if (comp(*b, *c))
 return b;
 else if (comp(*a, *c))
 return c;
 else
 return a;
 else //just swap a and b
 if (comp(*a, *c))
 return a;
 else if (comp(*b, *c))
 return c;
 else
 return b;
}

/** Similar to std::equal_to, but allows two different types. */
template <typename T1, typename T2>
struct equal_to : std::binary_function<T1, T2, bool>
{
 bool operator () (const T1& t1, const T2& t2) const
 {
 return t1 == t2;
 }
};

/** Similar to std::less, but allows two different types. */
template <typename T1, typename T2>
struct less : std::binary_function<T1, T2, bool>
{
 bool operator () (const T1& t1, const T2& t2) const
 {
 return t1 < t2;
 }
};

} // namespace parallel

STXXL_END_NAMESPACE

#endif // !STXXL_PARALLEL_BASE_HEADER