TestKthOrderStatistic.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 <kth_order_statistic.hxx>
22 
23 // STD includes
24 #include <functional>
25 
26 using namespace huc::search;
27 
28 #ifndef DOXYGEN_SKIP
29 namespace {
30  const int SortedArrayInt[] = {-3, -2, 0, 2, 8, 15, 36, 212, 366}; // Simple sorted array of integers with negative values
31  const int RandomArrayInt[] = {4, 3, 5, 2, -18, 3, 2, 3, 4, 5, -5}; // Simple random array of integers with negative values
32  const std::string RandomStr = "xacvgeze"; // Random string
33 
34  typedef std::vector<int> Container;
35  typedef Container::iterator IT;
36  typedef std::greater_equal<Container::value_type> GR_Compare;
37 }
38 #endif /* DOXYGEN_SKIP */
39 
40 // Test kth smallest elements
41 TEST(TestSearch, KthOrderStatistic)
42 {
43  {
44  // Basic run on random array - Should return 4
45  Container krandomdArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(int));
46  EXPECT_EQ(4, *KthOrderStatistic<IT>(krandomdArray.begin(), krandomdArray.end(), 7));
47  }
48 
49  Container ksortedArray(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(int));
50 
51  // Basic run on sorted array with unique element - Should the kth element
52  EXPECT_EQ(ksortedArray.begin() + 4, KthOrderStatistic<IT>(ksortedArray.begin(), ksortedArray.end(), 4));
53 
54  // Empty sequence - Should return end on empty sequence
55  EXPECT_EQ(ksortedArray.begin(), KthOrderStatistic<IT>(ksortedArray.begin(), ksortedArray.begin(), 0));
56 
57  // Unique element sequence - Should return the unique element
58  EXPECT_EQ(ksortedArray.begin(), KthOrderStatistic<IT>(ksortedArray.begin(), ksortedArray.begin() + 1, 0));
59 
60  // Negative index - Should return end for out of scope search (k = 0)
61  EXPECT_EQ(ksortedArray.begin(), KthOrderStatistic<IT>(ksortedArray.begin(), ksortedArray.end(), 0));
62 
63  // k bigger than the size of the sequence - Should return end for out of scope search
64  EXPECT_EQ(ksortedArray.end(), KthOrderStatistic<IT>(ksortedArray.begin(), ksortedArray.end(), 100));
65 
66  // String
67  {
68  std::string randomStr = RandomStr;
69  const char secondSmallestLetter = *KthOrderStatistic
70  <std::string::iterator, std::less_equal<char>>(randomStr.begin(), randomStr.end(), 1);
71  EXPECT_EQ('c', secondSmallestLetter);
72  }
73 }
74 
75 // Test kth min element
76 TEST(TestSearch, MinKthElement)
77 {
78  // Basic run on random array - Should return 5 (second biggest value)
79  Container krandomdArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(int));
80  IT::value_type value = *KthOrderStatistic<IT, GR_Compare>(krandomdArray.begin(), krandomdArray.end(), 1);
81  EXPECT_EQ(5, value);
82 }
IT KthOrderStatistic(const IT &begin, const IT &end, unsigned int k)
TEST(TestSearch, KthOrderStatistic)