ceph/src/boost/libs/icl/example/large_bitset_/large_bitset.cpp

   1 /*-----------------------------------------------------------------------------+
   2 Author: Joachim Faulhaber
   3 Copyright (c) 2009-2009: Joachim Faulhaber
   4 +------------------------------------------------------------------------------+
   5    Distributed under the Boost Software License, Version 1.0.
   6       (See accompanying file LICENCE.txt or copy at
   7            http://www.boost.org/LICENSE_1_0.txt)
   8 +-----------------------------------------------------------------------------*/
   9 /** Example large_bitset.cpp \file large_bitset.cpp
  10     \brief Shows a bitset class that combines interval and bitset compression
  11            in order to represent very large bitsets efficiently.
  12
  13     Example large_bitset.cpp demonstrates the usage of a large_bitset class
  14     template that is implemented as an interval_map of bitsets. The idea is
  15     to combine interval compression and bitset compression. Large uninterrupted
  16     runs of bits are represented by intervals (interval compression). Local
  17     nests of varying bitsequences are represented by associated bitests
  18     (bitset compression).
  19
  20     Find a commented sample implementation in the boost book documentation
  21     <a href="http://www.joachim-faulhaber.de/boost_itl/doc/libs/icl/doc/html/boost_itl/projects.html#boost_itl.projects.large_bitset">
  22     here</a>.
  23
  24     \include large_bitset_/large_bitset.cpp
  25 */
  26 #if defined(_MSC_VER)
  27 #pragma warning(disable:4244) // Msvc warns on some operations that are needed
  28 #pragma warning(disable:4245) // in this example - we're working on bit level.
  29 #endif                        // So we intentionally disable them.
  30
  31 //[large_bitset_cpp_includes
  32 #include <limits>
  33 #include "large_bitset.hpp"
  34
  35 using namespace std;
  36 using namespace boost;
  37 using namespace boost::icl;
  38 using namespace mini;
  39 //]
  40
  41
  42 //[large_bitset_test_large_set_all
  43 void test_large()
  44 {
  45     const nat64 much = 0xffffffffffffffffull;
  46     large_bitset<> venti; // ... the largest, I can think of ;)
  47     venti += discrete_interval<nat64>(0, much);
  48
  49     cout << "----- Test function test_large() -----------------------------------------------\n";
  50     cout << "We have just turned on the awesome amount of 18,446,744,073,709,551,616 bits ;-)\n";
  51     venti.show_segments();
  52     //]
  53
  54     //[large_bitset_test_large_erase_last
  55     cout << "---- Let's swich off the very last bit -----------------------------------------\n";
  56     venti -= much;
  57     venti.show_segments();
  58
  59     cout << "---- Venti is plenty ... let's do something small: A tall ----------------------\n\n";
  60 }
  61 //]
  62
  63 //[large_bitset_test_small
  64 void test_small()
  65 {
  66     large_bitset<nat32, bits8> tall; // small is tall ...
  67         // ... because even this 'small' large_bitset
  68         // can represent up to 2^32 == 4,294,967,296 bits.
  69
  70     cout << "----- Test function test_small() -----------\n";
  71     cout << "-- Switch on all bits in range [0,64] ------\n";
  72     tall += discrete_interval<nat>(0, 64);
  73     tall.show_segments();
  74     cout << "--------------------------------------------\n";
  75
  76     cout << "-- Turn off bits: 25,27,28 -----------------\n";
  77
  78     (((tall -= 25) -= 27) -= 28) ;
  79     tall.show_segments();
  80     cout << "--------------------------------------------\n";
  81
  82     cout << "-- Flip bits in range [24,30) --------------\n";
  83     tall ^= discrete_interval<nat>::right_open(24,30);
  84     tall.show_segments();
  85     cout << "--------------------------------------------\n";
  86
  87     cout << "-- Remove the first 10 bits ----------------\n";
  88     tall -= discrete_interval<nat>::right_open(0,10);
  89     tall.show_segments();
  90
  91     cout << "-- Remove even bits in range [0,72) --------\n";
  92     int bit;
  93     for(bit=0; bit<72; bit++) if(!(bit%2)) tall -= bit;
  94     tall.show_segments();
  95
  96     cout << "--    Set odd  bits in range [0,72) --------\n";
  97     for(bit=0; bit<72; bit++) if(bit%2) tall += bit;
  98     tall.show_segments();
  99
 100     cout << "--------------------------------------------\n\n";
 101
 102 }
 103 //]
 104
 105 //[large_bitset_test_picturesque
 106 void test_picturesque()
 107 {
 108     typedef large_bitset<nat, bits8> Bit8Set;
 109
 110     Bit8Set square, stare;
 111     square += discrete_interval<nat>(0,8);
 112     for(int i=1; i<5; i++)
 113     {
 114         square += 8*i;
 115         square += 8*i+7;
 116     }
 117
 118     square += discrete_interval<nat>(41,47);
 119
 120     cout << "----- Test function test_picturesque() -----\n";
 121     cout << "-------- empty face:       "
 122          << square.interval_count()           << " intervals -----\n";
 123     square.show_matrix(" *");
 124
 125     stare += 18; stare += 21;
 126     stare += discrete_interval<nat>(34,38);
 127
 128     cout << "-------- compressed smile: "
 129          << stare.interval_count()            << " intervals -----\n";
 130     stare.show_matrix(" *");
 131
 132     cout << "-------- staring bitset:   "
 133          << (square + stare).interval_count() << " intervals -----\n";
 134     (square + stare).show_matrix(" *");
 135
 136     cout << "--------------------------------------------\n";
 137 }
 138 //]
 139
 140 template<class NatT, class BitsT>
 141 void test_set()
 142 {
 143     const NatT much = (numeric_limits<NatT>::max)();
 144
 145     large_bitset<NatT, BitsT> venti; //the largest, I can think of
 146     venti += discrete_interval<NatT>(0, much);
 147
 148     cout << "--------------------------------------------------------------------------------\n";
 149     venti.show_segments();
 150
 151     venti -= much;
 152     cout << "--------------------------------------------------------------------------------\n";
 153     venti.show_segments();
 154 }
 155
 156
 157
 158 int main()
 159 {
 160     cout << ">>Interval Container Library: Sample large_bitset.cpp <<\n";
 161     cout << "--------------------------------------------------------\n";
 162     test_large();
 163     test_small();
 164     test_picturesque();
 165     //test_set<nat64,bits64>();
 166     return 0;
 167 }
 168