1/* Boost.MultiIndex example of use of rearrange facilities.
2 *
3 * Copyright 2003-2020 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#if !defined(NDEBUG)
12#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
13#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
14#endif
15
16#include <boost/config.hpp>
17#include <boost/multi_index_container.hpp>
18#include <boost/multi_index/random_access_index.hpp>
19#include <boost/random/binomial_distribution.hpp>
20#include <boost/random/uniform_real.hpp>
21#include <boost/random/mersenne_twister.hpp>
22#include <algorithm>
23#include <iostream>
24#include <iterator>
25#include <vector>
26
27#if !defined(BOOST_NO_CXX11_HDR_RANDOM)
28#include <random>
29#endif
30
31using boost::multi_index_container;
32using namespace boost::multi_index;
33
34/* We model a card deck with a random access array containing
35 * card numbers (from 0 to 51), supplemented with an additional
36 * index which retains the start ordering.
37 */
38
39class deck
40{
41 BOOST_STATIC_CONSTANT(std::size_t,num_cards=52);
42
43 typedef multi_index_container<
44 int,
45 indexed_by<
46 random_access<>, /* base index */
47 random_access<> /* "start" index */
48 >
49 > container_type;
50 container_type cont;
51
52public:
53 deck()
54 {
55 cont.reserve(n: num_cards);
56 get<1>(m&: cont).reserve(n: num_cards);
57 for(std::size_t i=0;i<num_cards;++i)cont.push_back(x: i);
58 }
59
60 typedef container_type::iterator iterator;
61 typedef container_type::size_type size_type;
62
63 iterator begin()const{return cont.begin();}
64 iterator end()const{return cont.end();}
65 size_type size()const{return cont.size();}
66
67 template<typename InputIterator>
68 void rearrange(InputIterator it)
69 {
70 cont.rearrange(it);
71 }
72
73 void reset()
74 {
75 /* simply rearrange the base index like the start index */
76
77 cont.rearrange(first: get<1>(m&: cont).begin());
78 }
79
80 std::size_t position(int i)const
81 {
82 /* The position of a card in the deck is calculated by locating
83 * the card through the start index (which is ordered), projecting
84 * to the base index and diffing with the begin position.
85 * Resulting complexity: constant.
86 */
87
88 return project<0>(m: cont,it: get<1>(m: cont).begin()+i)-cont.begin();
89 }
90
91 std::size_t rising_sequences()const
92 {
93 /* Iterate through all cards and increment the sequence count
94 * when the current position is left to the previous.
95 * Resulting complexity: O(n), n=num_cards.
96 */
97
98 std::size_t s=1;
99 std::size_t last_pos=0;
100
101 for(std::size_t i=0;i<num_cards;++i){
102 std::size_t pos=position(i);
103 if(pos<last_pos)++s;
104 last_pos=pos;
105 }
106
107 return s;
108 }
109};
110
111/* A vector of reference_wrappers to deck elements can be used
112 * as a view to the deck container.
113 * We use a special implicit_reference_wrapper having implicit
114 * ctor from its base type, as this simplifies the use of generic
115 * techniques on the resulting data structures.
116 */
117
118template<typename T>
119class implicit_reference_wrapper:public boost::reference_wrapper<T>
120{
121private:
122 typedef boost::reference_wrapper<T> super;
123public:
124 implicit_reference_wrapper(T& t):super(t){}
125};
126
127typedef std::vector<implicit_reference_wrapper<const int> > deck_view;
128
129/* Riffle shuffle is modeled like this: A cut is selected in the deck
130 * following a binomial distribution. Then, cards are randomly selected
131 * from one packet or the other with probability proportional to
132 * packet size.
133 */
134
135template<typename RandomAccessIterator,typename OutputIterator>
136void riffle_shuffle(
137 RandomAccessIterator first,RandomAccessIterator last,
138 OutputIterator out)
139{
140 static boost::mt19937 rnd_gen;
141
142 typedef typename std::iterator_traits<
143 RandomAccessIterator>::difference_type difference_type;
144 typedef boost::binomial_distribution<
145 difference_type> rnd_cut_select_type;
146 typedef boost::uniform_real<> rnd_deck_select_type;
147
148 rnd_cut_select_type cut_select(last-first);
149 RandomAccessIterator middle=first+cut_select(rnd_gen);
150 difference_type s0=middle-first;
151 difference_type s1=last-middle;
152 rnd_deck_select_type deck_select;
153
154 while(s0!=0&&s1!=0){
155 if(deck_select(rnd_gen)<(double)s0/(s0+s1)){
156 *out++=*first++;
157 --s0;
158 }
159 else{
160 *out++=*middle++;
161 --s1;
162 }
163 }
164 std::copy(first,first+s0,out);
165 std::copy(middle,middle+s1,out);
166}
167
168struct riffle_shuffler
169{
170 void operator()(deck& d)const
171 {
172 dv.clear();
173 dv.reserve(n: d.size());
174 riffle_shuffle(
175 first: d.begin(),last: d.end(),out: std::back_inserter(x&: dv)); /* do the shuffling */
176 d.rearrange(it: dv.begin()); /* apply to the deck */
177 }
178
179private:
180 mutable deck_view dv;
181};
182
183/* A truly random shuffle (up to stdlib implementation quality) using
184 * std::shuffle.
185 */
186
187struct random_shuffler
188{
189 void operator()(deck& d)
190 {
191 dv.clear();
192 dv.reserve(n: d.size());
193 std::copy(first: d.begin(),last: d.end(),result: std::back_inserter(x&: dv));
194 shuffle_view();
195 d.rearrange(it: dv.begin()); /* apply to the deck */
196 }
197
198private:
199 deck_view dv;
200
201#if !defined(BOOST_NO_CXX11_HDR_RANDOM)
202 std::mt19937 e;
203
204 void shuffle_view()
205 {
206 std::shuffle(first: dv.begin(),last: dv.end(),g&: e);
207 }
208#else
209 /* for pre-C++11 compilers we use std::random_shuffle */
210
211 void shuffle_view()
212 {
213 std::random_shuffle(dv.begin(),dv.end());
214 }
215#endif
216};
217
218/* Repeat a given shuffling algorithm repeats_num times
219 * and obtain the resulting rising sequences number. Average
220 * for tests_num trials.
221 */
222
223template<typename Shuffler>
224double shuffle_test(
225 unsigned int repeats_num,unsigned int tests_num
226 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Shuffler))
227{
228 deck d;
229 Shuffler sh;
230 unsigned long total=0;
231
232 for(unsigned int n=0;n<tests_num;++n){
233 for(unsigned m=0;m<repeats_num;++m)sh(d);
234 total+=d.rising_sequences();
235 d.reset();
236 }
237
238 return (double)total/tests_num;
239}
240
241int main()
242{
243 unsigned rifs_num=0;
244 unsigned tests_num=0;
245
246 std::cout<<"number of riffle shuffles (vg 5):";
247 std::cin>>rifs_num;
248 std::cout<<"number of tests (vg 1000):";
249 std::cin>>tests_num;
250
251 std::cout<<"shuffling..."<<std::endl;
252
253 std::cout<<"riffle shuffling\n"
254 " avg number of rising sequences: "
255 <<shuffle_test<riffle_shuffler>(repeats_num: rifs_num,tests_num)
256 <<std::endl;
257
258 std::cout<<"random shuffling\n"
259 " avg number of rising sequences: "
260 <<shuffle_test<random_shuffler>(repeats_num: 1,tests_num)
261 <<std::endl;
262
263 return 0;
264}
265

source code of boost/libs/multi_index/example/rearrange.cpp