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 | > |
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 | { |
42 | less_equal_than(int n_):n(n_){} |
43 | bool operator()(int x)const{return x<=n;} |
44 | int n; |
45 | }; |
46 | |
47 | struct greater_equal_than |
48 | { |
49 | greater_equal_than(int n_):n(n_){} |
50 | bool operator()(int x)const{return x>=n;} |
51 | int n; |
52 | }; |
53 | |
54 | template<typename Sequence> |
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 | |
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 | |