Line data    Source code

       1             : // Copyright (c) 2018-2024  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        1027 :             while(container.size() < size)
      73             :             {
      74        1017 :                 std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
      75        1017 :                 if(std::find(container.begin(), container.end(), s) == container.end())
      76             :                 {
      77         874 :                     container.push_back(s);
      78             :                 }
      79        1017 :             }
      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        1210 :             while(container.size() < size)
     103             :             {
     104        1200 :                 std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     105        1200 :                 if(std::find(container.begin(), container.end(), s) == container.end())
     106             :                 {
     107        1011 :                     container.push_back(s);
     108             :                 }
     109        1200 :             }
     110          10 :             std::vector<std::string> copy(container);
     111          10 :             std::size_t dups(rand() % 50 + 25);
     112         480 :             for(std::size_t i(0); i < dups; ++i)
     113             :             {
     114         470 :                 int const d(rand() % container.size());
     115         470 :                 int const p(rand() % (container.size() + 1));
     116         470 :                 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        1118 :             while(container.size() < size)
     148             :             {
     149        1108 :                 std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     150        1108 :                 if(std::find(container.begin(), container.end(), s) == container.end())
     151             :                 {
     152         931 :                     container.push_back(s);
     153             :                 }
     154        1108 :             }
     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        1284 :             while(container.size() < size)
     177             :             {
     178        1274 :                 std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     179        1274 :                 if(std::find(container.begin(), container.end(), s) == container.end())
     180             :                 {
     181        1084 :                     container.push_back(s);
     182             :                 }
     183        1274 :             }
     184          10 :             std::vector<std::string> copy(container);
     185          10 :             std::size_t dups(rand() % 50 + 25);
     186         551 :             for(std::size_t i(0); i < dups; ++i)
     187             :             {
     188         541 :                 int const d(rand() % container.size());
     189         541 :                 int const p(rand() % (container.size() + 1));
     190         541 :                 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        1126 :             while(container.size() < size)
     216             :             {
     217        1116 :                 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          80 :         while(container.size() < size)
     245             :         {
     246          79 :             std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     247          79 :             if(std::find(container.begin(), container.end(), s) == container.end())
     248             :             {
     249          66 :                 container.push_back(s);
     250             :             }
     251          79 :         }
     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          97 :         while(container.size() < size)
     270             :         {
     271          96 :             std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     272          96 :             if(std::find(container.begin(), container.end(), s) == container.end())
     273             :             {
     274          76 :                 container.push_back(s);
     275             :             }
     276          96 :         }
     277           1 :         std::vector<std::string> copy(container);
     278           1 :         std::size_t dups(rand() % 50 + 25);
     279          62 :         for(std::size_t i(0); i < dups; ++i)
     280             :         {
     281          61 :             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          61 :             int const p(d + rand() % (container.size() - d) + 1);
     287             : 
     288          61 :             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         130 :         while(container.size() < size)
     307             :         {
     308         129 :             std::string const s(SNAP_CATCH2_NAMESPACE::random_string(0, rand() % 25));
     309         129 :             if(std::find(container.begin(), container.end(), s) == container.end())
     310             :             {
     311         114 :                 container.push_back(s);
     312             :             }
     313         129 :         }
     314           1 :         std::list<std::string> copy(container);
     315           1 :         std::size_t dups(rand() % 50 + 25);
     316          27 :         for(std::size_t i(0); i < dups; ++i)
     317             :         {
     318          26 :             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          26 :             int const p(d + rand() % (container.size() - d) + 1);
     324             : 
     325          26 :             auto d_it(container.begin());
     326          26 :             std::advance(d_it, d);
     327          26 :             auto p_it(container.begin());
     328          26 :             std::advance(p_it, p);
     329          26 :             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         987 :             while(container.size() < size)
     351             :             {
     352         977 :                 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