libs/multi_index/example/rearrange.cpp
/* Boost.MultiIndex example of use of rearrange facilities. * * Copyright 2003-2015 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) * * See http://www.boost.org/libs/multi_index for library home page. */ #if !defined(NDEBUG) #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE #endif #include <boost/config.hpp> #include <boost/detail/iterator.hpp> #include <boost/multi_index_container.hpp> #include <boost/multi_index/random_access_index.hpp> #include <boost/random/binomial_distribution.hpp> #include <boost/random/uniform_real.hpp> #include <boost/random/mersenne_twister.hpp> #include <algorithm> #include <iostream> #include <iterator> #include <vector> #if !defined(BOOST_NO_CXX11_HDR_RANDOM) #include <random> #endif using boost::multi_index_container; using namespace boost::multi_index; /* We model a card deck with a random access array containing * card numbers (from 0 to 51), supplemented with an additional * index which retains the start ordering. */ class deck { BOOST_STATIC_CONSTANT(std::size_t,num_cards=52); typedef multi_index_container< int, indexed_by< random_access<>, /* base index */ random_access<> /* "start" index */ > > container_type; container_type cont; public: deck() { cont.reserve(num_cards); get<1>(cont).reserve(num_cards); for(std::size_t i=0;i<num_cards;++i)cont.push_back(i); } typedef container_type::iterator iterator; typedef container_type::size_type size_type; iterator begin()const{return cont.begin();} iterator end()const{return cont.end();} size_type size()const{return cont.size();} template<typename InputIterator> void rearrange(InputIterator it) { cont.rearrange(it); } void reset() { /* simply rearrange the base index like the start index */ cont.rearrange(get<1>(cont).begin()); } std::size_t position(int i)const { /* The position of a card in the deck is calculated by locating * the card through the start index (which is ordered), projecting * to the base index and diffing with the begin position. * Resulting complexity: constant. */ return project<0>(cont,get<1>(cont).begin()+i)-cont.begin(); } std::size_t rising_sequences()const { /* Iterate through all cards and increment the sequence count * when the current position is left to the previous. * Resulting complexity: O(n), n=num_cards. */ std::size_t s=1; std::size_t last_pos=0; for(std::size_t i=0;i<num_cards;++i){ std::size_t pos=position(i); if(pos<last_pos)++s; last_pos=pos; } return s; } }; /* A vector of reference_wrappers to deck elements can be used * as a view to the deck container. * We use a special implicit_reference_wrapper having implicit * ctor from its base type, as this simplifies the use of generic * techniques on the resulting data structures. */ template<typename T> class implicit_reference_wrapper:public boost::reference_wrapper<T> { private: typedef boost::reference_wrapper<T> super; public: implicit_reference_wrapper(T& t):super(t){} }; typedef std::vector<implicit_reference_wrapper<const int> > deck_view; /* Riffle shuffle is modeled like this: A cut is selected in the deck * following a binomial distribution. Then, cards are randomly selected * from one packet or the other with probability proportional to * packet size. */ template<typename RandomAccessIterator,typename OutputIterator> void riffle_shuffle( RandomAccessIterator first,RandomAccessIterator last, OutputIterator out) { static boost::mt19937 rnd_gen; typedef typename boost::detail::iterator_traits< RandomAccessIterator>::difference_type difference_type; typedef boost::binomial_distribution< difference_type> rnd_cut_select_type; typedef boost::uniform_real<> rnd_deck_select_type; rnd_cut_select_type cut_select(last-first); RandomAccessIterator middle=first+cut_select(rnd_gen); difference_type s0=middle-first; difference_type s1=last-middle; rnd_deck_select_type deck_select; while(s0!=0&&s1!=0){ if(deck_select(rnd_gen)<(double)s0/(s0+s1)){ *out++=*first++; --s0; } else{ *out++=*middle++; --s1; } } std::copy(first,first+s0,out); std::copy(middle,middle+s1,out); } struct riffle_shuffler { void operator()(deck& d)const { dv.clear(); dv.reserve(d.size()); riffle_shuffle( d.begin(),d.end(),std::back_inserter(dv)); /* do the shuffling */ d.rearrange(dv.begin()); /* apply to the deck */ } private: mutable deck_view dv; }; /* A truly random shuffle (up to stdlib implementation quality) using * std::shuffle. */ struct random_shuffler { void operator()(deck& d) { dv.clear(); dv.reserve(d.size()); std::copy(d.begin(),d.end(),std::back_inserter(dv)); shuffle_view(); d.rearrange(dv.begin()); /* apply to the deck */ } private: deck_view dv; #if !defined(BOOST_NO_CXX11_HDR_RANDOM) std::mt19937 e; void shuffle_view() { std::shuffle(dv.begin(),dv.end(),e); } #else /* for pre-C++11 compilers we use std::random_shuffle */ void shuffle_view() { std::random_shuffle(dv.begin(),dv.end()); } #endif }; /* Repeat a given shuffling algorithm repeats_num times * and obtain the resulting rising sequences number. Average * for tests_num trials. */ template<typename Shuffler> double shuffle_test( unsigned int repeats_num,unsigned int tests_num BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Shuffler)) { deck d; Shuffler sh; unsigned long total=0; for(unsigned int n=0;n<tests_num;++n){ for(unsigned m=0;m<repeats_num;++m)sh(d); total+=d.rising_sequences(); d.reset(); } return (double)total/tests_num; } int main() { unsigned rifs_num=0; unsigned tests_num=0; std::cout<<"number of riffle shuffles (vg 5):"; std::cin>>rifs_num; std::cout<<"number of tests (vg 1000):"; std::cin>>tests_num; std::cout<<"shuffling..."<<std::endl; std::cout<<"riffle shuffling\n" " avg number of rising sequences: " <<shuffle_test<riffle_shuffler>(rifs_num,tests_num) <<std::endl; std::cout<<"random shuffling\n" " avg number of rising sequences: " <<shuffle_test<random_shuffler>(1,tests_num) <<std::endl; return 0; }