Squashed 'third_party/boostorg/multi_index/' content from commit d95a949
Change-Id: Ie67c2d797c11dc122c7f11e767e81691bf2191a4
git-subtree-dir: third_party/boostorg/multi_index
git-subtree-split: d95a94942b918140e565feb99ed36ea97c30084e
diff --git a/example/rearrange.cpp b/example/rearrange.cpp
new file mode 100644
index 0000000..3138851
--- /dev/null
+++ b/example/rearrange.cpp
@@ -0,0 +1,265 @@
+/* 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;
+}