TestBinary.cxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * HUC - Hurna Core
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #include <gtest/gtest.h>
21 #include <binary.hxx>
22 
23 // Testing namespace
24 using namespace huc::search;
25 
26 #ifndef DOXYGEN_SKIP
27 namespace {
28  // Simple sorted array of integers with negative values
29  const int SortedArrayInt[] = {-3, -2, 0, 2, 8, 15, 36, 212, 366};
30  // Simple sorted array of floats with negative values
31  const double SortedDoubleArray[] = {-.3, 0.0, 0.12, 2.5, 8};
32  // Ordered string
33  const std::string OrderedStr = "acegmnoop";
34 
35  typedef std::vector<int> Container;
36  typedef Container::iterator IT;
37  typedef std::vector<double>::iterator IT_DL;
38 
39  template <typename T>
40  struct EQUIVALENT
41  {
42  bool operator()(const T& a, const T& b) const
43  { return std::abs(a - b) < std::numeric_limits<T>::epsilon(); }
44  };
45 
46  template <typename T>
47  struct EQUAL
48  {
49  bool operator()(const T& a, const T& b) const { return a == b; }
50  };
51 }
52 #endif /* DOXYGEN_SKIP */
53 
54 // Basic BinarySearchIterative tests on a sorted array of ints
55 TEST(TestSearch, BinarySearchBasics)
56 {
57  Container sortedArray(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(int));
58 
59  // Empty array
60  {
61  Container emptyArray = Container();
62  const auto index = BinarySearch<IT, EQUAL<int>>(emptyArray.begin(), emptyArray.end(), 0);
63  EXPECT_EQ(-1, index); // Should return -1 on empty array
64  }
65 
66  // First element
67  {
68  const auto index = BinarySearch<IT, EQUAL<int>>(sortedArray.begin(), sortedArray.end(), -3);
69  EXPECT_EQ(0, index);
70  }
71 
72  // Existing random value
73  {
74  const auto index = BinarySearch<IT, EQUAL<int>>(sortedArray.begin(), sortedArray.end(), 8);
75  EXPECT_EQ(4, index);
76  }
77 
78  // Non-existing element
79  {
80  const auto index = BinarySearch<IT, EQUAL<int>>(sortedArray.begin(), sortedArray.end(), 1);
81  EXPECT_EQ(-1, index);
82  }
83 
84  // String collection - Find letter
85  {
86  const auto index = BinarySearch<std::string::const_iterator, EQUAL<char>>
87  (OrderedStr.begin(), OrderedStr.end(), 'm');
88  EXPECT_EQ(4, index);
89  }
90 }
91 
92 // Basic BinarySearchIterative tests on a sorted array of doubles
93 TEST(TestSearch, BinarySearchDoubles)
94 {
95  std::vector<double> sortedDoubleArray
96  (SortedDoubleArray, SortedDoubleArray + sizeof(SortedDoubleArray) / sizeof(double));
97 
98  // First element
99  {
100  const auto index = BinarySearch<IT_DL, EQUIVALENT<double>>
101  (sortedDoubleArray.begin(), sortedDoubleArray.end(), static_cast<const double>(-.3));
102  EXPECT_EQ(0, index);
103  }
104 
105  // Existing element
106  {
107  const auto index = BinarySearch<IT_DL, EQUIVALENT<double>>
108  (sortedDoubleArray.begin(), sortedDoubleArray.end(), static_cast<const double>(0.12));
109  EXPECT_EQ(2, index);
110  }
111 
112  // Non Existing element
113  {
114  const auto index = BinarySearch<IT_DL, EQUIVALENT<double>>
115  (sortedDoubleArray.begin(), sortedDoubleArray.end(), static_cast<const double>(8.1));
116  EXPECT_EQ(-1, index);
117  }
118 
119  // Value in the middle when identical values
120  {
121  std::vector<double> identicalArray = std::vector<double>(10, 3.);
122  const auto index = BinarySearch<IT_DL, EQUIVALENT<double>>
123  (identicalArray.begin(), identicalArray.end(), static_cast<const double>(3.));
124  EXPECT_EQ(5, index);
125  }
126 }
TEST(TestSearch, BinarySearchBasics)
Definition: TestBinary.cxx:55