ceph/src/boost/libs/compute/test/test_binary_search.cpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
   3 //
   4 // Distributed under the Boost Software License, Version 1.0
   5 // See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt
   7 //
   8 // See http://boostorg.github.com/compute for more information.
   9 //---------------------------------------------------------------------------//
  10
  11 #define BOOST_TEST_MODULE TestBinarySearch
  12 #include <boost/test/unit_test.hpp>
  13
  14 #include <iterator>
  15
  16 #include <boost/compute/command_queue.hpp>
  17 #include <boost/compute/algorithm/binary_search.hpp>
  18 #include <boost/compute/algorithm/fill.hpp>
  19 #include <boost/compute/algorithm/lower_bound.hpp>
  20 #include <boost/compute/algorithm/upper_bound.hpp>
  21 #include <boost/compute/container/vector.hpp>
  22
  23 #include "context_setup.hpp"
  24
  25 BOOST_AUTO_TEST_CASE(binary_search_int)
  26 {
  27     // test data = { 1, ..., 2, ..., 4, 4, 5, 7, ..., 9, ..., 10 }
  28     boost::compute::vector<int> vector(size_t(4096), int(1), queue);
  29     boost::compute::vector<int>::iterator first = vector.begin() + 128;
  30     boost::compute::vector<int>::iterator last = first + (1024 - 128);
  31     boost::compute::fill(first, last, int(2), queue);
  32     last.write(4, queue); last++;
  33     last.write(4, queue); last++;
  34     last.write(5, queue); last++;
  35     first = last;
  36     last = first + 127;
  37     boost::compute::fill(first, last, 7, queue);
  38     first = last;
  39     last = vector.end() - 1;
  40     boost::compute::fill(first, last, 9, queue);
  41     last.write(10, queue);
  42     queue.finish();
  43
  44     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(0), queue) == false);
  45     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(1), queue) == true);
  46     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(2), queue) == true);
  47     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(3), queue) == false);
  48     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(4), queue) == true);
  49     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(5), queue) == true);
  50     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(6), queue) == false);
  51     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(7), queue) == true);
  52     BOOST_CHECK(boost::compute::binary_search(vector.begin(), vector.end(), int(8), queue) == false);
  53 }
  54
  55 BOOST_AUTO_TEST_CASE(range_bounds_int)
  56 {
  57     // test data = { 1, ..., 2, ..., 4, 4, 5, 7, ..., 9, ..., 10 }
  58     boost::compute::vector<int> vector(size_t(4096), int(1), queue);
  59     boost::compute::vector<int>::iterator first = vector.begin() + 128;
  60     boost::compute::vector<int>::iterator last = first + (1024 - 128);
  61     boost::compute::fill(first, last, int(2), queue);
  62     last.write(4, queue); last++; // 1024
  63     last.write(4, queue); last++; // 1025
  64     last.write(5, queue); last++; // 1026
  65     first = last;
  66     last = first + 127;
  67     boost::compute::fill(first, last, 7, queue);
  68     first = last;
  69     last = vector.end() - 1;
  70     boost::compute::fill(first, last, 9, queue);
  71     last.write(10, queue);
  72     queue.finish();
  73
  74     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(0), queue) == vector.begin());
  75     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(0), queue) == vector.begin());
  76
  77     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(1), queue) == vector.begin());
  78     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(1), queue) == vector.begin() + 128);
  79
  80     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(2), queue) == vector.begin() + 128);
  81     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(2), queue) == vector.begin() + 1024);
  82
  83     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(4), queue) == vector.begin() + 1024);
  84     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(4), queue) == vector.begin() + 1026);
  85
  86     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(5), queue) == vector.begin() + 1026);
  87     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(5), queue) == vector.begin() + 1027);
  88
  89     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(6), queue) == vector.begin() + 1027);
  90     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(6), queue) == vector.begin() + 1027);
  91
  92     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(7), queue) == vector.begin() + 1027);
  93     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(7), queue) == vector.begin() + (1027 + 127));
  94
  95     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(9), queue) == vector.begin() + (1027 + 127));
  96     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(9), queue) == vector.end() - 1);
  97
  98     BOOST_CHECK(boost::compute::lower_bound(vector.begin(), vector.end(), int(10), queue) == vector.end() - 1);
  99     BOOST_CHECK(boost::compute::upper_bound(vector.begin(), vector.end(), int(10), queue) == vector.end());
 100 }
 101
 102 BOOST_AUTO_TEST_SUITE_END()