1 /* Boost.MultiIndex test for rank operations.
2 *
3 * Copyright 2003-2017 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/multi_index for library home page.
9 */
10
11 #include "test_rank_ops.hpp"
12
13 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
14 #include <algorithm>
15 #include <iterator>
16 #include <set>
17 #include <boost/detail/lightweight_test.hpp>
18 #include "pre_multi_index.hpp"
19 #include <boost/multi_index_container.hpp>
20 #include <boost/multi_index/identity.hpp>
21 #include <boost/multi_index/ranked_index.hpp>
22
23 using namespace boost::multi_index;
24
25 template<
26 typename Sequence1,typename Iterator2,typename Sequence2
27 >
same_position(std::size_t n1,const Sequence1 & s1,Iterator2 it2,const Sequence2 & s2)28 bool same_position(
29 std::size_t n1,const Sequence1& s1,Iterator2 it2,const Sequence2& s2)
30 {
31 typedef typename Sequence1::const_iterator const_iterator1;
32 typedef typename Sequence2::const_iterator const_iterator2;
33
34 const_iterator1 cit1=s1.begin();
35 std::advance(cit1,n1);
36 const_iterator2 cit2=it2;
37 return std::distance(s1.begin(),cit1)==std::distance(s2.begin(),cit2);
38 }
39
40 struct less_equal_than
41 {
less_equal_thanless_equal_than42 less_equal_than(int n_):n(n_){}
operator ()less_equal_than43 bool operator()(int x)const{return x<=n;}
44 int n;
45 };
46
47 struct greater_equal_than
48 {
greater_equal_thangreater_equal_than49 greater_equal_than(int n_):n(n_){}
operator ()greater_equal_than50 bool operator()(int x)const{return x>=n;}
51 int n;
52 };
53
54 template<typename Sequence>
local_test_rank_ops()55 static void local_test_rank_ops()
56 {
57 int data[]={2,2,1,5,6,7,9,10,9,6,9,6,9};
58 Sequence s(data,data+sizeof(data)/sizeof(data[0]));
59 std::multiset<int> ss(s.begin(),s.end());
60
61 typedef typename Sequence::iterator iterator;
62
63 iterator it=s.begin();
64 for(std::size_t n=0;n<=s.size()+1;++n){
65 BOOST_TEST(s.nth(n)==it);
66 BOOST_TEST(s.rank(it)==(std::min)(s.size(),n));
67 if(it!=s.end())++it;
68 }
69
70 std::pair<std::size_t,std::size_t> p1;
71 std::pair<iterator,iterator> p2;
72
73 p1=s.range_rank(unbounded,unbounded);
74 p2=s.range(unbounded,unbounded);
75 BOOST_TEST(same_position(p1.first,s,p2.first,s));
76 BOOST_TEST(same_position(p1.second,s,p2.second,s));
77
78 for(int i=0;i<12;++i){
79 std::size_t pos=s.find_rank(i);
80 BOOST_TEST((pos==s.size()&&ss.find(i)==ss.end())||(*s.nth(pos)==i));
81 BOOST_TEST(same_position(s.lower_bound_rank(i),s,ss.lower_bound(i),ss));
82 BOOST_TEST(same_position(s.upper_bound_rank(i),s,ss.upper_bound(i),ss));
83 std::pair<std::size_t,std::size_t> posp=s.equal_range_rank(i);
84 BOOST_TEST(same_position(posp.first,s,ss.lower_bound(i),ss));
85 BOOST_TEST(same_position(posp.second,s,ss.upper_bound(i),ss));
86
87 p1=s.range_rank(greater_equal_than(i),unbounded);
88 p2=s.range(greater_equal_than(i),unbounded);
89 BOOST_TEST(same_position(p1.first,s,p2.first,s));
90 BOOST_TEST(same_position(p1.second,s,p2.second,s));
91 p1=s.range_rank(unbounded,less_equal_than(i));
92 p2=s.range(unbounded,less_equal_than(i));
93 BOOST_TEST(same_position(p1.first,s,p2.first,s));
94 BOOST_TEST(same_position(p1.second,s,p2.second,s));
95
96 for(int j=0;j<12;++j){
97 p1=s.range_rank(greater_equal_than(i),less_equal_than(j));
98 p2=s.range(greater_equal_than(i),less_equal_than(j));
99 BOOST_TEST(same_position(p1.first,s,p2.first,s));
100 BOOST_TEST(same_position(p1.second,s,p2.second,s));
101 }
102 }
103
104 Sequence se; /* empty */
105 BOOST_TEST(se.nth(0)==se.end());
106 BOOST_TEST(se.nth(1)==se.end());
107 BOOST_TEST(se.rank(se.end())==0);
108 BOOST_TEST(se.find_rank(0)==0);
109 BOOST_TEST(se.lower_bound_rank(0)==0);
110 BOOST_TEST(se.upper_bound_rank(0)==0);
111 p1=se.equal_range_rank(0);
112 BOOST_TEST(p1.first==0&&p1.second==0);
113 p1=se.range_rank(unbounded,unbounded);
114 BOOST_TEST(p1.first==0&&p1.second==0);
115 p1=se.range_rank(greater_equal_than(0),unbounded);
116 BOOST_TEST(p1.first==0&&p1.second==0);
117 p1=se.range_rank(unbounded,less_equal_than(0));
118 BOOST_TEST(p1.first==0&&p1.second==0);
119 p1=se.range_rank(greater_equal_than(0),less_equal_than(0));
120 BOOST_TEST(p1.first==0&&p1.second==0);
121 }
122
test_rank_ops()123 void test_rank_ops()
124 {
125 typedef multi_index_container<
126 int,
127 indexed_by<
128 ranked_unique<identity<int> >
129 >
130 > ranked_set;
131
132 local_test_rank_ops<ranked_set>();
133
134 typedef multi_index_container<
135 int,
136 indexed_by<
137 ranked_non_unique<identity<int> >
138 >
139 > ranked_multiset;
140
141 local_test_rank_ops<ranked_multiset>();
142
143 /* testcase for https://svn.boost.org/trac/boost/ticket/12955 */
144
145 typedef multi_index_container<
146 int,
147 indexed_by<
148 ranked_unique<identity<int> >,
149 ranked_non_unique<identity<int> >
150 >
151 > biranked_set;
152
153 local_test_rank_ops<biranked_set>();
154 }
155