20 #include <gtest/gtest.h> 34 const int SortedArrayInt[] = {-3, -2, 0, 2, 8, 15, 36, 212, 366};
36 const int SortedArrayIntWithRot[] = {-3, 2, 7, 20, 0, 2, 8, 15, 36};
38 const int SortedArrayIntPos[] = {0, 2, 8, 15, 36, 212, 366, 15478};
40 const int RandomArrayInt[] = {4, 3, 5, 2, -18, 3, 2, 3, 4, 5, -5};
42 const int RandomArrayIntPos[] = {4520, 30, 500, 20, 3, 2, 3, 4, 5, 15};
44 const std::string RandomStr =
"xacvgeze";
46 const std::string StringWithPivot =
"eknxasuw";
48 typedef std::vector<int> Container;
49 typedef Container::iterator IT;
55 TEST(TestMerge, MergeInPlaces)
59 Container sortedArrayWithRot
60 (SortedArrayIntWithRot, SortedArrayIntWithRot +
sizeof(SortedArrayIntWithRot) /
sizeof(
int));
62 (sortedArrayWithRot.begin(), sortedArrayWithRot.begin() + 4, sortedArrayWithRot.end());
65 for (
auto it = sortedArrayWithRot.begin(); it < sortedArrayWithRot.end() - 1; ++it)
66 EXPECT_LE(*it, *(it + 1));
71 Container sortedArrayPos
72 (SortedArrayIntPos, SortedArrayIntPos +
sizeof(SortedArrayIntPos) /
sizeof(
int));
73 MergeInPlace<IT>()(sortedArrayPos.begin(), sortedArrayPos.begin() + 5, sortedArrayPos.end());
76 for (
auto it = sortedArrayPos.begin(); it < sortedArrayPos.end() - 1; ++it)
77 EXPECT_LE(*it, *(it + 1));
82 Container randomArrayPos
83 (RandomArrayIntPos, RandomArrayIntPos +
sizeof(RandomArrayIntPos) /
sizeof(
int));
84 MergeInPlace<IT>()(randomArrayPos.end(), randomArrayPos.begin() + 3, randomArrayPos.begin());
87 for (
auto it = randomArrayPos.begin(); it < randomArrayPos.end(); ++it, ++i)
88 EXPECT_EQ(RandomArrayIntPos[i], *it);
94 MergeInPlace<IT>()(emptyArray.begin(), emptyArray.begin(), emptyArray.end());
99 Container uniqueValueArray(1, 511);
100 MergeInPlace<IT>()(uniqueValueArray.begin(), uniqueValueArray.end(), uniqueValueArray.end());
101 EXPECT_EQ(511, uniqueValueArray[0]);
106 Container doubleValuesArray(1, 511);
107 doubleValuesArray.push_back(66);
110 (doubleValuesArray.begin(), doubleValuesArray.begin() + 1, doubleValuesArray.end());
112 EXPECT_EQ(66, doubleValuesArray[0]);
113 EXPECT_EQ(511, doubleValuesArray[1]);
118 std::string stringToMerge = StringWithPivot;
120 (stringToMerge.begin(), stringToMerge.begin() + 4, stringToMerge.end());
123 for (
auto it = stringToMerge.begin(); it < stringToMerge.end() - 1; ++it)
124 EXPECT_LE(*it, *(it + 1));
130 TEST(TestMerge, MergeWithBuffers)
134 Container sortedArrayWithRot
135 (SortedArrayIntWithRot, SortedArrayIntWithRot +
sizeof(SortedArrayIntWithRot) /
sizeof(
int));
137 (sortedArrayWithRot.begin(), sortedArrayWithRot.begin() + 4, sortedArrayWithRot.end());
140 for (
auto it = sortedArrayWithRot.begin(); it < sortedArrayWithRot.end() - 1; ++it)
141 EXPECT_LE(*it, *(it + 1));
146 Container sortedArrayPos
147 (SortedArrayIntPos, SortedArrayIntPos +
sizeof(SortedArrayIntPos) /
sizeof(
int));
149 (sortedArrayPos.begin(), sortedArrayPos.begin() + 5, sortedArrayPos.end());
152 for (
auto it = sortedArrayPos.begin(); it < sortedArrayPos.end() - 1; ++it)
153 EXPECT_LE(*it, *(it + 1));
158 Container randomArrayPos
159 (RandomArrayIntPos, RandomArrayIntPos +
sizeof(RandomArrayIntPos) /
sizeof(
int));
161 (randomArrayPos.end(), randomArrayPos.begin() + 3, randomArrayPos.begin());
164 for (
auto it = randomArrayPos.begin(); it < randomArrayPos.end(); ++it, ++i)
165 EXPECT_EQ(RandomArrayIntPos[i], *it);
170 Container emptyArray;
176 Container uniqueValueArray(1, 511);
178 (uniqueValueArray.begin(), uniqueValueArray.end(), uniqueValueArray.end());
179 EXPECT_EQ(511, uniqueValueArray[0]);
184 Container doubleValuesArray(1, 511);
185 doubleValuesArray.push_back(66);
188 (doubleValuesArray.begin(), doubleValuesArray.begin() + 1, doubleValuesArray.end());
190 EXPECT_EQ(66, doubleValuesArray[0]);
191 EXPECT_EQ(511, doubleValuesArray[1]);
196 std::string stringToMerge =
"eknxasuw";
198 (stringToMerge.begin(), stringToMerge.begin() + 4, stringToMerge.end());
201 for (std::string::iterator it = stringToMerge.begin(); it < stringToMerge.end() - 1; ++it)
202 EXPECT_LE(*it, *(it + 1));
211 Container randomdArray(RandomArrayInt, RandomArrayInt +
sizeof(RandomArrayInt) /
sizeof(
int));
212 MergeSort<Container, IT>(randomdArray.begin(), randomdArray.end());
215 for (
auto it = randomdArray.begin(); it < randomdArray.end() - 1; ++it)
216 EXPECT_LE(*it, *(it + 1));
221 Container sortedArray(SortedArrayInt, SortedArrayInt +
sizeof(SortedArrayInt) /
sizeof(
int));
222 MergeSort<Container, IT>(sortedArray.begin(), sortedArray.end());
225 for (
auto it = sortedArray.begin(); it < sortedArray.end() - 1; ++it)
226 EXPECT_LE(*it, *(it + 1));
231 Container randomdArray(RandomArrayInt, RandomArrayInt +
sizeof(RandomArrayInt) /
sizeof(
int));
232 MergeSort<Container, IT>(randomdArray.end(), randomdArray.begin());
235 for (
auto it = randomdArray.begin(); it < randomdArray.end(); ++it, ++i)
236 EXPECT_EQ(RandomArrayInt[i], *it);
241 Container emptyArray;
242 MergeSort<Container, IT>(emptyArray.begin(), emptyArray.end());
247 Container uniqueValueArray(1, 511);
248 MergeSort<Container, IT>(uniqueValueArray.begin(), uniqueValueArray.end());
249 EXPECT_EQ(511, uniqueValueArray[0]);
254 std::string randomStr = RandomStr;
255 MergeSort<std::string, std::string::iterator, Aggregator_Str>(randomStr.begin(), randomStr.end());
258 for (
auto it = randomStr.begin(); it < randomStr.end() - 1; ++it)
259 EXPECT_LE(*it, *(it + 1));
TEST(TestMerge, MergeInPlaces)