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
test_large()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
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
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>
test_set()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
main()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
169