libs/multi_index/test/test_rank_ops.cpp

   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 }