Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : 
      11             : #define BOOST_AUTO_TEST_MAIN
      12             : #include <boost/test/included/unit_test.hpp>
      13             : 
      14             : #include <random>
      15             : #include <unordered_set>
      16             : 
      17             : #include "mcrl2/utilities/hash_utility.h"
      18             : #include "mcrl2/utilities/unordered_map.h"
      19             : 
      20             : 
      21             : using namespace mcrl2::utilities;
      22             : 
      23             : template<typename T>
      24           6 : unordered_set<T> construct(std::initializer_list<T> list)
      25             : {
      26           6 :   unordered_set<T> set;
      27             : 
      28          30 :   for (const T& element : list)
      29             :   {
      30          24 :     set.emplace(element);
      31             :   }
      32             : 
      33           6 :   return set;
      34           0 : }
      35             : 
      36           2 : BOOST_AUTO_TEST_CASE(test_small)
      37             : {
      38             :   // Test with inserting 5, 3, 2, 5 expected { 2,3,5 }
      39           1 :   unordered_set<int> set = construct({5,3,2,5});
      40             : 
      41           1 :   BOOST_CHECK(set.find(5) != set.end());
      42           1 :   BOOST_CHECK(set.find(2) != set.end());
      43           1 :   BOOST_CHECK(set.find(3) != set.end());
      44             : 
      45           1 :   BOOST_CHECK(set.count(5) != 0);
      46           1 :   BOOST_CHECK(set.count(2) != 0);
      47           1 :   BOOST_CHECK(set.count(3) != 0);
      48             : 
      49           1 :   BOOST_CHECK(set.size() == 3);
      50           1 :   BOOST_CHECK(!set.empty());
      51           1 : }
      52             : 
      53           2 : BOOST_AUTO_TEST_CASE(test_large)
      54             : {
      55             :   // Test inserting a large number of elements (tests resize behaviour).
      56           1 :   std::random_device dev;
      57           1 :   std::mt19937 rng(dev());
      58           1 :   std::uniform_int_distribution<std::mt19937::result_type> dist(1,10000);
      59             : 
      60           1 :   unordered_set<int> test;
      61             : 
      62             :   // Here, we assume that the standard library implementation is correct.
      63           1 :   std::unordered_set<int> correct;
      64      100001 :   for (std::size_t i = 0; i < 100000; ++i)
      65             :   {
      66      100000 :     auto value = dist(rng);
      67      100000 :     test.emplace(value);
      68      100000 :     correct.emplace(value);
      69             :   }
      70             : 
      71             :   // Check that both contain the same elements.
      72       10000 :   for (auto& value : correct)
      73             :   {
      74        9999 :     BOOST_CHECK(test.find(value) != test.end());
      75             :   }
      76             : 
      77           1 :   BOOST_CHECK(test.size() == correct.size());
      78             : 
      79       10000 :   for (auto& value : test)
      80             :   {
      81        9999 :     BOOST_CHECK(correct.find(value) != correct.end());
      82             :   }
      83           1 : }
      84             : 
      85           2 : BOOST_AUTO_TEST_CASE(test_copy)
      86             : {
      87             :   // Test the copy constructor.
      88           1 :   unordered_set<int> set = construct({5,3,2,5});
      89             : 
      90           1 :   unordered_set<int> copy(set);
      91           1 :   set.clear();
      92             : 
      93           1 :   BOOST_CHECK(copy.find(5) != copy.end());
      94           1 :   BOOST_CHECK(copy.find(2) != copy.end());
      95           1 :   BOOST_CHECK(copy.find(3) != copy.end());
      96           1 : }
      97             : 
      98           2 : BOOST_AUTO_TEST_CASE(test_move)
      99             : {
     100             :   // Test the move constructor.
     101           1 :   unordered_set<int> set = construct({5,3,2,5});
     102           1 :   unordered_set<int> moved = std::move(set);
     103           1 : }
     104             : 
     105           2 : BOOST_AUTO_TEST_CASE(test_empty)
     106             : {
     107           1 :   unordered_set<int> set(0);
     108             : 
     109           1 :   BOOST_CHECK(set.empty());
     110           1 :   BOOST_CHECK(set.size() == 0);
     111             : 
     112           1 :   for (auto it = set.begin(); it != set.end(); ++it)
     113             :   {
     114           0 :     BOOST_CHECK(false);
     115             :   }
     116           1 : }
     117             : 
     118           2 : BOOST_AUTO_TEST_CASE(test_find_erase)
     119             : {
     120             :   // Try to erase an element using the iterator returned by find.
     121           1 :   unordered_set<int> set = construct({5,3,2,5});
     122             : 
     123           1 :   auto it = set.find(3);
     124           1 :   BOOST_CHECK(it != set.end());
     125           1 :   set.erase(it);
     126           1 : }
     127             : 
     128           2 : BOOST_AUTO_TEST_CASE(test_erase_begin)
     129             : {
     130             :   // Try to erase an element using the iterator returned by find.
     131           1 :   unordered_set<int> set = construct({5,3,2,5});
     132           1 :   set.erase(set.begin());
     133           1 : }
     134             : 
     135           2 : BOOST_AUTO_TEST_CASE(test_const_iterator)
     136             : {
     137           1 :   unordered_set<int> set = construct({5,3,2,5});
     138           1 :   auto it = set.begin();
     139           1 :   unordered_set<int>::const_iterator const_it = it;
     140             : 
     141           1 :   const unordered_set<int>::iterator it2 = set.begin();
     142           1 :   int value = *it2;
     143           1 :   BOOST_CHECK(value == *const_it);
     144           1 : }
     145             : 
     146             : class Object
     147             : {
     148             : public:
     149           2 :   Object(std::vector<int>&& reference)
     150           2 :     : m_vector(std::forward<std::vector<int>>(reference))
     151           2 :   {}
     152             : 
     153           0 :   bool operator==(const Object& other) const
     154             :   {
     155           0 :     return m_vector == other.m_vector;
     156             :   }
     157             : 
     158             : private:
     159             :   std::vector<int> m_vector;
     160             : };
     161             : 
     162             : namespace std
     163             : {
     164             : 
     165             : template<>
     166             : struct hash<Object>
     167             : {
     168           1 :   std::size_t operator()(const Object& object) const
     169             :   {
     170           1 :     return reinterpret_cast<std::size_t>(&object);
     171             :   }
     172             : };
     173             : 
     174             : }
     175             : 
     176           2 : BOOST_AUTO_TEST_CASE(test_perfect_forwarding)
     177             : {
     178           1 :   unordered_set<Object> objects;
     179             : 
     180             :   // Move it into the unordered_set.
     181           1 :   std::vector<int> test;
     182           1 :   objects.emplace(std::move(test));
     183           1 : }
     184             : 
     185           2 : BOOST_AUTO_TEST_CASE(test_try_emplace)
     186             : {
     187           1 :   unordered_map<int, std::vector<int>> mapping;
     188             : 
     189             :   // Move it into the unordered_set.
     190           1 :   std::vector<int> test;
     191           1 :   mapping.try_emplace(5, 1000);
     192             : 
     193           1 :   BOOST_CHECK(mapping.try_emplace(5, 1000).second == false);
     194           1 : }
     195             : 
     196           2 : BOOST_AUTO_TEST_CASE(test_emplace)
     197             : {
     198           1 :   unordered_map<int, std::vector<int>> mapping;
     199             : 
     200             :   // Move it into the unordered_set.
     201           1 :   mapping.emplace(5, 1000);
     202             : 
     203           1 :   BOOST_CHECK(mapping.emplace(5, 1000).second == false);
     204           1 : }