#include <vtkm/cont/ArrayHandle.h>
#include <vtkm/cont/DeviceAdapter.h>
#include <vtkm/cont/TryExecute.h>

#include <vtkm/BinaryOperators.h>
#include <vtkm/BinaryPredicates.h>
#include <vtkm/UnaryPredicates.h>

#include <vtkm/cont/testing/Testing.h>

#include <vector>

////
//// BEGIN-EXAMPLE DeviceAdapterAlgorithmPrototype.cxx
////
namespace vtkm
{
namespace cont
{

template<typename DeviceAdapterTag>
struct DeviceAdapterAlgorithm;
}
} // namespace vtkm
////
//// END-EXAMPLE DeviceAdapterAlgorithmPrototype.cxx
////

namespace
{

template<typename T>
void CheckArray(const std::string& name,
                const vtkm::cont::ArrayHandle<T>& array,
                const std::vector<T>& expected)
{
  vtkm::Id numValues = array.GetNumberOfValues();
  auto portal = array.GetPortalConstControl();
  std::cout << name << ": { ";
  for (vtkm::Id index = 0; index < numValues; ++index)
  {
    std::cout << portal.Get(index) << ", ";
  }
  std::cout << "}" << std::endl;

  VTKM_TEST_ASSERT(numValues == static_cast<vtkm::Id>(expected.size()),
                   "Array is wrong size.");

  for (vtkm::Id index = 0; index < numValues; ++index)
  {
    VTKM_TEST_ASSERT(test_equal(portal.Get(index), expected[std::size_t(index)]),
                     "Bad values.");
  }
}

#define CHECK_ARRAY(array, T, ...)                                                  \
  CheckArray(#array, array, std::vector<T>{ __VA_ARGS__ })

template<typename DeviceAdapterTag>
struct DoFunctor
{
  VTKM_CONT void DoCopy()
  {
    std::cout << "Testing Copy" << std::endl;
    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmCopy.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> output;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Copy(input, output);

    // output has { 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 }
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmCopy.cxx
    ////
    CHECK_ARRAY(output, vtkm::Int32, 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3);
  }

  VTKM_CONT void DoCopyIf()
  {
    std::cout << "Testing CopyIf" << std::endl;
    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmCopyIf.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    std::vector<vtkm::UInt8> stencilBuffer{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);
    vtkm::cont::ArrayHandle<vtkm::UInt8> stencil =
      vtkm::cont::make_ArrayHandle(stencilBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> output;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::CopyIf(
      input, stencil, output);

    // output has { 0, 5, 3, 8, 3 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Int32, 0, 5, 3, 8, 3);
    //// RESUME-EXAMPLE

    struct LessThan5
    {
      VTKM_EXEC_CONT bool operator()(vtkm::Int32 x) const { return x < 5; }
    };

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::CopyIf(
      input, input, output, LessThan5());

    // output has { 0, 1, 1, 4, 3, 3 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Int32, 0, 1, 1, 4, 3, 3);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmCopyIf.cxx
    ////
  }

  VTKM_CONT void DoCopySubRange()
  {
    std::cout << "Testing CopySubRange" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmCopySubRange.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> output;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::CopySubRange(
      input, 1, 7, output);

    // output has { 0, 1, 1, 5, 5, 4, 3 }
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmCopySubRange.cxx
    ////
    CHECK_ARRAY(output, vtkm::Int32, 0, 1, 1, 5, 5, 4, 3);
  }

  VTKM_CONT void DoLowerBounds()
  {
    std::cout << "Testing LowerBounds" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmLowerBounds.cxx
    ////
    std::vector<vtkm::Int32> sortedBuffer{ 0, 1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 9 };
    std::vector<vtkm::Int32> valuesBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };

    vtkm::cont::ArrayHandle<vtkm::Int32> sorted =
      vtkm::cont::make_ArrayHandle(sortedBuffer);
    vtkm::cont::ArrayHandle<vtkm::Int32> values =
      vtkm::cont::make_ArrayHandle(valuesBuffer);

    vtkm::cont::ArrayHandle<vtkm::Id> output;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::LowerBounds(
      sorted, values, output);

    // output has { 8, 0, 1, 1, 6, 6, 5, 3, 8, 10, 11, 3 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Id, 8, 0, 1, 1, 6, 6, 5, 3, 8, 10, 11, 3);
    //// RESUME-EXAMPLE

    std::vector<vtkm::Int32> revSortedBuffer{ 9, 8, 7, 7, 5, 5, 4, 3, 3, 1, 1, 0 };
    vtkm::cont::ArrayHandle<vtkm::Int32> reverseSorted =
      vtkm::cont::make_ArrayHandle(revSortedBuffer);

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::LowerBounds(
      reverseSorted, values, output, vtkm::SortGreater());

    // output has { 2, 11, 9, 9, 4, 4, 6, 7, 2, 1, 0, 7 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Id, 2, 11, 9, 9, 4, 4, 6, 7, 2, 1, 0, 7);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmLowerBounds.cxx
    ////
  }

  VTKM_CONT void DoReduce()
  {
    std::cout << "Testing Reduce" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmReduce.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 1, 1, 5, 5 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::Int32 sum =
      vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Reduce(input, 0);

    // sum is 12

    vtkm::Int32 product =
      vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Reduce(
        input, 1, vtkm::Multiply());

    // product is 25
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmReduce.cxx
    ////

    VTKM_TEST_ASSERT(sum == 12, "Sum wrong.");
    VTKM_TEST_ASSERT(product == 25, "Product wrong.");
  }

  VTKM_CONT void DoReduceByKey()
  {
    std::cout << "Testing ReduceByKey" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmReduceByKey.cxx
    ////
    std::vector<vtkm::Id> keyBuffer{ 0, 0, 3, 3, 3, 3, 5, 6, 6, 6, 6, 6 };
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };

    vtkm::cont::ArrayHandle<vtkm::Id> keys = vtkm::cont::make_ArrayHandle(keyBuffer);
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Id> uniqueKeys;
    vtkm::cont::ArrayHandle<vtkm::Int32> sums;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ReduceByKey(
      keys, input, uniqueKeys, sums, vtkm::Add());

    // uniqueKeys is { 0, 3, 5, 6 }
    // sums is { 7, 12, 4, 30 }

    vtkm::cont::ArrayHandle<vtkm::Int32> products;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ReduceByKey(
      keys, input, uniqueKeys, products, vtkm::Multiply());

    // products is { 0, 25, 4, 4536 }
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmReduceByKey.cxx
    ////

    CHECK_ARRAY(uniqueKeys, vtkm::Id, 0, 3, 5, 6);
    CHECK_ARRAY(sums, vtkm::Int32, 7, 12, 4, 30);
    CHECK_ARRAY(products, vtkm::Int32, 0, 25, 4, 4536);
  }

  VTKM_CONT void DoScanExclusive()
  {
    std::cout << "Testing ScanExclusive" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmScanExclusive.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> runningSum;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanExclusive(input,
                                                                        runningSum);

    // runningSum is { 0, 7, 7, 8, 9, 14, 19, 23, 26, 33, 41, 50 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningSum, vtkm::Int32, 0, 7, 7, 8, 9, 14, 19, 23, 26, 33, 41, 50);
    //// RESUME-EXAMPLE

    vtkm::cont::ArrayHandle<vtkm::Int32> runningMax;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanExclusive(
      input, runningMax, vtkm::Maximum(), -1);

    // runningMax is { -1, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningMax, vtkm::Int32, -1, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmScanExclusive.cxx
    ////
  }

  VTKM_CONT void DoScanExclusiveByKey()
  {
    std::cout << "Testing ScanExclusiveByKey" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmScanExclusiveByKey.cxx
    ////
    std::vector<vtkm::Id> keyBuffer{ 0, 0, 3, 3, 3, 3, 5, 6, 6, 6, 6, 6 };
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };

    vtkm::cont::ArrayHandle<vtkm::Id> keys = vtkm::cont::make_ArrayHandle(keyBuffer);
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> runningSums;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanExclusiveByKey(
      keys, input, runningSums);

    // runningSums is { 0, 7, 0, 1, 2, 7, 0, 0, 3, 10, 18, 27 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningSums, vtkm::Int32, 0, 7, 0, 1, 2, 7, 0, 0, 3, 10, 18, 27);
    //// RESUME-EXAMPLE

    vtkm::cont::ArrayHandle<vtkm::Int32> runningMaxes;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanExclusiveByKey(
      keys, input, runningMaxes, -1, vtkm::Maximum());

    // runningMax is { -1, 7, -1, 1, 1, 5, -1, -1, 3, 7, 8, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningMaxes, vtkm::Int32, -1, 7, -1, 1, 1, 5, -1, -1, 3, 7, 8, 9);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmScanExclusiveByKey.cxx
    ////
  }

