/* Copyright (C) 2013 Chris Vine

The library comprised in this file or of which this file is part is
distributed by Chris Vine under the GNU Lesser General Public
License as follows:

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public License
   as published by the Free Software Foundation; either version 2.1 of
   the License, 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
   Lesser General Public License, version 2.1, for more details.

   You should have received a copy of the GNU Lesser General Public
   License, version 2.1, along with this library (see the file LGPL.TXT
   which came with this source code package in the c++-gtk-utils
   sub-directory); if not, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

However, it is not intended that the object code of a program whose
source code instantiates a template from this file or uses macros or
inline functions (of any length) should by reason only of that
instantiation or use be subject to the restrictions of use in the GNU
Lesser General Public License.  With that in mind, the words "and
macros, inline functions and instantiations of templates (of any
length)" shall be treated as substituted for the words "and small
macros and small inline functions (ten lines or less in length)" in
the fourth paragraph of section 5 of that licence.  This does not
affect any other reason why object code may be subject to the
restrictions in that licence (nor for the avoidance of doubt does it
affect the application of section 2 of that licence to modifications
of the source code in this file).

*/

#ifndef CGU_PARALLEL_H
#define CGU_PARALLEL_H

#include <utility>     // for std::move, std::forward and std::pair
#include <memory>      // for std::unique_ptr
#include <iterator>    // for std::iterator_traits and std::distance
#include <exception>   // for std::exception
#include <functional>  // for std::bind
#include <type_traits> // for std::remove_reference and std::remove_const
#include <limits>      // for std::numeric_limits
#include <algorithm>   // for std::min
#include <tuple>

#include <c++-gtk-utils/callback.h>
#include <c++-gtk-utils/task_manager.h>
#include <c++-gtk-utils/mutex.h>

