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