  VTKM_CONT void DoScanInclusive()
  {
    std::cout << "Testing ScanInclusive" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmScanInclusive.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> runningSum;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanInclusive(input,
                                                                        runningSum);

    // runningSum is { 7, 7, 8, 9, 14, 19, 23, 26, 33, 41, 50, 53 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningSum, vtkm::Int32, 7, 7, 8, 9, 14, 19, 23, 26, 33, 41, 50, 53);
    //// RESUME-EXAMPLE

    vtkm::cont::ArrayHandle<vtkm::Int32> runningMax;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanInclusive(
      input, runningMax, vtkm::Maximum());

    // runningMax is { 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningMax, vtkm::Int32, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmScanInclusive.cxx
    ////
  }

  VTKM_CONT void DoScanInclusiveByKey()
  {
    std::cout << "Testing ScanInclusiveByKey" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmScanInclusiveByKey.cxx
    ////
    std::vector<vtkm::Id> keyBuffer{ 0, 0, 3, 3, 3, 3, 5, 6, 6, 6, 6, 6 };
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };

    vtkm::cont::ArrayHandle<vtkm::Id> keys = vtkm::cont::make_ArrayHandle(keyBuffer);
    vtkm::cont::ArrayHandle<vtkm::Int32> input =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::ArrayHandle<vtkm::Int32> runningSums;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanInclusiveByKey(
      keys, input, runningSums);