namespace Cgu {

namespace Thread {

struct ParallelError: public std::exception {
  virtual const char* what() const throw() {return "ParallelError\n";}
};

#ifndef DOXYGEN_PARSING

// in version 2.2.2, this was the ParallelHelper namespace.  Because
// the meaning of the DiffType* argument of these functions has
// changed in version 2.2.3 (it is incremented rather than
// decremented), this is now the ParallelHelper2 namespace so that no
// ODR issues arise on library linking with old binaries
namespace ParallelHelper2 {

template <class ArgType, class DiffType, class Iterator>
void for_each_cb_func(const Cgu::Callback::SafeFunctorArg<ArgType&>& s_task,
		      Iterator iter,
		      Mutex* m, Cond* cond,
		      DiffType* done_count) {
  s_task(*iter);
  Mutex::Lock l{*m};
  ++*done_count;
  cond->signal();
}

template <class FType, class ArgType, class DestType>
void transform1_func(const FType& func,
		     ArgType& arg,
		     DestType& res) {
  res = func(arg);
}


template <class ArgType, class DestType, class DiffType, class SourceIterator>
void transform1_cb_func(const Cgu::Callback::SafeFunctorArg<ArgType&, DestType&>& s_task,
			SourceIterator source_iter,
			Mutex* m, Cond* cond,
			DiffType* done_count,
			DestType* results,
			DiffType index) {
  DestType res;
  s_task(*source_iter, res);
  Mutex::Lock l{*m};
  // move to 'results' within the mutex because g++ <= 4.7 does not
  // correctly implement the C++11 memory model on some 64 bit
  // platforms (this is a slight pessimization for gcc >= 4.8)
  results[index] = std::move(res);
  ++*done_count;
  cond->signal();
}

template <class FType, class Arg1Type,
          class Arg2Type, class DestType>
void transform2_func(const FType& func,
		     Arg1Type& arg1,
		     Arg2Type& arg2,
		     DestType& res) {
  res = func(arg1, arg2);
}


template <class Arg1Type, class Arg2Type, class DestType,
          class DiffType, class SourceIterator1, class SourceIterator2>
void transform2_cb_func(const Cgu::Callback::SafeFunctorArg<Arg1Type&, Arg2Type&, DestType&>& s_task,
			SourceIterator1 source_iter1,
			SourceIterator2 source_iter2,
			Mutex* m, Cond* cond,
			DiffType* done_count,
			DestType* results,
			DiffType index) {
  DestType res;
  s_task(*source_iter1, *source_iter2, res);
  Mutex::Lock l{*m};
  // move to 'results' within the mutex because g++ <= 4.7 does not
  // correctly implement the C++11 memory model on some 64 bit
  // platforms (this is a slight pessimization for gcc >= 4.8)
  results[index] = std::move(res);
  ++*done_count;
  cond->signal();
}

template <class DiffType>
void fail_func(Mutex* m, Cond* cond,
	       bool* error, DiffType* done_count) noexcept {
  Mutex::Lock l{*m};
  ++*done_count;
  *error = true;
  cond->signal();
}

} // namespace ParallelHelper2

#endif // DOXYGEN_PARSING

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function applies a callable object to each element of a
 * container in the range ['first', 'last'), by executing each such
 * application as a task of a Thread::TaskManager object.  Tasks are
 * added to the Thread::TaskManager object in the order in which the
 * respective elements appear in the container (and if a task mutates
 * its argument, it will do so in respect of the correct element of
 * the container), but no other ordering arises, and the tasks will
 * execute in parallel to the extent that the Thread::TaskManager
 * object has sufficient threads available to do so.
 *
 * Apart from that, and that this function returns void, it does the
 * same as std::for_each().  It can mutate container elements if the
 * callable object takes its argument by non-const reference.  It will
 * not return until the callable object has been applied to all of the
 * elements in the range ['first', 'last').
 *
 * This function can be called by a task running on the same
 * TaskManager object.
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first The beginning of the range to which 'func' is to be
 * applied.
 * @param last One past the last element to which 'func' is to be
 * applied.
 * @param func A callable object to be applied to each element in the
 * range ['first', 'last'), such as formed by a lambda expression or
 * the result of std::bind.  It should take a single unbound argument
 * of the value type of the container to which 'first' and 'last'
 * relate or a const or non-const reference to that type.  Any return
 * value is discarded.  If an exception propagates from 'func', the
 * exception will be consumed while the for each loop is running, and
 * an attempt will still be made to apply 'func' to all remaining
 * elements in the range ['first', 'last'), and only after that
 * attempt has completed will the exception Cgu::Thread::ParallelError
 * be thrown.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the container.
 * Such an exception will not stop an attempt being made to apply
 * 'func' (successfully or unsuccessfully) to all elements in the
 * range ['first', 'last').  Cgu::Thread::ParallelError will be thrown
 * after such attempted application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.19/2.2.2
 */
template <class Iterator, class Func>
void parallel_for_each(TaskManager& tm,
		       Iterator first,
		       Iterator last,
		       Func&& func) {

  typedef typename std::iterator_traits<Iterator>::value_type ArgType;
  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<ArgType&> s_task{
    Cgu::Callback::lambda<ArgType&>(std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first != last; ++first, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgType, DiffType, Iterator>,
			      s_task,
			      first,
			      &mutex,
			      &cond,
			      &done_count)
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
}

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function maps over a container in the range ['first', 'last'),
 * applying a unary callable object to each element of the container
 * in that range and storing the result in the destination range, by
 * executing each such application as a task of a Thread::TaskManager
 * object.  Tasks are added to the Thread::TaskManager object in the
 * order in which the respective elements appear in the source
 * container, and the final result appears in the destination
 * container in the same order as the source range from which it is
 * generated (including if a back_inserter iterator is used), but no
 * other ordering arises, and the tasks will execute in parallel to
 * the extent that the Thread::TaskManager object has sufficient
 * threads available to do so.
 *
 * Apart from that, this function does the same as the version of
 * std::transform() taking a unary function, except that it returns
 * void (see Thread::parallel_transform_partial() for a function which
 * returns a destination iterator and an iterator to the source
 * range).  It will not return until the callable object has been
 * applied to all of the elements in the range ['first', 'last').
 *
 * This function can be called by a task running on the same
 * TaskManager object (a result can therefore be delivered
 * asynchronously by calling this function in a task created by the
 * make_task_when(), make_task_compose() or make_task_when_full()
 * Thread::TaskManager methods).  A task can carry out a map-reduce
 * operation by passing the result of calling this function to
 * std::accumulate() to perform a fold-left or fold-right on that
 * result.
 *
 * A separate overload of this function takes a binary callable
 * object.
 *
 * Here is a trivial example of a map-reduce operation which maps over
 * a vector by multiplying each element by 2 in separate tasks, and
 * then folds-left using std::accumulate() (std::accumulate() can fold
 * using any callable object, but in this example the default of
 * addition is used):
 *
 * @code
 *   using namespace Cgu;
 *   std::vector<int> v{1, 2, 3, 4, 5};
 *   Thread::TaskManager tm;
 *
 *   Thread::parallel_transform(tm,
 *                              v.begin(),
 *                              v.end(),
 *                              v.begin(),
 *                              [] (int elt) {return elt * 2;});
 *  // res will be equal to 30
 *  int res = std::accumulate(v.begin(), v.end(), 0);
 * @endcode
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first The beginning of the range to which 'func' is to be
 * applied.
 * @param last One past the last element to which 'func' is to be
 * applied.
 * @param dest The beginning of the range to which the result of
 * applying 'func' to the elements in the range ['first', 'last') is
 * to be stored.  As in the case of std::transform, this can overlap
 * with or be the same as the source range.  It may also be an insert
 * iterator.
 * @param func A unary callable object to be applied to each element
 * in the range ['first', 'last'), such as formed by a lambda
 * expression or the result of std::bind.  It should take a single
 * unbound argument of the value type of the container to which
 * 'first' and 'last' relate or a const or non-const reference to that
 * type.  If an exception propagates from 'func', the exception will
 * be consumed while the transform loop is running, and an attempt
 * will still be made to apply 'func' to all remaining elements in the
 * range ['first', 'last'), and only after that attempt has completed
 * will the exception Cgu::Thread::ParallelError be thrown.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the source
 * container.  Such an exception will not stop an attempt being made
 * to apply 'func' (successfully or unsuccessfully) to all elements in
 * the range ['first', 'last').  Cgu::Thread::ParallelError will be
 * thrown after such attempted application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.19/2.2.2
 */
template <class SourceIterator, class DestIterator, class Func>
void parallel_transform(TaskManager& tm,
			SourceIterator first,
			SourceIterator last,
			DestIterator dest,
			Func&& func) {

  if (first == last) return;

  typedef typename std::iterator_traits<SourceIterator>::value_type ArgType;
  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
  typedef decltype(func(*first)) DestType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // intermediate results have to be held in an array so destination
  // ordering can be enforced when using insert interators.  This
  // causes some inefficiency for non-random access iterators
  std::unique_ptr<DestType[]> results(new DestType[std::distance(first, last)]);

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<ArgType&, DestType&> s_task{
    Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgType, DestType>,
			    std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first != last; ++first, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgType, DestType, DiffType, SourceIterator>,
					s_task,
					first,
					&mutex,
					&cond,
					&done_count,
					results.get(),
					start_count))
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
  for (DiffType index = 0; index < start_count; ++dest, ++index) {
    *dest = std::move(results[index]);
  }
}

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function maps over two containers, one in the range ['first1',
 * 'last1') and the other beginning at 'first2', applying a binary
 * callable object to each element of the containers in those ranges
 * and storing the result in the destination range, by executing each
 * such application as a task of a Thread::TaskManager object.  Tasks
 * are added to the Thread::TaskManager object in the order in which
 * the respective elements appear in the source containers, and the
 * final result appears in the destination container in the same order
 * as the source ranges from which it is generated (including if a
 * back_inserter iterator is used), but no other ordering arises, and
 * the tasks will execute in parallel to the extent that the
 * Thread::TaskManager object has sufficient threads available to do
 * so.
 *
 * Apart from that, this function does the same as the version of
 * std::transform() taking a binary function, except that it returns
 * void (see Thread::parallel_transform_partial() for a function which
 * returns a destination iterator and iterators to the source ranges).
 * It will not return until the callable object has been applied to
 * all of the elements in the source ranges.
 *
 * This function can be called by a task running on the same
 * TaskManager object (a result can therefore be delivered
 * asynchronously by calling this function in a task created by the
 * make_task_when(), make_task_compose() or make_task_when_full()
 * Thread::TaskManager methods).  A task can carry out a map-reduce
 * operation by passing the result of calling this function to
 * std::accumulate() to perform a fold-left or fold-right on that
 * result.
 *
 * A separate overload of this function takes a unary callable object.
 *
 * Here is a trivial example of a map-reduce operation which maps over
 * two vectors by adding respective elements of the vectors in
 * separate tasks, and then folds-left using std::accumulate()
 * (std::accumulate() can fold using any callable object, but in this
 * example the default of addition is used):
 *
 * @code
 *   using namespace Cgu;
 *   std::vector<int> v1{2, 4, 6, 8, 10};
 *   std::vector<int> v2{10, 20, 30, 40, 50};
 *   std::vector<int> v3;
 *   Thread::TaskManager tm;
 *
 *   Thread::parallel_transform(tm,
 *                              v1.begin(),
 *                              v1.end(),
 *                              v2.begin(),
 *                              std::back_inserter(v3),
 *                              std::plus<int>());
 *  // res will be equal to 180
 *  int res = std::accumulate(v3.begin(), v3.end(), 0);
 * @endcode
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first1 The beginning of the range which is to be passed as
 * the first argument of 'func'.
 * @param last1 One past the last element of the range which is to be
 * passed as the first argument of 'func'.
 * @param first2 The beginning of the range which is to be passed as
 * the second argument of 'func'.
 * @param dest The beginning of the range to which the result of
 * applying 'func' to the elements in the source ranges is to be
 * stored.  As in the case of std::transform, this can overlap with or
 * be the same as one of the source ranges.  It may also be an insert
 * iterator.
 * @param func A binary callable object to be applied to each element
 * in the source ranges, such as formed by a lambda expression or the
 * result of std::bind.  It should take two unbound arguments of the
 * value types of the containers to which 'first1' and 'first2' relate
 * or const or non-const references to those types.  If an exception
 * propagates from 'func', the exception will be consumed while the
 * transform loop is running, and an attempt will still be made to
 * apply 'func' to all remaining elements of the source ranges, and
 * only after that attempt has completed will the exception
 * Cgu::Thread::ParallelError be thrown.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the source
 * ranges.  Such an exception will not stop an attempt being made to
 * apply 'func' (successfully or unsuccessfully) to all elements in
 * the source ranges.  Cgu::Thread::ParallelError will be thrown after
 * such attempted application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.19/2.2.2
 */
template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
void parallel_transform(TaskManager& tm,
			SourceIterator1 first1,
			SourceIterator1 last1,
			SourceIterator2 first2,
			DestIterator dest,
			Func&& func) {

  if (first1 == last1) return;

  typedef typename std::iterator_traits<SourceIterator1>::value_type Arg1Type;
  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
  typedef typename std::iterator_traits<SourceIterator2>::value_type Arg2Type;
  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
  typedef decltype(func(*first1, *first2)) DestType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // intermediate results have to be held in an array so destination
  // ordering can be enforced when using insert interators.  This
  // causes some inefficiency for non-random access iterators
  std::unique_ptr<DestType[]> results(new DestType[std::distance(first1, last1)]);

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<Arg1Type&, Arg2Type&, DestType&> s_task{
    Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1Type, Arg2Type, DestType>,
			    std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first1 != last1; ++first1, ++first2, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1Type, Arg2Type, DestType, DiffType, SourceIterator1, SourceIterator2>,
					s_task,
					first1,
					first2,
					&mutex,
					&cond,
					&done_count,
					results.get(),
					start_count))
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
  for (DiffType index = 0; index < start_count; ++dest, ++index) {
    *dest = std::move(results[index]);
  }
}

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function applies a callable object to each element of a
 * container in the range ['first', 'last') subject to a maximum, by
 * executing each such application as a task of a Thread::TaskManager
 * object.  Tasks are added to the Thread::TaskManager object in the
 * order in which the respective elements appear in the container (and
 * if a task mutates its argument, it will do so in respect of the
 * correct element of the container), but no other ordering arises,
 * and the tasks will execute in parallel to the extent that the
 * Thread::TaskManager object has sufficient threads available to do
 * so.
 *
 * This function does the same as Thread::parallel_for_each(), except
 * that it returns an iterator to the element past the last element to
 * which the callable object has been applied, and it has a 'max'
 * parameter to limit the maximum number of elements to which the
 * callable object will be applied on any one call to this function
 * even if the range ['first', 'last') is greater than this maximum.
 * Whether this limitation has had effect on any one call can be
 * tested by checking whether the return value is equal to the 'last'
 * parameter.  If it is not, a further call to this function can be
 * made.
 *
 * The main purpose of this additional function is to enable the
 * application of the callable object to the elements of a container
 * to be dealt with in chunks, possibly to enable other tasks to be
 * interleaved at reasonable intervals.  For a container which does
 * not support random access iterators, the 'last' parameter can be
 * set to, say, the end of the container and the chunk size set with
 * the 'max' paramater, with the return value being used as the
 * 'first' parameter for subsequent calls to this function.  This
 * avoids having to increment the iterator for each "chunk" by
 * stepping through the container by hand.  In this usage, it
 * therefore represents a minor efficiency improvement.
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first The beginning of the range to which 'func' is to be
 * applied.
 * @param last One past the last element to which 'func' is to be
 * applied, subject to any maximum specified as the 'max' parameter.
 * @param max The maximum number of elements of the source container
 * to which 'func' will be applied on this call.  It is not an error
 * if it is greater than the distance between 'first' and 'last'.  If
 * it is equal to or greater than that distance, it follows that the
 * iterator returned will be equal to 'last'.  The same results if
 * 'max' is a negative number (in that case no maximum will take
 * effect and each element in the range ['first', 'last') will have
 * 'func' applied to it).
 * @param func A callable object to be applied (subject to the
 * maximum) to each element in the range ['first', 'last'), such as
 * formed by a lambda expression or the result of std::bind.  It
 * should take a single unbound argument of the value type of the
 * container to which 'first' and 'last' relate or a const or
 * non-const reference to that type.  Any return value is discarded.
 * If an exception propagates from 'func', the exception will be
 * consumed while the for each loop is running, and an attempt will
 * still be made to apply 'func' to all remaining elements in the
 * range ['first', 'last') subject to the maximum, and only after that
 * attempt has completed will the exception Cgu::Thread::ParallelError
 * be thrown.
 * @return An iterator representing the element past the last element
 * of the range to which 'func' was applied, which may be passed as
 * the 'first' argument of a subsequent call to this function.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the container.
 * Such an exception will not stop an attempt being made to apply
 * 'func' (successfully or unsuccessfully) to all elements in the
 * range ['first', 'last') subject to the maximum.
 * Cgu::Thread::ParallelError will be thrown after such attempted
 * application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.20/2.2.3
 */
template <class Iterator, class Func>
Iterator parallel_for_each_partial(TaskManager& tm,
				   Iterator first,
				   Iterator last,
				   int max,
				   Func&& func) {

  if (first == last || !max) return first;

  typedef typename std::iterator_traits<Iterator>::value_type ArgType;
  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // a specialization of std::numeric_limits::max() for all arithmetic
  // types is required by §3.9.1/8 of the standard.  The iterator
  // difference type must be a signed integer type (§24.2.1/1).  All
  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
  // §3.9.1/8).
  const DiffType local_max =
    (max >= 0) ? max : std::numeric_limits<DiffType>::max();

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<ArgType&> s_task{
    Cgu::Callback::lambda<ArgType&>(std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first != last && start_count < local_max; ++first, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgType, DiffType, Iterator>,
			      s_task,
			      first,
			      &mutex,
			      &cond,
			      &done_count)
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
  return first;
}

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function maps over a container in the range ['first', 'last')
 * subject to a maximum, applying a unary callable object to each
 * element of the container in that range (subject to the maximum) and
 * storing the result in the destination range, by executing each such
 * application as a task of a Thread::TaskManager object.  Tasks are
 * added to the Thread::TaskManager object in the order in which the
 * respective elements appear in the source container, and the final
 * result appears in the destination container in the same order as
 * the source range from which it is generated (including if a
 * back_inserter iterator is used), but no other ordering arises, and
 * the tasks will execute in parallel to the extent that the
 * Thread::TaskManager object has sufficient threads available to do
 * so.
 *
 * A separate overload of this function takes a binary callable
 * object.
 *
 * This function does the same as the version of
 * Thread::parallel_transform() taking a unary callable object, except
 * that it returns a std::pair object containing an iterator to the
 * element past the last element of the source range transformed, and
 * a destination iterator to the element past the last element stored
 * in the destination range, and it has a 'max' parameter to limit the
 * maximum number of elements which will be so transformed on any one
 * call to this function.  Whether this limitation has had effect on
 * any one call can be tested by checking whether the first value of
 * the pair returned is equal to the 'last' parameter.  If it is not,
 * a further call to this function can be made.
 *
 * The main purpose of this additional function is to enable the
 * parallel transform of the elements of a container to be dealt with
 * in chunks, possibly to enable other tasks to be interleaved at
 * reasonable intervals.  For source or destination containers which
 * do not support random access iterators, the 'last' parameter can be
 * set to, say, the end of the container and the chunk size set with
 * the 'max' paramater, with the values of the returned pair being
 * used as the 'first' and 'dest' parameters for subsequent calls to
 * this function.  This avoids having to increment the source and
 * destination iterators for each "chunk" by stepping through the
 * respective containers by hand.  In this usage, it therefore
 * represents a minor efficiency improvement.
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first The beginning of the range to which 'func' is to be
 * applied.
 * @param last One past the last element to which 'func' is to be
 * applied, subject to any maximum specified as the 'max' parameter.
 * @param dest The beginning of the range to which the result of
 * applying 'func' to the elements in the source range is to be
 * stored.  As in the case of std::transform, this can overlap with or
 * be the same as the source range.  It may also be an insert
 * iterator.
 * @param max The maximum number of elements of the source container
 * which will be transformed on this call.  It is not an error if it
 * is greater than the distance between 'first' and 'last'.  If it is
 * equal to or greater than that distance, it follows that the first
 * value of the pair returned by this function will be equal to
 * 'last'.  The same results if 'max' is a negative number (in that
 * case no maximum will take effect and all elements in the range
 * ['first', 'last') will be transformed), so passing -1 might be
 * useful as a means of obtaining a destination iterator (the second
 * value) for other purposes, particularly where it is not a random
 * access iterator).
 * @param func A unary callable object to be applied (subject to the
 * maximum) to each element in the range ['first', 'last'), such as
 * formed by a lambda expression or the result of std::bind.  It
 * should take a single unbound argument of the value type of the
 * container to which 'first' and 'last' relate or a const or
 * non-const reference to that type.  If an exception propagates from
 * 'func', the exception will be consumed while the transform loop is
 * running, and an attempt will still be made to apply 'func' to all
 * remaining elements in the range ['first', 'last') subject to the
 * maximum, and only after that attempt has completed will the
 * exception Cgu::Thread::ParallelError be thrown.
 * @return A std::pair object.  Its first member is an iterator
 * representing the element past the last element of the source range
 * transformed, which may be passed as the 'first' argument of a
 * subsequent call to this function; and its second member is an
 * iterator representing the element past the last element stored in
 * the destination range, which may be passed as the 'dest' argument
 * of the subsequent call.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the source
 * container.  Such an exception will not stop an attempt being made
 * to apply 'func' (successfully or unsuccessfully) to all elements in
 * the range ['first', 'last') subject to the maximum.
 * Cgu::Thread::ParallelError will be thrown after such attempted
 * application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.20/2.2.3
 */
template <class SourceIterator, class DestIterator, class Func>
std::pair<SourceIterator, DestIterator>
  parallel_transform_partial(TaskManager& tm,
			     SourceIterator first,
			     SourceIterator last,
			     DestIterator dest,
			     int max,
			     Func&& func) {

  if (first == last || !max) return {first, dest};

  typedef typename std::iterator_traits<SourceIterator>::value_type ArgType;
  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
  typedef decltype(func(*first)) DestType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // a specialization of std::numeric_limits::max() for all arithmetic
  // types is required by §3.9.1/8 of the standard.  The iterator
  // difference type must be a signed integer type (§24.2.1/1).  All
  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
  // §3.9.1/8).
  const DiffType local_max =
    (max >= 0) ? max : std::numeric_limits<DiffType>::max();

  // intermediate results have to be held in an array so destination
  // ordering can be enforced when using insert interators.  This
  // causes some inefficiency for non-random access iterators
  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
							    std::distance(first, last))]);

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<ArgType&, DestType&> s_task{
    Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgType, DestType>,
			    std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first != last && start_count < local_max; ++first, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgType, DestType, DiffType, SourceIterator>,
					s_task,
					first,
					&mutex,
					&cond,
					&done_count,
					results.get(),
					start_count))
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
  for (DiffType index = 0; index < start_count; ++dest, ++index) {
    *dest = std::move(results[index]);
  }
  return {first, dest};
}

