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 <set>
13 #include <map>
14 #include <iterator>
15 #include <algorithm>
16 #include <boost/type_traits/is_same.hpp>
17 #include "../objects/fwd.hpp"
18 #include "./metafunctions.hpp"
19 #include "./helpers.hpp"
20 #include "./equivalent.hpp"
21 #include "./list.hpp"
22 
23 namespace test
24 {
25     template <typename X>
26     struct equals_to_compare
27     {
28         typedef std::less<BOOST_DEDUCED_TYPENAME X::first_argument_type>
29             type;
30     };
31 
32     template <>
33     struct equals_to_compare<test::equal_to>
34     {
35         typedef test::less type;
36     };
37 
38     template <class X1, class X2>
compare_range(X1 const & x1,X2 const & x2)39     void compare_range(X1 const& x1, X2 const& x2)
40     {
41         typedef test::list<BOOST_DEDUCED_TYPENAME X1::value_type> value_list;
42         value_list values1(x1.begin(), x1.end());
43         value_list values2(x2.begin(), x2.end());
44         values1.sort();
45         values2.sort();
46         BOOST_TEST(values1.size() == values2.size() &&
47                 test::equal(values1.begin(), values1.end(), values2.begin(),
48                     test::equivalent));
49     }
50 
51     template <class X1, class X2, class T>
compare_pairs(X1 const & x1,X2 const & x2,T *)52     void compare_pairs(X1 const& x1, X2 const& x2, T*)
53     {
54         test::list<T> values1(x1.first, x1.second);
55         test::list<T> values2(x2.first, x2.second);
56         values1.sort();
57         values2.sort();
58         BOOST_TEST(values1.size() == values2.size() &&
59                 test::equal(values1.begin(), values1.end(),
60                     values2.begin(), test::equivalent));
61     }
62 
63     template <typename X>
64     struct ordered_base;
65 
66     template <class V, class H, class P, class A>
67     struct ordered_base<boost::unordered_set<V, H, P, A> >
68     {
69         typedef std::set<V,
70             BOOST_DEDUCED_TYPENAME equals_to_compare<P>::type>
71             type;
72     };
73 
74     template <class V, class H, class P, class A>
75     struct ordered_base<boost::unordered_multiset<V, H, P, A> >
76     {
77         typedef std::multiset<V,
78             BOOST_DEDUCED_TYPENAME equals_to_compare<P>::type>
79             type;
80     };
81 
82     template <class K, class M, class H, class P, class A>
83     struct ordered_base<boost::unordered_map<K, M, H, P, A> >
84     {
85         typedef std::map<K, M,
86             BOOST_DEDUCED_TYPENAME equals_to_compare<P>::type>
87             type;
88     };
89 
90     template <class K, class M, class H, class P, class A>
91     struct ordered_base<boost::unordered_multimap<K, M, H, P, A> >
92     {
93         typedef std::multimap<K, M,
94             BOOST_DEDUCED_TYPENAME equals_to_compare<P>::type>
95             type;
96     };
97 
98     template <class X>
99     class ordered : public ordered_base<X>::type
100     {
101         typedef BOOST_DEDUCED_TYPENAME ordered_base<X>::type base;
102     public:
103         typedef BOOST_DEDUCED_TYPENAME base::key_compare key_compare;
104 
ordered()105         ordered()
106             : base()
107         {}
108 
ordered(key_compare const & kc)109         explicit ordered(key_compare const& kc)
110             : base(kc)
111         {}
112 
compare(X const & x)113         void compare(X const& x)
114         {
115             compare_range(x, *this);
116         }
117 
compare_key(X const & x,BOOST_DEDUCED_TYPENAME X::value_type const & val)118         void compare_key(X const& x,
119             BOOST_DEDUCED_TYPENAME X::value_type const& val)
120         {
121             compare_pairs(
122                 x.equal_range(get_key<X>(val)),
123                 this->equal_range(get_key<X>(val)),
124                 (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
125         }
126 
127         template <class It>
insert_range(It b,It e)128         void insert_range(It b, It e) {
129             while(b != e) {
130                 this->insert(*b);
131                 ++b;
132             }
133         }
134     };
135 
136     template <class Equals>
137     BOOST_DEDUCED_TYPENAME
create_compare(Equals const &)138         equals_to_compare<Equals>::type create_compare(Equals const&)
139     {
140         BOOST_DEDUCED_TYPENAME equals_to_compare<Equals>::type x;
141         return x;
142     }
143 
144     template <class X>
create_ordered(X const & container)145     ordered<X> create_ordered(X const& container)
146     {
147         return ordered<X>(create_compare(container.key_eq()));
148     }
149 
150     template <class X1, class X2>
check_container(X1 const & container,X2 const & values)151     void check_container(X1 const& container, X2 const& values)
152     {
153         ordered<X1> tracker = create_ordered(container);
154         tracker.insert_range(values.begin(), values.end());
155         tracker.compare(container);
156     }
157 }
158 
159 #endif
160 
161