1 2 // Copyright 2006-2009 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 // This header contains metafunctions/functions to get the equivalent 7 // associative container for an unordered container, and compare the contents. 8 9 #if !defined(BOOST_UNORDERED_TEST_HELPERS_TRACKER_HEADER) 10 #define BOOST_UNORDERED_TEST_HELPERS_TRACKER_HEADER 11 12 #include "../objects/fwd.hpp" 13 #include "./equivalent.hpp" 14 #include "./helpers.hpp" 15 #include "./list.hpp" 16 #include "./metafunctions.hpp" 17 #include <algorithm> 18 #include <iterator> 19 #include <map> 20 #include <set> 21 22 namespace test { 23 template <typename X> struct equals_to_compare 24 { 25 typedef std::less<typename X::first_argument_type> type; 26 }; 27 28 template <> struct equals_to_compare<test::equal_to> 29 { 30 typedef test::less type; 31 }; 32 compare_range(X1 const & x1,X2 const & x2)33 template <class X1, class X2> void compare_range(X1 const& x1, X2 const& x2) 34 { 35 typedef test::list<typename X1::value_type> value_list; 36 value_list values1(x1.begin(), x1.end()); 37 value_list values2(x2.begin(), x2.end()); 38 values1.sort(); 39 values2.sort(); 40 BOOST_TEST(values1.size() == values2.size() && 41 test::equal(values1.begin(), values1.end(), values2.begin(), 42 test::equivalent)); 43 } 44 45 template <class X1, class X2, class T> compare_pairs(X1 const & x1,X2 const & x2,T *)46 void compare_pairs(X1 const& x1, X2 const& x2, T*) 47 { 48 test::list<T> values1(x1.first, x1.second); 49 test::list<T> values2(x2.first, x2.second); 50 values1.sort(); 51 values2.sort(); 52 BOOST_TEST(values1.size() == values2.size() && 53 test::equal(values1.begin(), values1.end(), values2.begin(), 54 test::equivalent)); 55 } 56 57 template <typename X, bool is_set = test::is_set<X>::value, 58 bool has_unique_keys = test::has_unique_keys<X>::value> 59 struct ordered_base; 60 61 template <typename X> struct ordered_base<X, true, true> 62 { 63 typedef std::set<typename X::value_type, 64 typename equals_to_compare<typename X::key_equal>::type> 65 type; 66 }; 67 68 template <typename X> struct ordered_base<X, true, false> 69 { 70 typedef std::multiset<typename X::value_type, 71 typename equals_to_compare<typename X::key_equal>::type> 72 type; 73 }; 74 75 template <typename X> struct ordered_base<X, false, true> 76 { 77 typedef std::map<typename X::key_type, typename X::mapped_type, 78 typename equals_to_compare<typename X::key_equal>::type> 79 type; 80 }; 81 82 template <typename X> struct ordered_base<X, false, false> 83 { 84 typedef std::multimap<typename X::key_type, typename X::mapped_type, 85 typename equals_to_compare<typename X::key_equal>::type> 86 type; 87 }; 88 89 template <class X> class ordered : public ordered_base<X>::type 90 { 91 typedef typename ordered_base<X>::type base; 92 93 public: 94 typedef typename base::key_compare key_compare; 95 ordered()96 ordered() : base() {} 97 ordered(key_compare const & kc)98 explicit ordered(key_compare const& kc) : base(kc) {} 99 compare(X const & x)100 void compare(X const& x) { compare_range(x, *this); } 101 compare_key(X const & x,typename X::value_type const & val)102 void compare_key(X const& x, typename X::value_type const& val) 103 { 104 compare_pairs(x.equal_range(get_key<X>(val)), 105 this->equal_range(get_key<X>(val)), (typename X::value_type*)0); 106 } 107 insert_range(It b,It e)108 template <class It> void insert_range(It b, It e) 109 { 110 while (b != e) { 111 this->insert(*b); 112 ++b; 113 } 114 } 115 }; 116 117 template <class Equals> create_compare(Equals const &)118 typename equals_to_compare<Equals>::type create_compare(Equals const&) 119 { 120 typename equals_to_compare<Equals>::type x; 121 return x; 122 } 123 create_ordered(X const & container)124 template <class X> ordered<X> create_ordered(X const& container) 125 { 126 return ordered<X>(create_compare(container.key_eq())); 127 } 128 129 template <class X1, class X2> check_container(X1 const & container,X2 const & values)130 void check_container(X1 const& container, X2 const& values) 131 { 132 ordered<X1> tracker = create_ordered(container); 133 tracker.insert_range(values.begin(), values.end()); 134 tracker.compare(container); 135 } 136 } 137 138 #endif 139