Line data Source code
1 : // Copyright (c) 2018-2025 Made to Order Software Corp. All Rights Reserved
2 : //
3 : // https://snapwebsites.org/project/snapdev
4 : // contact@m2osw.com
5 : //
6 : // This program is free software: you can redistribute it and/or modify
7 : // it under the terms of the GNU General Public License as published by
8 : // the Free Software Foundation, either version 3 of the License, or
9 : // (at your option) any later version.
10 : //
11 : // This program is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 : //
16 : // You should have received a copy of the GNU General Public License
17 : // along with this program. If not, see <https://www.gnu.org/licenses/>.
18 :
19 : /** \file
20 : * \brief Verify that the different remove duplicate algorithms work.
21 : *
22 : * This file implements tests for the different remove duplicate functions.
23 : */
24 :
25 : // self
26 : //
27 : #include <snapdev/remove_duplicates.h>
28 :
29 : #include "catch_main.h"
30 :
31 :
32 : // C++
33 : //
34 : #include <deque>
35 : #include <list>
36 :
37 :
38 : // last include
39 : //
40 : #include <snapdev/poison.h>
41 :
42 :
43 : namespace
44 : {
45 :
46 :
47 :
48 :
49 :
50 : }
51 : // no name namespace
52 :
53 :
54 :
55 3 : CATCH_TEST_CASE("sort_and_remove_duplicates", "[remove_duplicates][container]")
56 : {
57 3 : CATCH_START_SECTION("sort_and_remove_duplicates: empty container")
58 : {
59 1 : std::vector<std::string> empty;
60 1 : std::vector<std::string> *output = &snapdev::sort_and_remove_duplicates(empty);
61 1 : CATCH_REQUIRE(&empty == output);
62 1 : CATCH_REQUIRE(empty.empty());
63 1 : }
64 3 : CATCH_END_SECTION()
65 :
66 3 : CATCH_START_SECTION("sort_and_remove_duplicates: container without duplicates")
67 : {
68 11 : for(int count(0); count < 10; ++count)
69 : {
70 10 : std::vector<std::string> container;
71 10 : std::size_t size(rand() % 100 + 50);
72 1159 : while(container.size() < size)
73 : {
74 1149 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
75 1149 : if(std::find(container.begin(), container.end(), s) == container.end())
76 : {
77 970 : container.push_back(s);
78 : }
79 1149 : }
80 10 : std::vector<std::string> copy(container);
81 10 : std::vector<std::string> *output = &snapdev::sort_and_remove_duplicates(container);
82 10 : CATCH_REQUIRE(&container == output);
83 10 : CATCH_REQUIRE(container.size() == copy.size());
84 :
85 10 : std::sort(copy.begin(), copy.end());
86 10 : CATCH_REQUIRE(container == copy);
87 10 : }
88 : }
89 3 : CATCH_END_SECTION()
90 :
91 3 : CATCH_START_SECTION("sort_and_remove_duplicates: container with duplicates")
92 : {
93 11 : for(int count(0); count < 10; ++count)
94 : {
95 10 : std::vector<std::string> container;
96 :
97 : // we want to be in control of the duplication and know exactly what
98 : // we are going to get back out so we need to create a container
99 : // without duplicates first then add duplicates in a second loop
100 : //
101 10 : std::size_t size(rand() % 100 + 50);
102 1221 : while(container.size() < size)
103 : {
104 1211 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
105 1211 : if(std::find(container.begin(), container.end(), s) == container.end())
106 : {
107 1013 : container.push_back(s);
108 : }
109 1211 : }
110 10 : std::vector<std::string> copy(container);
111 10 : std::size_t dups(rand() % 50 + 25);
112 491 : for(std::size_t i(0); i < dups; ++i)
113 : {
114 481 : int const d(rand() % container.size());
115 481 : int const p(rand() % (container.size() + 1));
116 481 : container.insert(container.begin() + p, container[d]);
117 : }
118 10 : std::vector<std::string> *output = &snapdev::sort_and_remove_duplicates(container);
119 10 : CATCH_REQUIRE(&container == output);
120 10 : CATCH_REQUIRE(container.size() == copy.size());
121 :
122 10 : std::sort(copy.begin(), copy.end());
123 10 : CATCH_REQUIRE(container == copy);
124 10 : }
125 : }
126 3 : CATCH_END_SECTION()
127 3 : }
128 :
129 :
130 4 : CATCH_TEST_CASE("sorted_remove_duplicates", "[remove_duplicates][container]")
131 : {
132 4 : CATCH_START_SECTION("sorted_remove_duplicates: empty container")
133 : {
134 1 : std::vector<std::string> empty;
135 1 : std::vector<std::string> *output = &snapdev::sorted_remove_duplicates(empty);
136 1 : CATCH_REQUIRE(&empty == output);
137 1 : CATCH_REQUIRE(empty.empty());
138 1 : }
139 4 : CATCH_END_SECTION()
140 :
141 4 : CATCH_START_SECTION("sorted_remove_duplicates: container without duplicates")
142 : {
143 11 : for(int count(0); count < 10; ++count)
144 : {
145 10 : std::vector<std::string> container;
146 10 : std::size_t size(rand() % 100 + 50);
147 1477 : while(container.size() < size)
148 : {
149 1467 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
150 1467 : if(std::find(container.begin(), container.end(), s) == container.end())
151 : {
152 1245 : container.push_back(s);
153 : }
154 1467 : }
155 10 : std::sort(container.begin(), container.end());
156 10 : std::vector<std::string> copy(container);
157 10 : std::vector<std::string> *output = &snapdev::sorted_remove_duplicates(container);
158 10 : CATCH_REQUIRE(&container == output);
159 10 : CATCH_REQUIRE(container.size() == copy.size());
160 10 : CATCH_REQUIRE(container == copy);
161 10 : }
162 : }
163 4 : CATCH_END_SECTION()
164 :
165 4 : CATCH_START_SECTION("sorted_remove_duplicates: container with duplicates")
166 : {
167 11 : for(int count(0); count < 10; ++count)
168 : {
169 10 : std::vector<std::string> container;
170 :
171 : // we want to be in control of the duplication and know exactly what
172 : // we are going to get back out so we need to create a container
173 : // without duplicates first then add duplicates in a second loop
174 : //
175 10 : std::size_t size(rand() % 100 + 50);
176 1073 : while(container.size() < size)
177 : {
178 1063 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
179 1063 : if(std::find(container.begin(), container.end(), s) == container.end())
180 : {
181 877 : container.push_back(s);
182 : }
183 1063 : }
184 10 : std::vector<std::string> copy(container);
185 10 : std::size_t dups(rand() % 50 + 25);
186 571 : for(std::size_t i(0); i < dups; ++i)
187 : {
188 561 : int const d(rand() % container.size());
189 561 : int const p(rand() % (container.size() + 1));
190 561 : container.insert(container.begin() + p, container[d]);
191 : }
192 10 : std::sort(container.begin(), container.end());
193 10 : std::vector<std::string> *output = &snapdev::sorted_remove_duplicates(container);
194 10 : CATCH_REQUIRE(&container == output);
195 10 : CATCH_REQUIRE(container.size() == copy.size());
196 :
197 10 : std::sort(copy.begin(), copy.end());
198 10 : CATCH_REQUIRE(container == copy);
199 10 : }
200 : }
201 4 : CATCH_END_SECTION()
202 :
203 4 : CATCH_START_SECTION("sorted_remove_duplicates: container with one item duplicated")
204 : {
205 11 : for(int count(0); count < 10; ++count)
206 : {
207 10 : std::list<std::string> container;
208 :
209 : // we want to be in control of the duplication and know exactly what
210 : // we are going to get back out so we need to create a container
211 : // without duplicates first then add duplicates in a second loop
212 : //
213 10 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
214 10 : std::size_t size(rand() % 100 + 50);
215 1080 : while(container.size() < size)
216 : {
217 1070 : container.push_back(s);
218 : }
219 10 : std::list<std::string> *output = &snapdev::sorted_remove_duplicates(container);
220 10 : CATCH_REQUIRE(&container == output);
221 10 : CATCH_REQUIRE(container.size() == 1);
222 10 : CATCH_REQUIRE(container.front() == s);
223 10 : }
224 : }
225 4 : CATCH_END_SECTION()
226 4 : }
227 :
228 :
229 5 : CATCH_TEST_CASE("unsorted_remove_duplicates", "[remove_duplicates][container]")
230 : {
231 5 : CATCH_START_SECTION("unsorted_remove_duplicates: empty container")
232 : {
233 1 : std::vector<std::string> empty;
234 1 : std::vector<std::string> *output = &snapdev::unsorted_remove_duplicates(empty);
235 1 : CATCH_REQUIRE(&empty == output);
236 1 : CATCH_REQUIRE(empty.empty());
237 1 : }
238 5 : CATCH_END_SECTION()
239 :
240 5 : CATCH_START_SECTION("unsorted_remove_duplicates: container without duplicates")
241 : {
242 1 : std::vector<std::string> container;
243 1 : std::size_t size(rand() % 100 + 50);
244 82 : while(container.size() < size)
245 : {
246 81 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
247 81 : if(std::find(container.begin(), container.end(), s) == container.end())
248 : {
249 73 : container.push_back(s);
250 : }
251 81 : }
252 1 : std::vector<std::string> copy(container);
253 1 : std::vector<std::string> *output = &snapdev::unsorted_remove_duplicates(container);
254 1 : CATCH_REQUIRE(&container == output);
255 1 : CATCH_REQUIRE(container.size() == copy.size());
256 1 : CATCH_REQUIRE(container == copy);
257 1 : }
258 5 : CATCH_END_SECTION()
259 :
260 5 : CATCH_START_SECTION("unsorted_remove_duplicates: container with duplicates (vector)")
261 : {
262 1 : std::vector<std::string> container;
263 :
264 : // we want to be in control of the duplication and know exactly what
265 : // we are going to get back out so we need to create a container
266 : // without duplicates first then add duplicates in a second loop
267 : //
268 1 : std::size_t size(rand() % 100 + 50);
269 144 : while(container.size() < size)
270 : {
271 143 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
272 143 : if(std::find(container.begin(), container.end(), s) == container.end())
273 : {
274 125 : container.push_back(s);
275 : }
276 143 : }
277 1 : std::vector<std::string> copy(container);
278 1 : std::size_t dups(rand() % 50 + 25);
279 33 : for(std::size_t i(0); i < dups; ++i)
280 : {
281 32 : int const d(rand() % container.size());
282 :
283 : // since items do not get sorted, we need p > d for this test
284 : // to work properly
285 : //
286 32 : int const p(d + rand() % (container.size() - d) + 1);
287 :
288 32 : container.insert(container.begin() + p, container[d]);
289 : }
290 1 : std::vector<std::string> *output = &snapdev::unsorted_remove_duplicates(container);
291 1 : CATCH_REQUIRE(&container == output);
292 1 : CATCH_REQUIRE(container.size() == copy.size());
293 1 : CATCH_REQUIRE(container == copy);
294 1 : }
295 5 : CATCH_END_SECTION()
296 :
297 5 : CATCH_START_SECTION("unsorted_remove_duplicates: container with duplicates (list)")
298 : {
299 1 : std::list<std::string> container;
300 :
301 : // we want to be in control of the duplication and know exactly what
302 : // we are going to get back out so we need to create a container
303 : // without duplicates first then add duplicates in a second loop
304 : //
305 1 : std::size_t size(rand() % 100 + 50);
306 114 : while(container.size() < size)
307 : {
308 113 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
309 113 : if(std::find(container.begin(), container.end(), s) == container.end())
310 : {
311 95 : container.push_back(s);
312 : }
313 113 : }
314 1 : std::list<std::string> copy(container);
315 1 : std::size_t dups(rand() % 50 + 25);
316 34 : for(std::size_t i(0); i < dups; ++i)
317 : {
318 33 : int const d(rand() % container.size());
319 :
320 : // since items do not get sorted, we need p > d for this test
321 : // to work properly
322 : //
323 33 : int const p(d + rand() % (container.size() - d) + 1);
324 :
325 33 : auto d_it(container.begin());
326 : std::advance(d_it, d);
327 33 : auto p_it(container.begin());
328 : std::advance(p_it, p);
329 33 : container.insert(p_it, *d_it);
330 : }
331 1 : std::list<std::string> *output = &snapdev::unsorted_remove_duplicates(container);
332 1 : CATCH_REQUIRE(&container == output);
333 1 : CATCH_REQUIRE(container.size() == copy.size());
334 1 : CATCH_REQUIRE(container == copy);
335 1 : }
336 5 : CATCH_END_SECTION()
337 :
338 5 : CATCH_START_SECTION("unsorted_remove_duplicates: container with one item duplicated")
339 : {
340 11 : for(int count(0); count < 10; ++count)
341 : {
342 10 : std::deque<std::string> container;
343 :
344 : // we want to be in control of the duplication and know exactly what
345 : // we are going to get back out so we need to create a container
346 : // without duplicates first then add duplicates in a second loop
347 : //
348 10 : std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
349 10 : std::size_t size(rand() % 100 + 50);
350 990 : while(container.size() < size)
351 : {
352 980 : container.push_back(s);
353 : }
354 10 : std::deque<std::string> *output = &snapdev::sorted_remove_duplicates(container);
355 10 : CATCH_REQUIRE(&container == output);
356 10 : CATCH_REQUIRE(container.size() == 1);
357 10 : CATCH_REQUIRE(container.front() == s);
358 10 : }
359 : }
360 5 : CATCH_END_SECTION()
361 5 : }
362 :
363 :
364 :
365 : // vim: ts=4 sw=4 et
|
