projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <html> |
| 2 | <head> | |
| 3 | <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> | |
| 4 | <title>Projects</title> | |
| 5 | <link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css"> | |
| 6 | <meta name="generator" content="DocBook XSL Stylesheets V1.74.0"> | |
| 7 | <link rel="home" href="../index.html" title="Chapter 1. Boost.Icl"> | |
| 8 | <link rel="up" href="../index.html" title="Chapter 1. Boost.Icl"> | |
| 9 | <link rel="prev" href="examples/custom_interval.html" title="Custom interval"> | |
| 10 | <link rel="next" href="concepts.html" title="Concepts"> | |
| 11 | </head> | |
| 12 | <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> | |
| 13 | <table cellpadding="2" width="100%"><tr> | |
| 14 | <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td> | |
| 15 | <td align="center"><a href="../../../../../index.html">Home</a></td> | |
| 16 | <td align="center"><a href="../../../../libraries.htm">Libraries</a></td> | |
| 17 | <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> | |
| 18 | <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> | |
| 19 | <td align="center"><a href="../../../../../more/index.htm">More</a></td> | |
| 20 | </tr></table> | |
| 21 | <hr> | |
| 22 | <div class="spirit-nav"> | |
| 23 | <a accesskey="p" href="examples/custom_interval.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concepts.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> | |
| 24 | </div> | |
| 25 | <div class="section boost_icl_projects" lang="en"> | |
| 26 | <div class="titlepage"><div><div><h2 class="title" style="clear: both"> | |
| 27 | <a name="boost_icl.projects"></a><a class="link" href="projects.html" title="Projects">Projects</a> | |
| 28 | </h2></div></div></div> | |
| 29 | <div class="toc"><dl><dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset">Large Bitset</a></span></dt></dl></div> | |
| 30 | <p> | |
| 31 | <span class="emphasis"><em><span class="bold"><strong>Projects</strong></span></em></span> are examples | |
| 32 | on the usage of interval containers that go beyond small toy snippets of code. | |
| 33 | The code presented here addresses more serious applications that approach the | |
| 34 | quality of real world programming. At the same time it aims to guide the reader | |
| 35 | more deeply into various aspects of the library. In order not to overburden | |
| 36 | the reader with implementation details, the code in <span class="emphasis"><em><span class="bold"><strong>projects</strong></span></em></span> | |
| 37 | tries to be <span class="emphasis"><em><span class="bold"><strong>minimal</strong></span></em></span>. | |
| 38 | It has a focus on the main aspects of the projects and is not intended to be | |
| 39 | complete and mature like the library code itself. Cause it's minimal, project | |
| 40 | code lives in <code class="computeroutput"><span class="keyword">namespace</span> <span class="identifier">mini</span></code>. | |
| 41 | </p> | |
| 42 | <div class="section boost_icl_projects_large_bitset" lang="en"> | |
| 43 | <div class="titlepage"><div><div><h3 class="title"> | |
| 44 | <a name="boost_icl.projects.large_bitset"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset" title="Large Bitset">Large Bitset</a> | |
| 45 | </h3></div></div></div> | |
| 46 | <div class="toc"><dl> | |
| 47 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.using_large_bitset">Using | |
| 48 | large_bitset</a></span></dt> | |
| 49 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.the_interval_bitmap">The | |
| 50 | interval_bitmap</a></span></dt> | |
| 51 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.a_class_implementation_for_the_bitset_type">A | |
| 52 | class implementation for the bitset type</a></span></dt> | |
| 53 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset">Implementation | |
| 54 | of a large bitset</a></span></dt> | |
| 55 | </dl></div> | |
| 56 | <p> | |
| 57 | Bitsets are just sets. Sets of unsigned integrals, to be more precise. The | |
| 58 | prefix <span class="emphasis"><em><span class="bold"><strong>bit</strong></span></em></span> usually | |
| 59 | only indicates, that the representation of those sets is organized in a compressed | |
| 60 | form that exploits the fact, that we can switch on an off single bits in | |
| 61 | machine words. Bitsets are therefore known to be very small and thus efficient. | |
| 62 | The efficiency of bitsets is usually coupled to the precondition that the | |
| 63 | range of values of elements is relatively small, like [0..32) or [0..64), | |
| 64 | values that can be typically represented in single or a small number of machine | |
| 65 | words. If we wanted to represent a set containing two values {1, 1000000}, | |
| 66 | we would be much better off using other sets like e.g. an <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code>. | |
| 67 | </p> | |
| 68 | <p> | |
| 69 | Bitsets compress well, if elements spread over narrow ranges only. Interval | |
| 70 | sets compress well, if many elements are clustered over intervals. They can | |
| 71 | span large sets very efficiently then. In project <span class="emphasis"><em><span class="bold"><strong>Large | |
| 72 | Bitset</strong></span></em></span> we want to <span class="emphasis"><em><span class="bold"><strong>combine | |
| 73 | the bit compression and the interval compression</strong></span></em></span> to | |
| 74 | achieve a set implementation, that is capable of spanning large chunks of | |
| 75 | contiguous elements using intervals and also to represent more narrow <span class="emphasis"><em>nests</em></span> | |
| 76 | of varying bit sequences using bitset compression. As we will see, this can | |
| 77 | be achieved using only a small amount of code because most of the properties | |
| 78 | we need are provided by an <code class="computeroutput"><a class="link" href="../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
| 79 | of <code class="computeroutput"><span class="identifier">bitsets</span></code>: | |
| 80 | </p> | |
| 81 | <p> | |
| 82 | ||
| 83 | </p> | |
| 84 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">interval_map</span><span class="special"><</span><span class="identifier">IntegralT</span><span class="special">,</span> <span class="identifier">SomeBitSet</span><span class="special"><</span><span class="identifier">N</span><span class="special">>,</span> <span class="identifier">partial_absorber</span><span class="special">,</span> | |
| 85 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special">,</span> <span class="identifier">inplace_bit_add</span><span class="special">,</span> <span class="identifier">inplace_bit_and</span><span class="special">></span> <span class="identifier">IntervalBitmap</span><span class="special">;</span> | |
| 86 | </pre> | |
| 87 | <p> | |
| 88 | </p> | |
| 89 | <p> | |
| 90 | Such an <code class="computeroutput"><span class="identifier">IntervalBitmap</span></code> represents | |
| 91 | <code class="computeroutput"><span class="identifier">k</span><span class="special">*</span><span class="identifier">N</span></code> bits for every segment. | |
| 92 | </p> | |
| 93 | <pre class="programlisting"><span class="special">[</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">a</span><span class="special">+</span><span class="identifier">k</span><span class="special">)-></span><span class="char">'1111....1111'</span> <span class="comment">// N bits associated: Represents a total of k*N bits. | |
| 94 | </span></pre> | |
| 95 | <p> | |
| 96 | </p> | |
| 97 | <p> | |
| 98 | For the interval <code class="computeroutput"><span class="special">[</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">a</span><span class="special">+</span><span class="identifier">k</span><span class="special">)</span></code> above | |
| 99 | all bits are set. But we can also have individual <span class="emphasis"><em>nests</em></span> | |
| 100 | or <span class="emphasis"><em>clusters</em></span> of bitsequences. | |
| 101 | </p> | |
| 102 | <p> | |
| 103 | ||
| 104 | </p> | |
| 105 | <pre class="programlisting"><span class="special">[</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">b</span><span class="special">+</span><span class="number">1</span><span class="special">)-></span><span class="char">'01001011...1'</span> | |
| 106 | <span class="special">[</span><span class="identifier">b</span><span class="special">+</span><span class="number">1</span><span class="special">,</span><span class="identifier">b</span><span class="special">+</span><span class="number">2</span><span class="special">)-></span><span class="char">'11010001...0'</span> | |
| 107 | <span class="special">.</span> <span class="special">.</span> <span class="special">.</span> | |
| 108 | </pre> | |
| 109 | <p> | |
| 110 | </p> | |
| 111 | <p> | |
| 112 | and we can span intervals of equal bit sequences that represent periodic | |
| 113 | patterns. | |
| 114 | </p> | |
| 115 | <p> | |
| 116 | ||
| 117 | </p> | |
| 118 | <pre class="programlisting"><span class="special">[</span><span class="identifier">c</span><span class="special">,</span><span class="identifier">d</span><span class="special">)-></span><span class="char">'010101....01'</span> <span class="comment">// Every second bit is set in range [c,d) | |
| 119 | </span><span class="special">[</span><span class="identifier">d</span><span class="special">,</span><span class="identifier">e</span><span class="special">)-></span><span class="char">'001100..0011'</span> <span class="comment">// Every two bits alterate in range [d,e) | |
| 120 | </span><span class="special">[</span><span class="identifier">e</span><span class="special">,</span><span class="identifier">f</span><span class="special">)-></span><span class="char">'bit-sequence'</span> <span class="comment">// 'bit-sequence' reoccurs every N bits in range [e,f) | |
| 121 | </span></pre> | |
| 122 | <p> | |
| 123 | </p> | |
| 124 | <p> | |
| 125 | An <code class="computeroutput"><span class="identifier">IntervalBitmap</span></code> can represent | |
| 126 | <code class="computeroutput"><span class="identifier">N</span><span class="special">*(</span><span class="number">2</span><span class="special">^</span><span class="identifier">M</span><span class="special">)</span></code> elements, if <code class="computeroutput"><span class="identifier">M</span></code> | |
| 127 | is the number of bits of the integral type <code class="computeroutput"><span class="identifier">IntegralT</span></code>. | |
| 128 | Unlike bitsets, that usually represent <span class="emphasis"><em><span class="bold"><strong>unsigned</strong></span></em></span> | |
| 129 | integral numbers, large_bitset may range over negative numbers as well. There | |
| 130 | are fields where such large bitsets implementations are needed. E.g. for | |
| 131 | the compact representation of large file allocation tables. What remains | |
| 132 | to be done for project <span class="bold"><strong>Large Bitset</strong></span> is to | |
| 133 | code a wrapper <code class="computeroutput"><span class="keyword">class</span> <span class="identifier">large_bitset</span></code> | |
| 134 | around <code class="computeroutput"><span class="identifier">IntervalBitmap</span></code> so | |
| 135 | that <code class="computeroutput"><span class="identifier">large_bitset</span></code> looks and | |
| 136 | feels like a usual set class. | |
| 137 | </p> | |
| 138 | <div class="section boost_icl_projects_large_bitset_using_large_bitset" lang="en"> | |
| 139 | <div class="titlepage"><div><div><h4 class="title"> | |
| 140 | <a name="boost_icl.projects.large_bitset.using_large_bitset"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.using_large_bitset" title="Using large_bitset">Using | |
| 141 | large_bitset</a> | |
| 142 | </h4></div></div></div> | |
| 143 | <p> | |
| 144 | To quicken your appetite for a look at the implementation here are a few | |
| 145 | use cases first. Within the examples that follow, we will use <code class="computeroutput"><span class="identifier">nat</span></code><code class="literal"><span class="emphasis"><em>k</em></span></code> | |
| 146 | for unsigned integrals and <code class="computeroutput"><span class="identifier">bits</span></code><code class="literal"><span class="emphasis"><em>k</em></span></code> | |
| 147 | for bitsets containing <code class="literal"><span class="emphasis"><em>k</em></span></code> bits. | |
| 148 | </p> | |
| 149 | <p> | |
| 150 | Let's start large. In the first example . . . | |
| 151 | </p> | |
| 152 | <p> | |
| 153 | </p> | |
| 154 | <p> | |
| 155 | ||
| 156 | </p> | |
| 157 | <pre class="programlisting"><span class="keyword">void</span> <span class="identifier">test_large</span><span class="special">()</span> | |
| 158 | <span class="special">{</span> | |
| 159 | <span class="keyword">const</span> <span class="identifier">nat64</span> <span class="identifier">much</span> <span class="special">=</span> <span class="number">0</span><span class="identifier">xffffffffffffffffull</span><span class="special">;</span> | |
| 160 | <span class="identifier">large_bitset</span><span class="special"><></span> <span class="identifier">venti</span><span class="special">;</span> <span class="comment">// ... the largest, I can think of ;) | |
| 161 | </span> <span class="identifier">venti</span> <span class="special">+=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat64</span><span class="special">>(</span><span class="number">0</span><span class="special">,</span> <span class="identifier">much</span><span class="special">);</span> | |
| 162 | ||
| 163 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"----- Test function test_large() -----------------------------------------------\n"</span><span class="special">;</span> | |
| 164 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"We have just turned on the awesome amount of 18,446,744,073,709,551,616 bits ;-)\n"</span><span class="special">;</span> | |
| 165 | <span class="identifier">venti</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 166 | </pre> | |
| 167 | <p> | |
| 168 | </p> | |
| 169 | <p> | |
| 170 | </p> | |
| 171 | <p> | |
| 172 | . . . we are testing the limits. First we set all bits and then we switch | |
| 173 | off the very last bit. | |
| 174 | </p> | |
| 175 | <p> | |
| 176 | </p> | |
| 177 | <p> | |
| 178 | ||
| 179 | </p> | |
| 180 | <pre class="programlisting"> <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"---- Let's swich off the very last bit -----------------------------------------\n"</span><span class="special">;</span> | |
| 181 | <span class="identifier">venti</span> <span class="special">-=</span> <span class="identifier">much</span><span class="special">;</span> | |
| 182 | <span class="identifier">venti</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 183 | ||
| 184 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"---- Venti is plenty ... let's do something small: A tall ----------------------\n\n"</span><span class="special">;</span> | |
| 185 | <span class="special">}</span> | |
| 186 | </pre> | |
| 187 | <p> | |
| 188 | </p> | |
| 189 | <p> | |
| 190 | </p> | |
| 191 | <p> | |
| 192 | Program output (<span class="emphasis"><em>a little beautified</em></span>): | |
| 193 | </p> | |
| 194 | <pre class="programlisting"><span class="special">-----</span> <span class="identifier">Test</span> <span class="identifier">function</span> <span class="identifier">test_large</span><span class="special">()</span> <span class="special">-----------------------------------------------</span> | |
| 195 | <span class="identifier">We</span> <span class="identifier">have</span> <span class="identifier">just</span> <span class="identifier">turned</span> <span class="identifier">on</span> <span class="identifier">the</span> <span class="identifier">awesome</span> <span class="identifier">amount</span> <span class="identifier">of</span> <span class="number">18</span><span class="special">,</span><span class="number">446</span><span class="special">,</span><span class="number">744</span><span class="special">,</span><span class="number">073</span><span class="special">,</span><span class="number">709</span><span class="special">,</span><span class="number">551</span><span class="special">,</span><span class="number">616</span> <span class="identifier">bits</span> <span class="special">;-)</span> | |
| 196 | <span class="special">[</span> <span class="number">0</span><span class="special">,</span> <span class="number">288230376151711744</span><span class="special">)</span> <span class="special">-></span> <span class="number">1111111111111111111111111111111111111111111111111111111111111111</span> | |
| 197 | <span class="special">----</span> <span class="identifier">Let</span><span class="char">'s swich off the very last bit ----------------------------------------- | |
| 198 | [ 0, 288230376151711743) -> 1111111111111111111111111111111111111111111111111111111111111111 | |
| 199 | [288230376151711743, 288230376151711744) -> 1111111111111111111111111111111111111111111111111111111111111110 | |
| 200 | ---- Venti is plenty ... let'</span><span class="identifier">s</span> <span class="keyword">do</span> <span class="identifier">something</span> <span class="identifier">small</span><span class="special">:</span> <span class="identifier">A</span> <span class="identifier">tall</span> <span class="special">----------------------</span> | |
| 201 | </pre> | |
| 202 | <p> | |
| 203 | </p> | |
| 204 | <p> | |
| 205 | More readable is a smaller version of <code class="computeroutput"><span class="identifier">large_bitset</span></code>. | |
| 206 | In function <code class="computeroutput"><span class="identifier">test_small</span><span class="special">()</span></code> we apply a few more operations . . . | |
| 207 | </p> | |
| 208 | <p> | |
| 209 | </p> | |
| 210 | <p> | |
| 211 | ||
| 212 | </p> | |
| 213 | <pre class="programlisting"><span class="keyword">void</span> <span class="identifier">test_small</span><span class="special">()</span> | |
| 214 | <span class="special">{</span> | |
| 215 | <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">nat32</span><span class="special">,</span> <span class="identifier">bits8</span><span class="special">></span> <span class="identifier">tall</span><span class="special">;</span> <span class="comment">// small is tall ... | |
| 216 | </span> <span class="comment">// ... because even this 'small' large_bitset | |
| 217 | </span> <span class="comment">// can represent up to 2^32 == 4,294,967,296 bits. | |
| 218 | </span> | |
| 219 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"----- Test function test_small() -----------\n"</span><span class="special">;</span> | |
| 220 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Switch on all bits in range [0,64] ------\n"</span><span class="special">;</span> | |
| 221 | <span class="identifier">tall</span> <span class="special">+=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>(</span><span class="number">0</span><span class="special">,</span> <span class="number">64</span><span class="special">);</span> | |
| 222 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 223 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"--------------------------------------------\n"</span><span class="special">;</span> | |
| 224 | ||
| 225 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Turn off bits: 25,27,28 -----------------\n"</span><span class="special">;</span> | |
| 226 | ||
| 227 | <span class="special">(((</span><span class="identifier">tall</span> <span class="special">-=</span> <span class="number">25</span><span class="special">)</span> <span class="special">-=</span> <span class="number">27</span><span class="special">)</span> <span class="special">-=</span> <span class="number">28</span><span class="special">)</span> <span class="special">;</span> | |
| 228 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 229 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"--------------------------------------------\n"</span><span class="special">;</span> | |
| 230 | ||
| 231 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Flip bits in range [24,30) --------------\n"</span><span class="special">;</span> | |
| 232 | <span class="identifier">tall</span> <span class="special">^=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span><span class="number">24</span><span class="special">,</span><span class="number">30</span><span class="special">);</span> | |
| 233 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 234 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"--------------------------------------------\n"</span><span class="special">;</span> | |
| 235 | ||
| 236 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Remove the first 10 bits ----------------\n"</span><span class="special">;</span> | |
| 237 | <span class="identifier">tall</span> <span class="special">-=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span><span class="number">0</span><span class="special">,</span><span class="number">10</span><span class="special">);</span> | |
| 238 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 239 | ||
| 240 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Remove even bits in range [0,72) --------\n"</span><span class="special">;</span> | |
| 241 | <span class="keyword">int</span> <span class="identifier">bit</span><span class="special">;</span> | |
| 242 | <span class="keyword">for</span><span class="special">(</span><span class="identifier">bit</span><span class="special">=</span><span class="number">0</span><span class="special">;</span> <span class="identifier">bit</span><span class="special"><</span><span class="number">72</span><span class="special">;</span> <span class="identifier">bit</span><span class="special">++)</span> <span class="keyword">if</span><span class="special">(!(</span><span class="identifier">bit</span><span class="special">%</span><span class="number">2</span><span class="special">))</span> <span class="identifier">tall</span> <span class="special">-=</span> <span class="identifier">bit</span><span class="special">;</span> | |
| 243 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 244 | ||
| 245 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-- Set odd bits in range [0,72) --------\n"</span><span class="special">;</span> | |
| 246 | <span class="keyword">for</span><span class="special">(</span><span class="identifier">bit</span><span class="special">=</span><span class="number">0</span><span class="special">;</span> <span class="identifier">bit</span><span class="special"><</span><span class="number">72</span><span class="special">;</span> <span class="identifier">bit</span><span class="special">++)</span> <span class="keyword">if</span><span class="special">(</span><span class="identifier">bit</span><span class="special">%</span><span class="number">2</span><span class="special">)</span> <span class="identifier">tall</span> <span class="special">+=</span> <span class="identifier">bit</span><span class="special">;</span> | |
| 247 | <span class="identifier">tall</span><span class="special">.</span><span class="identifier">show_segments</span><span class="special">();</span> | |
| 248 | ||
| 249 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"--------------------------------------------\n\n"</span><span class="special">;</span> | |
| 250 | ||
| 251 | <span class="special">}</span> | |
| 252 | </pre> | |
| 253 | <p> | |
| 254 | </p> | |
| 255 | <p> | |
| 256 | </p> | |
| 257 | <p> | |
| 258 | . . . producing this output: | |
| 259 | </p> | |
| 260 | <pre class="programlisting"><span class="special">-----</span> <span class="identifier">Test</span> <span class="identifier">function</span> <span class="identifier">test_small</span><span class="special">()</span> <span class="special">-----------</span> | |
| 261 | <span class="special">--</span> <span class="identifier">Switch</span> <span class="identifier">on</span> <span class="identifier">all</span> <span class="identifier">bits</span> <span class="identifier">in</span> <span class="identifier">range</span> <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">64</span><span class="special">]</span> <span class="special">------</span> | |
| 262 | <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">8</span><span class="special">)-></span><span class="number">11111111</span> | |
| 263 | <span class="special">[</span><span class="number">8</span><span class="special">,</span><span class="number">9</span><span class="special">)-></span><span class="number">10000000</span> | |
| 264 | <span class="special">--------------------------------------------</span> | |
| 265 | <span class="special">--</span> <span class="identifier">Turn</span> <span class="identifier">off</span> <span class="identifier">bits</span><span class="special">:</span> <span class="number">25</span><span class="special">,</span><span class="number">27</span><span class="special">,</span><span class="number">28</span> <span class="special">-----------------</span> | |
| 266 | <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span><span class="number">11111111</span> | |
| 267 | <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span><span class="number">10100111</span> | |
| 268 | <span class="special">[</span><span class="number">4</span><span class="special">,</span><span class="number">8</span><span class="special">)-></span><span class="number">11111111</span> | |
| 269 | <span class="special">[</span><span class="number">8</span><span class="special">,</span><span class="number">9</span><span class="special">)-></span><span class="number">10000000</span> | |
| 270 | <span class="special">--------------------------------------------</span> | |
| 271 | <span class="special">--</span> <span class="identifier">Flip</span> <span class="identifier">bits</span> <span class="identifier">in</span> <span class="identifier">range</span> <span class="special">[</span><span class="number">24</span><span class="special">,</span><span class="number">30</span><span class="special">)</span> <span class="special">--------------</span> | |
| 272 | <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span><span class="number">11111111</span> | |
| 273 | <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span><span class="number">01011011</span> | |
| 274 | <span class="special">[</span><span class="number">4</span><span class="special">,</span><span class="number">8</span><span class="special">)-></span><span class="number">11111111</span> | |
| 275 | <span class="special">[</span><span class="number">8</span><span class="special">,</span><span class="number">9</span><span class="special">)-></span><span class="number">10000000</span> | |
| 276 | <span class="special">--------------------------------------------</span> | |
| 277 | <span class="special">--</span> <span class="identifier">Remove</span> <span class="identifier">the</span> <span class="identifier">first</span> <span class="number">10</span> <span class="identifier">bits</span> <span class="special">----------------</span> | |
| 278 | <span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">)-></span><span class="number">00111111</span> | |
| 279 | <span class="special">[</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span><span class="number">11111111</span> | |
| 280 | <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span><span class="number">01011011</span> | |
| 281 | <span class="special">[</span><span class="number">4</span><span class="special">,</span><span class="number">8</span><span class="special">)-></span><span class="number">11111111</span> | |
| 282 | <span class="special">[</span><span class="number">8</span><span class="special">,</span><span class="number">9</span><span class="special">)-></span><span class="number">10000000</span> | |
| 283 | <span class="special">--</span> <span class="identifier">Remove</span> <span class="identifier">even</span> <span class="identifier">bits</span> <span class="identifier">in</span> <span class="identifier">range</span> <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">72</span><span class="special">)</span> <span class="special">--------</span> | |
| 284 | <span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">)-></span><span class="number">00010101</span> | |
| 285 | <span class="special">[</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span><span class="number">01010101</span> | |
| 286 | <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span><span class="number">01010001</span> | |
| 287 | <span class="special">[</span><span class="number">4</span><span class="special">,</span><span class="number">8</span><span class="special">)-></span><span class="number">01010101</span> | |
| 288 | <span class="special">--</span> <span class="identifier">Set</span> <span class="identifier">odd</span> <span class="identifier">bits</span> <span class="identifier">in</span> <span class="identifier">range</span> <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">72</span><span class="special">)</span> <span class="special">--------</span> | |
| 289 | <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">9</span><span class="special">)-></span><span class="number">01010101</span> | |
| 290 | <span class="special">--------------------------------------------</span> | |
| 291 | </pre> | |
| 292 | <p> | |
| 293 | </p> | |
| 294 | <p> | |
| 295 | Finally, we present a little <span class="emphasis"><em>picturesque</em></span> example, | |
| 296 | that demonstrates that <code class="computeroutput"><span class="identifier">large_bitset</span></code> | |
| 297 | can also serve as a self compressing bitmap, that we can 'paint' with. | |
| 298 | </p> | |
| 299 | <p> | |
| 300 | </p> | |
| 301 | <p> | |
| 302 | ||
| 303 | </p> | |
| 304 | <pre class="programlisting"><span class="keyword">void</span> <span class="identifier">test_picturesque</span><span class="special">()</span> | |
| 305 | <span class="special">{</span> | |
| 306 | <span class="keyword">typedef</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">nat</span><span class="special">,</span> <span class="identifier">bits8</span><span class="special">></span> <span class="identifier">Bit8Set</span><span class="special">;</span> | |
| 307 | ||
| 308 | <span class="identifier">Bit8Set</span> <span class="identifier">square</span><span class="special">,</span> <span class="identifier">stare</span><span class="special">;</span> | |
| 309 | <span class="identifier">square</span> <span class="special">+=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>(</span><span class="number">0</span><span class="special">,</span><span class="number">8</span><span class="special">);</span> | |
| 310 | <span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">1</span><span class="special">;</span> <span class="identifier">i</span><span class="special"><</span><span class="number">5</span><span class="special">;</span> <span class="identifier">i</span><span class="special">++)</span> | |
| 311 | <span class="special">{</span> | |
| 312 | <span class="identifier">square</span> <span class="special">+=</span> <span class="number">8</span><span class="special">*</span><span class="identifier">i</span><span class="special">;</span> | |
| 313 | <span class="identifier">square</span> <span class="special">+=</span> <span class="number">8</span><span class="special">*</span><span class="identifier">i</span><span class="special">+</span><span class="number">7</span><span class="special">;</span> | |
| 314 | <span class="special">}</span> | |
| 315 | ||
| 316 | <span class="identifier">square</span> <span class="special">+=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>(</span><span class="number">41</span><span class="special">,</span><span class="number">47</span><span class="special">);</span> | |
| 317 | ||
| 318 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"----- Test function test_picturesque() -----\n"</span><span class="special">;</span> | |
| 319 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-------- empty face: "</span> | |
| 320 | <span class="special"><<</span> <span class="identifier">square</span><span class="special">.</span><span class="identifier">interval_count</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" intervals -----\n"</span><span class="special">;</span> | |
| 321 | <span class="identifier">square</span><span class="special">.</span><span class="identifier">show_matrix</span><span class="special">(</span><span class="string">" *"</span><span class="special">);</span> | |
| 322 | ||
| 323 | <span class="identifier">stare</span> <span class="special">+=</span> <span class="number">18</span><span class="special">;</span> <span class="identifier">stare</span> <span class="special">+=</span> <span class="number">21</span><span class="special">;</span> | |
| 324 | <span class="identifier">stare</span> <span class="special">+=</span> <span class="identifier">discrete_interval</span><span class="special"><</span><span class="identifier">nat</span><span class="special">>(</span><span class="number">34</span><span class="special">,</span><span class="number">38</span><span class="special">);</span> | |
| 325 | ||
| 326 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-------- compressed smile: "</span> | |
| 327 | <span class="special"><<</span> <span class="identifier">stare</span><span class="special">.</span><span class="identifier">interval_count</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" intervals -----\n"</span><span class="special">;</span> | |
| 328 | <span class="identifier">stare</span><span class="special">.</span><span class="identifier">show_matrix</span><span class="special">(</span><span class="string">" *"</span><span class="special">);</span> | |
| 329 | ||
| 330 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-------- staring bitset: "</span> | |
| 331 | <span class="special"><<</span> <span class="special">(</span><span class="identifier">square</span> <span class="special">+</span> <span class="identifier">stare</span><span class="special">).</span><span class="identifier">interval_count</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" intervals -----\n"</span><span class="special">;</span> | |
| 332 | <span class="special">(</span><span class="identifier">square</span> <span class="special">+</span> <span class="identifier">stare</span><span class="special">).</span><span class="identifier">show_matrix</span><span class="special">(</span><span class="string">" *"</span><span class="special">);</span> | |
| 333 | ||
| 334 | <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"--------------------------------------------\n"</span><span class="special">;</span> | |
| 335 | <span class="special">}</span> | |
| 336 | </pre> | |
| 337 | <p> | |
| 338 | </p> | |
| 339 | <p> | |
| 340 | </p> | |
| 341 | <p> | |
| 342 | Note that we have two <code class="computeroutput"><span class="identifier">large_bitsets</span></code> | |
| 343 | for the <span class="emphasis"><em>outline</em></span> and the <span class="emphasis"><em>interior</em></span>. | |
| 344 | Both parts are compressed but we can compose both by <code class="computeroutput"><span class="keyword">operator</span> | |
| 345 | <span class="special">+</span></code>, because the right <span class="emphasis"><em>positions</em></span> | |
| 346 | are provided. This is the program output: | |
| 347 | </p> | |
| 348 | <p> | |
| 349 | ||
| 350 | </p> | |
| 351 | <pre class="programlisting"><span class="special">-----</span> <span class="identifier">Test</span> <span class="identifier">function</span> <span class="identifier">test_picturesque</span><span class="special">()</span> <span class="special">-----</span> | |
| 352 | <span class="special">--------</span> <span class="identifier">empty</span> <span class="identifier">face</span><span class="special">:</span> <span class="number">3</span> <span class="identifier">intervals</span> <span class="special">-----</span> | |
| 353 | <span class="special">********</span> | |
| 354 | <span class="special">*</span> <span class="special">*</span> | |
| 355 | <span class="special">*</span> <span class="special">*</span> | |
| 356 | <span class="special">*</span> <span class="special">*</span> | |
| 357 | <span class="special">*</span> <span class="special">*</span> | |
| 358 | <span class="special">******</span> | |
| 359 | <span class="special">--------</span> <span class="identifier">compressed</span> <span class="identifier">smile</span><span class="special">:</span> <span class="number">2</span> <span class="identifier">intervals</span> <span class="special">-----</span> | |
| 360 | <span class="special">*</span> <span class="special">*</span> | |
| 361 | <span class="special">****</span> | |
| 362 | <span class="special">--------</span> <span class="identifier">staring</span> <span class="identifier">bitset</span><span class="special">:</span> <span class="number">6</span> <span class="identifier">intervals</span> <span class="special">-----</span> | |
| 363 | <span class="special">********</span> | |
| 364 | <span class="special">*</span> <span class="special">*</span> | |
| 365 | <span class="special">*</span> <span class="special">*</span> <span class="special">*</span> <span class="special">*</span> | |
| 366 | <span class="special">*</span> <span class="special">*</span> | |
| 367 | <span class="special">*</span> <span class="special">****</span> <span class="special">*</span> | |
| 368 | <span class="special">******</span> | |
| 369 | <span class="special">--------------------------------------------</span> | |
| 370 | </pre> | |
| 371 | <p> | |
| 372 | </p> | |
| 373 | <p> | |
| 374 | So, may be you are curious how this class template is coded on top of | |
| 375 | <code class="computeroutput"><a class="link" href="../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> using | |
| 376 | only about 250 lines of code. This is shown in the sections that follow. | |
| 377 | </p> | |
| 378 | </div> | |
| 379 | <div class="section boost_icl_projects_large_bitset_the_interval_bitmap" lang="en"> | |
| 380 | <div class="titlepage"><div><div><h4 class="title"> | |
| 381 | <a name="boost_icl.projects.large_bitset.the_interval_bitmap"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.the_interval_bitmap" title="The interval_bitmap">The | |
| 382 | interval_bitmap</a> | |
| 383 | </h4></div></div></div> | |
| 384 | <p> | |
| 385 | To begin, let's look at the basic data type again, that will be providing | |
| 386 | the major functionality: | |
| 387 | </p> | |
| 388 | <p> | |
| 389 | ||
| 390 | </p> | |
| 391 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">interval_map</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span> <span class="identifier">BitSetT</span><span class="special">,</span> <span class="identifier">partial_absorber</span><span class="special">,</span> | |
| 392 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special">,</span> <span class="identifier">inplace_bit_add</span><span class="special">,</span> <span class="identifier">inplace_bit_and</span><span class="special">></span> <span class="identifier">IntervalBitmap</span><span class="special">;</span> | |
| 393 | </pre> | |
| 394 | <p> | |
| 395 | </p> | |
| 396 | <p> | |
| 397 | <code class="computeroutput"><span class="identifier">DomainT</span></code> is supposed to | |
| 398 | be an integral type, the bitset type <code class="computeroutput"><span class="identifier">BitSetT</span></code> | |
| 399 | will be a wrapper class around an unsigned integral type. <code class="computeroutput"><span class="identifier">BitSetT</span></code> has to implement bitwise operators | |
| 400 | that will be called by the functors <code class="computeroutput"><span class="identifier">inplace_bit_add</span><span class="special"><</span><span class="identifier">BitSetT</span><span class="special">></span></code> and <code class="computeroutput"><span class="identifier">inplace_bit_and</span><span class="special"><</span><span class="identifier">BitSetT</span><span class="special">></span></code>. The type trait of interval_map is | |
| 401 | <code class="computeroutput"><span class="identifier">partial_absorber</span></code>, which | |
| 402 | means that it is <span class="emphasis"><em>partial</em></span> and that empty <code class="computeroutput"><span class="identifier">BitSetTs</span></code> are not stored in the map. This | |
| 403 | is desired and keeps the <code class="computeroutput"><span class="identifier">interval_map</span></code> | |
| 404 | minimal, storing only bitsets, that contain at least one bit switched on. | |
| 405 | Functor template <code class="computeroutput"><span class="identifier">inplace_bit_add</span></code> | |
| 406 | for parameter <code class="computeroutput"><span class="identifier">Combine</span></code> indicates | |
| 407 | that we do not expect <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code> as addition but the bitwise operator | |
| 408 | <code class="computeroutput"><span class="special">|=</span></code>. For template parameter | |
| 409 | <code class="computeroutput"><span class="identifier">Section</span></code> which is instaniated | |
| 410 | by <code class="computeroutput"><span class="identifier">inplace_bit_and</span></code> we expect | |
| 411 | the bitwise <code class="computeroutput"><span class="special">&=</span></code> operator. | |
| 412 | </p> | |
| 413 | </div> | |
| 414 | <div class="section boost_icl_projects_large_bitset_a_class_implementation_for_the_bitset_type" lang="en"> | |
| 415 | <div class="titlepage"><div><div><h4 class="title"> | |
| 416 | <a name="boost_icl.projects.large_bitset.a_class_implementation_for_the_bitset_type"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.a_class_implementation_for_the_bitset_type" title="A class implementation for the bitset type">A | |
| 417 | class implementation for the bitset type</a> | |
| 418 | </h4></div></div></div> | |
| 419 | <p> | |
| 420 | The code of the project is enclosed in a <code class="computeroutput"><span class="keyword">namespace</span> | |
| 421 | <span class="identifier">mini</span></code>. The name indicates, that | |
| 422 | the implementation is a <span class="emphasis"><em>minimal</em></span> example implementation. | |
| 423 | The name of the bitset class will be <code class="computeroutput"><span class="identifier">bits</span></code> | |
| 424 | or <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> if qualified. | |
| 425 | </p> | |
| 426 | <p> | |
| 427 | To be used as a codomain parameter of class template <code class="computeroutput"><a class="link" href="../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>, | |
| 428 | <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> has to implement all the functions | |
| 429 | that are required for a codomain_type in general, which are the default | |
| 430 | constructor <code class="computeroutput"><span class="identifier">bits</span><span class="special">()</span></code> | |
| 431 | and an equality <code class="computeroutput"><span class="keyword">operator</span><span class="special">==</span></code>. | |
| 432 | Moreover <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> has to implement operators required | |
| 433 | by the instantiations for parameter <code class="computeroutput"><span class="identifier">Combine</span></code> | |
| 434 | and <code class="computeroutput"><span class="identifier">Section</span></code> which are | |
| 435 | <code class="computeroutput"><span class="identifier">inplace_bit_add</span></code> and <code class="computeroutput"><span class="identifier">inplace_bit_and</span></code>. From functors <code class="computeroutput"><span class="identifier">inplace_bit_add</span></code> and <code class="computeroutput"><span class="identifier">inplace_bit_and</span></code> | |
| 436 | there are inverse functors <code class="computeroutput"><span class="identifier">inplace_bit_subtract</span></code> | |
| 437 | and <code class="computeroutput"><span class="identifier">inplace_bit_xor</span></code>. Those | |
| 438 | functors use operators <code class="computeroutput"><span class="special">|=</span> <span class="special">&=</span> <span class="special">^=</span></code> | |
| 439 | and <code class="computeroutput"><span class="special">~</span></code>. Finally if we want | |
| 440 | to apply lexicographical and subset comparison on large_bitset, we also | |
| 441 | need an <code class="computeroutput"><span class="keyword">operator</span> <span class="special"><</span></code>. | |
| 442 | All the operators that we need can be implemented for <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> | |
| 443 | on a few lines: | |
| 444 | </p> | |
| 445 | <p> | |
| 446 | </p> | |
| 447 | <p> | |
| 448 | ||
| 449 | </p> | |
| 450 | <pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NaturalT</span><span class="special">></span> <span class="keyword">class</span> <span class="identifier">bits</span> | |
| 451 | <span class="special">{</span> | |
| 452 | <span class="keyword">public</span><span class="special">:</span> | |
| 453 | <span class="keyword">typedef</span> <span class="identifier">NaturalT</span> <span class="identifier">word_type</span><span class="special">;</span> | |
| 454 | <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">digits</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">>::</span><span class="identifier">digits</span><span class="special">;</span> | |
| 455 | <span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">word_type</span> <span class="identifier">w1</span> <span class="special">=</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">>(</span><span class="number">1</span><span class="special">)</span> <span class="special">;</span> | |
| 456 | ||
| 457 | <span class="identifier">bits</span><span class="special">():</span><span class="identifier">_bits</span><span class="special">(){}</span> | |
| 458 | <span class="keyword">explicit</span> <span class="identifier">bits</span><span class="special">(</span><span class="identifier">word_type</span> <span class="identifier">value</span><span class="special">):</span><span class="identifier">_bits</span><span class="special">(</span><span class="identifier">value</span><span class="special">){}</span> | |
| 459 | ||
| 460 | <span class="identifier">word_type</span> <span class="identifier">word</span><span class="special">()</span><span class="keyword">const</span><span class="special">{</span> <span class="keyword">return</span> <span class="identifier">_bits</span><span class="special">;</span> <span class="special">}</span> | |
| 461 | <span class="identifier">bits</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">|=</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">bits</span><span class="special">&</span> <span class="identifier">value</span><span class="special">){</span><span class="identifier">_bits</span> <span class="special">|=</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">_bits</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 462 | <span class="identifier">bits</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">&=</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">bits</span><span class="special">&</span> <span class="identifier">value</span><span class="special">){</span><span class="identifier">_bits</span> <span class="special">&=</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">_bits</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 463 | <span class="identifier">bits</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">^=</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">bits</span><span class="special">&</span> <span class="identifier">value</span><span class="special">){</span><span class="identifier">_bits</span> <span class="special">^=</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">_bits</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 464 | <span class="identifier">bits</span> <span class="keyword">operator</span> <span class="special">~</span> <span class="special">()</span><span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">bits</span><span class="special">(~</span><span class="identifier">_bits</span><span class="special">);</span> <span class="special">}</span> | |
| 465 | <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special"><</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">bits</span><span class="special">&</span> <span class="identifier">value</span><span class="special">)</span><span class="keyword">const</span><span class="special">{</span><span class="keyword">return</span> <span class="identifier">_bits</span> <span class="special"><</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">_bits</span><span class="special">;}</span> | |
| 466 | <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special">==</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">bits</span><span class="special">&</span> <span class="identifier">value</span><span class="special">)</span><span class="keyword">const</span><span class="special">{</span><span class="keyword">return</span> <span class="identifier">_bits</span> <span class="special">==</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">_bits</span><span class="special">;}</span> | |
| 467 | ||
| 468 | <span class="keyword">bool</span> <span class="identifier">contains</span><span class="special">(</span><span class="identifier">word_type</span> <span class="identifier">element</span><span class="special">)</span><span class="keyword">const</span><span class="special">{</span> <span class="keyword">return</span> <span class="special">((</span><span class="identifier">w1</span> <span class="special"><<</span> <span class="identifier">element</span><span class="special">)</span> <span class="special">&</span> <span class="identifier">_bits</span><span class="special">)</span> <span class="special">!=</span> <span class="number">0</span><span class="special">;</span> <span class="special">}</span> | |
| 469 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">as_string</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">char</span> <span class="identifier">off_on</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">=</span> <span class="string">" 1"</span><span class="special">)</span><span class="keyword">const</span><span class="special">;</span> | |
| 470 | ||
| 471 | <span class="keyword">private</span><span class="special">:</span> | |
| 472 | <span class="identifier">word_type</span> <span class="identifier">_bits</span><span class="special">;</span> | |
| 473 | <span class="special">};</span> | |
| 474 | </pre> | |
| 475 | <p> | |
| 476 | </p> | |
| 477 | <p> | |
| 478 | </p> | |
| 479 | <p> | |
| 480 | Finally there is one important piece of meta information, we have to provide: | |
| 481 | <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> has to be recognized as a <code class="computeroutput"><span class="identifier">Set</span></code> by the icl code. Otherwise we can | |
| 482 | not exploit the fact that a map of sets is model of <code class="computeroutput"><span class="identifier">Set</span></code> | |
| 483 | and the resulting large_bitset would not behave like a set. So we have | |
| 484 | to say that <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> shall be sets: | |
| 485 | </p> | |
| 486 | <p> | |
| 487 | </p> | |
| 488 | <p> | |
| 489 | ||
| 490 | </p> | |
| 491 | <pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">icl</span> | |
| 492 | <span class="special">{</span> | |
| 493 | <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NaturalT</span><span class="special">></span> | |
| 494 | <span class="keyword">struct</span> <span class="identifier">is_set</span><span class="special"><</span><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">></span> <span class="special">></span> | |
| 495 | <span class="special">{</span> | |
| 496 | <span class="keyword">typedef</span> <span class="identifier">is_set</span><span class="special"><</span><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">></span> <span class="special">></span> <span class="identifier">type</span><span class="special">;</span> | |
| 497 | <span class="identifier">BOOST_STATIC_CONSTANT</span><span class="special">(</span><span class="keyword">bool</span><span class="special">,</span> <span class="identifier">value</span> <span class="special">=</span> <span class="keyword">true</span><span class="special">);</span> | |
| 498 | <span class="special">};</span> | |
| 499 | ||
| 500 | <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NaturalT</span><span class="special">></span> | |
| 501 | <span class="keyword">struct</span> <span class="identifier">has_set_semantics</span><span class="special"><</span><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">></span> <span class="special">></span> | |
| 502 | <span class="special">{</span> | |
| 503 | <span class="keyword">typedef</span> <span class="identifier">has_set_semantics</span><span class="special"><</span><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span><span class="special"><</span><span class="identifier">NaturalT</span><span class="special">></span> <span class="special">></span> <span class="identifier">type</span><span class="special">;</span> | |
| 504 | <span class="identifier">BOOST_STATIC_CONSTANT</span><span class="special">(</span><span class="keyword">bool</span><span class="special">,</span> <span class="identifier">value</span> <span class="special">=</span> <span class="keyword">true</span><span class="special">);</span> | |
| 505 | <span class="special">};</span> | |
| 506 | <span class="special">}}</span> | |
| 507 | </pre> | |
| 508 | <p> | |
| 509 | </p> | |
| 510 | <p> | |
| 511 | </p> | |
| 512 | <p> | |
| 513 | This is done by adding a partial template specialization to the type trait | |
| 514 | template <code class="computeroutput"><span class="identifier">icl</span><span class="special">::</span><span class="identifier">is_set</span></code>. For the extension of this type | |
| 515 | trait template and the result values of inclusion_compare we need these | |
| 516 | <code class="computeroutput"><span class="preprocessor">#includes</span></code> for the implementation | |
| 517 | of <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code>: | |
| 518 | </p> | |
| 519 | <p> | |
| 520 | </p> | |
| 521 | <p> | |
| 522 | ||
| 523 | </p> | |
| 524 | <pre class="programlisting"> <span class="comment">// These includes are needed ... | |
| 525 | </span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">string</span><span class="special">></span> <span class="comment">// for conversion to output and to | |
| 526 | </span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">icl</span><span class="special">/</span><span class="identifier">type_traits</span><span class="special">/</span><span class="identifier">has_set_semantics</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">>//</span><span class="identifier">declare</span> <span class="identifier">that</span> <span class="identifier">bits</span> <span class="identifier">has</span> <span class="identifier">the</span> | |
| 527 | <span class="comment">// behavior of a set. | |
| 528 | </span></pre> | |
| 529 | <p> | |
| 530 | </p> | |
| 531 | <p> | |
| 532 | </p> | |
| 533 | </div> | |
| 534 | <div class="section boost_icl_projects_large_bitset_implementation_of_a_large_bitset" lang="en"> | |
| 535 | <div class="titlepage"><div><div><h4 class="title"> | |
| 536 | <a name="boost_icl.projects.large_bitset.implementation_of_a_large_bitset"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset" title="Implementation of a large bitset">Implementation | |
| 537 | of a large bitset</a> | |
| 538 | </h4></div></div></div> | |
| 539 | <div class="toc"><dl> | |
| 540 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__public_interface">large_bitset: | |
| 541 | Public interface</a></span></dt> | |
| 542 | <dt><span class="section"><a href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__private_implementation">large_bitset: | |
| 543 | Private implementation</a></span></dt> | |
| 544 | </dl></div> | |
| 545 | <p> | |
| 546 | Having finished our <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> | |
| 547 | implementation, we can start to code the wrapper class that hides the efficient | |
| 548 | interval map of mini::bits and exposes a simple and convenient set behavior | |
| 549 | to the world of users. | |
| 550 | </p> | |
| 551 | <p> | |
| 552 | Let's start with the required <code class="computeroutput"><span class="preprocessor">#include</span></code>s | |
| 553 | this time: | |
| 554 | </p> | |
| 555 | <p> | |
| 556 | </p> | |
| 557 | <p> | |
| 558 | ||
| 559 | </p> | |
| 560 | <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span> <span class="comment">// to organize output | |
| 561 | </span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">limits</span><span class="special">></span> <span class="comment">// limits and associated constants | |
| 562 | </span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">operators</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> <span class="comment">// to define operators with minimal effort | |
| 563 | </span><span class="preprocessor">#include</span> <span class="string">"meta_log.hpp"</span> <span class="comment">// a meta logarithm | |
| 564 | </span><span class="preprocessor">#include</span> <span class="string">"bits.hpp"</span> <span class="comment">// a minimal bitset implementation | |
| 565 | </span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">icl</span><span class="special">/</span><span class="identifier">interval_map</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> <span class="comment">// base of large bitsets | |
| 566 | </span> | |
| 567 | <span class="keyword">namespace</span> <span class="identifier">mini</span> <span class="comment">// minimal implementations for example projects | |
| 568 | </span><span class="special">{</span> | |
| 569 | </pre> | |
| 570 | <p> | |
| 571 | </p> | |
| 572 | <p> | |
| 573 | </p> | |
| 574 | <p> | |
| 575 | Besides <code class="computeroutput"><span class="identifier">boost</span><span class="special">/</span><span class="identifier">icl</span><span class="special">/</span><span class="identifier">interval_map</span><span class="special">.</span><span class="identifier">hpp</span></code> and <code class="computeroutput"><span class="identifier">bits</span><span class="special">.</span><span class="identifier">hpp</span></code> | |
| 576 | the most important include here is <code class="computeroutput"><span class="identifier">boost</span><span class="special">/</span><span class="identifier">operators</span><span class="special">.</span><span class="identifier">hpp</span></code>. | |
| 577 | We use this library in order to further minimize the code and to provide | |
| 578 | pretty extensive operator functionality using very little code. | |
| 579 | </p> | |
| 580 | <p> | |
| 581 | For a short and concise naming of the most important unsigned integer types | |
| 582 | and the corresponding <code class="computeroutput"><span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits</span></code> | |
| 583 | we define this: | |
| 584 | </p> | |
| 585 | <p> | |
| 586 | </p> | |
| 587 | <p> | |
| 588 | ||
| 589 | </p> | |
| 590 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">char</span> <span class="identifier">nat8</span><span class="special">;</span> <span class="comment">// nati i: number bits | |
| 591 | </span><span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">short</span> <span class="identifier">nat16</span><span class="special">;</span> | |
| 592 | <span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="identifier">nat32</span><span class="special">;</span> | |
| 593 | <span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">nat64</span><span class="special">;</span> | |
| 594 | <span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="identifier">nat</span><span class="special">;</span> | |
| 595 | ||
| 596 | <span class="keyword">typedef</span> <span class="identifier">bits</span><span class="special"><</span><span class="identifier">nat8</span><span class="special">></span> <span class="identifier">bits8</span><span class="special">;</span> | |
| 597 | <span class="keyword">typedef</span> <span class="identifier">bits</span><span class="special"><</span><span class="identifier">nat16</span><span class="special">></span> <span class="identifier">bits16</span><span class="special">;</span> | |
| 598 | <span class="keyword">typedef</span> <span class="identifier">bits</span><span class="special"><</span><span class="identifier">nat32</span><span class="special">></span> <span class="identifier">bits32</span><span class="special">;</span> | |
| 599 | <span class="keyword">typedef</span> <span class="identifier">bits</span><span class="special"><</span><span class="identifier">nat64</span><span class="special">></span> <span class="identifier">bits64</span><span class="special">;</span> | |
| 600 | </pre> | |
| 601 | <p> | |
| 602 | </p> | |
| 603 | <p> | |
| 604 | </p> | |
| 605 | <div class="section boost_icl_projects_large_bitset_implementation_of_a_large_bitset_large_bitset__public_interface" lang="en"> | |
| 606 | <div class="titlepage"><div><div><h5 class="title"> | |
| 607 | <a name="boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__public_interface"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__public_interface" title="large_bitset: Public interface">large_bitset: | |
| 608 | Public interface</a> | |
| 609 | </h5></div></div></div> | |
| 610 | <p> | |
| 611 | And now let's code <code class="computeroutput"><span class="identifier">large_bitset</span></code>. | |
| 612 | </p> | |
| 613 | <p> | |
| 614 | </p> | |
| 615 | <p> | |
| 616 | ||
| 617 | </p> | |
| 618 | <pre class="programlisting"><span class="keyword">template</span> | |
| 619 | <span class="special"><</span> | |
| 620 | <span class="keyword">typename</span> <span class="identifier">DomainT</span> <span class="special">=</span> <span class="identifier">nat64</span><span class="special">,</span> | |
| 621 | <span class="keyword">typename</span> <span class="identifier">BitSetT</span> <span class="special">=</span> <span class="identifier">bits64</span><span class="special">,</span> | |
| 622 | <span class="identifier">ICL_COMPARE</span> <span class="identifier">Compare</span> <span class="special">=</span> <span class="identifier">ICL_COMPARE_INSTANCE</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special">,</span> <span class="identifier">DomainT</span><span class="special">),</span> | |
| 623 | <span class="identifier">ICL_INTERVAL</span><span class="special">(</span><span class="identifier">ICL_COMPARE</span><span class="special">)</span> <span class="identifier">Interval</span> <span class="special">=</span> <span class="identifier">ICL_INTERVAL_INSTANCE</span><span class="special">(</span><span class="identifier">ICL_INTERVAL_DEFAULT</span><span class="special">,</span> <span class="identifier">DomainT</span><span class="special">,</span> <span class="identifier">Compare</span><span class="special">),</span> | |
| 624 | <span class="identifier">ICL_ALLOC</span> <span class="identifier">Alloc</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span> | |
| 625 | <span class="special">></span> | |
| 626 | <span class="keyword">class</span> <span class="identifier">large_bitset</span> | |
| 627 | <span class="special">:</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">equality_comparable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 628 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">less_than_comparable</span><span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 629 | ||
| 630 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">addable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 631 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">orable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 632 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">subtractable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 633 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">andable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 634 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">xorable</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">></span> | |
| 635 | ||
| 636 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">addable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">DomainT</span> | |
| 637 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">orable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">DomainT</span> | |
| 638 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">subtractable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">DomainT</span> | |
| 639 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">andable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">DomainT</span> | |
| 640 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">xorable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">DomainT</span> | |
| 641 | ||
| 642 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">addable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">ICL_INTERVAL_TYPE</span><span class="special">(</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">)</span> | |
| 643 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">orable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">ICL_INTERVAL_TYPE</span><span class="special">(</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">)</span> | |
| 644 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">subtractable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">ICL_INTERVAL_TYPE</span><span class="special">(</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">)</span> | |
| 645 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">andable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">ICL_INTERVAL_TYPE</span><span class="special">(</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">)</span> | |
| 646 | <span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">xorable2</span> <span class="special"><</span> <span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">BitSetT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">,</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">Alloc</span><span class="special">>,</span> <span class="identifier">ICL_INTERVAL_TYPE</span><span class="special">(</span><span class="identifier">Interval</span><span class="special">,</span><span class="identifier">DomainT</span><span class="special">,</span><span class="identifier">Compare</span><span class="special">)</span> | |
| 647 | <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="special">></span> | |
| 648 | <span class="comment">//^ & - | + ^ & - | + ^ & - | + < == | |
| 649 | </span> <span class="comment">//segment element container | |
| 650 | </span></pre> | |
| 651 | <p> | |
| 652 | </p> | |
| 653 | <p> | |
| 654 | </p> | |
| 655 | <p> | |
| 656 | The first template parameter <code class="computeroutput"><span class="identifier">DomainT</span></code> | |
| 657 | will be instantiated with an integral type that defines the kind of numbers | |
| 658 | that can be elements of the set. Since we want to go for a large set | |
| 659 | we use <code class="computeroutput"><span class="identifier">nat64</span></code> as default | |
| 660 | which is a 64 bit unsigned integer ranging from <code class="computeroutput"><span class="number">0</span></code> | |
| 661 | to <code class="computeroutput"><span class="number">2</span><span class="special">^</span><span class="number">64</span><span class="special">-</span><span class="number">1</span></code>. | |
| 662 | As bitset parameter we also choose a 64-bit default. Parameters <code class="computeroutput"><span class="identifier">Combine</span></code> and <code class="computeroutput"><span class="identifier">Interval</span></code> | |
| 663 | are necessary to be passed to dependent type expressions. An allocator | |
| 664 | can be chosen, if desired. | |
| 665 | </p> | |
| 666 | <p> | |
| 667 | The nested list of private inheritance contains groups of template instantiations | |
| 668 | from <a href="http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm" target="_top">Boost.Operator</a>, | |
| 669 | that provides derivable operators from more fundamental once. Implementing | |
| 670 | the fundamental operators, we get the derivable ones <span class="emphasis"><em>for free</em></span>. | |
| 671 | Below is a short overview of what we get using Boost.Operator, where | |
| 672 | <a class="link" href="interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a> | |
| 673 | stands for <code class="computeroutput"><span class="identifier">large_bitset</span></code>, | |
| 674 | <a class="link" href="interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a> | |
| 675 | for it's <code class="computeroutput"><span class="identifier">interval_type</span></code> | |
| 676 | and <a class="link" href="interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a> | |
| 677 | for it's <code class="computeroutput"><span class="identifier">domain_type</span></code> | |
| 678 | or <code class="computeroutput"><span class="identifier">element_type</span></code>. | |
| 679 | </p> | |
| 680 | <div class="informaltable"><table class="table"> | |
| 681 | <colgroup> | |
| 682 | <col> | |
| 683 | <col> | |
| 684 | <col> | |
| 685 | </colgroup> | |
| 686 | <thead><tr> | |
| 687 | <th> | |
| 688 | <p> | |
| 689 | Group | |
| 690 | </p> | |
| 691 | </th> | |
| 692 | <th> | |
| 693 | <p> | |
| 694 | fundamental | |
| 695 | </p> | |
| 696 | </th> | |
| 697 | <th> | |
| 698 | <p> | |
| 699 | derivable | |
| 700 | </p> | |
| 701 | </th> | |
| 702 | </tr></thead> | |
| 703 | <tbody> | |
| 704 | <tr> | |
| 705 | <td> | |
| 706 | <p> | |
| 707 | Equality, ordering | |
| 708 | </p> | |
| 709 | </td> | |
| 710 | <td> | |
| 711 | <p> | |
| 712 | <code class="computeroutput"><span class="special">==</span></code> | |
| 713 | </p> | |
| 714 | </td> | |
| 715 | <td> | |
| 716 | <p> | |
| 717 | <code class="computeroutput"><span class="special">!=</span></code> | |
| 718 | </p> | |
| 719 | </td> | |
| 720 | </tr> | |
| 721 | <tr> | |
| 722 | <td> | |
| 723 | <p> | |
| 724 | </p> | |
| 725 | </td> | |
| 726 | <td> | |
| 727 | <p> | |
| 728 | <code class="computeroutput"><span class="special"><</span></code> | |
| 729 | </p> | |
| 730 | </td> | |
| 731 | <td> | |
| 732 | <p> | |
| 733 | <code class="computeroutput"><span class="special">></span> <span class="special"><=</span> | |
| 734 | <span class="special">>=</span></code> | |
| 735 | </p> | |
| 736 | </td> | |
| 737 | </tr> | |
| 738 | <tr> | |
| 739 | <td> | |
| 740 | <p> | |
| 741 | Set operators (<a class="link" href="interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a> | |
| 742 | x <a class="link" href="interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>) | |
| 743 | </p> | |
| 744 | </td> | |
| 745 | <td> | |
| 746 | <p> | |
| 747 | <code class="computeroutput"><span class="special">+=</span> <span class="special">|=</span> | |
| 748 | <span class="special">-=</span> <span class="special">&=</span> | |
| 749 | <span class="special">^=</span></code> | |
| 750 | </p> | |
| 751 | </td> | |
| 752 | <td> | |
| 753 | <p> | |
| 754 | <code class="computeroutput"><span class="special">+</span> <span class="special">|</span> | |
| 755 | <span class="special">-</span> <span class="special">&</span> | |
| 756 | <span class="special">^</span></code> | |
| 757 | </p> | |
| 758 | </td> | |
| 759 | </tr> | |
| 760 | <tr> | |
| 761 | <td> | |
| 762 | <p> | |
| 763 | Set operators (<a class="link" href="interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a> | |
| 764 | x <a class="link" href="interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>) | |
| 765 | </p> | |
| 766 | </td> | |
| 767 | <td> | |
| 768 | <p> | |
| 769 | <code class="computeroutput"><span class="special">+=</span> <span class="special">|=</span> | |
| 770 | <span class="special">-=</span> <span class="special">&=</span> | |
| 771 | <span class="special">^=</span></code> | |
| 772 | </p> | |
| 773 | </td> | |
| 774 | <td> | |
| 775 | <p> | |
| 776 | <code class="computeroutput"><span class="special">+</span> <span class="special">|</span> | |
| 777 | <span class="special">-</span> <span class="special">&</span> | |
| 778 | <span class="special">^</span></code> | |
| 779 | </p> | |
| 780 | </td> | |
| 781 | </tr> | |
| 782 | <tr> | |
| 783 | <td> | |
| 784 | <p> | |
| 785 | Set operators (<a class="link" href="interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a> | |
| 786 | x <a class="link" href="interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>) | |
| 787 | </p> | |
| 788 | </td> | |
| 789 | <td> | |
| 790 | <p> | |
| 791 | <code class="computeroutput"><span class="special">+=</span> <span class="special">|=</span> | |
| 792 | <span class="special">-=</span> <span class="special">&=</span> | |
| 793 | <span class="special">^=</span></code> | |
| 794 | </p> | |
| 795 | </td> | |
| 796 | <td> | |
| 797 | <p> | |
| 798 | <code class="computeroutput"><span class="special">+</span> <span class="special">|</span> | |
| 799 | <span class="special">-</span> <span class="special">&</span> | |
| 800 | <span class="special">^</span></code> | |
| 801 | </p> | |
| 802 | </td> | |
| 803 | </tr> | |
| 804 | </tbody> | |
| 805 | </table></div> | |
| 806 | <p> | |
| 807 | There is a number of associated types | |
| 808 | </p> | |
| 809 | <p> | |
| 810 | </p> | |
| 811 | <p> | |
| 812 | ||
| 813 | </p> | |
| 814 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">interval_map</span> | |
| 815 | <span class="special"><</span><span class="identifier">DomainT</span><span class="special">,</span> <span class="identifier">BitSetT</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">partial_absorber</span><span class="special">,</span> | |
| 816 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">inplace_bit_add</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">inplace_bit_and</span><span class="special">></span> <span class="identifier">interval_bitmap_type</span><span class="special">;</span> | |
| 817 | ||
| 818 | <span class="keyword">typedef</span> <span class="identifier">DomainT</span> <span class="identifier">domain_type</span><span class="special">;</span> | |
| 819 | <span class="keyword">typedef</span> <span class="identifier">DomainT</span> <span class="identifier">element_type</span><span class="special">;</span> | |
| 820 | <span class="keyword">typedef</span> <span class="identifier">BitSetT</span> <span class="identifier">bitset_type</span><span class="special">;</span> | |
| 821 | <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">BitSetT</span><span class="special">::</span><span class="identifier">word_type</span> <span class="identifier">word_type</span><span class="special">;</span> | |
| 822 | <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">interval_bitmap_type</span><span class="special">::</span><span class="identifier">interval_type</span> <span class="identifier">interval_type</span><span class="special">;</span> | |
| 823 | <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">interval_bitmap_type</span><span class="special">::</span><span class="identifier">value_type</span> <span class="identifier">value_type</span><span class="special">;</span> | |
| 824 | </pre> | |
| 825 | <p> | |
| 826 | </p> | |
| 827 | <p> | |
| 828 | </p> | |
| 829 | <p> | |
| 830 | most importantly the implementing <code class="computeroutput"><span class="identifier">interval_bitmap_type</span></code> | |
| 831 | that is used for the implementing container. | |
| 832 | </p> | |
| 833 | <p> | |
| 834 | </p> | |
| 835 | <p> | |
| 836 | ||
| 837 | </p> | |
| 838 | <pre class="programlisting"><span class="keyword">private</span><span class="special">:</span> | |
| 839 | <span class="identifier">interval_bitmap_type</span> <span class="identifier">_map</span><span class="special">;</span> | |
| 840 | </pre> | |
| 841 | <p> | |
| 842 | </p> | |
| 843 | <p> | |
| 844 | </p> | |
| 845 | <p> | |
| 846 | In order to use <a href="http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm" target="_top">Boost.Operator</a> | |
| 847 | we have to implement the fundamental operators as class members. This | |
| 848 | can be done quite schematically. | |
| 849 | </p> | |
| 850 | <p> | |
| 851 | </p> | |
| 852 | <p> | |
| 853 | ||
| 854 | </p> | |
| 855 | <pre class="programlisting"><span class="keyword">public</span><span class="special">:</span> | |
| 856 | <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special">==(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span><span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">_map</span> <span class="special">==</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="special">}</span> | |
| 857 | <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special"><</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span><span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">_map</span> <span class="special"><</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="special">}</span> | |
| 858 | ||
| 859 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">+=(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="identifier">_map</span> <span class="special">+=</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 860 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">|=(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="identifier">_map</span> <span class="special">|=</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 861 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">-=(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="identifier">_map</span> <span class="special">-=</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 862 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">&=(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="identifier">_map</span> <span class="special">&=</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 863 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">^=(</span><span class="keyword">const</span> <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="identifier">_map</span> <span class="special">^=</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">_map</span><span class="special">;</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;}</span> | |
| 864 | ||
| 865 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">+=(</span><span class="keyword">const</span> <span class="identifier">element_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">));</span> <span class="special">}</span> | |
| 866 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">|=(</span><span class="keyword">const</span> <span class="identifier">element_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">));</span> <span class="special">}</span> | |
| 867 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">-=(</span><span class="keyword">const</span> <span class="identifier">element_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">subtract</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">));</span> <span class="special">}</span> | |
| 868 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">&=(</span><span class="keyword">const</span> <span class="identifier">element_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">intersect</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">));}</span> | |
| 869 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">^=(</span><span class="keyword">const</span> <span class="identifier">element_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">flip</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">));</span> <span class="special">}</span> | |
| 870 | ||
| 871 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">+=(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">);</span> <span class="special">}</span> | |
| 872 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">|=(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">);</span> <span class="special">}</span> | |
| 873 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">-=(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">subtract</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">);</span> <span class="special">}</span> | |
| 874 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">&=(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">intersect</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">);}</span> | |
| 875 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="keyword">operator</span> <span class="special">^=(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">flip</span><span class="special">(</span><span class="identifier">rhs</span><span class="special">);</span> <span class="special">}</span> | |
| 876 | </pre> | |
| 877 | <p> | |
| 878 | </p> | |
| 879 | <p> | |
| 880 | </p> | |
| 881 | <p> | |
| 882 | As we can see, the seven most important operators that work on the class | |
| 883 | type <code class="computeroutput"><span class="identifier">large_bitset</span></code> can | |
| 884 | be directly implemented by propagating the operation to the implementing | |
| 885 | <code class="computeroutput"><span class="identifier">_map</span></code> of type <code class="computeroutput"><span class="identifier">interval_bitmap_type</span></code>. For the operators | |
| 886 | that work on segment and element types, we use member functions <code class="computeroutput"><span class="identifier">add</span></code>, <code class="computeroutput"><span class="identifier">subtract</span></code>, | |
| 887 | <code class="computeroutput"><span class="identifier">intersect</span></code> and <code class="computeroutput"><span class="identifier">flip</span></code>. As we will see only a small amount | |
| 888 | of adaper code is needed to couple those functions with the functionality | |
| 889 | of the implementing container. | |
| 890 | </p> | |
| 891 | <p> | |
| 892 | Member functions <code class="computeroutput"><span class="identifier">add</span></code>, | |
| 893 | <code class="computeroutput"><span class="identifier">subtract</span></code>, <code class="computeroutput"><span class="identifier">intersect</span></code> and <code class="computeroutput"><span class="identifier">flip</span></code>, | |
| 894 | that allow to combine <span class="emphasis"><em><span class="bold"><strong>intervals</strong></span></em></span> | |
| 895 | to <code class="computeroutput"><span class="identifier">large_bitsets</span></code> can | |
| 896 | be uniformly implemented using a private function <code class="computeroutput"><span class="identifier">segment_apply</span></code> | |
| 897 | that applies <span class="emphasis"><em>addition</em></span>, <span class="emphasis"><em>subtraction</em></span>, | |
| 898 | <span class="emphasis"><em>intersection</em></span> or <span class="emphasis"><em>symmetric difference</em></span>, | |
| 899 | after having translated the interval's borders into the right bitset | |
| 900 | positions. | |
| 901 | </p> | |
| 902 | <p> | |
| 903 | </p> | |
| 904 | <p> | |
| 905 | ||
| 906 | </p> | |
| 907 | <pre class="programlisting"><span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">add</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">segment_apply</span><span class="special">(&</span><span class="identifier">large_bitset</span><span class="special">::</span><span class="identifier">add_</span><span class="special">,</span> <span class="identifier">rhs</span><span class="special">);}</span> | |
| 908 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">subtract</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">segment_apply</span><span class="special">(&</span><span class="identifier">large_bitset</span><span class="special">::</span><span class="identifier">subtract_</span><span class="special">,</span> <span class="identifier">rhs</span><span class="special">);}</span> | |
| 909 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">intersect</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">segment_apply</span><span class="special">(&</span><span class="identifier">large_bitset</span><span class="special">::</span><span class="identifier">intersect_</span><span class="special">,</span><span class="identifier">rhs</span><span class="special">);}</span> | |
| 910 | <span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">flip</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">rhs</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">segment_apply</span><span class="special">(&</span><span class="identifier">large_bitset</span><span class="special">::</span><span class="identifier">flip_</span><span class="special">,</span> <span class="identifier">rhs</span><span class="special">);}</span> | |
| 911 | </pre> | |
| 912 | <p> | |
| 913 | </p> | |
| 914 | <p> | |
| 915 | </p> | |
| 916 | <p> | |
| 917 | In the sample programs, that we will present to demonstrate the capabilities | |
| 918 | of <code class="computeroutput"><span class="identifier">large_bitset</span></code> we will | |
| 919 | need a few additional functions specifically output functions in two | |
| 920 | different flavors. | |
| 921 | </p> | |
| 922 | <p> | |
| 923 | </p> | |
| 924 | <p> | |
| 925 | ||
| 926 | </p> | |
| 927 | <pre class="programlisting"><span class="identifier">size_t</span> <span class="identifier">interval_count</span><span class="special">()</span><span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">interval_count</span><span class="special">(</span><span class="identifier">_map</span><span class="special">);</span> <span class="special">}</span> | |
| 928 | ||
| 929 | <span class="keyword">void</span> <span class="identifier">show_segments</span><span class="special">()</span><span class="keyword">const</span> | |
| 930 | <span class="special">{</span> | |
| 931 | <span class="keyword">for</span><span class="special">(</span><span class="keyword">typename</span> <span class="identifier">interval_bitmap_type</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">it_</span> <span class="special">=</span> <span class="identifier">_map</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> | |
| 932 | <span class="identifier">it_</span> <span class="special">!=</span> <span class="identifier">_map</span><span class="special">.</span><span class="identifier">end</span><span class="special">();</span> <span class="special">++</span><span class="identifier">it_</span><span class="special">)</span> | |
| 933 | <span class="special">{</span> | |
| 934 | <span class="identifier">interval_type</span> <span class="identifier">itv</span> <span class="special">=</span> <span class="identifier">it_</span><span class="special">-></span><span class="identifier">first</span><span class="special">;</span> | |
| 935 | <span class="identifier">bitset_type</span> <span class="identifier">bits</span> <span class="special">=</span> <span class="identifier">it_</span><span class="special">-></span><span class="identifier">second</span><span class="special">;</span> | |
| 936 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">itv</span> <span class="special"><<</span> <span class="string">"->"</span> <span class="special"><<</span> <span class="identifier">bits</span><span class="special">.</span><span class="identifier">as_string</span><span class="special">(</span><span class="string">"01"</span><span class="special">)</span> <span class="special"><<</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span> | |
| 937 | <span class="special">}</span> | |
| 938 | <span class="special">}</span> | |
| 939 | ||
| 940 | <span class="keyword">void</span> <span class="identifier">show_matrix</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">char</span> <span class="identifier">off_on</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">=</span> <span class="string">" 1"</span><span class="special">)</span><span class="keyword">const</span> | |
| 941 | <span class="special">{</span> | |
| 942 | <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">;</span> | |
| 943 | <span class="keyword">typename</span> <span class="identifier">interval_bitmap_type</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">iter</span> <span class="special">=</span> <span class="identifier">_map</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> | |
| 944 | <span class="keyword">while</span><span class="special">(</span><span class="identifier">iter</span> <span class="special">!=</span> <span class="identifier">_map</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span> | |
| 945 | <span class="special">{</span> | |
| 946 | <span class="identifier">element_type</span> <span class="identifier">fst</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">first</span><span class="special">(</span><span class="identifier">iter</span><span class="special">-></span><span class="identifier">first</span><span class="special">),</span> <span class="identifier">lst</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">last</span><span class="special">(</span><span class="identifier">iter</span><span class="special">-></span><span class="identifier">first</span><span class="special">);</span> | |
| 947 | <span class="keyword">for</span><span class="special">(</span><span class="identifier">element_type</span> <span class="identifier">chunk</span> <span class="special">=</span> <span class="identifier">fst</span><span class="special">;</span> <span class="identifier">chunk</span> <span class="special"><=</span> <span class="identifier">lst</span><span class="special">;</span> <span class="identifier">chunk</span><span class="special">++)</span> | |
| 948 | <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">iter</span><span class="special">-></span><span class="identifier">second</span><span class="special">.</span><span class="identifier">as_string</span><span class="special">(</span><span class="identifier">off_on</span><span class="special">)</span> <span class="special"><<</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span> | |
| 949 | <span class="special">++</span><span class="identifier">iter</span><span class="special">;</span> | |
| 950 | <span class="special">}</span> | |
| 951 | <span class="special">}</span> | |
| 952 | </pre> | |
| 953 | <p> | |
| 954 | </p> | |
| 955 | <p> | |
| 956 | </p> | |
| 957 | <div class="itemizedlist"><ul type="disc"> | |
| 958 | <li> | |
| 959 | The first one, <code class="computeroutput"><span class="identifier">show_segments</span><span class="special">()</span></code> shows the container content as it | |
| 960 | is implemented, in the compressed form. | |
| 961 | </li> | |
| 962 | <li> | |
| 963 | The second function <code class="computeroutput"><span class="identifier">show_matrix</span></code> | |
| 964 | shows the complete matrix of bits that is represented by the container. | |
| 965 | </li> | |
| 966 | </ul></div> | |
| 967 | </div> | |
| 968 | <div class="section boost_icl_projects_large_bitset_implementation_of_a_large_bitset_large_bitset__private_implementation" lang="en"> | |
| 969 | <div class="titlepage"><div><div><h5 class="title"> | |
| 970 | <a name="boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__private_implementation"></a><a class="link" href="projects.html#boost_icl.projects.large_bitset.implementation_of_a_large_bitset.large_bitset__private_implementation" title="large_bitset: Private implementation">large_bitset: | |
| 971 | Private implementation</a> | |
| 972 | </h5></div></div></div> | |
| 973 | <p> | |
| 974 | In order to implement operations like the addition of an element say | |
| 975 | <code class="computeroutput"><span class="number">42</span></code> to the large bitset, we | |
| 976 | need to translate the <span class="emphasis"><em>value</em></span> to the <span class="emphasis"><em>position</em></span> | |
| 977 | of the associated <span class="bold"><strong>bit</strong></span> representing | |
| 978 | <code class="computeroutput"><span class="number">42</span></code> in the interval container | |
| 979 | of bitsets. As an example, suppose we use a | |
| 980 | </p> | |
| 981 | <pre class="programlisting"><span class="identifier">large_bitset</span><span class="special"><</span><span class="identifier">nat</span><span class="special">,</span> <span class="identifier">mini</span><span class="special">::</span><span class="identifier">bits8</span><span class="special">></span> <span class="identifier">lbs</span><span class="special">;</span> | |
| 982 | </pre> | |
| 983 | <p> | |
| 984 | that carries small bitsets of 8 bits only. The first four interval of | |
| 985 | <code class="computeroutput"><span class="identifier">lbs</span></code> are assumed to be | |
| 986 | associated with some bitsets. Now we want to add the interval <code class="computeroutput"><span class="special">[</span><span class="identifier">a</span><span class="special">,</span><span class="identifier">b</span><span class="special">]==[</span><span class="number">5</span><span class="special">,</span><span class="number">27</span><span class="special">]</span></code>. This | |
| 987 | will result in the following situation: | |
| 988 | </p> | |
| 989 | <pre class="programlisting"> <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">)-></span> <span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">)-></span> <span class="special">[</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span> <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span> | |
| 990 | <span class="special">[</span><span class="number">00101100</span><span class="special">][</span><span class="number">11001011</span><span class="special">][</span><span class="number">11101001</span><span class="special">][</span><span class="number">11100000</span><span class="special">]</span> | |
| 991 | <span class="special">+</span> <span class="special">[</span><span class="number">111</span> <span class="number">11111111</span> <span class="number">11111111</span> <span class="number">1111</span><span class="special">]</span> <span class="special">[</span><span class="number">5</span><span class="special">,</span><span class="number">27</span><span class="special">]</span> <span class="identifier">as</span> <span class="identifier">bitset</span> | |
| 992 | <span class="identifier">a</span> <span class="identifier">b</span> | |
| 993 | ||
| 994 | <span class="special">=></span> <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">)-></span> <span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span> <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span> | |
| 995 | <span class="special">[</span><span class="number">00101111</span><span class="special">][</span><span class="number">11111111</span><span class="special">][</span><span class="number">11110000</span><span class="special">]</span> | |
| 996 | </pre> | |
| 997 | <p> | |
| 998 | So we have to convert values 5 and 27 into a part that points to the | |
| 999 | interval and a part that refers to the position within the interval, | |
| 1000 | which is done by a <span class="emphasis"><em>division</em></span> and a <span class="emphasis"><em>modulo</em></span> | |
| 1001 | computation. (In order to have a consistent representation of the bitsequences | |
| 1002 | across the containers, within this project, bitsets are denoted with | |
| 1003 | the <span class="emphasis"><em><span class="bold"><strong>least significant bit on the left!</strong></span></em></span>) | |
| 1004 | </p> | |
| 1005 | <p> | |
| 1006 | ||
| 1007 | </p> | |
| 1008 | <pre class="programlisting"><span class="identifier">A</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">/</span><span class="number">8</span> <span class="special">=</span> <span class="number">5</span><span class="special">/</span><span class="number">8</span> <span class="special">=</span> <span class="number">0</span> <span class="comment">// refers to interval | |
| 1009 | </span><span class="identifier">B</span> <span class="special">=</span> <span class="identifier">b</span><span class="special">/</span><span class="number">8</span> <span class="special">=</span> <span class="number">27</span><span class="special">/</span><span class="number">8</span> <span class="special">=</span> <span class="number">3</span> | |
| 1010 | <span class="identifier">R</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">%</span><span class="number">8</span> <span class="special">=</span> <span class="number">5</span><span class="special">%</span><span class="number">8</span> <span class="special">=</span> <span class="number">5</span> <span class="comment">// refers to the position in the associated bitset. | |
| 1011 | </span><span class="identifier">S</span> <span class="special">=</span> <span class="identifier">b</span><span class="special">%</span><span class="number">8</span> <span class="special">=</span> <span class="number">27</span><span class="special">%</span><span class="number">8</span> <span class="special">=</span> <span class="number">3</span> | |
| 1012 | </pre> | |
| 1013 | <p> | |
| 1014 | </p> | |
| 1015 | <p> | |
| 1016 | All <span class="emphasis"><em>division</em></span> and <span class="emphasis"><em>modulo operations</em></span> | |
| 1017 | needed here are always done using a divisor <code class="computeroutput"><span class="identifier">d</span></code> | |
| 1018 | that is a power of <code class="computeroutput"><span class="number">2</span></code>: <code class="computeroutput"><span class="identifier">d</span> <span class="special">=</span> <span class="number">2</span><span class="special">^</span><span class="identifier">x</span></code>. | |
| 1019 | Therefore division and modulo can be expressed by bitset operations. | |
| 1020 | The constants needed for those bitset computations are defined here: | |
| 1021 | </p> | |
| 1022 | <p> | |
| 1023 | </p> | |
| 1024 | <p> | |
| 1025 | ||
| 1026 | </p> | |
| 1027 | <pre class="programlisting"><span class="keyword">private</span><span class="special">:</span> <span class="comment">// Example value | |
| 1028 | </span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">word_type</span> <span class="comment">// 8-bit case | |
| 1029 | </span> <span class="identifier">digits</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span> <span class="comment">// -------------------------------------------------------------- | |
| 1030 | </span> <span class="special"><</span><span class="identifier">word_type</span><span class="special">>::</span><span class="identifier">digits</span> <span class="special">,</span> <span class="comment">// 8 Size of the associated bitsets | |
| 1031 | </span> <span class="identifier">divisor</span> <span class="special">=</span> <span class="identifier">digits</span> <span class="special">,</span> <span class="comment">// 8 Divisor to find intervals for values | |
| 1032 | </span> <span class="identifier">last</span> <span class="special">=</span> <span class="identifier">digits</span><span class="special">-</span><span class="number">1</span> <span class="special">,</span> <span class="comment">// 7 Last bit (0 based) | |
| 1033 | </span> <span class="identifier">shift</span> <span class="special">=</span> <span class="identifier">log2_</span><span class="special"><</span><span class="identifier">divisor</span><span class="special">>::</span><span class="identifier">value</span> <span class="special">,</span> <span class="comment">// 3 To express the division as bit shift | |
| 1034 | </span> <span class="identifier">w1</span> <span class="special">=</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">word_type</span><span class="special">>(</span><span class="number">1</span><span class="special">)</span> <span class="special">,</span> <span class="comment">// Helps to avoid static_casts for long long | |
| 1035 | </span> <span class="identifier">mask</span> <span class="special">=</span> <span class="identifier">divisor</span> <span class="special">-</span> <span class="identifier">w1</span> <span class="special">,</span> <span class="comment">// 7=11100000 Helps to express the modulo operation as bit_and | |
| 1036 | </span> <span class="identifier">all</span> <span class="special">=</span> <span class="special">~</span><span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">word_type</span><span class="special">>(</span><span class="number">0</span><span class="special">),</span> <span class="comment">// 255=11111111 Helps to express a complete associated bitset | |
| 1037 | </span> <span class="identifier">top</span> <span class="special">=</span> <span class="identifier">w1</span> <span class="special"><<</span> <span class="special">(</span><span class="identifier">digits</span><span class="special">-</span><span class="identifier">w1</span><span class="special">)</span> <span class="special">;</span> <span class="comment">// 128=00000001 Value of the most significant bit of associated bitsets | |
| 1038 | </span> <span class="comment">// !> Note: Most signigicant bit on the right. | |
| 1039 | </span> </pre> | |
| 1040 | <p> | |
| 1041 | </p> | |
| 1042 | <p> | |
| 1043 | </p> | |
| 1044 | <p> | |
| 1045 | Looking at the example again, we can see that we have to identify the | |
| 1046 | positions of the beginning and ending of the interval [5,27] that is | |
| 1047 | to insert, and then <span class="emphasis"><em><span class="bold"><strong>subdivide</strong></span></em></span> | |
| 1048 | that range of bitsets into three partitions. | |
| 1049 | </p> | |
| 1050 | <div class="orderedlist"><ol type="1"> | |
| 1051 | <li> | |
| 1052 | The bitset where the interval starts. | |
| 1053 | </li> | |
| 1054 | <li> | |
| 1055 | the bitset where the interval ends | |
| 1056 | </li> | |
| 1057 | <li> | |
| 1058 | The bitsets that are completely overlapped by the interval | |
| 1059 | </li> | |
| 1060 | </ol></div> | |
| 1061 | <p> | |
| 1062 | ||
| 1063 | </p> | |
| 1064 | <pre class="programlisting"><span class="identifier">combine</span> <span class="identifier">interval</span> <span class="special">[</span><span class="number">5</span><span class="special">,</span><span class="number">27</span><span class="special">]</span> <span class="identifier">to</span> <span class="identifier">large_bitset</span> <span class="identifier">lbs</span> <span class="identifier">w</span><span class="special">.</span><span class="identifier">r</span><span class="special">.</span><span class="identifier">t</span><span class="special">.</span> <span class="identifier">some</span> <span class="identifier">operation</span> <span class="identifier">o</span> | |
| 1065 | ||
| 1066 | <span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">)-></span> <span class="special">[</span><span class="number">1</span><span class="special">,</span><span class="number">2</span><span class="special">)-></span> <span class="special">[</span><span class="number">2</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span> <span class="special">[</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span> | |
| 1067 | <span class="special">[</span><span class="number">00101100</span><span class="special">][</span><span class="number">11001011</span><span class="special">][</span><span class="number">11101001</span><span class="special">][</span><span class="number">11100000</span><span class="special">]</span> | |
| 1068 | <span class="identifier">o</span> <span class="special">[</span><span class="number">111</span> <span class="number">11111111</span> <span class="number">11111111</span> <span class="number">1111</span><span class="special">]</span> | |
| 1069 | <span class="identifier">a</span> <span class="identifier">b</span> | |
| 1070 | <span class="identifier">subdivide</span><span class="special">:</span> | |
| 1071 | <span class="special">[</span><span class="identifier">first</span><span class="special">!</span> <span class="special">][</span><span class="identifier">mid_1</span><span class="special">]</span> <span class="special">.</span> <span class="special">.</span> <span class="special">.[</span><span class="identifier">mid_n</span><span class="special">][</span> <span class="special">!</span><span class="identifier">last</span><span class="special">]</span> | |
| 1072 | <span class="special">[</span><span class="number">00000111</span><span class="special">][</span><span class="number">1.</span><span class="special">..</span><span class="number">1</span><span class="special">]</span> <span class="special">.</span> <span class="special">.</span> <span class="special">.[</span><span class="number">1.</span><span class="special">..</span><span class="number">1</span><span class="special">][</span><span class="number">11110000</span><span class="special">]</span> | |
| 1073 | </pre> | |
| 1074 | <p> | |
| 1075 | </p> | |
| 1076 | <p> | |
| 1077 | After subdividing, we perform the operation <code class="computeroutput"><span class="identifier">o</span></code> | |
| 1078 | as follows: | |
| 1079 | </p> | |
| 1080 | <div class="orderedlist"><ol type="1"> | |
| 1081 | <li> | |
| 1082 | For the first bitset: Set all bits from ther starting bit (<code class="computeroutput"><span class="special">!</span></code>) to the end of the bitset to <code class="computeroutput"><span class="number">1</span></code>. All other bits are <code class="computeroutput"><span class="number">0</span></code>. | |
| 1083 | Then perform operation <code class="computeroutput"><span class="identifier">o</span></code>: | |
| 1084 | <code class="computeroutput"><span class="identifier">_map</span> <span class="identifier">o</span><span class="special">=</span> <span class="special">([</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">)-></span><span class="number">00000111</span><span class="special">)</span></code> | |
| 1085 | </li> | |
| 1086 | <li> | |
| 1087 | For the last bitset: Set all bits from the beginning of the bitset | |
| 1088 | to the ending bit (<code class="computeroutput"><span class="special">!</span></code>) | |
| 1089 | to <code class="computeroutput"><span class="number">1</span></code>. All other bits are | |
| 1090 | <code class="computeroutput"><span class="number">0</span></code>. Then perform operation | |
| 1091 | <code class="computeroutput"><span class="identifier">o</span></code>: <code class="computeroutput"><span class="identifier">_map</span> | |
| 1092 | <span class="identifier">o</span><span class="special">=</span> | |
| 1093 | <span class="special">([</span><span class="number">3</span><span class="special">,</span><span class="number">4</span><span class="special">)-></span><span class="number">11110000</span><span class="special">)</span></code> | |
| 1094 | </li> | |
| 1095 | <li> | |
| 1096 | For the range of bitsets in between the staring and ending one, perform | |
| 1097 | operation <code class="computeroutput"><span class="identifier">o</span></code>: <code class="computeroutput"><span class="identifier">_map</span> <span class="identifier">o</span><span class="special">=</span> <span class="special">([</span><span class="number">1</span><span class="special">,</span><span class="number">3</span><span class="special">)-></span><span class="number">11111111</span><span class="special">)</span></code> | |
| 1098 | </li> | |
| 1099 | </ol></div> | |
| 1100 | <p> | |
| 1101 | The algorithm, that has been outlined and illustrated by the example, | |
| 1102 | is implemented by the private member function <code class="computeroutput"><span class="identifier">segment_apply</span></code>. | |
| 1103 | To make the combiner operation a variable in this algorithm, we use a | |
| 1104 | <span class="emphasis"><em>pointer to member function type</em></span> | |
| 1105 | </p> | |
| 1106 | <p> | |
| 1107 | </p> | |
| 1108 | <p> | |
| 1109 | ||
| 1110 | </p> | |
| 1111 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="keyword">void</span> <span class="special">(</span><span class="identifier">large_bitset</span><span class="special">::*</span><span class="identifier">segment_combiner</span><span class="special">)(</span><span class="identifier">element_type</span><span class="special">,</span> <span class="identifier">element_type</span><span class="special">,</span> <span class="identifier">bitset_type</span><span class="special">);</span> | |
| 1112 | </pre> | |
| 1113 | <p> | |
| 1114 | </p> | |
| 1115 | <p> | |
| 1116 | </p> | |
| 1117 | <p> | |
| 1118 | as first function argument. We will pass member functions <code class="computeroutput"><span class="identifier">combine_</span></code> here, | |
| 1119 | </p> | |
| 1120 | <pre class="programlisting"><span class="identifier">combine_</span><span class="special">(</span><span class="identifier">first_of_interval</span><span class="special">,</span> <span class="identifier">end_of_interval</span><span class="special">,</span> <span class="identifier">some_bitset</span><span class="special">);</span> | |
| 1121 | </pre> | |
| 1122 | <p> | |
| 1123 | that take the beginning and ending of an interval and a bitset and combine | |
| 1124 | them to the implementing <code class="computeroutput"><span class="identifier">interval_bitmap_type</span> | |
| 1125 | <span class="identifier">_map</span></code>. Here are these functions: | |
| 1126 | </p> | |
| 1127 | <p> | |
| 1128 | </p> | |
| 1129 | <p> | |
| 1130 | ||
| 1131 | </p> | |
| 1132 | <pre class="programlisting"><span class="keyword">void</span> <span class="identifier">add_</span><span class="special">(</span><span class="identifier">DomainT</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">DomainT</span> <span class="identifier">up</span><span class="special">,</span> <span class="identifier">BitSetT</span> <span class="identifier">bits</span><span class="special">){</span><span class="identifier">_map</span> <span class="special">+=</span> <span class="identifier">value_type</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">lo</span><span class="special">,</span><span class="identifier">up</span><span class="special">),</span> <span class="identifier">bits</span><span class="special">);}</span> | |
| 1133 | <span class="keyword">void</span> <span class="identifier">subtract_</span><span class="special">(</span><span class="identifier">DomainT</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">DomainT</span> <span class="identifier">up</span><span class="special">,</span> <span class="identifier">BitSetT</span> <span class="identifier">bits</span><span class="special">){</span><span class="identifier">_map</span> <span class="special">-=</span> <span class="identifier">value_type</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">lo</span><span class="special">,</span><span class="identifier">up</span><span class="special">),</span> <span class="identifier">bits</span><span class="special">);}</span> | |
| 1134 | <span class="keyword">void</span> <span class="identifier">intersect_</span><span class="special">(</span><span class="identifier">DomainT</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">DomainT</span> <span class="identifier">up</span><span class="special">,</span> <span class="identifier">BitSetT</span> <span class="identifier">bits</span><span class="special">){</span><span class="identifier">_map</span> <span class="special">&=</span> <span class="identifier">value_type</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">lo</span><span class="special">,</span><span class="identifier">up</span><span class="special">),</span> <span class="identifier">bits</span><span class="special">);}</span> | |
| 1135 | <span class="keyword">void</span> <span class="identifier">flip_</span><span class="special">(</span><span class="identifier">DomainT</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">DomainT</span> <span class="identifier">up</span><span class="special">,</span> <span class="identifier">BitSetT</span> <span class="identifier">bits</span><span class="special">){</span><span class="identifier">_map</span> <span class="special">^=</span> <span class="identifier">value_type</span><span class="special">(</span><span class="identifier">interval_type</span><span class="special">::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">lo</span><span class="special">,</span><span class="identifier">up</span><span class="special">),</span> <span class="identifier">bits</span><span class="special">);}</span> | |
| 1136 | </pre> | |
| 1137 | <p> | |
| 1138 | </p> | |
| 1139 | <p> | |
| 1140 | </p> | |
| 1141 | <p> | |
| 1142 | Finally we can code function <code class="computeroutput"><span class="identifier">segment_apply</span></code>, | |
| 1143 | that does the partitioning and subsequent combining: | |
| 1144 | </p> | |
| 1145 | <p> | |
| 1146 | </p> | |
| 1147 | <p> | |
| 1148 | ||
| 1149 | </p> | |
| 1150 | <pre class="programlisting"><span class="identifier">large_bitset</span><span class="special">&</span> <span class="identifier">segment_apply</span><span class="special">(</span><span class="identifier">segment_combiner</span> <span class="identifier">combine</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">interval_type</span><span class="special">&</span> <span class="identifier">operand</span><span class="special">)</span> | |
| 1151 | <span class="special">{</span> | |
| 1152 | <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">;</span> | |
| 1153 | <span class="keyword">if</span><span class="special">(</span><span class="identifier">icl</span><span class="special">::</span><span class="identifier">is_empty</span><span class="special">(</span><span class="identifier">operand</span><span class="special">))</span> | |
| 1154 | <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;</span> | |
| 1155 | <span class="comment">// same as | |
| 1156 | </span> <span class="identifier">element_type</span> <span class="identifier">base</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">first</span><span class="special">(</span><span class="identifier">operand</span><span class="special">)</span> <span class="special">>></span> <span class="identifier">shift</span><span class="special">,</span> <span class="comment">// icl::first(operand) / divisor | |
| 1157 | </span> <span class="identifier">ceil</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">last</span> <span class="special">(</span><span class="identifier">operand</span><span class="special">)</span> <span class="special">>></span> <span class="identifier">shift</span><span class="special">;</span> <span class="comment">// icl::last (operand) / divisor | |
| 1158 | </span> <span class="identifier">word_type</span> <span class="identifier">base_rest</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">first</span><span class="special">(</span><span class="identifier">operand</span><span class="special">)</span> <span class="special">&</span> <span class="identifier">mask</span> <span class="special">,</span> <span class="comment">// icl::first(operand) % divisor | |
| 1159 | </span> <span class="identifier">ceil_rest</span> <span class="special">=</span> <span class="identifier">icl</span><span class="special">::</span><span class="identifier">last</span> <span class="special">(</span><span class="identifier">operand</span><span class="special">)</span> <span class="special">&</span> <span class="identifier">mask</span> <span class="special">;</span> <span class="comment">// icl::last (operand) % divisor | |
| 1160 | </span> | |
| 1161 | <span class="keyword">if</span><span class="special">(</span><span class="identifier">base</span> <span class="special">==</span> <span class="identifier">ceil</span><span class="special">)</span> <span class="comment">// [first, last] are within one bitset (chunk) | |
| 1162 | </span> <span class="special">(</span><span class="keyword">this</span><span class="special">->*</span><span class="identifier">combine</span><span class="special">)(</span><span class="identifier">base</span><span class="special">,</span> <span class="identifier">base</span><span class="special">+</span><span class="number">1</span><span class="special">,</span> <span class="identifier">bitset_type</span><span class="special">(</span> <span class="identifier">to_upper_from</span><span class="special">(</span><span class="identifier">base_rest</span><span class="special">)</span> | |
| 1163 | <span class="special">&</span> <span class="identifier">from_lower_to</span><span class="special">(</span><span class="identifier">ceil_rest</span><span class="special">)));</span> | |
| 1164 | <span class="keyword">else</span> <span class="comment">// [first, last] spread over more than one bitset (chunk) | |
| 1165 | </span> <span class="special">{</span> | |
| 1166 | <span class="identifier">element_type</span> <span class="identifier">mid_low</span> <span class="special">=</span> <span class="identifier">base_rest</span> <span class="special">==</span> <span class="number">0</span> <span class="special">?</span> <span class="identifier">base</span> <span class="special">:</span> <span class="identifier">base</span><span class="special">+</span><span class="number">1</span><span class="special">,</span> <span class="comment">// first element of mid part | |
| 1167 | </span> <span class="identifier">mid_up</span> <span class="special">=</span> <span class="identifier">ceil_rest</span> <span class="special">==</span> <span class="identifier">all</span> <span class="special">?</span> <span class="identifier">ceil</span><span class="special">+</span><span class="number">1</span> <span class="special">:</span> <span class="identifier">ceil</span> <span class="special">;</span> <span class="comment">// last element of mid part | |
| 1168 | </span> | |
| 1169 | <span class="keyword">if</span><span class="special">(</span><span class="identifier">base_rest</span> <span class="special">></span> <span class="number">0</span><span class="special">)</span> <span class="comment">// Bitset of base interval has to be filled from base_rest to last | |
| 1170 | </span> <span class="special">(</span><span class="keyword">this</span><span class="special">->*</span><span class="identifier">combine</span><span class="special">)(</span><span class="identifier">base</span><span class="special">,</span> <span class="identifier">base</span><span class="special">+</span><span class="number">1</span><span class="special">,</span> <span class="identifier">bitset_type</span><span class="special">(</span><span class="identifier">to_upper_from</span><span class="special">(</span><span class="identifier">base_rest</span><span class="special">)));</span> | |
| 1171 | <span class="keyword">if</span><span class="special">(</span><span class="identifier">ceil_rest</span> <span class="special"><</span> <span class="identifier">all</span><span class="special">)</span> <span class="comment">// Bitset of ceil interval has to be filled from first to ceil_rest | |
| 1172 | </span> <span class="special">(</span><span class="keyword">this</span><span class="special">->*</span><span class="identifier">combine</span><span class="special">)(</span><span class="identifier">ceil</span><span class="special">,</span> <span class="identifier">ceil</span><span class="special">+</span><span class="number">1</span><span class="special">,</span> <span class="identifier">bitset_type</span><span class="special">(</span><span class="identifier">from_lower_to</span><span class="special">(</span><span class="identifier">ceil_rest</span><span class="special">)));</span> | |
| 1173 | <span class="keyword">if</span><span class="special">(</span><span class="identifier">mid_low</span> <span class="special"><</span> <span class="identifier">mid_up</span><span class="special">)</span> <span class="comment">// For the middle part all bits have to set. | |
| 1174 | </span> <span class="special">(</span><span class="keyword">this</span><span class="special">->*</span><span class="identifier">combine</span><span class="special">)(</span><span class="identifier">mid_low</span><span class="special">,</span> <span class="identifier">mid_up</span><span class="special">,</span> <span class="identifier">bitset_type</span><span class="special">(</span><span class="identifier">all</span><span class="special">));</span> | |
| 1175 | <span class="special">}</span> | |
| 1176 | <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;</span> | |
| 1177 | <span class="special">}</span> | |
| 1178 | </pre> | |
| 1179 | <p> | |
| 1180 | </p> | |
| 1181 | <p> | |
| 1182 | </p> | |
| 1183 | <p> | |
| 1184 | The functions that help filling bitsets to and from a given bit are implemented | |
| 1185 | here: | |
| 1186 | </p> | |
| 1187 | <p> | |
| 1188 | ||
| 1189 | </p> | |
| 1190 | <pre class="programlisting"><span class="keyword">static</span> <span class="identifier">word_type</span> <span class="identifier">from_lower_to</span><span class="special">(</span><span class="identifier">word_type</span> <span class="identifier">bit</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">bit</span><span class="special">==</span><span class="identifier">last</span> <span class="special">?</span> <span class="identifier">all</span> <span class="special">:</span> <span class="special">(</span><span class="identifier">w1</span><span class="special"><<(</span><span class="identifier">bit</span><span class="special">+</span><span class="identifier">w1</span><span class="special">))-</span><span class="identifier">w1</span><span class="special">;}</span> | |
| 1191 | <span class="keyword">static</span> <span class="identifier">word_type</span> <span class="identifier">to_upper_from</span><span class="special">(</span><span class="identifier">word_type</span> <span class="identifier">bit</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">bit</span><span class="special">==</span><span class="identifier">last</span> <span class="special">?</span> <span class="identifier">top</span> <span class="special">:</span> <span class="special">~((</span><span class="identifier">w1</span><span class="special"><<</span><span class="identifier">bit</span><span class="special">)-</span><span class="identifier">w1</span><span class="special">);</span> <span class="special">}</span> | |
| 1192 | </pre> | |
| 1193 | <p> | |
| 1194 | </p> | |
| 1195 | <p> | |
| 1196 | </p> | |
| 1197 | <p> | |
| 1198 | This completes the implementation of class template <code class="computeroutput"><span class="identifier">large_bitset</span></code>. | |
| 1199 | Using only a small amount of mostly schematic code, we have been able | |
| 1200 | to provide a pretty powerful, self compressing and generally usable set | |
| 1201 | type for all integral domain types. | |
| 1202 | </p> | |
| 1203 | </div> | |
| 1204 | </div> | |
| 1205 | </div> | |
| 1206 | </div> | |
| 1207 | <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> | |
| 1208 | <td align="left"></td> | |
| 1209 | <td align="right"><div class="copyright-footer">Copyright © 2007 -2010 Joachim Faulhaber<br>Copyright © 1999 -2006 Cortex Software GmbH<p> | |
| 1210 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
| 1211 | file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) | |
| 1212 | </p> | |
| 1213 | </div></td> | |
| 1214 | </tr></table> | |
| 1215 | <hr> | |
| 1216 | <div class="spirit-nav"> | |
| 1217 | <a accesskey="p" href="examples/custom_interval.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="concepts.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> | |
| 1218 | </div> | |
| 1219 | </body> | |
| 1220 | </html> |