// -*- C++ -*-

// Copyright (C) 2007 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

/** @file parallel/base.h
 *  @brief Sequential helper functions.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Johannes Singler.

#ifndef _GLIBCXX_PARALLEL_BASE_H
#define _GLIBCXX_PARALLEL_BASE_H 1

#include <parallel/features.h>
#include <functional>
#include <parallel/basic_iterator.h>
#include <parallel/parallel.h>
#include <cstdio>

namespace __gnu_parallel
{
  // XXX remove std::duplicates from here if possible,
  // XXX but keep minimal dependencies.

  /** @brief Calculates the rounded-down logarithm of @c n for base 2.
   *  @param n Argument.
   *  @return Returns 0 for argument 0.
   */
  template<typename Size> 
    inline Size 
    log2(Size n)
    {
      Size k;
      for (k = 0; n != 1; n >>= 1)
	++k;
      return k;
    }

  /** @brief Encode two integers into one __gnu_parallel::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 __gnu_parallel::lcas_t value encoding @c a and @c b.
   *  @see decode2 
   */
  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);
  }

  /** @brief Decode two integers from one __gnu_parallel::lcas_t.
   *  @param x __gnu_parallel::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
   */
  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);
  }

  /** @brief Constructs predicate for equality from strict weak
   *  ordering predicate
   */
  // XXX comparator at the end, as per others
  template<typename 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)
    {
      return !comp(a, b) && !comp(b, a);
    }
  };


  /** @brief Similar to std::binder1st, but giving the argument types explicitly. */
  template<typename _Predicate, typename argument_type>
    class unary_negate
    : public std::unary_function<argument_type, bool>
    {
    protected:
      _Predicate _M_pred;

    public:
      explicit
      unary_negate(const _Predicate& __x) : _M_pred(__x) { }

      bool
      operator()(const argument_type& __x)
      { return !_M_pred(__x); }
    };

  /** @brief Similar to std::binder1st, but giving the argument types explicitly. */
  template<typename _Operation, typename first_argument_type, typename second_argument_type, typename result_type>
    class binder1st
    : public std::unary_function<second_argument_type, result_type>
    {
    protected:
      _Operation op;
      first_argument_type value;

    public:
      binder1st(const _Operation& __x,
		const first_argument_type& __y)
      : op(__x), value(__y) { }

      result_type
      operator()(const second_argument_type& __x)
      { return op(value, __x); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 109.  Missing binders for non-const sequence elements
      result_type
      operator()(second_argument_type& __x) const
      { return op(value, __x); }
    };

  /** 
   *  @brief Similar to std::binder2nd, but giving the argument types
   *  explicitly. 
   */
  template<typename _Operation, typename first_argument_type, typename second_argument_type, typename result_type>
    class binder2nd
    : public std::unary_function<first_argument_type, result_type>
    {
    protected:
      _Operation op;
      second_argument_type value;

    public:
      binder2nd(const _Operation& __x,
		const second_argument_type& __y)
      : op(__x), value(__y) { }

      result_type
      operator()(const first_argument_type& __x) const
      { return op(__x, value); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 109.  Missing binders for non-const sequence elements
      result_type
      operator()(first_argument_type& __x)
      { return op(__x, value); }
    };

  /** @brief 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; }
  };

  /** @brief 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; }

    bool 
    operator()(const T2& t2, const T1& t1) const
    { return t2 < t1; }
  };

  // Partial specialization for one type. Same as std::less.
  template<typename _Tp>
  struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };


    /** @brief Similar to std::plus, but allows two different types. */
  template<typename _Tp1, typename _Tp2>
    struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
    {
      typedef typeof(*static_cast<_Tp1*>(NULL) + *static_cast<_Tp2*>(NULL)) result;

      result
      operator()(const _Tp1& __x, const _Tp2& __y) const
      { return __x + __y; }
    };

  // Partial specialization for one type. Same as std::plus.
  template<typename _Tp>
    struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
    {
      typedef typeof(*static_cast<_Tp*>(NULL) + *static_cast<_Tp*>(NULL)) result;

      result
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x + __y; }
    };


  /** @brief Similar to std::multiplies, but allows two different types. */
  template<typename _Tp1, typename _Tp2>
    struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
    {
      typedef typeof(*static_cast<_Tp1*>(NULL) * *static_cast<_Tp2*>(NULL)) result;

      result
      operator()(const _Tp1& __x, const _Tp2& __y) const
      { return __x * __y; }
    };

  // Partial specialization for one type. Same as std::multiplies.
  template<typename _Tp>
    struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
    {
      typedef typeof(*static_cast<_Tp*>(NULL) * *static_cast<_Tp*>(NULL)) result;

      result
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x * __y; }
    };


  template<typename T, typename _DifferenceTp>
  class pseudo_sequence;

  /** @brief Iterator associated with __gnu_parallel::pseudo_sequence.
   *  If features the usual random-access iterator functionality.
   *  @param T Sequence value type.
   *  @param difference_type Sequence difference type. 
   */
  template<typename T, typename _DifferenceTp>
  class pseudo_sequence_iterator
  {
  public:
    typedef _DifferenceTp difference_type;

  private:
    typedef pseudo_sequence_iterator<T, _DifferenceTp> type;

    const T& val;
    difference_type pos;

  public:
    pseudo_sequence_iterator(const T& val, difference_type pos)
    : val(val), pos(pos) { }

    // Pre-increment operator.
    type&
    operator++()
    {
      ++pos;
      return *this;
    }

    // Post-increment operator.
    const type
    operator++(int)
    { return type(pos++); }

    const T& 
    operator*() const
    { return val; }

    const T& 
    operator[](difference_type) const
    { return val; }

    bool 
    operator==(const type& i2)
    { return pos == i2.pos; }

    difference_type 
    operator!=(const type& i2)
    { return pos != i2.pos; }

    difference_type 
    operator-(const type& i2)
    { return pos - i2.pos; }
  };

  /** @brief Sequence that conceptually consists of multiple copies of
      the same element.
   *  The copies are not stored explicitly, of course.
   *  @param T Sequence value type.
   *  @param difference_type Sequence difference type. 
   */
  template<typename T, typename _DifferenceTp>
  class pseudo_sequence
  {
    typedef pseudo_sequence<T, _DifferenceTp> type;

  public:
    typedef _DifferenceTp difference_type;

    // Better case down to uint64, than up to _DifferenceTp.
    typedef pseudo_sequence_iterator<T, uint64> iterator;

    /** @brief Constructor.
     *  @param val Element of the sequence.
     *  @param count Number of (virtual) copies.
     */
    pseudo_sequence(const T& val, difference_type count) 
    : val(val), count(count)  { }

    /** @brief Begin iterator. */
    iterator
    begin() const
    { return iterator(val, 0); }

    /** @brief End iterator. */
    iterator
    end() const
    { return iterator(val, count); }

  private:
    const T& val;
    difference_type count;
  };

  /** @brief Functor that does nothing */
  template<typename _ValueTp>
  class void_functor
  {
    inline void 
    operator()(const _ValueTp& v) const { }
  };

  /** @brief 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;
      }
  }

  // Avoid the use of assert, because we're trying to keep the <cassert>
  // include out of the mix. (Same as debug mode).
  inline void
  __replacement_assert(const char* __file, int __line, 
		       const char* __function, const char* __condition)
  {
    std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
		__function, __condition);
    __builtin_abort();
  }
  
#define _GLIBCXX_PARALLEL_ASSERT(_Condition)                            \
  do 								        \
    {									\
      if (!(_Condition))						\
	__gnu_parallel::__replacement_assert(__FILE__, __LINE__,	\
				    __PRETTY_FUNCTION__, #_Condition);	\
    } while (false)
  
} //namespace __gnu_parallel

#endif