/**
 * \#include <c++-gtk-utils/parallel.h>
 *
 * This function maps over two containers, one in the range ['first1',
 * 'last1') subject to a maximum, and the other beginning at 'first2',
 * applying a binary callable object to each element of the containers
 * in those ranges (subject to the maximum) and storing the result in
 * the destination range, by executing each such application as a task
 * of a Thread::TaskManager object.  Tasks are added to the
 * Thread::TaskManager object in the order in which the respective
 * elements appear in the source containers, and the final result
 * appears in the destination container in the same order as the
 * source ranges from which it is generated (including if a
 * back_inserter iterator is used), but no other ordering arises, and
 * the tasks will execute in parallel to the extent that the
 * Thread::TaskManager object has sufficient threads available to do
 * so.
 *
 * A separate overload of this function takes a unary callable object.
 *
 * This function does the same as the version of
 * Thread::parallel_transform() taking a binary callable object,
 * except that it returns a std::tuple object containing iterators to
 * the element past the last elements of the source ranges
 * transformed, and a destination iterator to the element past the
 * last element stored in the destination range, and it has a 'max'
 * parameter to limit the maximum number of elements which will be so
 * transformed on any one call to this function.  Whether this
 * limitation has had effect on any one call can be tested by checking
 * whether the first value of the tuple returned is equal to the
 * 'last' parameter.  If it is not, a further call to this function
 * can be made.
 *
 * The main purpose of this additional function is to enable the
 * parallel transform of the elements of a container to be dealt with
 * in chunks, possibly to enable other tasks to be interleaved at
 * reasonable intervals.  For source or destination containers which
 * do not support random access iterators, the 'last' parameter can be
 * set to, say, the end of the container and the chunk size set with
 * the 'max' paramater, with the values of the returned tuple being
 * used as the 'first1', 'first2' and 'dest' parameters for subsequent
 * calls to this function.  This avoids having to increment the source
 * and destination iterators for each "chunk" by stepping through the
 * respective containers by hand.  In this usage, it therefore
 * represents a minor efficiency improvement.
 *
 * @param tm The Thread::TaskManager object on which the tasks will
 * run.
 * @param first1 The beginning of the range which is to be passed as
 * the first argument of 'func'.
 * @param last1 One past the last element of the range which is to be
 * passed as the first argument of 'func', subject to any maximum
 * specified as the 'max' parameter.
 * @param first2 The beginning of the range which is to be passed as
 * the second argument of 'func'.
 * @param dest The beginning of the range to which the result of
 * applying 'func' to the elements in the source ranges is to be
 * stored.  As in the case of std::transform, this can overlap with or
 * be the same as one of the source ranges.  It may also be an insert
 * iterator.
 * @param max The maximum number of elements of the source containers
 * which will be transformed on this call.  It is not an error if it
 * is greater than the distance between 'first1' and 'last1'.  If it
 * is equal to or greater than that distance, it follows that the
 * first value of the tuple returned by this function will be equal to
 * 'last1'.  The same results if 'max' is a negative number (in that
 * case no maximum will take effect and all elements in the range
 * ['first1', 'last1') will be transformed), so passing -1 might be
 * useful as a means of obtaining a second source iterator (the second
 * value of the tuple) or destination iterator (the third value) for
 * other purposes, particularly where they are not random access
 * iterators.
 * @param func A binary callable object to be applied (subject to the
 * maximum) to each element in the source ranges, such as formed by a
 * lambda expression or the result of std::bind.  It should take two
 * unbound arguments of the value types of the containers to which
 * 'first1' and 'first2' relate or const or non-const references to
 * those types.  If an exception propagates from 'func', the exception
 * will be consumed while the transform loop is running, and an
 * attempt will still be made to apply 'func' to all remaining
 * elements of the source ranges subject to the maximum, and only
 * after that attempt has completed will the exception
 * Cgu::Thread::ParallelError be thrown.
 * @return A std::tuple object.  Its first value is an iterator
 * representing the element past the last element of the first source
 * range transformed, which may be passed as the 'first1' argument of
 * a subsequent call to this function; its second value is an iterator
 * representing the element past the last element of the second source
 * range transformed, which may be passed as the 'first2' argument of
 * the subsequent call; and its third value is an iterator
 * representing the element past the last element stored in the
 * destination range, which may be passed as the 'dest' argument of
 * the subsequent call.
 * @exception std::bad_alloc This exception will be thrown if memory
 * is exhausted and the system throws in that case.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion).  If this exception
 * is thrown, some tasks may nonetheless have already started by
 * virtue of the call to this function, but subsequent ones will not.
 * @exception Cgu::Thread::TaskError This exception will be thrown if
 * stop_all() has previously been called on the Thread::TaskManager
 * object, or if another thread calls stop_all() after this method is
 * called but before it has returned.  It will also be thrown if the
 * Thread::TaskManager object's is_error() method would return true
 * because its internal thread pool loop implementation has thrown
 * std::bad_alloc, or a thread has failed to start correctly because
 * pthread has run out of resources.  (On systems with
 * over-commit/lazy-commit combined with virtual memory (swap), it is
 * rarely useful to check for memory exhaustion, and if a reasonable
 * maximum thread count has been chosen for the Thread::TaskManager
 * object pthread should not run out of other resources, but there may
 * be some specialized cases where the return value of is_error() is
 * useful.)  If this exception is thrown, some tasks may nonetheless
 * have already started by virtue of the call to this function.
 * @exception Cgu::Thread::ParallelError This exception will be thrown
 * if an exception propagates from the 'func' callable object when it
 * executes on being applied to one or more elements of the source
 * ranges.  Such an exception will not stop an attempt being made to
 * apply 'func' (successfully or unsuccessfully) to all elements in
 * the source ranges subject to the maximum.
 * Cgu::Thread::ParallelError will be thrown after such attempted
 * application has finished.
 * @exception Cgu::Thread::MutexError This exception will be thrown if
 * initialization of a mutex used by this function fails.  (It is
 * often not worth checking for this, as it means either memory is
 * exhausted or pthread has run out of other resources to create new
 * mutexes.)  If this exception is thrown, no tasks will start.
 * @exception Cgu::Thread::CondError This exception will be thrown if
 * initialization of a condition variable used by this function fails.
 * (It is often not worth checking for this, as it means either memory
 * is exhausted or pthread has run out of other resources to create
 * new condition variables.)  If this exception is thrown, no tasks
 * will start.
 * @note An exception might also be thrown if the copy or move
 * constructor of the 'func' callable objects throws.  If such an
 * exception is thrown, no tasks will start.
 * 
 * Since 2.0.20/2.2.3
 */
