libs/unordered/test/unordered/extract_tests.cpp

   1
   2 // Copyright 2016 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_map.hpp>
   9 #include <boost/unordered_set.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include "../helpers/equivalent.hpp"
  14 #include "../helpers/helpers.hpp"
  15 #include "../helpers/invariants.hpp"
  16 #include "../helpers/random_values.hpp"
  17 #include "../helpers/test.hpp"
  18 #include "../helpers/tracker.hpp"
  19 #include "../objects/test.hpp"
  20 #include <boost/next_prior.hpp>
  21
  22 #include <iostream>
  23
  24 namespace extract_tests {
  25
  26 test::seed_t initialize_seed(85638);
  27
  28 template <class Container>
  29 void extract_tests1(Container*, test::random_generator generator)
  30 {
  31     std::cerr << "Extract by key.\n";
  32     {
  33         test::check_instances check_;
  34
  35         test::random_values<Container> v(1000, generator);
  36         Container x(v.begin(), v.end());
  37         int iterations = 0;
  38         for (BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator
  39                  it = v.begin();
  40              it != v.end(); ++it) {
  41             std::size_t count = x.count(test::get_key<Container>(*it));
  42             std::size_t old_size = x.size();
  43             std::size_t new_count = count ? count - 1 : count;
  44             std::size_t new_size = count ? old_size - 1 : old_size;
  45             typename Container::node_type n =
  46                 x.extract(test::get_key<Container>(*it));
  47             BOOST_TEST((n ? true : false) == (count ? true : false));
  48             BOOST_TEST(x.size() == new_size);
  49             BOOST_TEST(x.count(test::get_key<Container>(*it)) == new_count);
  50             if (!new_count) {
  51                 BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
  52             } else {
  53                 BOOST_TEST(x.find(test::get_key<Container>(*it)) != x.end());
  54             }
  55             if (++iterations % 20 == 0)
  56                 test::check_equivalent_keys(x);
  57         }
  58         BOOST_TEST(x.empty());
  59     }
  60
  61     std::cerr << "extract(begin()).\n";
  62     {
  63         test::check_instances check_;
  64
  65         test::random_values<Container> v(1000, generator);
  66         Container x(v.begin(), v.end());
  67         std::size_t size = x.size();
  68         int iterations = 0;
  69         while (size > 0 && !x.empty()) {
  70             BOOST_DEDUCED_TYPENAME Container::key_type key =
  71                 test::get_key<Container>(*x.begin());
  72             std::size_t count = x.count(key);
  73             typename Container::node_type n = x.extract(x.begin());
  74             BOOST_TEST(n);
  75             --size;
  76             BOOST_TEST(x.count(key) == count - 1);
  77             BOOST_TEST(x.size() == size);
  78             if (++iterations % 20 == 0)
  79                 test::check_equivalent_keys(x);
  80         }
  81         BOOST_TEST(x.empty());
  82     }
  83
  84     std::cerr << "extract(random position).\n";
  85     {
  86         test::check_instances check_;
  87
  88         test::random_values<Container> v(1000, generator);
  89         Container x(v.begin(), v.end());
  90         std::size_t size = x.size();
  91         int iterations = 0;
  92         while (size > 0 && !x.empty()) {
  93             using namespace std;
  94             int index = rand() % (int)x.size();
  95             BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
  96             if (index == 0) {
  97                 prev = pos = x.begin();
  98             } else {
  99                 prev = boost::next(x.begin(), index - 1);
 100                 pos = boost::next(prev);
 101             }
 102             next = boost::next(pos);
 103             BOOST_DEDUCED_TYPENAME Container::key_type key =
 104                 test::get_key<Container>(*pos);
 105             std::size_t count = x.count(key);
 106             typename Container::node_type n = x.extract(pos);
 107             BOOST_TEST(n);
 108             --size;
 109             if (size > 0)
 110                 BOOST_TEST(
 111                     index == 0 ? next == x.begin() : next == boost::next(prev));
 112             BOOST_TEST(x.count(key) == count - 1);
 113             BOOST_TEST(x.size() == size);
 114             if (++iterations % 20 == 0)
 115                 test::check_equivalent_keys(x);
 116         }
 117         BOOST_TEST(x.empty());
 118     }
 119
 120     std::cerr << "\n";
 121 }
 122
 123 boost::unordered_set<test::object, test::hash, test::equal_to,
 124     test::allocator1<test::object> >* test_set;
 125 boost::unordered_multiset<test::object, test::hash, test::equal_to,
 126     test::allocator2<test::object> >* test_multiset;
 127 boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 128     test::allocator1<test::object> >* test_map;
 129 boost::unordered_multimap<test::object, test::object, test::hash,
 130     test::equal_to, test::allocator2<test::object> >* test_multimap;
 131
 132 using test::default_generator;
 133 using test::generate_collisions;
 134
 135 UNORDERED_TEST(
 136     extract_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
 137                         (default_generator)(generate_collisions)))
 138 }
 139
 140 RUN_TESTS()