    // runningSums is { 7, 7, 1, 2, 7, 12, 4, 3, 10, 18, 27, 30 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningSums, vtkm::Int32, 7, 7, 1, 2, 7, 12, 4, 3, 10, 18, 27, 30);
    //// RESUME-EXAMPLE

    vtkm::cont::ArrayHandle<vtkm::Int32> runningMaxes;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::ScanInclusiveByKey(
      keys, input, runningMaxes, vtkm::Maximum());

    // runningMax is { 7, 7, 1, 1, 5, 5, 4, 3, 7, 8, 9, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(runningMaxes, vtkm::Int32, 7, 7, 1, 1, 5, 5, 4, 3, 7, 8, 9, 9);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmScanInclusiveByKey.cxx
    ////
  }

  VTKM_CONT void DoSort()
  {
    std::cout << "Testing Sort" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmSort.cxx
    ////
    std::vector<vtkm::Int32> inputBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };
    vtkm::cont::ArrayHandle<vtkm::Int32> array =
      vtkm::cont::make_ArrayHandle(inputBuffer);

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Sort(array);

    // array has { 0, 1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(array, vtkm::Int32, 0, 1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 9);
    //// RESUME-EXAMPLE

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Sort(array,
                                                               vtkm::SortGreater());

    // array has { 9, 8, 7, 7, 5, 5, 4, 3, 3, 1, 1, 0 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(array, vtkm::Int32, 9, 8, 7, 7, 5, 5, 4, 3, 3, 1, 1, 0);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmSort.cxx
    ////
  }

  VTKM_CONT void DoSortByKey()
  {
    std::cout << "Testing SortByKey" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmSortByKey.cxx
    ////
    std::vector<vtkm::Int32> keyBuffer{ 7, 0, 1, 5, 4, 8, 9, 3 };
    std::vector<vtkm::Id> valueBuffer{ 0, 1, 2, 3, 4, 5, 6, 7 };

    vtkm::cont::ArrayHandle<vtkm::Int32> keys =
      vtkm::cont::make_ArrayHandle(keyBuffer);
    vtkm::cont::ArrayHandle<vtkm::Id> values =
      vtkm::cont::make_ArrayHandle(valueBuffer);

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::SortByKey(keys, values);

    // keys has   { 0, 1, 3, 4, 5, 7, 8, 9 }
    // values has { 1, 2, 7, 4, 3, 0, 5, 6 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(keys, vtkm::Int32, 0, 1, 3, 4, 5, 7, 8, 9);
    CHECK_ARRAY(values, vtkm::Id, 1, 2, 7, 4, 3, 0, 5, 6);
    //// RESUME-EXAMPLE

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::SortByKey(
      keys, values, vtkm::SortGreater());

    // keys has   { 9, 8, 7, 5, 4, 3, 1, 0 }
    // values has { 6, 5, 0, 3, 4, 7, 2, 1 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(keys, vtkm::Int32, 9, 8, 7, 5, 4, 3, 1, 0);
    CHECK_ARRAY(values, vtkm::Id, 6, 5, 0, 3, 4, 7, 2, 1);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmSortByKey.cxx
    ////
  }

  VTKM_CONT void DoUnique()
  {
    std::cout << "Testing Unqiue" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmUnique.cxx
    ////
    std::vector<vtkm::Int32> valuesBuffer{ 0, 1, 1, 3, 3, 4, 5, 5, 7, 7, 7, 9 };
    vtkm::cont::ArrayHandle<vtkm::Int32> values =
      vtkm::cont::make_ArrayHandle(valuesBuffer);

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Unique(values);

    // values has {0, 1, 3, 4, 5, 7, 9}

    std::vector<vtkm::Float64> fvaluesBuffer{ 0.0, 0.001, 0.0, 1.5, 1.499, 2.0 };
    vtkm::cont::ArrayHandle<vtkm::Float64> fvalues =
      vtkm::cont::make_ArrayHandle(fvaluesBuffer);

    struct AlmostEqualFunctor
    {
      VTKM_EXEC_CONT bool operator()(vtkm::Float64 x, vtkm::Float64 y) const
      {
        return (vtkm::Abs(x - y) < 0.1);
      }
    };

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::Unique(
      fvalues, AlmostEqualFunctor());

    // values has {0.0, 1.5, 2.0}
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmUnique.cxx
    ////

    CHECK_ARRAY(values, vtkm::Int32, 0, 1, 3, 4, 5, 7, 9);
    CHECK_ARRAY(fvalues, vtkm::Float64, 0.0, 1.5, 2.0);
  }

  VTKM_CONT void DoUpperBounds()
  {
    std::cout << "Testing UpperBounds" << std::endl;

    ////
    //// BEGIN-EXAMPLE DeviceAdapterAlgorithmUpperBounds.cxx
    ////
    std::vector<vtkm::Int32> sortedBuffer{ 0, 1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 9 };
    std::vector<vtkm::Int32> valuesBuffer{ 7, 0, 1, 1, 5, 5, 4, 3, 7, 8, 9, 3 };

    vtkm::cont::ArrayHandle<vtkm::Int32> sorted =
      vtkm::cont::make_ArrayHandle(sortedBuffer);
    vtkm::cont::ArrayHandle<vtkm::Int32> values =
      vtkm::cont::make_ArrayHandle(valuesBuffer);

    vtkm::cont::ArrayHandle<vtkm::Id> output;

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::UpperBounds(
      sorted, values, output);

    // output has { 10, 1, 3, 3, 8, 8, 6, 5, 10, 11, 12, 5 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Id, 10, 1, 3, 3, 8, 8, 6, 5, 10, 11, 12, 5);
    //// RESUME-EXAMPLE

    std::vector<vtkm::Int32> revSortedBuffer{ 9, 8, 7, 7, 5, 5, 4, 3, 3, 1, 1, 0 };
    vtkm::cont::ArrayHandle<vtkm::Int32> reverseSorted =
      vtkm::cont::make_ArrayHandle(revSortedBuffer);

    vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapterTag>::UpperBounds(
      reverseSorted, values, output, vtkm::SortGreater());

    // output has { 4, 12, 11, 11, 6, 6, 7, 9, 4, 2, 1, 9 }
    //// PAUSE-EXAMPLE
    CHECK_ARRAY(output, vtkm::Id, 4, 12, 11, 11, 6, 6, 7, 9, 4, 2, 1, 9);
    //// RESUME-EXAMPLE
    ////
    //// END-EXAMPLE DeviceAdapterAlgorithmUpperBounds.cxx
    ////
  }

  VTKM_CONT void Run()
  {
    std::cout << "Running tests on device "
              << vtkm::cont::DeviceAdapterTraits<DeviceAdapterTag>::GetName()
              << std::endl;
    this->DoCopy();
    this->DoCopyIf();
    this->DoCopySubRange();
    this->DoLowerBounds();
    this->DoReduce();
    this->DoReduceByKey();
    this->DoScanExclusive();
    this->DoScanExclusiveByKey();
    this->DoScanInclusive();
    this->DoScanInclusiveByKey();
    this->DoSort();
    this->DoSortByKey();
    this->DoUnique();
    this->DoUpperBounds();
  }
};

void Test()
{
  DoFunctor<VTKM_DEFAULT_DEVICE_ADAPTER_TAG> functor;
  functor.Run();
}

} // anonymous namespace

int DeviceAdapterAlgorithms(int, char* [])
{
  return vtkm::cont::testing::Testing::Run(Test);
}
