TestMaxSubSequence.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 <max_sub_sequence.hxx>
22 
23 // STD includes
24 #include <functional>
25 
26 // Testing namespace
27 using namespace huc::search;
28 
29 #ifndef DOXYGEN_SKIP
30 namespace {
31  // Simple sorted array of integers with negative values
32  const int SortedArrayInt[] = {-3, -2, 0, 2, 8, 15, 36, 212, 366};
33  // Simple random array of integers with negative values
34  const int RandomArrayInt[] = {4, 3, 5, 2, -18, 3, 2, 3, 4, 5, -5};
35 
36  typedef std::vector<int> Container;
37  typedef Container::iterator IT;
38 }
39 #endif /* DOXYGEN_SKIP */
40 
41 // Test MaxSubSequence
42 TEST(TestSearch, MaxSubSequence)
43 {
44  // Should return <5,9> (maximal sum of 17)
45  {
46  Container kMarketPrices(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(int));
47  const auto kMaxBeneficeIndexes = MaxSubSequence<IT>(kMarketPrices.begin(), kMarketPrices.end());
48  EXPECT_EQ(5, kMaxBeneficeIndexes.first);
49  EXPECT_EQ(9, kMaxBeneficeIndexes.second);
50  }
51 
52  // Should return <FirstPositiveIdx, idxEnd> on sorted array
53  {
54  Container kSortedArray(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(int));
55  const auto kIndexes = MaxSubSequence<IT>(kSortedArray.begin(), kSortedArray.end());
56  EXPECT_EQ(2, kIndexes.first);
57  EXPECT_EQ(static_cast<int>(kSortedArray.size()) - 1, kIndexes.second);
58  }
59 
60  // Should return <-1,-1> on insufficient array
61  {
62  Container insufficientArray = Container(1, 2);
63  const auto kIndexes = MaxSubSequence<IT>(insufficientArray.begin(), insufficientArray.end());
64  EXPECT_EQ(-1, kIndexes.first);
65  EXPECT_EQ(-1, kIndexes.second);
66  }
67 
68  // Should return <0,1> on array containing only two positive elements
69  {
70  Container twoElementArray = Container(2, 2);
71  const auto kIndexes = MaxSubSequence<IT>(twoElementArray.begin(), twoElementArray.end());
72  EXPECT_EQ(0, kIndexes.first);
73  EXPECT_EQ(1, kIndexes.second);
74  }
75 
76  // Should return <0, idxEnd> on array containing the same positive value
77  {
78  const int kSize = 10;
79  Container sameElementArray = Container(kSize, 2);
80  const auto indexes = MaxSubSequence<IT>(sameElementArray.begin(), sameElementArray.end());
81  EXPECT_EQ(0, indexes.first);
82  EXPECT_EQ(kSize - 1, indexes.second);
83  }
84 }
std::pair< int, int > MaxSubSequence(const IT &begin, const IT &end)
TEST(TestSearch, MaxSubSequence)