template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
std::tuple<SourceIterator1, SourceIterator2, DestIterator>
  parallel_transform_partial(TaskManager& tm,
			     SourceIterator1 first1,
			     SourceIterator1 last1,
			     SourceIterator2 first2,
			     DestIterator dest,
			     int max,
			     Func&& func) {

  if (first1 == last1 || !max) return std::make_tuple(first1, first2, dest);

  typedef typename std::iterator_traits<SourceIterator1>::value_type Arg1Type;
  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
  typedef typename std::iterator_traits<SourceIterator2>::value_type Arg2Type;
  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
  typedef decltype(func(*first1, *first2)) DestType;

  Mutex mutex;
  Cond cond;
  DiffType start_count = 0;
  DiffType done_count = 0;
  bool error = false;

  // a specialization of std::numeric_limits::max() for all arithmetic
  // types is required by §3.9.1/8 of the standard.  The iterator
  // difference type must be a signed integer type (§24.2.1/1).  All
  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
  // §3.9.1/8).
  const DiffType local_max =
    (max >= 0) ? max : std::numeric_limits<DiffType>::max();

  // intermediate results have to be held in an array so destination
  // ordering can be enforced when using insert interators.  This
  // causes some inefficiency for non-random access iterators
  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
							    std::distance(first1, last1))]);

  // construct SafeFunctorArg objects so that they can be shared
  // between different tasks
  Cgu::Callback::SafeFunctorArg<Arg1Type&, Arg2Type&, DestType&> s_task{
    Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1Type, Arg2Type, DestType>,
			    std::forward<Func>(func))
  };
  Cgu::Callback::SafeFunctor s_fail{
    Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
			&mutex,
			&cond,
			&error,
			&done_count)
  };

  for (; first1 != last1 && start_count < local_max; ++first1, ++first2, ++start_count) {
    std::unique_ptr<const Cgu::Callback::Callback> task_cb(
      Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1Type, Arg2Type, DestType, DiffType, SourceIterator1, SourceIterator2>,
					s_task,
					first1,
					first2,
					&mutex,
					&cond,
					&done_count,
					results.get(),
					start_count))
    );
    std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
      Cgu::Callback::lambda<>([s_fail] () {s_fail();})
    );

    tm.add_task(std::move(task_cb), std::move(fail_cb));
  }
  
  Mutex::Lock l{mutex};
  while (start_count > done_count) cond.wait(mutex);
  if (error) throw ParallelError();
  for (DiffType index = 0; index < start_count; ++dest, ++index) {
    *dest = std::move(results[index]);
  }
  return std::make_tuple(first1, first2, dest);
}

} // namespace Thread

} // namespace Cgu

#endif // CGU_PARALLEL_H
