text: //  Copyright (c) 2015 Daniel Bourgeois
  //
  //  SPDX-License-Identifier: BSL-1.0
  //  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)
  
  #pragma once
  
  #include <hpx/hpx.hpp>
  #include <hpx/hpx_init.hpp>
  #include <hpx/include/parallel_executors.hpp>
  #include <hpx/include/parallel_is_sorted.hpp>
  #include <hpx/modules/testing.hpp>
  
  #include <cstddef>
  #include <iterator>
  #include <numeric>
  #include <random>
  #include <utility>
  #include <vector>
  
  #include "test_utils.hpp"
  
  ////////////////////////////////////////////////////////////////////////////////
  int seed = std::random_device{}();
  std::mt19937 gen(seed);
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted1(ExPolicy&& policy, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c), std::end(c), 0);
  
      bool is_ordered = hpx::parallel::is_sorted(std::forward<ExPolicy>(policy),
          iterator(std::begin(c)), iterator(std::end(c)));
  
      HPX_TEST(is_ordered);
  }
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted1_async(ExPolicy&& p, IteratorTag)
  {
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c), std::end(c), 0);
  
      hpx::future<bool> f = hpx::parallel::is_sorted(std::forward<ExPolicy>(p),
          iterator(std::begin(c)), iterator(std::end(c)));
      f.wait();
  
      HPX_TEST(f.get());
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted2(ExPolicy policy, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c), std::end(c), 0);
      //Add a certain large value in middle of array to ignore
      std::size_t ignore = 20000;
      c[c.size() / 2] = ignore;
      //Provide custom predicate to ignore the value of ignore
      //pred should return true when it is given something deemed not sorted
      auto pred = [&ignore](std::size_t ahead, std::size_t behind) {
          return behind > ahead && behind != ignore;
      };
  
      bool is_ordered = hpx::parallel::is_sorted(
          policy, iterator(std::begin(c)), iterator(std::end(c)), pred);
  
      HPX_TEST(is_ordered);
  }
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted2_async(ExPolicy p, IteratorTag)
  {
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c), std::end(c), 0);
      //Add a certain large value in middle of array to ignore
      std::size_t ignore = 20000;
      c[c.size() / 2] = ignore;
      //Provide custom predicate to ignore the value of ignore
      //pred should return true when it is given something deemed not sorted
      auto pred = [&ignore](std::size_t ahead, std::size_t behind) {
          return behind > ahead && behind != ignore;
      };
  
      hpx::future<bool> f = hpx::parallel::is_sorted(
          p, iterator(std::begin(c)), iterator(std::end(c)), pred);
      f.wait();
  
      HPX_TEST(f.get());
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted3(ExPolicy policy, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c_beg(10007);
      std::vector<std::size_t> c_end(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c_beg), std::end(c_beg), 0);
      std::iota(std::begin(c_end), std::end(c_end), 0);
      //add unsorted element to c_beg, c_end at the beginning, end respectively
      c_beg[0] = 20000;
      c_end[c_end.size() - 1] = 0;
  
      bool is_ordered1 = hpx::parallel::is_sorted(
          policy, iterator(std::begin(c_beg)), iterator(std::end(c_beg)));
      bool is_ordered2 = hpx::parallel::is_sorted(
          policy, iterator(std::begin(c_end)), iterator(std::end(c_end)));
  
      HPX_TEST(!is_ordered1);
      HPX_TEST(!is_ordered2);
  }
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted3_async(ExPolicy p, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::test_iterator<base_iterator, IteratorTag> iterator;
  
      std::vector<std::size_t> c_beg(10007);
      std::vector<std::size_t> c_end(10007);
      //Fill with sorted values from 0 to 10006
      std::iota(std::begin(c_beg), std::end(c_beg), 0);
      std::iota(std::begin(c_end), std::end(c_end), 0);
      //add unsorted element to c_beg, c_end at the beginning, end respectively
      c_beg[0] = 20000;
      c_end[c_end.size() - 1] = 0;
  
      hpx::future<bool> f1 = hpx::parallel::is_sorted(
          p, iterator(std::begin(c_beg)), iterator(std::end(c_beg)));
      hpx::future<bool> f2 = hpx::parallel::is_sorted(
          p, iterator(std::begin(c_end)), iterator(std::end(c_end)));
      f1.wait();
      HPX_TEST(!f1.get());
      f2.wait();
      HPX_TEST(!f2.get());
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted_exception(ExPolicy policy, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::decorated_iterator<base_iterator, IteratorTag>
          decorated_iterator;
      std::vector<std::size_t> c(10007);
      std::iota(std::begin(c), std::end(c), 0);
  
      bool caught_exception = false;
      try
      {
          hpx::parallel::is_sorted(policy,
              decorated_iterator(
                  std::begin(c), []() { throw std::runtime_error("test"); }),
              decorated_iterator(
                  std::end(c), []() { throw std::runtime_error("test"); }));
      }
      catch (hpx::exception_list const& e)
      {
          caught_exception = true;
          test::test_num_exceptions<ExPolicy, IteratorTag>::call(policy, e);
      }
      catch (...)
      {
          HPX_TEST(false);
      }
  
      HPX_TEST(caught_exception);
  }
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted_exception_async(ExPolicy p, IteratorTag)
  {
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::decorated_iterator<base_iterator, IteratorTag>
          decorated_iterator;
  
      std::vector<std::size_t> c(10007);
      std::iota(std::begin(c), std::end(c), gen() + 1);
  
      bool caught_exception = false;
      try
      {
          hpx::future<bool> f = hpx::parallel::is_sorted(p,
              decorated_iterator(
                  std::begin(c), []() { throw std::runtime_error("test"); }),
              decorated_iterator(
                  std::end(c), []() { throw std::runtime_error("test"); }));
          f.get();
  
          HPX_TEST(false);
      }
      catch (hpx::exception_list const& e)
      {
          caught_exception = true;
          test::test_num_exceptions<ExPolicy, IteratorTag>::call(p, e);
      }
      catch (...)
      {
          HPX_TEST(false);
      }
  
      HPX_TEST(caught_exception);
  }
  
  ////////////////////////////////////////////////////////////////////////////////
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted_bad_alloc(ExPolicy policy, IteratorTag)
  {
      static_assert(hpx::is_execution_policy<ExPolicy>::value,
          "hpx::is_execution_policy<ExPolicy>::value");
  
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::decorated_iterator<base_iterator, IteratorTag>
          decorated_iterator;
  
      std::vector<std::size_t> c(100007);
      std::iota(std::begin(c), std::end(c), 0);
  
      bool caught_bad_alloc = false;
      try
      {
          hpx::parallel::is_sorted(policy,
              decorated_iterator(std::begin(c), []() { throw std::bad_alloc(); }),
              decorated_iterator(std::end(c), []() { throw std::bad_alloc(); }));
          HPX_TEST(false);
      }
      catch (std::bad_alloc const&)
      {
          caught_bad_alloc = true;
      }
      catch (...)
      {
          HPX_TEST(false);
      }
  
      HPX_TEST(caught_bad_alloc);
  }
  
  template <typename ExPolicy, typename IteratorTag>
  void test_sorted_bad_alloc_async(ExPolicy p, IteratorTag)
  {
      typedef std::vector<std::size_t>::iterator base_iterator;
      typedef test::decorated_iterator<base_iterator, IteratorTag>
          decorated_iterator;
  
      std::vector<std::size_t> c(10007);
      std::iota(std::begin(c), std::end(c), 0);
  
      bool caught_bad_alloc = false;
      try
      {
          hpx::future<bool> f = hpx::parallel::is_sorted(p,
              decorated_iterator(std::begin(c), []() { throw std::bad_alloc(); }),
              decorated_iterator(std::end(c), []() { throw std::bad_alloc(); }));
  
          f.get();
          HPX_TEST(false);
      }
      catch (std::bad_alloc const&)
      {
          caught_bad_alloc = true;
      }
      catch (...)
      {
          HPX_TEST(false);
      }
  
      HPX_TEST(caught_bad_alloc);
  }
  