File: a00102.html

package info (click to toggle)
bmagic 3.4.0-4
links: PTS
area: main
in suites: etch, etch-m68k
size: 4,208 kB
ctags: 2,500
sloc: cpp: 9,399; ansic: 3,142; sh: 2,430; makefile: 340
file content (2956 lines) | stat: -rw-r--r-- 203,464 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>BitMagic: bm.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.4.1 -->
<div class="qindex"><a class="qindex" href="index.html">Main&nbsp;Page</a> | <a class="qindex" href="modules.html">Modules</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class&nbsp;Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical&nbsp;List</a> | <a class="qindex" href="annotated.html">Data&nbsp;Structures</a> | <a class="qindex" href="dirs.html">Directories</a> | <a class="qindex" href="files.html">File&nbsp;List</a> | <a class="qindex" href="namespacemembers.html">Namespace&nbsp;Members</a> | <a class="qindex" href="functions.html">Data&nbsp;Fields</a> | <a class="qindex" href="globals.html">Globals</a> | <a class="qindex" href="examples.html">Examples</a></div>
<div class="nav">
<a class="el" href="dir_000000.html">src</a></div>
<h1>bm.h</h1><a href="a00074.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment">00001 <span class="comment">/*</span>
00002 <span class="comment">Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)</span>
00003 <span class="comment"></span>
00004 <span class="comment">PermiFor more information please visit:  http://bmagic.sourceforge.net</span>
00005 <span class="comment">ssion is hereby granted, free of charge, to any person </span>
00006 <span class="comment">obtaining a copy of this software and associated documentation </span>
00007 <span class="comment">files (the "Software"), to deal in the Software without restriction, </span>
00008 <span class="comment">including without limitation the rights to use, copy, modify, merge, </span>
00009 <span class="comment">publish, distribute, sublicense, and/or sell copies of the Software, </span>
00010 <span class="comment">and to permit persons to whom the Software is furnished to do so, </span>
00011 <span class="comment">subject to the following conditions:</span>
00012 <span class="comment"></span>
00013 <span class="comment">The above copyright notice and this permission notice shall be included </span>
00014 <span class="comment">in all copies or substantial portions of the Software.</span>
00015 <span class="comment"></span>
00016 <span class="comment">THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, </span>
00017 <span class="comment">EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES </span>
00018 <span class="comment">OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. </span>
00019 <span class="comment">IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, </span>
00020 <span class="comment">DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, </span>
00021 <span class="comment">ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR </span>
00022 <span class="comment">OTHER DEALINGS IN THE SOFTWARE.</span>
00023 <span class="comment"></span>
00024 <span class="comment">For more information please visit:  http://bmagic.sourceforge.net</span>
00025 <span class="comment"></span>
00026 <span class="comment">*/</span>
00027 
00028 <span class="preprocessor">#ifndef BM__H__INCLUDED__</span>
00029 <span class="preprocessor"></span><span class="preprocessor">#define BM__H__INCLUDED__</span>
00030 <span class="preprocessor"></span>
00031 <span class="preprocessor">#include &lt;string.h&gt;</span>
00032 <span class="preprocessor">#include &lt;assert.h&gt;</span>
00033 <span class="preprocessor">#include &lt;limits.h&gt;</span>
00034 
00035 <span class="comment">// define BM_NO_STL if you use BM in "STL free" environment and want</span>
00036 <span class="comment">// to disable any references to STL headers</span>
00037 <span class="preprocessor">#ifndef BM_NO_STL</span>
00038 <span class="preprocessor"></span><span class="preprocessor"># include &lt;iterator&gt;</span>
00039 <span class="preprocessor">#endif</span>
00040 <span class="preprocessor"></span>
00041 <span class="preprocessor">#include "<a class="code" href="a00076.html">bmconst.h</a>"</span>
00042 <span class="preprocessor">#include "<a class="code" href="a00077.html">bmdef.h</a>"</span>
00043 
00044 
00045 <span class="comment">// Vector based optimizations are incompatible with 64-bit optimization</span>
00046 <span class="comment">// which is considered a form of vectorization</span>
00047 <span class="preprocessor">#ifdef BMSSE2OPT</span>
00048 <span class="preprocessor"></span><span class="preprocessor"># undef BM64OPT</span>
<a name="l00049"></a><a class="code" href="a00074.html#a0">00049</a> <span class="preprocessor"></span><span class="preprocessor"># define BMVECTOPT</span>
00050 <span class="preprocessor"></span><span class="preprocessor"># include "<a class="code" href="a00079.html">bmsse2.h</a>"</span>
00051 <span class="preprocessor">#endif</span>
00052 <span class="preprocessor"></span>
00053 <span class="preprocessor">#include "bmfwd.h"</span>
00054 <span class="preprocessor">#include "<a class="code" href="a00078.html">bmfunc.h</a>"</span>
00055 <span class="preprocessor">#include "<a class="code" href="a00081.html">bmvmin.h</a>"</span>
00056 <span class="preprocessor">#include "<a class="code" href="a00082.html">encoding.h</a>"</span>
00057 <span class="preprocessor">#include "bmalloc.h"</span>
00058 <span class="preprocessor">#include "bmblocks.h"</span>
00059 
<a name="l00060"></a><a class="code" href="a00092.html">00060</a> <span class="keyword">namespace </span>bm
00061 {
00062 
00063 
00064 <span class="preprocessor">#ifdef BMCOUNTOPT</span>
00065 <span class="preprocessor"></span>
00066 <span class="preprocessor"># define BMCOUNT_INC ++count_;</span>
00067 <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_DEC --count_;</span>
00068 <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_VALID(x) count_is_valid_ = x;</span>
00069 <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_SET(x) count_ = x; count_is_valid_ = true;</span>
00070 <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_ADJ(x) if (x) ++count_; else --count_;</span>
00071 <span class="preprocessor"></span>
00072 <span class="preprocessor">#else</span>
00073 <span class="preprocessor"></span>
<a name="l00074"></a><a class="code" href="a00074.html#a1">00074</a> <span class="preprocessor"># define BMCOUNT_INC</span>
<a name="l00075"></a><a class="code" href="a00074.html#a2">00075</a> <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_DEC</span>
<a name="l00076"></a><a class="code" href="a00074.html#a3">00076</a> <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_VALID(x)</span>
<a name="l00077"></a><a class="code" href="a00074.html#a4">00077</a> <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_SET(x)</span>
<a name="l00078"></a><a class="code" href="a00074.html#a5">00078</a> <span class="preprocessor"></span><span class="preprocessor"># define BMCOUNT_ADJ(x)</span>
00079 <span class="preprocessor"></span>
00080 <span class="preprocessor">#endif</span>
00081 <span class="preprocessor"></span>
00082 
00083 
<a name="l00084"></a><a class="code" href="a00092.html#a0">00084</a> <span class="keyword">typedef</span> <a class="code" href="a00072.html">bm::miniset&lt;bm::block_allocator, bm::set_total_blocks&gt;</a> <a class="code" href="a00072.html">mem_save_set</a>;
00085 
00086 <span class="comment"></span>
00087 <span class="comment">/** @defgroup bmagic BitMagic C++ Library</span>
00088 <span class="comment"> *  For more information please visit:  http://bmagic.sourceforge.net</span>
00089 <span class="comment"> *  </span>
00090 <span class="comment"> */</span>
00091 
00092 <span class="comment"></span>
00093 <span class="comment">/** @defgroup bvector The Main bvector&lt;&gt; Group</span>
00094 <span class="comment"> *  This is the main group. It includes bvector template: front end of the bm library.</span>
00095 <span class="comment"> *  @ingroup bmagic </span>
00096 <span class="comment"> */</span>
00097 
00098 
00099 
00100 <span class="comment"></span>
00101 <span class="comment">/*!</span>
00102 <span class="comment">   @brief bitvector with runtime compression of bits.</span>
00103 <span class="comment">   @ingroup bvector</span>
00104 <span class="comment">*/</span>
00105 
00106 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l00107"></a><a class="code" href="a00048.html">00107</a> <span class="keyword">class </span><a class="code" href="a00048.html">bvector</a>
00108 {
00109 <span class="keyword">public</span>:
00110 
<a name="l00111"></a><a class="code" href="a00048.html#w0">00111</a>     <span class="keyword">typedef</span> Alloc  <a class="code" href="a00048.html#w0">allocator_type</a>;
<a name="l00112"></a><a class="code" href="a00048.html#w1">00112</a>     <span class="keyword">typedef</span> blocks_manager&lt;Alloc, MS&gt;  <a class="code" href="a00048.html#w1">blocks_manager_type</a>;<span class="comment"></span>
00113 <span class="comment">    /** Type used to count bits in the bit vector */</span>
<a name="l00114"></a><a class="code" href="a00048.html#w2">00114</a>     <span class="keyword">typedef</span> bm::id_t                   <a class="code" href="a00048.html#w2">size_type</a>; 
00115 <span class="comment"></span>
00116 <span class="comment">    /*!</span>
00117 <span class="comment">       @brief Structure with statistical information about bitset's memory </span>
00118 <span class="comment">              allocation details. </span>
00119 <span class="comment">       @ingroup bvector</span>
00120 <span class="comment">    */</span>
<a name="l00121"></a><a class="code" href="a00057.html">00121</a>     <span class="keyword">struct </span><a class="code" href="a00057.html">statistics</a>
00122     {<span class="comment"></span>
00123 <span class="comment">        /// Number of bit blocks.</span>
<a name="l00124"></a><a class="code" href="a00057.html#o0">00124</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span> <a class="code" href="a00057.html#o0">bit_blocks</a>; <span class="comment"></span>
00125 <span class="comment">        /// Number of GAP blocks.</span>
<a name="l00126"></a><a class="code" href="a00057.html#o1">00126</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span> <a class="code" href="a00057.html#o1">gap_blocks</a>;  <span class="comment"></span>
00127 <span class="comment">        /// Estimated maximum of memory required for serialization.</span>
<a name="l00128"></a><a class="code" href="a00057.html#o2">00128</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span> <a class="code" href="a00057.html#o2">max_serialize_mem</a>;<span class="comment"></span>
00129 <span class="comment">        /// Memory used by bitvector including temp and service blocks</span>
<a name="l00130"></a><a class="code" href="a00057.html#o3">00130</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span>  <a class="code" href="a00057.html#o3">memory_used</a>;<span class="comment"></span>
00131 <span class="comment">        /// Array of all GAP block lengths in the bvector.</span>
<a name="l00132"></a><a class="code" href="a00057.html#o4">00132</a> <span class="comment"></span>        <a class="code" href="a00092.html#a19">gap_word_t</a>   <a class="code" href="a00057.html#o4">gap_length</a>[bm::set_total_blocks];<span class="comment"></span>
00133 <span class="comment">        /// GAP lengths used by bvector</span>
<a name="l00134"></a><a class="code" href="a00057.html#o5">00134</a> <span class="comment"></span>        <a class="code" href="a00092.html#a19">gap_word_t</a>  <a class="code" href="a00057.html#o5">gap_levels</a>[bm::gap_levels];
00135     };
00136 <span class="comment"></span>
00137 <span class="comment">    /**</span>
00138 <span class="comment">        @brief Class reference implements an object for bit assignment.</span>
00139 <span class="comment">        Since C++ does not provide with build-in bit type supporting l-value </span>
00140 <span class="comment">        operations we have to emulate it.</span>
00141 <span class="comment"></span>
00142 <span class="comment">        @ingroup bvector</span>
00143 <span class="comment">    */</span>
<a name="l00144"></a><a class="code" href="a00056.html">00144</a>     <span class="keyword">class </span><a class="code" href="a00056.html">reference</a>
00145     {
00146     <span class="keyword">public</span>:
<a name="l00147"></a><a class="code" href="a00056.html#a0">00147</a>         <a class="code" href="a00056.html#a0">reference</a>(<a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; bv, bm::id_t position) 
00148         : bv_(bv),
00149           position_(position)
00150         {}
00151 
<a name="l00152"></a><a class="code" href="a00056.html#a1">00152</a>         <a class="code" href="a00056.html#a0">reference</a>(<span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; ref)
00153         : bv_(ref.bv_), 
00154           position_(ref.position_)
00155         {
00156             bv_.set(position_, ref.bv_.get_bit(position_));
00157         }
00158         
<a name="l00159"></a><a class="code" href="a00056.html#a2">00159</a>         <a class="code" href="a00056.html#a2">operator bool</a>()<span class="keyword"> const</span>
00160 <span class="keyword">        </span>{
00161             <span class="keywordflow">return</span> bv_.get_bit(position_);
00162         }
00163 
<a name="l00164"></a><a class="code" href="a00056.html#a3">00164</a>         <span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a3">operator=</a>(<span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; ref)<span class="keyword"> const</span>
00165 <span class="keyword">        </span>{
00166             bv_.set(position_, (<span class="keywordtype">bool</span>)ref);
00167             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00168         }
00169 
<a name="l00170"></a><a class="code" href="a00056.html#a4">00170</a>         <span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a3">operator=</a>(<span class="keywordtype">bool</span> value)<span class="keyword"> const</span>
00171 <span class="keyword">        </span>{
00172             bv_.set(position_, value);
00173             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00174         }
00175 
<a name="l00176"></a><a class="code" href="a00056.html#a5">00176</a>         <span class="keywordtype">bool</span> <a class="code" href="a00056.html#a5">operator==</a>(<span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; ref)<span class="keyword"> const</span>
00177 <span class="keyword">        </span>{
00178             <span class="keywordflow">return</span> bool(*<span class="keyword">this</span>) == bool(ref);
00179         }
00180 <span class="comment"></span>
00181 <span class="comment">        /*! Bitwise AND. Performs operation: bit = bit AND value */</span>
<a name="l00182"></a><a class="code" href="a00056.html#a6">00182</a>         <span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a6">operator&amp;=</a>(<span class="keywordtype">bool</span> value)<span class="keyword"> const</span>
00183 <span class="keyword">        </span>{
00184             bv_.set(position_, value);
00185             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00186         }
00187 <span class="comment"></span>
00188 <span class="comment">        /*! Bitwise OR. Performs operation: bit = bit OR value */</span>
<a name="l00189"></a><a class="code" href="a00056.html#a7">00189</a>         <span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a7">operator|=</a>(<span class="keywordtype">bool</span> value)<span class="keyword"> const</span>
00190 <span class="keyword">        </span>{
00191             <span class="keywordflow">if</span> (value != bv_.get_bit(position_))
00192             {
00193                 bv_.set_bit(position_);
00194             }
00195             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00196         }
00197 <span class="comment"></span>
00198 <span class="comment">        /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */</span>
<a name="l00199"></a><a class="code" href="a00056.html#a8">00199</a>         <span class="keyword">const</span> <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a8">operator^=</a>(<span class="keywordtype">bool</span> value)<span class="keyword"> const</span>
00200 <span class="keyword">        </span>{
00201             bv_.set(position_, value != bv_.get_bit(position_));
00202             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00203         }
00204 <span class="comment"></span>
00205 <span class="comment">        /*! Logical Not operator */</span>
<a name="l00206"></a><a class="code" href="a00056.html#a9">00206</a>         <span class="keywordtype">bool</span> <a class="code" href="a00056.html#a9">operator!</a>()<span class="keyword"> const</span>
00207 <span class="keyword">        </span>{
00208             <span class="keywordflow">return</span> !bv_.get_bit(position_);
00209         }
00210 <span class="comment"></span>
00211 <span class="comment">        /*! Bit Not operator */</span>
<a name="l00212"></a><a class="code" href="a00056.html#a10">00212</a>         <span class="keywordtype">bool</span> <a class="code" href="a00056.html#a10">operator~</a>()<span class="keyword"> const</span>
00213 <span class="keyword">        </span>{
00214             <span class="keywordflow">return</span> !bv_.get_bit(position_);
00215         }
00216 <span class="comment"></span>
00217 <span class="comment">        /*! Negates the bit value */</span>
<a name="l00218"></a><a class="code" href="a00056.html#a11">00218</a>         <a class="code" href="a00056.html">reference</a>&amp; <a class="code" href="a00056.html#a11">flip</a>()
00219         {
00220             bv_.<a class="code" href="a00056.html#a11">flip</a>(position_);
00221             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00222         }
00223 
00224     <span class="keyword">private</span>:
00225         <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; bv_;       <span class="comment">//!&lt; Reference variable on the parent.</span>
00226 <span class="comment"></span>        bm::id_t            position_; <span class="comment">//!&lt; Position in the parent bitvector.</span>
00227 <span class="comment"></span>    };
00228 
<a name="l00229"></a><a class="code" href="a00048.html#w3">00229</a>     <span class="keyword">typedef</span> <span class="keywordtype">bool</span> <a class="code" href="a00048.html#w3">const_reference</a>;
00230 <span class="comment"></span>
00231 <span class="comment">    /*!</span>
00232 <span class="comment">        @brief Base class for all iterators.</span>
00233 <span class="comment">        @ingroup bvector</span>
00234 <span class="comment">    */</span>
<a name="l00235"></a><a class="code" href="a00052.html">00235</a>     <span class="keyword">class </span><a class="code" href="a00052.html">iterator_base</a>
00236     {
<a name="l00237"></a><a class="code" href="a00052.html#n0">00237</a>     <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00048.html">bvector</a>;
00238     <span class="keyword">public</span>:
<a name="l00239"></a><a class="code" href="a00052.html#a0">00239</a>         <a class="code" href="a00052.html#a0">iterator_base</a>() : <a class="code" href="a00052.html#p2">block_</a>(0) {}
00240 
<a name="l00241"></a><a class="code" href="a00052.html#a1">00241</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a1">operator==</a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00242 <span class="keyword">        </span>{
00243             <span class="keywordflow">return</span> (<a class="code" href="a00052.html#p1">position_</a> == it.position_) &amp;&amp; (<a class="code" href="a00052.html#p0">bv_</a> == it.bv_);
00244         }
00245 
<a name="l00246"></a><a class="code" href="a00052.html#a2">00246</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a2">operator!=</a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00247 <span class="keyword">        </span>{
00248             <span class="keywordflow">return</span> ! <a class="code" href="a00052.html#a1">operator==</a>(it);
00249         }
00250 
<a name="l00251"></a><a class="code" href="a00052.html#a3">00251</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a3">operator &lt; </a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00252 <span class="keyword">        </span>{
00253             <span class="keywordflow">return</span> <a class="code" href="a00052.html#p1">position_</a> &lt; it.<a class="code" href="a00056.html#r1">position_</a>;
00254         }
00255 
<a name="l00256"></a><a class="code" href="a00052.html#a4">00256</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a4">operator &lt;= </a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00257 <span class="keyword">        </span>{
00258             <span class="keywordflow">return</span> <a class="code" href="a00052.html#p1">position_</a> &lt;= it.<a class="code" href="a00056.html#r1">position_</a>;
00259         }
00260 
<a name="l00261"></a><a class="code" href="a00052.html#a5">00261</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a5">operator &gt; </a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00262 <span class="keyword">        </span>{
00263             <span class="keywordflow">return</span> <a class="code" href="a00052.html#p1">position_</a> &gt; it.<a class="code" href="a00056.html#r1">position_</a>;
00264         }
00265 
<a name="l00266"></a><a class="code" href="a00052.html#a6">00266</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a6">operator &gt;= </a>(<span class="keyword">const</span> <a class="code" href="a00052.html">iterator_base</a>&amp; it)<span class="keyword"> const</span>
00267 <span class="keyword">        </span>{
00268             <span class="keywordflow">return</span> <a class="code" href="a00052.html#p1">position_</a> &gt;= it.<a class="code" href="a00056.html#r1">position_</a>;
00269         }
00270 <span class="comment"></span>
00271 <span class="comment">        /**</span>
00272 <span class="comment">           \fn bool bm::bvector::iterator_base::valid() const</span>
00273 <span class="comment">           \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.</span>
00274 <span class="comment">           \returns true if iterator is valid.</span>
00275 <span class="comment">        */</span>
<a name="l00276"></a><a class="code" href="a00052.html#a7">00276</a>         <span class="keywordtype">bool</span> <a class="code" href="a00052.html#a7">valid</a>()<span class="keyword"> const</span>
00277 <span class="keyword">        </span>{
00278             <span class="keywordflow">return</span> <a class="code" href="a00052.html#p1">position_</a> != bm::id_max;
00279         }
00280 <span class="comment"></span>
00281 <span class="comment">        /**</span>
00282 <span class="comment">           \fn bool bm::bvector::iterator_base::invalidate() </span>
00283 <span class="comment">           \brief Turns iterator into an invalid state.</span>
00284 <span class="comment">        */</span>
<a name="l00285"></a><a class="code" href="a00052.html#a8">00285</a>         <span class="keywordtype">void</span> <a class="code" href="a00052.html#a8">invalidate</a>()
00286         {
00287             <a class="code" href="a00052.html#p1">position_</a> = bm::id_max;
00288         }
00289 
00290     <span class="keyword">public</span>:
00291 <span class="comment"></span>
00292 <span class="comment">        /** Information about current bitblock. */</span>
<a name="l00293"></a><a class="code" href="a00053.html">00293</a>         <span class="keyword">struct </span><a class="code" href="a00053.html">bitblock_descr</a>
00294         {
<a name="l00295"></a><a class="code" href="a00053.html#o0">00295</a>             <span class="keyword">const</span> bm::word_t*   <a class="code" href="a00053.html#o0">ptr</a>;      <span class="comment">//!&lt; Word pointer.</span>
<a name="l00296"></a><a class="code" href="a00053.html#o1">00296</a> <span class="comment"></span>            <span class="keywordtype">unsigned</span>            <a class="code" href="a00053.html#o1">bits</a>[32]; <span class="comment">//!&lt; Unpacked list of ON bits</span>
<a name="l00297"></a><a class="code" href="a00053.html#o2">00297</a> <span class="comment"></span>            <span class="keywordtype">unsigned</span>            <a class="code" href="a00053.html#o2">idx</a>;      <span class="comment">//!&lt; Current position in the bit list</span>
<a name="l00298"></a><a class="code" href="a00053.html#o3">00298</a> <span class="comment"></span>            <span class="keywordtype">unsigned</span>            <a class="code" href="a00053.html#o3">cnt</a>;      <span class="comment">//!&lt; Number of ON bits</span>
<a name="l00299"></a><a class="code" href="a00053.html#o4">00299</a> <span class="comment"></span>            bm::id_t            <a class="code" href="a00053.html#o4">pos</a>;      <span class="comment">//!&lt; Last bit position before </span>
00300 <span class="comment"></span>        };
00301 <span class="comment"></span>
00302 <span class="comment">        /** Information about current DGAP block. */</span>
<a name="l00303"></a><a class="code" href="a00055.html">00303</a>         <span class="keyword">struct </span><a class="code" href="a00055.html">dgap_descr</a>
00304         {
<a name="l00305"></a><a class="code" href="a00055.html#o0">00305</a>             <span class="keyword">const</span> <a class="code" href="a00092.html#a19">gap_word_t</a>*   <a class="code" href="a00055.html#o0">ptr</a>;       <span class="comment">//!&lt; Word pointer.</span>
<a name="l00306"></a><a class="code" href="a00055.html#o1">00306</a> <span class="comment"></span>            <a class="code" href="a00092.html#a19">gap_word_t</a>          <a class="code" href="a00055.html#o1">gap_len</a>;   <span class="comment">//!&lt; Current dgap length.</span>
00307 <span class="comment"></span>        };
00308 
00309     <span class="keyword">protected</span>:
<a name="l00310"></a><a class="code" href="a00052.html#p0">00310</a>         <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>* <a class="code" href="a00052.html#p0">bv_</a>;         <span class="comment">//!&lt; Pointer on parent bitvector</span>
<a name="l00311"></a><a class="code" href="a00052.html#p1">00311</a> <span class="comment"></span>        bm::id_t                <a class="code" href="a00052.html#p1">position_</a>;   <span class="comment">//!&lt; Bit position (bit idx)</span>
<a name="l00312"></a><a class="code" href="a00052.html#p2">00312</a> <span class="comment"></span>        <span class="keyword">const</span> bm::word_t*       <a class="code" href="a00052.html#p2">block_</a>;      <span class="comment">//!&lt; Block pointer.(NULL-invalid)</span>
<a name="l00313"></a><a class="code" href="a00052.html#p3">00313</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span>                <a class="code" href="a00052.html#p3">block_type_</a>; <span class="comment">//!&lt; Type of block. 0-Bit, 1-GAP</span>
<a name="l00314"></a><a class="code" href="a00052.html#p4">00314</a> <span class="comment"></span>        <span class="keywordtype">unsigned</span>                <a class="code" href="a00052.html#p4">block_idx_</a>;  <span class="comment">//!&lt; Block index</span>
00315 <span class="comment"></span><span class="comment"></span>
00316 <span class="comment">        /*! Block type dependent information for current block. */</span>
<a name="l00317"></a><a class="code" href="a00054.html">00317</a>         <span class="keyword">union </span><a class="code" href="a00054.html">block_descr</a>
00318         {
<a name="l00319"></a><a class="code" href="a00054.html#o0">00319</a>             <a class="code" href="a00053.html">bitblock_descr</a>   <a class="code" href="a00054.html#o0">bit_</a>;  <span class="comment">//!&lt; BitBlock related info.</span>
<a name="l00320"></a><a class="code" href="a00054.html#o1">00320</a> <span class="comment"></span>            <a class="code" href="a00055.html">dgap_descr</a>       <a class="code" href="a00054.html#o1">gap_</a>;  <span class="comment">//!&lt; DGAP block related info.</span>
00321 <span class="comment"></span>        } <a class="code" href="a00052.html#p5">bdescr_</a>;
00322     };
00323 <span class="comment"></span>
00324 <span class="comment">    /*!</span>
00325 <span class="comment">        @brief Output iterator iterator designed to set "ON" bits based on</span>
00326 <span class="comment">        input sequence of integers (bit indeces).</span>
00327 <span class="comment"></span>
00328 <span class="comment">        STL container can be converted to bvector using this iterator</span>
00329 <span class="comment">        Insert iterator guarantees the vector will be dynamically resized</span>
00330 <span class="comment">        (set_bit does not do that).</span>
00331 <span class="comment"></span>
00332 <span class="comment">        @note</span>
00333 <span class="comment">        If you have many bits to set it is a good idea to use output iterator</span>
00334 <span class="comment">        instead of explicitly calling set, because iterator may implement</span>
00335 <span class="comment">        some performance specific tricks to make sure bulk insert is fast.</span>
00336 <span class="comment"></span>
00337 <span class="comment">        @ingroup bvector</span>
00338 <span class="comment">    */</span>
<a name="l00339"></a><a class="code" href="a00051.html">00339</a>     <span class="keyword">class </span><a class="code" href="a00051.html">insert_iterator</a>
00340     {
00341     <span class="keyword">public</span>:
00342 <span class="preprocessor">#ifndef BM_NO_STL</span>
<a name="l00343"></a><a class="code" href="a00051.html#w0">00343</a> <span class="preprocessor"></span>        <span class="keyword">typedef</span> std::output_iterator_tag  <a class="code" href="a00051.html#w0">iterator_category</a>;
00344 <span class="preprocessor">#endif</span>
<a name="l00345"></a><a class="code" href="a00051.html#w1">00345</a> <span class="preprocessor"></span>        <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span> <a class="code" href="a00051.html#w1">value_type</a>;
<a name="l00346"></a><a class="code" href="a00051.html#w2">00346</a>         <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00051.html#w2">difference_type</a>;
<a name="l00347"></a><a class="code" href="a00051.html#w3">00347</a>         <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00051.html#w3">pointer</a>;
<a name="l00348"></a><a class="code" href="a00051.html#w4">00348</a>         <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00056.html">reference</a>;
00349 
<a name="l00350"></a><a class="code" href="a00051.html#a0">00350</a>         <a class="code" href="a00051.html#a0">insert_iterator</a>(<a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00351             : <a class="code" href="a00051.html#p0">bvect_</a>(<a class="code" href="a00048.html">bvect</a>), 
00352               <a class="code" href="a00051.html#p1">max_bit_</a>(<a class="code" href="a00048.html">bvect</a>.size())
00353         {
00354         }
00355         
<a name="l00356"></a><a class="code" href="a00051.html#a1">00356</a>         <a class="code" href="a00051.html">insert_iterator</a>&amp; <a class="code" href="a00051.html#a1">operator=</a>(bm::id_t n)
00357         {
00358             <a class="code" href="a00077.html#a0">BM_ASSERT</a>(n &lt; bm::id_max);
00359 
00360             <span class="keywordflow">if</span> (n &gt;= <a class="code" href="a00051.html#p1">max_bit_</a>) 
00361             {
00362                 <a class="code" href="a00051.html#p1">max_bit_</a> = n;
00363                 <span class="keywordflow">if</span> (n &gt;= <a class="code" href="a00051.html#p0">bvect_</a>.size()) 
00364                 {
00365                     <a class="code" href="a00051.html#p0">bvect_</a>.resize(n + 1);
00366                 }
00367             }
00368 
00369             <a class="code" href="a00051.html#p0">bvect_</a>.set(n);
00370             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00371         }
00372         <span class="comment"></span>
00373 <span class="comment">        /*! Returns *this without doing anything (no-op) */</span>
<a name="l00374"></a><a class="code" href="a00051.html#a2">00374</a>         <a class="code" href="a00051.html">insert_iterator</a>&amp; <a class="code" href="a00051.html#a2">operator*</a>() { <span class="keywordflow">return</span> *<span class="keyword">this</span>; }<span class="comment"></span>
00375 <span class="comment">        /*! Returns *this. This iterator does not move (no-op) */</span>
<a name="l00376"></a><a class="code" href="a00051.html#a3">00376</a>         <a class="code" href="a00051.html">insert_iterator</a>&amp; <a class="code" href="a00051.html#a3">operator++</a>() { <span class="keywordflow">return</span> *<span class="keyword">this</span>; }<span class="comment"></span>
00377 <span class="comment">        /*! Returns *this. This iterator does not move (no-op)*/</span>
<a name="l00378"></a><a class="code" href="a00051.html#a4">00378</a>         <a class="code" href="a00051.html">insert_iterator</a>&amp; <a class="code" href="a00051.html#a3">operator++</a>(<span class="keywordtype">int</span>) { <span class="keywordflow">return</span> *<span class="keyword">this</span>; }
00379         
00380     <span class="keyword">protected</span>:
<a name="l00381"></a><a class="code" href="a00051.html#p0">00381</a>         <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp;   <a class="code" href="a00051.html#p0">bvect_</a>;
<a name="l00382"></a><a class="code" href="a00051.html#p1">00382</a>         bm::id_t                  <a class="code" href="a00051.html#p1">max_bit_</a>;
00383     };
00384 <span class="comment"></span>
00385 <span class="comment">    /*!</span>
00386 <span class="comment">        @brief Constant input iterator designed to enumerate "ON" bits</span>
00387 <span class="comment">        @ingroup bvector</span>
00388 <span class="comment">    */</span>
<a name="l00389"></a><a class="code" href="a00050.html">00389</a>     <span class="keyword">class </span><a class="code" href="a00050.html">enumerator</a> : <span class="keyword">public</span> <a class="code" href="a00052.html">iterator_base</a>
00390     {
00391     <span class="keyword">public</span>:
00392 <span class="preprocessor">#ifndef BM_NO_STL</span>
<a name="l00393"></a><a class="code" href="a00050.html#w0">00393</a> <span class="preprocessor"></span>        <span class="keyword">typedef</span> std::input_iterator_tag  <a class="code" href="a00050.html#w0">iterator_category</a>;
00394 <span class="preprocessor">#endif</span>
<a name="l00395"></a><a class="code" href="a00050.html#w1">00395</a> <span class="preprocessor"></span>        <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span>   <a class="code" href="a00050.html#w1">value_type</a>;
<a name="l00396"></a><a class="code" href="a00050.html#w2">00396</a>         <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span>   <a class="code" href="a00050.html#w2">difference_type</a>;
<a name="l00397"></a><a class="code" href="a00050.html#w3">00397</a>         <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span>*  <a class="code" href="a00050.html#w3">pointer</a>;
<a name="l00398"></a><a class="code" href="a00050.html#w4">00398</a>         <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span>&amp;  <a class="code" href="a00056.html">reference</a>;
00399 
00400     <span class="keyword">public</span>:
<a name="l00401"></a><a class="code" href="a00050.html#a0">00401</a>         <a class="code" href="a00050.html#a0">enumerator</a>() : <a class="code" href="a00052.html">iterator_base</a>() {}
<a name="l00402"></a><a class="code" href="a00050.html#a1">00402</a>         <a class="code" href="a00050.html#a0">enumerator</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>* <a class="code" href="a00048.html">bvect</a>, <span class="keywordtype">int</span> position)
00403             : <a class="code" href="a00052.html">iterator_base</a>()
00404         { 
00405             this-&gt;bv_ = const_cast&lt;bvector&lt;Alloc, MS&gt;*&gt;(<a class="code" href="a00048.html">bvect</a>);
00406             <span class="keywordflow">if</span> (position == 0)
00407             {
00408                 <a class="code" href="a00050.html#a5">go_first</a>();
00409             }
00410             <span class="keywordflow">else</span>
00411             {
00412                 this-&gt;<a class="code" href="a00052.html#a8">invalidate</a>();
00413             }
00414         }
00415 
<a name="l00416"></a><a class="code" href="a00050.html#a2">00416</a>         bm::id_t <a class="code" href="a00050.html#a2">operator*</a>()<span class="keyword"> const</span>
00417 <span class="keyword">        </span>{ 
00418             <span class="keywordflow">return</span> this-&gt;position_; 
00419         }
00420 
<a name="l00421"></a><a class="code" href="a00050.html#a3">00421</a>         <a class="code" href="a00050.html">enumerator</a>&amp; <a class="code" href="a00050.html#a3">operator++</a>()
00422         {
00423             <span class="keywordflow">return</span> this-&gt;<a class="code" href="a00050.html#a6">go_up</a>();
00424         }
00425 
<a name="l00426"></a><a class="code" href="a00050.html#a4">00426</a>         <a class="code" href="a00050.html">enumerator</a> <a class="code" href="a00050.html#a3">operator++</a>(<span class="keywordtype">int</span>)
00427         {
00428             <a class="code" href="a00050.html">enumerator</a> tmp = *<span class="keyword">this</span>;
00429             this-&gt;<a class="code" href="a00050.html#a6">go_up</a>();
00430             <span class="keywordflow">return</span> tmp;
00431         }
00432 
00433 
<a name="l00434"></a><a class="code" href="a00050.html#a5">00434</a>         <span class="keywordtype">void</span> <a class="code" href="a00050.html#a5">go_first</a>()
00435         {
00436             <a class="code" href="a00077.html#a0">BM_ASSERT</a>(this-&gt;bv_);
00437 
00438 <span class="preprocessor">        #ifdef BMCOUNTOPT</span>
00439 <span class="preprocessor"></span>            <span class="keywordflow">if</span> (this-&gt;bv_-&gt;count_is_valid_ &amp;&amp; 
00440                 this-&gt;bv_-&gt;count_ == 0)
00441             {
00442                 this-&gt;<a class="code" href="a00052.html#a8">invalidate</a>();
00443                 <span class="keywordflow">return</span>;
00444             }
00445 <span class="preprocessor">        #endif</span>
00446 <span class="preprocessor"></span>
00447             blocks_manager_type* bman = &amp;(this-&gt;bv_-&gt;blockman_);
00448             bm::word_t*** blk_root = bman-&gt;blocks_root();
00449 
00450             this-&gt;block_idx_ = this-&gt;position_= 0;
00451             <span class="keywordtype">unsigned</span> i, j;
00452 
00453             <span class="keywordflow">for</span> (i = 0; i &lt; bman-&gt;top_block_size(); ++i)
00454             {
00455                 bm::word_t** blk_blk = blk_root[i];
00456 
00457                 <span class="keywordflow">if</span> (blk_blk == 0) <span class="comment">// not allocated</span>
00458                 {
00459                     this-&gt;block_idx_ += bm::set_array_size;
00460                     this-&gt;position_ += bm::bits_in_array;
00461                     <span class="keywordflow">continue</span>;
00462                 }
00463 
00464 
00465                 <span class="keywordflow">for</span> (j = 0; j &lt; bm::set_array_size; ++j,++(this-&gt;block_idx_))
00466                 {
00467                     this-&gt;block_ = blk_blk[j];
00468 
00469                     <span class="keywordflow">if</span> (this-&gt;block_ == 0)
00470                     {
00471                         this-&gt;position_ += <a class="code" href="a00092.html#a29">bits_in_block</a>;
00472                         <span class="keywordflow">continue</span>;
00473                     }
00474 
00475                     <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*bman), this-&gt;block_, this-&gt;block_idx_))
00476                     {
00477                         this-&gt;block_type_ = 1;
00478                         <span class="keywordflow">if</span> (search_in_gapblock())
00479                         {
00480                             <span class="keywordflow">return</span>;
00481                         }
00482                     }
00483                     <span class="keywordflow">else</span>
00484                     {
00485                         this-&gt;block_type_ = 0;
00486                         <span class="keywordflow">if</span> (search_in_bitblock())
00487                         {
00488                             <span class="keywordflow">return</span>;
00489                         }
00490                     }
00491             
00492                 } <span class="comment">// for j</span>
00493 
00494             } <span class="comment">// for i</span>
00495 
00496             this-&gt;<a class="code" href="a00052.html#a8">invalidate</a>();
00497         }
00498 
<a name="l00499"></a><a class="code" href="a00050.html#a6">00499</a>         <a class="code" href="a00050.html">enumerator</a>&amp; <a class="code" href="a00050.html#a6">go_up</a>()
00500         {
00501             <span class="comment">// Current block search.</span>
00502             ++this-&gt;position_;
00503             <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00054.html">iterator_base::block_descr</a> block_descr_type;
00504             
00505             block_descr_type* bdescr = &amp;(this-&gt;bdescr_);
00506 
00507             <span class="keywordflow">switch</span> (this-&gt;block_type_)
00508             {
00509             <span class="keywordflow">case</span> 0:   <span class="comment">//  BitBlock</span>
00510                 {
00511 
00512                 <span class="comment">// check if we can get the value from the </span>
00513                 <span class="comment">// bits cache</span>
00514 
00515                 <span class="keywordtype">unsigned</span> idx = ++(bdescr-&gt;bit_.idx);
00516                 <span class="keywordflow">if</span> (idx &lt; bdescr-&gt;bit_.cnt)
00517                 {
00518                     this-&gt;position_ = bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.pos + 
00519                                       bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.bits[idx];
00520                     <span class="keywordflow">return</span> *<span class="keyword">this</span>; 
00521                 }
00522                 this-&gt;position_ += 31 - bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.bits[--idx];
00523 
00524                 <span class="keyword">const</span> bm::word_t* pend = this-&gt;block_ + bm::set_block_size;
00525 
00526                 <span class="keywordflow">while</span> (++(bdescr-&gt;bit_.ptr) &lt; pend)
00527                 {
00528                     bm::word_t w = *(bdescr-&gt;bit_.ptr);
00529                     <span class="keywordflow">if</span> (w)
00530                     {
00531                         bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.idx = 0;
00532                         bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.pos = this-&gt;position_;
00533                         bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.cnt = <a class="code" href="a00097.html#ga39">bm::bit_list</a>(w, bdescr-&gt;bit_.bits); 
00534                         this-&gt;position_ += bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.bits[0];
00535                         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00536                     }
00537                     <span class="keywordflow">else</span>
00538                     {
00539                         this-&gt;position_ += 32;
00540                     }
00541                 }
00542     
00543                 }
00544                 <span class="keywordflow">break</span>;
00545 
00546             <span class="keywordflow">case</span> 1:   <span class="comment">// DGAP Block</span>
00547                 {
00548                     <span class="keywordflow">if</span> (--(bdescr-&gt;gap_.gap_len))
00549                     {
00550                         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00551                     }
00552 
00553                     <span class="comment">// next gap is "OFF" by definition.</span>
00554                     <span class="keywordflow">if</span> (*(bdescr-&gt;gap_.ptr) == bm::gap_max_bits - 1)
00555                     {
00556                         <span class="keywordflow">break</span>;
00557                     }
00558                     <a class="code" href="a00092.html#a19">gap_word_t</a> prev = *(bdescr-&gt;gap_.ptr);
00559                     <span class="keyword">register</span> <span class="keywordtype">unsigned</span> val = *(++(bdescr-&gt;gap_.ptr));
00560 
00561                     this-&gt;position_ += val - prev;
00562                     <span class="comment">// next gap is now "ON"</span>
00563 
00564                     <span class="keywordflow">if</span> (*(bdescr-&gt;gap_.ptr) == bm::gap_max_bits - 1)
00565                     {
00566                         <span class="keywordflow">break</span>;
00567                     }
00568                     prev = *(bdescr-&gt;gap_.ptr);
00569                     val = *(++(bdescr-&gt;gap_.ptr));
00570                     bdescr-&gt;<a class="code" href="a00054.html#o1">gap_</a>.gap_len = val - prev;
00571                     <span class="keywordflow">return</span> *<span class="keyword">this</span>;  <span class="comment">// next "ON" found;</span>
00572                 }
00573 
00574             <span class="keywordflow">default</span>:
00575                 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(0);
00576 
00577             } <span class="comment">// switch</span>
00578 
00579 
00580             <span class="comment">// next bit not present in the current block</span>
00581             <span class="comment">// keep looking in the next blocks.</span>
00582             ++(this-&gt;block_idx_);
00583             <span class="keywordtype">unsigned</span> i = this-&gt;block_idx_ &gt;&gt; bm::set_array_shift;
00584             <span class="keywordtype">unsigned</span> top_block_size = this-&gt;bv_-&gt;blockman_.top_block_size();
00585             <span class="keywordflow">for</span> (; i &lt; top_block_size; ++i)
00586             {
00587                 bm::word_t** blk_blk = this-&gt;bv_-&gt;blockman_.blocks_root()[i];
00588                 <span class="keywordflow">if</span> (blk_blk == 0)
00589                 {
00590                     this-&gt;block_idx_ += bm::set_array_size;
00591                     this-&gt;position_ += bm::bits_in_array;
00592                     <span class="keywordflow">continue</span>;
00593                 }
00594 
00595                 <span class="keywordtype">unsigned</span> j = this-&gt;block_idx_ &amp; bm::set_array_mask;
00596 
00597                 <span class="keywordflow">for</span>(; j &lt; bm::set_array_size; ++j, ++(this-&gt;block_idx_))
00598                 {
00599                     this-&gt;block_ = blk_blk[j];
00600 
00601                     <span class="keywordflow">if</span> (this-&gt;block_ == 0)
00602                     {
00603                         this-&gt;position_ += bm::bits_in_block;
00604                         <span class="keywordflow">continue</span>;
00605                     }
00606 
00607                     <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a10">BM_IS_GAP</a>((this-&gt;bv_-&gt;blockman_), 
00608                                    this-&gt;block_, 
00609                                    this-&gt;block_idx_))
00610                     {
00611                         this-&gt;block_type_ = 1;
00612                         <span class="keywordflow">if</span> (search_in_gapblock())
00613                         {
00614                             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00615                         }
00616                     }
00617                     <span class="keywordflow">else</span>
00618                     {
00619                         this-&gt;block_type_ = 0;
00620                         <span class="keywordflow">if</span> (search_in_bitblock())
00621                         {
00622                             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00623                         }
00624                     }
00625 
00626             
00627                 } <span class="comment">// for j</span>
00628 
00629             } <span class="comment">// for i</span>
00630 
00631 
00632             this-&gt;<a class="code" href="a00052.html#a8">invalidate</a>();
00633             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00634         }
00635 
00636 
00637     <span class="keyword">private</span>:
00638         <span class="keywordtype">bool</span> search_in_bitblock()
00639         {
00640             <a class="code" href="a00077.html#a0">BM_ASSERT</a>(this-&gt;block_type_ == 0);
00641             
00642             <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00054.html">iterator_base::block_descr</a> block_descr_type;
00643             block_descr_type* bdescr = &amp;(this-&gt;bdescr_);            
00644 
00645             <span class="comment">// now lets find the first bit in block.</span>
00646             bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.ptr = this-&gt;block_;
00647 
00648             <span class="keyword">const</span> <a class="code" href="a00092.html#a10">word_t</a>* ptr_end = this-&gt;block_ + bm::set_block_size;
00649 
00650             <span class="keywordflow">do</span>
00651             {
00652                 <span class="keyword">register</span> bm::word_t w = *(bdescr-&gt;bit_.ptr);
00653 
00654                 <span class="keywordflow">if</span> (w)  
00655                 {
00656                     bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.idx = 0;
00657                     bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.pos = this-&gt;position_;
00658                     bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.cnt = 
00659                               <a class="code" href="a00097.html#ga39">bm::bit_list</a>(w, bdescr-&gt;bit_.bits);
00660                     this-&gt;position_ += bdescr-&gt;<a class="code" href="a00054.html#o0">bit_</a>.bits[0];
00661 
00662                     <span class="keywordflow">return</span> <span class="keyword">true</span>;
00663                 }
00664                 <span class="keywordflow">else</span>
00665                 {
00666                     this-&gt;position_ += 32;
00667                 }
00668 
00669             } 
00670             <span class="keywordflow">while</span> (++(bdescr-&gt;bit_.ptr) &lt; ptr_end);
00671 
00672             <span class="keywordflow">return</span> <span class="keyword">false</span>;
00673         }
00674 
00675         <span class="keywordtype">bool</span> search_in_gapblock()
00676         {
00677             <a class="code" href="a00077.html#a0">BM_ASSERT</a>(this-&gt;block_type_ == 1);
00678 
00679             <span class="keyword">typedef</span> <span class="keyword">typename</span> iterator_base::block_descr block_descr_type;
00680             block_descr_type* bdescr = &amp;(this-&gt;<a class="code" href="a00052.html#p5">bdescr_</a>);            
00681 
00682             bdescr-&gt;<a class="code" href="a00054.html#o1">gap_</a>.ptr = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(this-&gt;block_);
00683             <span class="keywordtype">unsigned</span> bitval = *(bdescr-&gt;gap_.ptr) &amp; 1;
00684 
00685             ++(bdescr-&gt;gap_.ptr);
00686 
00687             <span class="keywordflow">do</span>
00688             {
00689                 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> val = *(bdescr-&gt;gap_.ptr);
00690 
00691                 <span class="keywordflow">if</span> (bitval)
00692                 {
00693                     <a class="code" href="a00092.html#a19">gap_word_t</a>* first = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(this-&gt;block_) + 1;
00694                     <span class="keywordflow">if</span> (bdescr-&gt;gap_.ptr == first)
00695                     {
00696                         bdescr-&gt;<a class="code" href="a00054.html#o1">gap_</a>.gap_len = val + 1;
00697                     }
00698                     <span class="keywordflow">else</span>
00699                     {
00700                         bdescr-&gt;<a class="code" href="a00054.html#o1">gap_</a>.gap_len = 
00701                              val - *(bdescr-&gt;gap_.ptr-1);
00702                     }
00703            
00704                     <span class="keywordflow">return</span> <span class="keyword">true</span>;
00705                 }
00706                 this-&gt;<a class="code" href="a00052.html#p1">position_</a> += val + 1;
00707 
00708                 <span class="keywordflow">if</span> (val == bm::gap_max_bits - 1)
00709                 {
00710                     <span class="keywordflow">break</span>;
00711                 }
00712 
00713                 bitval ^= 1;
00714                 ++(bdescr-&gt;gap_.ptr);
00715 
00716             } <span class="keywordflow">while</span> (1);
00717 
00718             <span class="keywordflow">return</span> <span class="keyword">false</span>;
00719         }
00720 
00721     };
00722     <span class="comment"></span>
00723 <span class="comment">    /*!</span>
00724 <span class="comment">        @brief Constant input iterator designed to enumerate "ON" bits</span>
00725 <span class="comment">        counted_enumerator keeps bitcount, ie number of ON bits starting</span>
00726 <span class="comment">        from the position 0 in the bit string up to the currently enumerated bit</span>
00727 <span class="comment">        </span>
00728 <span class="comment">        When increment operator called current position is increased by 1.</span>
00729 <span class="comment">        </span>
00730 <span class="comment">        @ingroup bvector</span>
00731 <span class="comment">    */</span>
<a name="l00732"></a><a class="code" href="a00049.html">00732</a>     <span class="keyword">class </span><a class="code" href="a00049.html">counted_enumerator</a> : <span class="keyword">public</span> <a class="code" href="a00050.html">enumerator</a>
00733     {
00734     <span class="keyword">public</span>:
00735 <span class="preprocessor">#ifndef BM_NO_STL</span>
<a name="l00736"></a><a class="code" href="a00049.html#w0">00736</a> <span class="preprocessor"></span>        <span class="keyword">typedef</span> std::input_iterator_tag  <a class="code" href="a00049.html#w0">iterator_category</a>;
00737 <span class="preprocessor">#endif</span>
<a name="l00738"></a><a class="code" href="a00049.html#a0">00738</a> <span class="preprocessor"></span>        <a class="code" href="a00049.html#a0">counted_enumerator</a>() : bit_count_(0){}
00739         
<a name="l00740"></a><a class="code" href="a00049.html#a1">00740</a>         <a class="code" href="a00049.html#a0">counted_enumerator</a>(<span class="keyword">const</span> <a class="code" href="a00050.html">enumerator</a>&amp; en)
00741         : <a class="code" href="a00050.html">enumerator</a>(en)
00742         {
00743             <span class="keywordflow">if</span> (this-&gt;valid())
00744                 bit_count_ = 1;
00745         }
00746         
<a name="l00747"></a><a class="code" href="a00049.html#a2">00747</a>         <a class="code" href="a00049.html">counted_enumerator</a>&amp; <a class="code" href="a00049.html#a2">operator=</a>(<span class="keyword">const</span> <a class="code" href="a00050.html">enumerator</a>&amp; en)
00748         {
00749             <a class="code" href="a00050.html">enumerator</a>* me = <span class="keyword">this</span>;
00750             *me = en;
00751             <span class="keywordflow">if</span> (this-&gt;valid())
00752                 this-&gt;bit_count_ = 1;
00753             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00754         }
00755         
<a name="l00756"></a><a class="code" href="a00049.html#a3">00756</a>         <a class="code" href="a00049.html">counted_enumerator</a>&amp; <a class="code" href="a00049.html#a3">operator++</a>()
00757         {
00758             this-&gt;<a class="code" href="a00050.html#a6">go_up</a>();
00759             <span class="keywordflow">if</span> (this-&gt;valid())
00760                 ++(this-&gt;bit_count_);
00761             <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00762         }
00763 
<a name="l00764"></a><a class="code" href="a00049.html#a4">00764</a>         <a class="code" href="a00049.html">counted_enumerator</a> <a class="code" href="a00049.html#a3">operator++</a>(<span class="keywordtype">int</span>)
00765         {
00766             <a class="code" href="a00049.html">counted_enumerator</a> tmp(*<span class="keyword">this</span>);
00767             this-&gt;<a class="code" href="a00050.html#a6">go_up</a>();
00768             <span class="keywordflow">if</span> (this-&gt;valid())
00769                 ++bit_count_;
00770             <span class="keywordflow">return</span> tmp;
00771         }
00772         <span class="comment"></span>
00773 <span class="comment">        /*! @brief Number of bits ON starting from the .</span>
00774 <span class="comment">        </span>
00775 <span class="comment">            Method returns number of ON bits fromn the bit 0 to the current bit </span>
00776 <span class="comment">            For the first bit in bitvector it is 1, for the second 2 </span>
00777 <span class="comment">        */</span>
<a name="l00778"></a><a class="code" href="a00049.html#a5">00778</a>         bm::id_t <a class="code" href="a00049.html#a5">count</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> bit_count_; }
00779         
00780     <span class="keyword">private</span>:
00781         bm::id_t   bit_count_;
00782     };
00783 
<a name="l00784"></a><a class="code" href="a00048.html#n0">00784</a>     <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00052.html">iterator_base</a>;
<a name="l00785"></a><a class="code" href="a00048.html#n1">00785</a>     <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00050.html">enumerator</a>;
00786 
00787 <span class="keyword">public</span>:
00788 
00789 <span class="preprocessor">#ifdef BMCOUNTOPT</span>
00790 <span class="preprocessor"></span>    <a class="code" href="a00048.html#a0">bvector</a>(strategy          strat      = BM_BIT,
00791             <span class="keyword">const</span> gap_word_t* glevel_len = <a class="code" href="a00068.html">bm::gap_len_table&lt;true&gt;</a>::_len,
00792             size_type         bv_size    = bm::id_max,
00793             <span class="keyword">const</span> Alloc&amp;      alloc      = Alloc()) 
00794     : count_(0),
00795       count_is_valid_(true),
00796       blockman_(glevel_len, bv_size, alloc),
00797       new_blocks_strat_(strat),
00798       size_(bv_size)
00799     {}
00800 
00801     <a class="code" href="a00048.html#a0">bvector</a>(size_type         bv_size,
00802             bm::strategy      strat      = BM_BIT,
00803             <span class="keyword">const</span> gap_word_t* glevel_len = <a class="code" href="a00068.html">bm::gap_len_table&lt;true&gt;</a>::_len,
00804             <span class="keyword">const</span> Alloc&amp;      alloc = Alloc()) 
00805     : count_(0),
00806       count_is_valid_(true),
00807       blockman_(glevel_len, bv_size, alloc),
00808       new_blocks_strat_(strat),
00809       size_(bv_size)
00810     {}
00811 
00812 
00813     <a class="code" href="a00048.html#a0">bvector</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00814      : count_(<a class="code" href="a00048.html">bvect</a>.count_),
00815        count_is_valid_(<a class="code" href="a00048.html">bvect</a>.count_is_valid_),
00816        blockman_(<a class="code" href="a00048.html">bvect</a>.blockman_),
00817        new_blocks_strat_(<a class="code" href="a00048.html">bvect</a>.new_blocks_strat_),
00818        size_(<a class="code" href="a00048.html">bvect</a>.size_)
00819     {}
00820 
00821 <span class="preprocessor">#else</span>
00822 <span class="preprocessor"></span><span class="comment">    /*!</span>
00823 <span class="comment">        \brief Constructs bvector class</span>
00824 <span class="comment">        \param strat - operation mode strategy, </span>
00825 <span class="comment">                       BM_BIT - default strategy, bvector use plain bitset </span>
00826 <span class="comment">                       blocks, (performance oriented strategy).</span>
00827 <span class="comment">                       BM_GAP - memory effitent strategy, bvector allocates </span>
00828 <span class="comment">                       blocks as array of intervals(gaps) and convert blocks </span>
00829 <span class="comment">                       into plain bitsets only when enthropy grows.</span>
00830 <span class="comment">        \param glevel_len </span>
00831 <span class="comment">           - pointer on C-style array keeping GAP block sizes. </span>
00832 <span class="comment">            (Put bm::gap_len_table_min&lt;true&gt;::_len for GAP memory saving mode)</span>
00833 <span class="comment">        \param bv_size </span>
00834 <span class="comment">          - bvector size (number of bits addressable by bvector), bm::id_max means </span>
00835 <span class="comment">          "no limits" (recommended). </span>
00836 <span class="comment">          bit vector allocates this space dynamically on demand.</span>
00837 <span class="comment"></span>
00838 <span class="comment">        \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat</span>
00839 <span class="comment">    */</span>
<a name="l00840"></a><a class="code" href="a00048.html#a0">00840</a>     <a class="code" href="a00048.html#a0">bvector</a>(strategy          strat      = BM_BIT,
00841             <span class="keyword">const</span> gap_word_t* glevel_len = <a class="code" href="a00068.html">bm::gap_len_table&lt;true&gt;</a>::_len,
00842             size_type         bv_size    = bm::id_max,
00843             <span class="keyword">const</span> Alloc&amp;      alloc      = Alloc()) 
00844     : blockman_(glevel_len, bv_size, alloc),
00845       new_blocks_strat_(strat),
00846       size_(bv_size)
00847     {}
00848 <span class="comment"></span>
00849 <span class="comment">    /*!</span>
00850 <span class="comment">        \brief Constructs bvector class</span>
00851 <span class="comment">    */</span>
<a name="l00852"></a><a class="code" href="a00048.html#a1">00852</a>     <a class="code" href="a00048.html#a0">bvector</a>(size_type         bv_size,
00853             strategy          strat      = BM_BIT,
00854             <span class="keyword">const</span> gap_word_t* glevel_len = <a class="code" href="a00068.html">bm::gap_len_table&lt;true&gt;</a>::_len,
00855             <span class="keyword">const</span> Alloc&amp;      alloc      = Alloc()) 
00856     : blockman_(glevel_len, bv_size, alloc),
00857       new_blocks_strat_(strat),
00858       size_(bv_size)
00859     {}
00860 
00861 
<a name="l00862"></a><a class="code" href="a00048.html#a2">00862</a>     <a class="code" href="a00048.html#a0">bvector</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00863         :  blockman_(<a class="code" href="a00048.html">bvect</a>.blockman_),
00864            new_blocks_strat_(<a class="code" href="a00048.html">bvect</a>.new_blocks_strat_),
00865            size_(<a class="code" href="a00048.html">bvect</a>.size_)
00866     {}
00867 
00868 <span class="preprocessor">#endif</span>
00869 <span class="preprocessor"></span>
<a name="l00870"></a><a class="code" href="a00048.html#a3">00870</a>     <a class="code" href="a00048.html">bvector</a>&amp; <a class="code" href="a00048.html#a3">operator=</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00871     {
00872         <a class="code" href="a00048.html#a24">clear</a>(<span class="keyword">true</span>); <span class="comment">// memory free cleaning</span>
00873         <a class="code" href="a00048.html#a29">resize</a>(<a class="code" href="a00048.html">bvect</a>.size());
00874         <a class="code" href="a00048.html#a46">bit_or</a>(<a class="code" href="a00048.html">bvect</a>);
00875         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00876     }
00877 
<a name="l00878"></a><a class="code" href="a00048.html#a4">00878</a>     <a class="code" href="a00056.html">reference</a> <a class="code" href="a00048.html#a4">operator[]</a>(bm::id_t n)
00879     {
00880         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(n &lt; size_);
00881         <span class="keywordflow">return</span> <a class="code" href="a00056.html">reference</a>(*<span class="keyword">this</span>, n);
00882     }
00883 
00884 
<a name="l00885"></a><a class="code" href="a00048.html#a5">00885</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a4">operator[]</a>(bm::id_t n)<span class="keyword"> const</span>
00886 <span class="keyword">    </span>{
00887         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(n &lt; size_);
00888         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a35">get_bit</a>(n);
00889     }
00890 
<a name="l00891"></a><a class="code" href="a00048.html#a6">00891</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a6">operator &amp;= </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00892     {
00893         <a class="code" href="a00048.html#a47">bit_and</a>(<a class="code" href="a00048.html">bvect</a>);
00894     }
00895 
<a name="l00896"></a><a class="code" href="a00048.html#a7">00896</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a7">operator ^= </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00897     {
00898         <a class="code" href="a00048.html#a48">bit_xor</a>(<a class="code" href="a00048.html">bvect</a>);
00899     }
00900 
<a name="l00901"></a><a class="code" href="a00048.html#a8">00901</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a8">operator |= </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00902     {
00903         <a class="code" href="a00048.html#a46">bit_or</a>(<a class="code" href="a00048.html">bvect</a>);
00904     }
00905 
<a name="l00906"></a><a class="code" href="a00048.html#a9">00906</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a9">operator -= </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00907     {
00908         <a class="code" href="a00048.html#a49">bit_sub</a>(<a class="code" href="a00048.html">bvect</a>);
00909     }
00910 
<a name="l00911"></a><a class="code" href="a00048.html#a10">00911</a>     <span class="keywordtype">bool</span> operator &lt; (const bvector&lt;Alloc, MS&gt;&amp; <a class="code" href="a00048.html">bvect</a>) <span class="keyword">const</span>
00912     {
00913         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) &lt; 0;
00914     }
00915 
<a name="l00916"></a><a class="code" href="a00048.html#a11">00916</a>     <span class="keywordtype">bool</span> operator &lt;= (const bvector&lt;Alloc, MS&gt;&amp; <a class="code" href="a00048.html">bvect</a>) <span class="keyword">const</span>
00917     {
00918         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) &lt;= 0;
00919     }
00920 
<a name="l00921"></a><a class="code" href="a00048.html#a12">00921</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a12">operator &gt; </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)<span class="keyword"> const</span>
00922 <span class="keyword">    </span>{
00923         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) &gt; 0;
00924     }
00925 
<a name="l00926"></a><a class="code" href="a00048.html#a13">00926</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a13">operator &gt;= </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)<span class="keyword"> const</span>
00927 <span class="keyword">    </span>{
00928         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) &gt;= 0;
00929     }
00930 
<a name="l00931"></a><a class="code" href="a00048.html#a14">00931</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a14">operator == </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)<span class="keyword"> const</span>
00932 <span class="keyword">    </span>{
00933         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) == 0;
00934     }
00935 
<a name="l00936"></a><a class="code" href="a00048.html#a15">00936</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a15">operator != </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)<span class="keyword"> const</span>
00937 <span class="keyword">    </span>{
00938         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a56">compare</a>(<a class="code" href="a00048.html">bvect</a>) != 0;
00939     }
00940 
<a name="l00941"></a><a class="code" href="a00048.html#a16">00941</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> <a class="code" href="a00048.html#a16">operator~</a>()<span class="keyword"> const</span>
00942 <span class="keyword">    </span>{
00943         <span class="keywordflow">return</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>(*this).invert();
00944     }
00945     
<a name="l00946"></a><a class="code" href="a00048.html#a17">00946</a>     Alloc <a class="code" href="a00048.html#a17">get_allocator</a>()<span class="keyword"> const</span>
00947 <span class="keyword">    </span>{
00948         <span class="keywordflow">return</span> blockman_.get_allocator();
00949     }
00950 
00951 <span class="comment"></span>
00952 <span class="comment">    /*!</span>
00953 <span class="comment">       \brief Sets bit n.</span>
00954 <span class="comment">       \param n - index of the bit to be set. </span>
00955 <span class="comment">       \param val - new bit value</span>
00956 <span class="comment">       \return  TRUE if bit was changed</span>
00957 <span class="comment">    */</span>
<a name="l00958"></a><a class="code" href="a00048.html#a18">00958</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a18">set_bit</a>(bm::id_t n, <span class="keywordtype">bool</span> val = <span class="keyword">true</span>)
00959     {
00960         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(n &lt; size_);
00961         <span class="keywordflow">return</span> set_bit_no_check(n, val);
00962     }
00963 
00964 <span class="comment"></span>
00965 <span class="comment">    /*!</span>
00966 <span class="comment">        \brief Sets bit n if val is true, clears bit n if val is false</span>
00967 <span class="comment">        \param n - index of the bit to be set</span>
00968 <span class="comment">        \param val - new bit value</span>
00969 <span class="comment">        \return *this</span>
00970 <span class="comment">    */</span>
<a name="l00971"></a><a class="code" href="a00048.html#a19">00971</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a20">set</a>(bm::id_t n, <span class="keywordtype">bool</span> val = <span class="keyword">true</span>)
00972     {
00973         <a class="code" href="a00048.html#a18">set_bit</a>(n, val);
00974         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00975     }
00976 
00977 
00978 <span class="comment"></span>
00979 <span class="comment">    /*!</span>
00980 <span class="comment">       \brief Sets every bit in this bitset to 1.</span>
00981 <span class="comment">       \return *this</span>
00982 <span class="comment">    */</span>
<a name="l00983"></a><a class="code" href="a00048.html#a20">00983</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a20">set</a>()
00984     {
00985         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)
00986         <a class="code" href="a00048.html#a21">set_range</a>(0, size_ - 1, <span class="keyword">true</span>);
00987         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00988     }
00989 
00990 <span class="comment"></span>
00991 <span class="comment">    /*!</span>
00992 <span class="comment">        \brief Sets all bits in the specified closed interval [left,right]</span>
00993 <span class="comment">        Interval must be inside the bvector's size. </span>
00994 <span class="comment">        This method DOES NOT resize vector.</span>
00995 <span class="comment">        </span>
00996 <span class="comment">        \param left  - interval start</span>
00997 <span class="comment">        \param right - interval end (closed interval)</span>
00998 <span class="comment">        \param value - value to set interval in</span>
00999 <span class="comment">        </span>
01000 <span class="comment">        \return *this</span>
01001 <span class="comment">    */</span>
01002     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a21">set_range</a>(bm::id_t left,
01003                                   bm::id_t right,
01004                                   <span class="keywordtype">bool</span>     value = <span class="keyword">true</span>);
01005 
01006     <span class="comment"></span>
01007 <span class="comment">    /*! Function erturns insert iterator for this bitvector */</span>
<a name="l01008"></a><a class="code" href="a00048.html#a22">01008</a>     <a class="code" href="a00051.html">insert_iterator</a> <a class="code" href="a00048.html#a22">inserter</a>()
01009     {
01010         <span class="keywordflow">return</span> <a class="code" href="a00051.html">insert_iterator</a>(*<span class="keyword">this</span>);
01011     }
01012 
01013 <span class="comment"></span>
01014 <span class="comment">    /*!</span>
01015 <span class="comment">       \brief Clears bit n.</span>
01016 <span class="comment">       \param n - bit's index to be cleaned.</span>
01017 <span class="comment">    */</span>
<a name="l01018"></a><a class="code" href="a00048.html#a23">01018</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a23">clear_bit</a>(bm::id_t n)
01019     {
01020         <a class="code" href="a00048.html#a20">set</a>(n, <span class="keyword">false</span>);
01021     }
01022 
01023 <span class="comment"></span>
01024 <span class="comment">    /*!</span>
01025 <span class="comment">       \brief Clears every bit in the bitvector.</span>
01026 <span class="comment"></span>
01027 <span class="comment">       \param free_mem if "true" (default) bvector frees the memory,</span>
01028 <span class="comment">       otherwise sets blocks to 0.</span>
01029 <span class="comment">    */</span>
<a name="l01030"></a><a class="code" href="a00048.html#a24">01030</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a24">clear</a>(<span class="keywordtype">bool</span> free_mem = <span class="keyword">false</span>)
01031     {
01032         blockman_.set_all_zero(free_mem);
01033         <a class="code" href="a00074.html#a4">BMCOUNT_SET</a>(0);
01034     }
01035 <span class="comment"></span>
01036 <span class="comment">    /*!</span>
01037 <span class="comment">       \brief Clears every bit in the bitvector.</span>
01038 <span class="comment">       \return *this;</span>
01039 <span class="comment">    */</span>
<a name="l01040"></a><a class="code" href="a00048.html#a25">01040</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a25">reset</a>()
01041     {
01042         <a class="code" href="a00048.html#a24">clear</a>();
01043         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01044     }
01045 
01046 <span class="comment"></span>
01047 <span class="comment">    /*!</span>
01048 <span class="comment">       \brief Returns count of bits which are 1.</span>
01049 <span class="comment">       \return Total number of bits ON. </span>
01050 <span class="comment">    */</span>
01051     bm::id_t <a class="code" href="a00048.html#a26">count</a>() <span class="keyword">const</span>;
01052 <span class="comment"></span>
01053 <span class="comment">    /**</span>
01054 <span class="comment">        \brief Returns bvector's capacity (number of bits it can store)</span>
01055 <span class="comment">    */</span>
<a name="l01056"></a><a class="code" href="a00048.html#a27">01056</a>     <a class="code" href="a00048.html#w2">size_type</a> <a class="code" href="a00048.html#a27">capacity</a>()<span class="keyword"> const </span>
01057 <span class="keyword">    </span>{
01058         <span class="keywordflow">return</span> blockman_.capacity();
01059     }
01060 <span class="comment"></span>
01061 <span class="comment">    /*!</span>
01062 <span class="comment">        \brief return current size of the vector (bits)</span>
01063 <span class="comment">    */</span>
<a name="l01064"></a><a class="code" href="a00048.html#a28">01064</a>     <a class="code" href="a00048.html#w2">size_type</a> <a class="code" href="a00048.html#a28">size</a>()<span class="keyword"> const </span>
01065 <span class="keyword">    </span>{
01066         <span class="keywordflow">return</span> size_;
01067     }
01068 <span class="comment"></span>
01069 <span class="comment">    /*!</span>
01070 <span class="comment">        \brief Change size of the bvector</span>
01071 <span class="comment">        \param new_size - new size in bits</span>
01072 <span class="comment">    */</span>
01073     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a29">resize</a>(size_type new_size);
01074 <span class="comment"></span>
01075 <span class="comment">    /*! \brief Computes bitcount values for all bvector blocks</span>
01076 <span class="comment">        \param arr - pointer on array of block bit counts</span>
01077 <span class="comment">        \return Index of the last block counted. </span>
01078 <span class="comment">        This number +1 gives you number of arr elements initialized during the</span>
01079 <span class="comment">        function call.</span>
01080 <span class="comment">    */</span>
<a name="l01081"></a><a class="code" href="a00048.html#a30">01081</a>     <span class="keywordtype">unsigned</span> <a class="code" href="a00048.html#a30">count_blocks</a>(<span class="keywordtype">unsigned</span>* arr)<span class="keyword"> const</span>
01082 <span class="keyword">    </span>{
01083         bm::word_t*** blk_root = blockman_.get_rootblock();
01084         <span class="keyword">typename</span> blocks_manager_type::block_count_arr_func func(blockman_, &amp;(arr[0]));
01085         <a class="code" href="a00092.html#a53">for_each_nzblock</a>(blk_root, blockman_.top_block_size(), 
01086                                    bm::set_array_size, func);
01087         <span class="keywordflow">return</span> func.last_block();
01088     }
01089 <span class="comment"></span>
01090 <span class="comment">    /*!</span>
01091 <span class="comment">       \brief Returns count of 1 bits in the given diapason.</span>
01092 <span class="comment">       \param left - index of first bit start counting from</span>
01093 <span class="comment">       \param right - index of last bit </span>
01094 <span class="comment">       \param block_count_arr - optional parameter (bitcount by bvector blocks)</span>
01095 <span class="comment">              calculated by count_blocks method. Used to improve performance of</span>
01096 <span class="comment">              wide range searches</span>
01097 <span class="comment">       \return Total number of bits ON. </span>
01098 <span class="comment">    */</span>
01099     bm::id_t <a class="code" href="a00048.html#a31">count_range</a>(bm::id_t left, 
01100                          bm::id_t right, 
01101                          <span class="keywordtype">unsigned</span>* block_count_arr=0) <span class="keyword">const</span>;
01102 
01103 
<a name="l01104"></a><a class="code" href="a00048.html#a32">01104</a>     bm::id_t <a class="code" href="a00048.html#a32">recalc_count</a>()
01105     {
01106         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)
01107         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a26">count</a>();
01108     }
01109     <span class="comment"></span>
01110 <span class="comment">    /*!</span>
01111 <span class="comment">        Disables count cache. Next call to count() or recalc_count()</span>
01112 <span class="comment">        restores count caching.</span>
01113 <span class="comment">        </span>
01114 <span class="comment">        @note Works only if BMCOUNTOPT enabled(defined). </span>
01115 <span class="comment">        Othewise does nothing.</span>
01116 <span class="comment">    */</span>
<a name="l01117"></a><a class="code" href="a00048.html#a33">01117</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a33">forget_count</a>()
01118     {
01119         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)    
01120     }
01121 <span class="comment"></span>
01122 <span class="comment">    /*!</span>
01123 <span class="comment">        \brief Inverts all bits.</span>
01124 <span class="comment">    */</span>
01125     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a34">invert</a>();
01126 
01127 <span class="comment"></span>
01128 <span class="comment">    /*!</span>
01129 <span class="comment">       \brief returns true if bit n is set and false is bit n is 0. </span>
01130 <span class="comment">       \param n - Index of the bit to check.</span>
01131 <span class="comment">       \return Bit value (1 or 0)</span>
01132 <span class="comment">    */</span>
01133     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a35">get_bit</a>(bm::id_t n) <span class="keyword">const</span>;
01134 <span class="comment"></span>
01135 <span class="comment">    /*!</span>
01136 <span class="comment">       \brief returns true if bit n is set and false is bit n is 0. </span>
01137 <span class="comment">       \param n - Index of the bit to check.</span>
01138 <span class="comment">       \return Bit value (1 or 0)</span>
01139 <span class="comment">    */</span>
<a name="l01140"></a><a class="code" href="a00048.html#a36">01140</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a36">test</a>(bm::id_t n)<span class="keyword"> const </span>
01141 <span class="keyword">    </span>{ 
01142         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a35">get_bit</a>(n); 
01143     }
01144 <span class="comment"></span>
01145 <span class="comment">    /*!</span>
01146 <span class="comment">       \brief Returns true if any bits in this bitset are set, and otherwise returns false.</span>
01147 <span class="comment">       \return true if any bit is set</span>
01148 <span class="comment">    */</span>
<a name="l01149"></a><a class="code" href="a00048.html#a37">01149</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a37">any</a>()<span class="keyword"> const</span>
01150 <span class="keyword">    </span>{
01151 <span class="preprocessor">    #ifdef BMCOUNTOPT</span>
01152 <span class="preprocessor"></span>        <span class="keywordflow">if</span> (count_is_valid_ &amp;&amp; count_) <span class="keywordflow">return</span> <span class="keyword">true</span>;
01153 <span class="preprocessor">    #endif</span>
01154 <span class="preprocessor"></span>        
01155         <a class="code" href="a00092.html#a10">word_t</a>*** blk_root = blockman_.get_rootblock();
01156         <span class="keywordflow">if</span> (!blk_root) <span class="keywordflow">return</span> <span class="keyword">false</span>;
01157         <span class="keyword">typename</span> blocks_manager_type::block_any_func func(blockman_);
01158         <span class="keywordflow">return</span> <a class="code" href="a00092.html#a54">for_each_nzblock_if</a>(blk_root, blockman_.top_block_size(),
01159                                              bm::set_array_size, func);
01160     }
01161 <span class="comment"></span>
01162 <span class="comment">    /*!</span>
01163 <span class="comment">        \brief Returns true if no bits are set, otherwise returns false.</span>
01164 <span class="comment">    */</span>
<a name="l01165"></a><a class="code" href="a00048.html#a38">01165</a>     <span class="keywordtype">bool</span> <a class="code" href="a00048.html#a38">none</a>()<span class="keyword"> const</span>
01166 <span class="keyword">    </span>{
01167         <span class="keywordflow">return</span> !<a class="code" href="a00048.html#a37">any</a>();
01168     }
01169 <span class="comment"></span>
01170 <span class="comment">    /*!</span>
01171 <span class="comment">       \brief Flips bit n</span>
01172 <span class="comment">       \return *this</span>
01173 <span class="comment">    */</span>
<a name="l01174"></a><a class="code" href="a00048.html#a39">01174</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a40">flip</a>(bm::id_t n) 
01175     {
01176         <a class="code" href="a00048.html#a20">set</a>(n, !<a class="code" href="a00048.html#a35">get_bit</a>(n));
01177         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01178     }
01179 <span class="comment"></span>
01180 <span class="comment">    /*!</span>
01181 <span class="comment">       \brief Flips all bits</span>
01182 <span class="comment">       \return *this</span>
01183 <span class="comment">    */</span>
<a name="l01184"></a><a class="code" href="a00048.html#a40">01184</a>     <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a40">flip</a>() 
01185     {
01186         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a34">invert</a>();
01187     }
01188 <span class="comment"></span>
01189 <span class="comment">    /*! \brief Exchanges content of bv and this bitvector.</span>
01190 <span class="comment">    */</span>
<a name="l01191"></a><a class="code" href="a00048.html#a41">01191</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a41">swap</a>(<a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; bv)
01192     {
01193         <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;bv) 
01194         {
01195             blockman_.swap(bv.blockman_);
01196             <a class="code" href="a00092.html#a48">bm::xor_swap</a>(size_,bv.size_);
01197 <span class="preprocessor">    #ifdef BMCOUNTOPT</span>
01198 <span class="preprocessor"></span>            <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)
01199             bv.recalc_count();
01200 <span class="preprocessor">    #endif</span>
01201 <span class="preprocessor"></span>        }
01202     }
01203 
01204 <span class="comment"></span>
01205 <span class="comment">    /*!</span>
01206 <span class="comment">       \fn bm::id_t bvector::get_first() const</span>
01207 <span class="comment">       \brief Gets number of first bit which is ON.</span>
01208 <span class="comment">       \return Index of the first 1 bit.</span>
01209 <span class="comment">       \sa get_next</span>
01210 <span class="comment">    */</span>
<a name="l01211"></a><a class="code" href="a00048.html#a42">01211</a>     bm::id_t <a class="code" href="a00048.html#a42">get_first</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> check_or_next(0); }
01212 <span class="comment"></span>
01213 <span class="comment">    /*!</span>
01214 <span class="comment">       \fn bm::id_t bvector::get_next(bm::id_t prev) const</span>
01215 <span class="comment">       \brief Finds the number of the next bit ON.</span>
01216 <span class="comment">       \param prev - Index of the previously found bit. </span>
01217 <span class="comment">       \return Index of the next bit which is ON or 0 if not found.</span>
01218 <span class="comment">       \sa get_first</span>
01219 <span class="comment">    */</span>
<a name="l01220"></a><a class="code" href="a00048.html#a43">01220</a>     bm::id_t <a class="code" href="a00048.html#a43">get_next</a>(bm::id_t prev)<span class="keyword"> const</span>
01221 <span class="keyword">    </span>{
01222         <span class="keywordflow">return</span> (++prev == bm::id_max) ? 0 : check_or_next(prev);
01223     }
01224 
<a name="l01225"></a><a class="code" href="a00048.html#a44">01225</a>     bm::id_t <a class="code" href="a00048.html#a44">extract_next</a>(bm::id_t prev)
01226     {
01227         <span class="keywordflow">return</span> (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
01228     }
01229 
01230 <span class="comment"></span>
01231 <span class="comment">    /*!</span>
01232 <span class="comment">       @brief Calculates bitvector statistics.</span>
01233 <span class="comment"></span>
01234 <span class="comment">       @param st - pointer on statistics structure to be filled in. </span>
01235 <span class="comment"></span>
01236 <span class="comment">       Function fills statistics structure containing information about how </span>
01237 <span class="comment">       this vector uses memory and estimation of max. amount of memory </span>
01238 <span class="comment">       bvector needs to serialize itself.</span>
01239 <span class="comment"></span>
01240 <span class="comment">       @sa statistics</span>
01241 <span class="comment">    */</span>
01242     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a45">calc_stat</a>(<span class="keyword">struct</span> statistics* st) <span class="keyword">const</span>;
01243 <span class="comment"></span>
01244 <span class="comment">    /*!</span>
01245 <span class="comment">       \brief Logical OR operation.</span>
01246 <span class="comment">       \param vect - Argument vector.</span>
01247 <span class="comment">    */</span>
<a name="l01248"></a><a class="code" href="a00048.html#a46">01248</a>     <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a46">bit_or</a>(<span class="keyword">const</span>  <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; vect)
01249     {
01250         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>);
01251         combine_operation(vect, <a class="code" href="a00092.html#a159a2">BM_OR</a>);
01252         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01253     }
01254 <span class="comment"></span>
01255 <span class="comment">    /*!</span>
01256 <span class="comment">       \brief Logical AND operation.</span>
01257 <span class="comment">       \param vect - Argument vector.</span>
01258 <span class="comment">    */</span>
<a name="l01259"></a><a class="code" href="a00048.html#a47">01259</a>     <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a47">bit_and</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; vect)
01260     {
01261         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>);
01262         combine_operation(vect, <a class="code" href="a00092.html#a159a1">BM_AND</a>);
01263         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01264     }
01265 <span class="comment"></span>
01266 <span class="comment">    /*!</span>
01267 <span class="comment">       \brief Logical XOR operation.</span>
01268 <span class="comment">       \param vect - Argument vector.</span>
01269 <span class="comment">    */</span>
<a name="l01270"></a><a class="code" href="a00048.html#a48">01270</a>     <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a48">bit_xor</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; vect)
01271     {
01272         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>);
01273         combine_operation(vect, <a class="code" href="a00092.html#a159a4">BM_XOR</a>);
01274         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01275     }
01276 <span class="comment"></span>
01277 <span class="comment">    /*!</span>
01278 <span class="comment">       \brief Logical SUB operation.</span>
01279 <span class="comment">       \param vect - Argument vector.</span>
01280 <span class="comment">    */</span>
<a name="l01281"></a><a class="code" href="a00048.html#a49">01281</a>     <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html#a49">bit_sub</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; vect)
01282     {
01283         <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>);
01284         combine_operation(vect, <a class="code" href="a00092.html#a159a3">BM_SUB</a>);
01285         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01286     }
01287 
01288 <span class="comment"></span>
01289 <span class="comment">    /*!</span>
01290 <span class="comment">       \brief Sets new blocks allocation strategy.</span>
01291 <span class="comment">       \param strat - Strategy code 0 - bitblocks allocation only.</span>
01292 <span class="comment">                      1 - Blocks mutation mode (adaptive algorithm)</span>
01293 <span class="comment">    */</span>
<a name="l01294"></a><a class="code" href="a00048.html#a50">01294</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a50">set_new_blocks_strat</a>(strategy strat) 
01295     { 
01296         new_blocks_strat_ = strat; 
01297     }
01298 <span class="comment"></span>
01299 <span class="comment">    /*!</span>
01300 <span class="comment">       \brief Returns blocks allocation strategy.</span>
01301 <span class="comment">       \return - Strategy code 0 - bitblocks allocation only.</span>
01302 <span class="comment">                 1 - Blocks mutation mode (adaptive algorithm)</span>
01303 <span class="comment">       \sa set_new_blocks_strat</span>
01304 <span class="comment">    */</span>
<a name="l01305"></a><a class="code" href="a00048.html#a51">01305</a>     <a class="code" href="a00095.html#ga0">strategy</a>  <a class="code" href="a00048.html#a51">get_new_blocks_strat</a>()<span class="keyword"> const </span>
01306 <span class="keyword">    </span>{ 
01307         <span class="keywordflow">return</span> new_blocks_strat_; 
01308     }
01309 
01310     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a52">stat</a>(<span class="keywordtype">unsigned</span> blocks=0) <span class="keyword">const</span>;
01311 <span class="comment"></span>
01312 <span class="comment">    /*! </span>
01313 <span class="comment">        \brief Optimization mode</span>
01314 <span class="comment">        Every next level means additional checks (better compression vs time)</span>
01315 <span class="comment">        \sa optimize</span>
01316 <span class="comment">    */</span>
<a name="l01317"></a><a class="code" href="a00048.html#w7">01317</a>     <span class="keyword">enum</span> <a class="code" href="a00048.html#w7">optmode</a>
01318     {
01319         <a class="code" href="a00048.html#w7w4">opt_free_0</a>    = 1, <span class="comment">///&lt; Free unused 0 blocks</span>
01320 <span class="comment"></span>        <a class="code" href="a00048.html#w7w5">opt_free_01</a>   = 2, <span class="comment">///&lt; Free unused 0 and 1 blocks</span>
01321 <span class="comment"></span>        <a class="code" href="a00048.html#w7w6">opt_compress</a>  = 3  <span class="comment">///&lt; compress blocks when possible</span>
01322 <span class="comment"></span>    };
01323 <span class="comment"></span>
01324 <span class="comment">    /*!</span>
01325 <span class="comment">       \brief Optimize memory bitvector's memory allocation.</span>
01326 <span class="comment">   </span>
01327 <span class="comment">       Function analyze all blocks in the bitvector, compresses blocks </span>
01328 <span class="comment">       with a regular structure, frees some memory. This function is recommended</span>
01329 <span class="comment">       after a bulk modification of the bitvector using set_bit, clear_bit or</span>
01330 <span class="comment">       logical operations.</span>
01331 <span class="comment">       </span>
01332 <span class="comment">       @sa optmode, optimize_gap_size</span>
01333 <span class="comment">    */</span>
01334     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a53">optimize</a>(bm::word_t* temp_block=0, optmode opt_mode = opt_compress);
01335 <span class="comment"></span>
01336 <span class="comment">    /*!</span>
01337 <span class="comment">       \brief Optimize sizes of GAP blocks</span>
01338 <span class="comment"></span>
01339 <span class="comment">       This method runs an analysis to find optimal GAP levels for the </span>
01340 <span class="comment">       specific vector. Current GAP compression algorithm uses several fixed</span>
01341 <span class="comment">       GAP sizes. By default bvector uses some reasonable preset. </span>
01342 <span class="comment">    */</span>
01343     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a54">optimize_gap_size</a>();
01344 
01345 <span class="comment"></span>
01346 <span class="comment">    /*!</span>
01347 <span class="comment">        @brief Sets new GAP lengths table. All GAP blocks will be reallocated </span>
01348 <span class="comment">        to match the new scheme.</span>
01349 <span class="comment"></span>
01350 <span class="comment">        @param glevel_len - pointer on C-style array keeping GAP block sizes. </span>
01351 <span class="comment">    */</span>
01352     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a55">set_gap_levels</a>(<span class="keyword">const</span> gap_word_t* glevel_len);
01353 <span class="comment"></span>
01354 <span class="comment">    /*!</span>
01355 <span class="comment">        \brief Lexicographical comparison with a bitvector.</span>
01356 <span class="comment"></span>
01357 <span class="comment">        Function compares current bitvector with the provided argument </span>
01358 <span class="comment">        bit by bit and returns -1 if our bitvector less than the argument, </span>
01359 <span class="comment">        1 - greater, 0 - equal.</span>
01360 <span class="comment">    */</span>
01361     <span class="keywordtype">int</span> <a class="code" href="a00048.html#a56">compare</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>) <span class="keyword">const</span>;
01362 <span class="comment"></span>
01363 <span class="comment">    /*! @brief Allocates temporary block of memory. </span>
01364 <span class="comment"></span>
01365 <span class="comment">        Temp block can be passed to bvector functions requiring some temp memory</span>
01366 <span class="comment">        for their operation. (like serialize)</span>
01367 <span class="comment">        </span>
01368 <span class="comment">        @note method is marked const, but it's not quite true, since</span>
01369 <span class="comment">        it can in some cases modify the state of the block allocator</span>
01370 <span class="comment">        (if it has a state). (Can be important in MT programs).</span>
01371 <span class="comment"></span>
01372 <span class="comment">        @sa free_tempblock</span>
01373 <span class="comment">    */</span>
<a name="l01374"></a><a class="code" href="a00048.html#a57">01374</a>     bm::word_t* <a class="code" href="a00048.html#a57">allocate_tempblock</a>()<span class="keyword"> const</span>
01375 <span class="keyword">    </span>{
01376         <a class="code" href="a00048.html#w1">blocks_manager_type</a>* bm = 
01377             const_cast&lt;blocks_manager_type*&gt;(&amp;blockman_);
01378         <span class="keywordflow">return</span> bm-&gt;get_allocator().alloc_bit_block();
01379     }
01380 <span class="comment"></span>
01381 <span class="comment">    /*! @brief Frees temporary block of memory. </span>
01382 <span class="comment"></span>
01383 <span class="comment">        @note method is marked const, but it's not quite true, since</span>
01384 <span class="comment">        it can in some cases modify the state of the block allocator</span>
01385 <span class="comment">        (if it has a state). (Can be important in MT programs).</span>
01386 <span class="comment"></span>
01387 <span class="comment">        @sa allocate_tempblock</span>
01388 <span class="comment">    */</span>
<a name="l01389"></a><a class="code" href="a00048.html#a58">01389</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a58">free_tempblock</a>(bm::word_t* block)<span class="keyword"> const</span>
01390 <span class="keyword">    </span>{
01391         <a class="code" href="a00048.html#w1">blocks_manager_type</a>* bm = 
01392             const_cast&lt;blocks_manager_type*&gt;(&amp;blockman_);
01393         bm-&gt;get_allocator().free_bit_block(block);
01394     }
01395 <span class="comment"></span>
01396 <span class="comment">    /**</span>
01397 <span class="comment">       \brief Returns enumerator pointing on the first non-zero bit.</span>
01398 <span class="comment">    */</span>
<a name="l01399"></a><a class="code" href="a00048.html#a59">01399</a>     <a class="code" href="a00050.html">enumerator</a> <a class="code" href="a00048.html#a59">first</a>()<span class="keyword"> const</span>
01400 <span class="keyword">    </span>{
01401         <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a><a class="code" href="a00050.html">::enumerator</a> enumerator_type;
01402         <span class="keywordflow">return</span> enumerator_type(<span class="keyword">this</span>, 0);
01403     }
01404 <span class="comment"></span>
01405 <span class="comment">    /**</span>
01406 <span class="comment">       \fn bvector::enumerator bvector::end() const</span>
01407 <span class="comment">       \brief Returns enumerator pointing on the next bit after the last.</span>
01408 <span class="comment">    */</span>
<a name="l01409"></a><a class="code" href="a00048.html#a60">01409</a>     <a class="code" href="a00050.html">enumerator</a> <a class="code" href="a00048.html#a60">end</a>()<span class="keyword"> const</span>
01410 <span class="keyword">    </span>{
01411         <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a><a class="code" href="a00050.html">::enumerator</a> enumerator_type;
01412         <span class="keywordflow">return</span> enumerator_type(<span class="keyword">this</span>, 1);
01413     }
01414 
01415 
<a name="l01416"></a><a class="code" href="a00048.html#a61">01416</a>     <span class="keyword">const</span> bm::word_t* <a class="code" href="a00048.html#a61">get_block</a>(<span class="keywordtype">unsigned</span> nb)<span class="keyword"> const </span>
01417 <span class="keyword">    </span>{ 
01418         <span class="keywordflow">return</span> blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb); 
01419     }
01420     
01421 <span class="keyword">private</span>:
01422 
01423     bm::id_t check_or_next(bm::id_t prev) <span class="keyword">const</span>;
01424     <span class="comment"></span>
01425 <span class="comment">    /// check if specified bit is 1, and set it to 0</span>
01426 <span class="comment">    /// if specified bit is 0, scan for the next 1 and returns it</span>
01427 <span class="comment">    /// if no 1 found returns 0</span>
01428 <span class="comment"></span>    bm::id_t check_or_next_extract(bm::id_t prev);
01429 <span class="comment"></span>
01430 <span class="comment">    /**</span>
01431 <span class="comment">        \brief Set spacified bit without checking preconditions (size, etc)</span>
01432 <span class="comment">    */</span>
01433     <span class="keywordtype">bool</span> set_bit_no_check(bm::id_t n, <span class="keywordtype">bool</span> val);
01434 
01435 
01436     <span class="keywordtype">void</span> combine_operation(<span class="keyword">const</span> <a class="code" href="a00048.html">bm::bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>, 
01437                             bm::operation                opcode);
01438 
01439     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(<span class="keywordtype">unsigned</span> nb,
01440                                       <span class="keywordtype">unsigned</span> gap,
01441                                       bm::word_t* blk,
01442                                       <span class="keyword">const</span> bm::word_t* arg_blk,
01443                                       <span class="keywordtype">int</span> arg_gap,
01444                                       bm::operation opcode);
01445 <span class="keyword">public</span>:
<a name="l01446"></a><a class="code" href="a00048.html#a62">01446</a>     <span class="keywordtype">void</span> <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(<span class="keywordtype">unsigned</span> nb,
01447                                       <span class="keyword">const</span> bm::word_t* arg_blk,
01448                                       <span class="keywordtype">int</span> arg_gap,
01449                                       bm::operation opcode)
01450     {
01451         bm::word_t* blk = const_cast&lt;bm::word_t*&gt;(<a class="code" href="a00048.html#a61">get_block</a>(nb));
01452         <span class="keywordtype">bool</span> gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*<span class="keyword">this</span>), blk, nb);
01453         <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(nb, gap, blk, arg_blk, arg_gap, opcode);
01454     }
01455 <span class="keyword">private</span>:
01456     <span class="keywordtype">void</span> <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(<span class="keywordtype">unsigned</span> nb,
01457                                             <span class="keyword">const</span> bm::word_t* arg_blk,
01458                                             <span class="keywordtype">int</span> arg_gap,
01459                                             bm::operation opcode)
01460     {
01461         <span class="keyword">const</span> bm::word_t* blk = <a class="code" href="a00048.html#a61">get_block</a>(nb);
01462         <span class="keywordtype">bool</span> gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*<span class="keyword">this</span>), blk, nb);
01463         <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(nb, gap, blk, arg_blk, arg_gap, opcode);
01464     }
01465 
01466 <span class="comment"></span>
01467 <span class="comment">    /**</span>
01468 <span class="comment">       \brief Extends GAP block to the next level or converts it to bit block.</span>
01469 <span class="comment">       \param nb - Block's linear index.</span>
01470 <span class="comment">       \param blk - Blocks's pointer </span>
01471 <span class="comment">    */</span>
01472     <span class="keywordtype">void</span> extend_gap_block(<span class="keywordtype">unsigned</span> nb, gap_word_t* blk)
01473     {
01474         blockman_.<a class="code" href="a00048.html#d6">extend_gap_block</a>(nb, blk);
01475     }
01476 <span class="comment"></span>
01477 <span class="comment">    /**</span>
01478 <span class="comment">       \brief Set range without validity checking</span>
01479 <span class="comment">    */</span>
01480     <span class="keywordtype">void</span> set_range_no_check(bm::id_t left,
01481                             bm::id_t right,
01482                             <span class="keywordtype">bool</span>     value);
01483 <span class="keyword">public</span>:
01484 
<a name="l01485"></a><a class="code" href="a00048.html#a63">01485</a>     <span class="keyword">const</span> <a class="code" href="a00048.html#w1">blocks_manager_type</a>&amp; <a class="code" href="a00048.html#a63">get_blocks_manager</a>()<span class="keyword"> const</span>
01486 <span class="keyword">    </span>{
01487         <span class="keywordflow">return</span> blockman_;
01488     }
01489 
<a name="l01490"></a><a class="code" href="a00048.html#a64">01490</a>     <a class="code" href="a00048.html#w1">blocks_manager_type</a>&amp; <a class="code" href="a00048.html#a63">get_blocks_manager</a>()
01491     {
01492         <span class="keywordflow">return</span> blockman_;
01493     }
01494 
01495 
01496 <span class="keyword">private</span>:
01497 
01498 <span class="comment">// This block defines two additional hidden variables used for bitcount</span>
01499 <span class="comment">// optimization, in rare cases can make bitvector thread unsafe.</span>
01500 <span class="preprocessor">#ifdef BMCOUNTOPT</span>
01501 <span class="preprocessor"></span>    <span class="keyword">mutable</span> <a class="code" href="a00092.html#a9">id_t</a>      count_;            <span class="comment">//!&lt; number of 1 bits in the vector</span>
01502 <span class="comment"></span>    <span class="keyword">mutable</span> <span class="keywordtype">bool</span>      count_is_valid_;   <span class="comment">//!&lt; actualization flag</span>
01503 <span class="comment"></span><span class="preprocessor">#endif</span>
01504 <span class="preprocessor"></span>
01505     blocks_manager_type  blockman_;         <span class="comment">//!&lt; bitblocks manager</span>
01506 <span class="comment"></span>    <a class="code" href="a00095.html#ga0">strategy</a>             new_blocks_strat_; <span class="comment">//!&lt; block allocation strategy</span>
01507 <span class="comment"></span>    size_type            size_;             <span class="comment">//!&lt; size in bits</span>
01508 <span class="comment"></span>};
01509 
01510 
01511 
01512 
01513 
01514 <span class="comment">//---------------------------------------------------------------------</span>
01515 
01516 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l01517"></a><a class="code" href="a00092.html#a43">01517</a> <span class="keyword">inline</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> <a class="code" href="a00092.html#a43">operator&amp; </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v1,
01518                                      <span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v2)
01519 {
01520 <span class="preprocessor">#ifdef BM_USE_EXPLICIT_TEMP</span>
01521 <span class="preprocessor"></span>    <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> ret(v1);
01522     ret.<a class="code" href="a00048.html#a47">bit_and</a>(v2);
01523     <span class="keywordflow">return</span> ret;
01524 <span class="preprocessor">#else    </span>
01525 <span class="preprocessor"></span>    <span class="keywordflow">return</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>(v1).<a class="code" href="a00048.html#a47">bit_and</a>(v2);
01526 <span class="preprocessor">#endif</span>
01527 <span class="preprocessor"></span>}
01528 
01529 <span class="comment">//---------------------------------------------------------------------</span>
01530 
01531 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l01532"></a><a class="code" href="a00092.html#a44">01532</a> <span class="keyword">inline</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> <a class="code" href="a00092.html#a44">operator| </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v1,
01533                                      <span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc&gt;</a>&amp; v2)
01534 {
01535 <span class="preprocessor">#ifdef BM_USE_EXPLICIT_TEMP</span>
01536 <span class="preprocessor"></span>    <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> ret(v1);
01537     ret.<a class="code" href="a00048.html#a46">bit_or</a>(v2);
01538     <span class="keywordflow">return</span> ret;
01539 <span class="preprocessor">#else    </span>
01540 <span class="preprocessor"></span>    <span class="keywordflow">return</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>(v1).<a class="code" href="a00048.html#a46">bit_or</a>(v2);
01541 <span class="preprocessor">#endif</span>
01542 <span class="preprocessor"></span>}
01543 
01544 <span class="comment">//---------------------------------------------------------------------</span>
01545 
01546 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l01547"></a><a class="code" href="a00092.html#a45">01547</a> <span class="keyword">inline</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> <a class="code" href="a00092.html#a45">operator^ </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v1,
01548                                      <span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v2)
01549 {
01550 <span class="preprocessor">#ifdef BM_USE_EXPLICIT_TEMP</span>
01551 <span class="preprocessor"></span>    <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> ret(v1);
01552     ret.<a class="code" href="a00048.html#a48">bit_xor</a>(v2);
01553     <span class="keywordflow">return</span> ret;
01554 <span class="preprocessor">#else    </span>
01555 <span class="preprocessor"></span>    <span class="keywordflow">return</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>(v1).<a class="code" href="a00048.html#a48">bit_xor</a>(v2);
01556 <span class="preprocessor">#endif</span>
01557 <span class="preprocessor"></span>}
01558 
01559 <span class="comment">//---------------------------------------------------------------------</span>
01560 
01561 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l01562"></a><a class="code" href="a00092.html#a46">01562</a> <span class="keyword">inline</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> <a class="code" href="a00092.html#a46">operator- </a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v1,
01563                                      <span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; v2)
01564 {
01565 <span class="preprocessor">#ifdef BM_USE_EXPLICIT_TEMP</span>
01566 <span class="preprocessor"></span>    <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a> ret(v1);
01567     ret.<a class="code" href="a00048.html#a49">bit_sub</a>(v2);
01568     <span class="keywordflow">return</span> ret;
01569 <span class="preprocessor">#else    </span>
01570 <span class="preprocessor"></span>    <span class="keywordflow">return</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>(v1).<a class="code" href="a00048.html#a49">bit_sub</a>(v2);
01571 <span class="preprocessor">#endif</span>
01572 <span class="preprocessor"></span>}
01573 
01574 
01575 
01576 
01577 <span class="comment">// -----------------------------------------------------------------------</span>
01578 
01579 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01580"></a><a class="code" href="a00048.html#a21">01580</a> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::set_range</a>(bm::id_t left,
01581                                                   bm::id_t right,
01582                                                   <span class="keywordtype">bool</span>     value)
01583 {
01584     <span class="keywordflow">if</span> (right &lt; left)
01585     {
01586         <span class="keywordflow">return</span> <a class="code" href="a00048.html#a21">set_range</a>(right, left, value);
01587     }
01588 
01589     <a class="code" href="a00077.html#a0">BM_ASSERT</a>(left &lt; size_);
01590     <a class="code" href="a00077.html#a0">BM_ASSERT</a>(right &lt; size_);
01591 
01592     <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)
01593     <a class="code" href="a00077.html#a13">BM_SET_MMX_GUARD</a>
01594 
01595     set_range_no_check(left, right, value);
01596 
01597     <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01598 }
01599 
01600 <span class="comment">// -----------------------------------------------------------------------</span>
01601 
01602 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01603"></a><a class="code" href="a00048.html#a26">01603</a> bm::id_t <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::count</a>()<span class="keyword"> const</span>
01604 <span class="keyword"></span>{
01605 <span class="preprocessor">#ifdef BMCOUNTOPT</span>
01606 <span class="preprocessor"></span>    <span class="keywordflow">if</span> (count_is_valid_) <span class="keywordflow">return</span> count_;
01607 <span class="preprocessor">#endif</span>
01608 <span class="preprocessor"></span>    <a class="code" href="a00092.html#a10">word_t</a>*** blk_root = blockman_.get_rootblock();
01609     <span class="keyword">typename</span> blocks_manager_type::block_count_func func(blockman_);
01610     <a class="code" href="a00092.html#a53">for_each_nzblock</a>(blk_root, blockman_.top_block_size(), 
01611                                 bm::set_array_size, func);
01612 
01613     <a class="code" href="a00074.html#a4">BMCOUNT_SET</a>(func.count());
01614     <span class="keywordflow">return</span> func.<a class="code" href="a00048.html#a26">count</a>();
01615 }
01616 
01617 <span class="comment">// -----------------------------------------------------------------------</span>
01618 
01619 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01620"></a><a class="code" href="a00048.html#a29">01620</a> <span class="keywordtype">void</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::resize</a>(size_type new_size)
01621 {
01622     <span class="keywordflow">if</span> (size_ == new_size) <span class="keywordflow">return</span>; <span class="comment">// nothing to do</span>
01623     <span class="keywordflow">if</span> (size_ &lt; new_size) <span class="comment">// size grows </span>
01624     {
01625         blockman_.reserve(new_size);
01626         size_ = new_size;
01627     }
01628     <span class="keywordflow">else</span> <span class="comment">// shrink</span>
01629     {
01630         <a class="code" href="a00048.html#a21">set_range</a>(new_size, size_ - 1, <span class="keyword">false</span>); <span class="comment">// clear the tail</span>
01631         size_ = new_size;
01632     }
01633 }
01634 
01635 <span class="comment">// -----------------------------------------------------------------------</span>
01636 
01637 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01638"></a><a class="code" href="a00048.html#a31">01638</a> bm::id_t <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::count_range</a>(bm::id_t left, 
01639                                          bm::id_t right, 
01640                                          <span class="keywordtype">unsigned</span>* block_count_arr)<span class="keyword"> const</span>
01641 <span class="keyword"></span>{
01642     <a class="code" href="a00077.html#a0">BM_ASSERT</a>(left &lt;= right);
01643 
01644     <span class="keywordtype">unsigned</span> <a class="code" href="a00048.html#a26">count</a> = 0;
01645 
01646     <span class="comment">// calculate logical number of start and destination blocks</span>
01647     <span class="keywordtype">unsigned</span> nblock_left  = unsigned(left  &gt;&gt;  bm::set_block_shift);
01648     <span class="keywordtype">unsigned</span> nblock_right = unsigned(right &gt;&gt;  bm::set_block_shift);
01649 
01650     <span class="keyword">const</span> bm::word_t* block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock_left);
01651     <span class="keywordtype">bool</span> left_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, block, nblock_left);
01652 
01653     <span class="keywordtype">unsigned</span> nbit_left  = unsigned(left  &amp; bm::set_block_mask); 
01654     <span class="keywordtype">unsigned</span> nbit_right = unsigned(right &amp; bm::set_block_mask); 
01655 
01656     <span class="keywordtype">unsigned</span> r = 
01657         (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
01658 
01659     <span class="keyword">typename</span> blocks_manager_type::block_count_func func(blockman_);
01660 
01661     <span class="keywordflow">if</span> (block)
01662     {
01663         <span class="keywordflow">if</span> ((nbit_left == 0) &amp;&amp; (r == (bm::bits_in_block-1))) <span class="comment">// whole block</span>
01664         {
01665             <span class="keywordflow">if</span> (block_count_arr)
01666             {
01667                 count += block_count_arr[nblock_left];
01668             }
01669             <span class="keywordflow">else</span>
01670             {
01671                 func(block, nblock_left);
01672             }
01673         }
01674         <span class="keywordflow">else</span>
01675         {
01676             <span class="keywordflow">if</span> (left_gap)
01677             {
01678                 count += <a class="code" href="a00092.html#a59">gap_bit_count_range</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block), 
01679                                             (<a class="code" href="a00092.html#a19">gap_word_t</a>)nbit_left,
01680                                             (<a class="code" href="a00092.html#a19">gap_word_t</a>)r);
01681             }
01682             <span class="keywordflow">else</span>
01683             {
01684                 count += <a class="code" href="a00097.html#ga16">bit_block_calc_count_range</a>(block, nbit_left, r);
01685             }
01686         }
01687     }
01688 
01689     <span class="keywordflow">if</span> (nblock_left == nblock_right)  <span class="comment">// in one block</span>
01690     {
01691         <span class="keywordflow">return</span> count + func.<a class="code" href="a00048.html#a26">count</a>();
01692     }
01693 
01694     <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> nb = nblock_left+1; nb &lt; nblock_right; ++nb)
01695     {
01696         block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb);
01697         <span class="keywordflow">if</span> (block_count_arr)
01698         {
01699             count += block_count_arr[nb];
01700         }
01701         <span class="keywordflow">else</span> 
01702         {
01703             <span class="keywordflow">if</span> (block)
01704                 func(block, nb);
01705         }
01706     }
01707     count += func.<a class="code" href="a00048.html#a26">count</a>();
01708 
01709     block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock_right);
01710     <span class="keywordtype">bool</span> right_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, block, nblock_right);
01711 
01712     <span class="keywordflow">if</span> (block)
01713     {
01714         <span class="keywordflow">if</span> (right_gap)
01715         {
01716             count += <a class="code" href="a00092.html#a59">gap_bit_count_range</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block),
01717                                         (<a class="code" href="a00092.html#a19">gap_word_t</a>)0,
01718                                         (<a class="code" href="a00092.html#a19">gap_word_t</a>)nbit_right);
01719         }
01720         <span class="keywordflow">else</span>
01721         {
01722             count += <a class="code" href="a00097.html#ga16">bit_block_calc_count_range</a>(block, 0, nbit_right);
01723         }
01724     }
01725 
01726     <span class="keywordflow">return</span> count;
01727 }
01728 
01729 <span class="comment">// -----------------------------------------------------------------------</span>
01730 
01731 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt;
<a name="l01732"></a><a class="code" href="a00048.html#a34">01732</a> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::invert</a>()
01733 {
01734     <a class="code" href="a00074.html#a3">BMCOUNT_VALID</a>(<span class="keyword">false</span>)
01735     <a class="code" href="a00077.html#a13">BM_SET_MMX_GUARD</a>
01736 
01737     bm::word_t*** blk_root = blockman_.get_rootblock();
01738     <span class="keyword">typename</span> blocks_manager_type::block_invert_func func(blockman_);    
01739     <a class="code" href="a00092.html#a55">for_each_block</a>(blk_root, blockman_.top_block_size(),
01740                                 bm::set_array_size, func);
01741     <span class="keywordflow">if</span> (size_ == bm::id_max) 
01742     {
01743         set_bit_no_check(bm::id_max, <span class="keyword">false</span>);
01744     } 
01745     <span class="keywordflow">else</span>
01746     {
01747         set_range_no_check(size_, bm::id_max, <span class="keyword">false</span>);
01748     }
01749 
01750     <span class="keywordflow">return</span> *<span class="keyword">this</span>;
01751 }
01752 
01753 <span class="comment">// -----------------------------------------------------------------------</span>
01754 
01755 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01756"></a><a class="code" href="a00048.html#a35">01756</a> <span class="keywordtype">bool</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::get_bit</a>(bm::id_t n)<span class="keyword"> const</span>
01757 <span class="keyword"></span>{    
01758     <a class="code" href="a00077.html#a0">BM_ASSERT</a>(n &lt; size_);
01759 
01760     <span class="comment">// calculate logical block number</span>
01761     <span class="keywordtype">unsigned</span> nblock = unsigned(n &gt;&gt;  bm::set_block_shift); 
01762 
01763     <span class="keyword">const</span> bm::word_t* block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock);
01764 
01765     <span class="keywordflow">if</span> (block)
01766     {
01767         <span class="comment">// calculate word number in block and bit</span>
01768         <span class="keywordtype">unsigned</span> nbit = unsigned(n &amp; bm::set_block_mask); 
01769         <span class="keywordtype">unsigned</span> is_set;
01770 
01771         <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, block, nblock))
01772         {
01773             is_set = <a class="code" href="a00096.html#ga0">gap_test</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block), nbit);
01774         }
01775         <span class="keywordflow">else</span> 
01776         {
01777             <span class="keywordtype">unsigned</span> nword  = unsigned(nbit &gt;&gt; bm::set_word_shift); 
01778             nbit &amp;= bm::set_word_mask;
01779 
01780             is_set = (block[nword] &amp; (((bm::word_t)1) &lt;&lt; nbit));
01781         }
01782         <span class="keywordflow">return</span> is_set != 0;
01783     }
01784     <span class="keywordflow">return</span> <span class="keyword">false</span>;
01785 }
01786 
01787 <span class="comment">// -----------------------------------------------------------------------</span>
01788 
01789 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01790"></a><a class="code" href="a00048.html#a53">01790</a> <span class="keywordtype">void</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::optimize</a>(bm::word_t* temp_block, optmode opt_mode)
01791 {
01792     <a class="code" href="a00092.html#a10">word_t</a>*** blk_root = blockman_.blocks_root();
01793 
01794     <span class="keywordflow">if</span> (!temp_block)
01795         temp_block = blockman_.check_allocate_tempblock();
01796 
01797     <span class="keyword">typename</span> 
01798         blocks_manager_type::block_opt_func  opt_func(blockman_, 
01799                                                 temp_block, 
01800                                                 (<span class="keywordtype">int</span>)opt_mode);
01801     <a class="code" href="a00092.html#a53">for_each_nzblock</a>(blk_root, blockman_.top_block_size(),
01802                                 bm::set_array_size, opt_func);
01803 }
01804 
01805 <span class="comment">// -----------------------------------------------------------------------</span>
01806 
01807 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01808"></a><a class="code" href="a00048.html#a54">01808</a> <span class="keywordtype">void</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::optimize_gap_size</a>()
01809 {
01810     <span class="keyword">struct </span><a class="code" href="a00048.html">bvector</a>&lt;Alloc, MS&gt;::<a class="code" href="a00057.html">statistics</a> st;
01811     <a class="code" href="a00048.html#a45">calc_stat</a>(&amp;st);
01812 
01813     if (!st.gap_blocks)
01814         return;
01815 
01816     <a class="code" href="a00092.html#a19">gap_word_t</a> opt_glen[bm::<a class="code" href="a00092.html#a23">gap_levels</a>];
01817     ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
01818 
01819     <a class="code" href="a00096.html#ga33">improve_gap_levels</a>(st.gap_length, 
01820                             st.gap_length + st.gap_blocks, 
01821                             opt_glen);
01822     
01823     <a class="code" href="a00048.html#a55">set_gap_levels</a>(opt_glen);
01824 }
01825 
01826 <span class="comment">// -----------------------------------------------------------------------</span>
01827 
01828 template&lt;typename Alloc, typename MS&gt; 
<a name="l01829"></a><a class="code" href="a00048.html#a55">01829</a> void <a class="code" href="a00048.html">bvector</a>&lt;Alloc, MS&gt;::<a class="code" href="a00048.html#a55">set_gap_levels</a>(const gap_word_t* glevel_len)
01830 {
01831     <a class="code" href="a00092.html#a10">word_t</a>*** blk_root = blockman_.blocks_root();
01832 
01833     <span class="keyword">typename</span> 
01834         blocks_manager_type::gap_level_func  gl_func(blockman_, glevel_len);
01835 
01836     <a class="code" href="a00092.html#a53">for_each_nzblock</a>(blk_root, blockman_.top_block_size(),
01837                                 bm::set_array_size, gl_func);
01838 
01839     blockman_.set_glen(glevel_len);
01840 }
01841 
01842 <span class="comment">// -----------------------------------------------------------------------</span>
01843 
01844 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
<a name="l01845"></a><a class="code" href="a00048.html#a56">01845</a> <span class="keywordtype">int</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::compare</a>(<span class="keyword">const</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>&amp; <a class="code" href="a00048.html">bvect</a>)<span class="keyword"> const</span>
01846 <span class="keyword"></span>{
01847     <span class="keywordtype">int</span> res;
01848     <span class="keywordtype">unsigned</span> bn = 0;
01849 
01850     <span class="keywordtype">unsigned</span> top_blocks = blockman_.top_block_size();
01851     <span class="keywordtype">unsigned</span> bvect_top_blocks = <a class="code" href="a00048.html">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.top_block_size();
01852 
01853     <span class="keywordflow">if</span> (bvect_top_blocks &gt; top_blocks) top_blocks = bvect_top_blocks;
01854 
01855     <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; top_blocks; ++i)
01856     {
01857         <span class="keyword">const</span> bm::word_t* <span class="keyword">const</span>* blk_blk = blockman_.get_topblock(i);
01858         <span class="keyword">const</span> bm::word_t* <span class="keyword">const</span>* arg_blk_blk = 
01859                                 <a class="code" href="a00048.html">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.get_topblock(i);
01860 
01861         <span class="keywordflow">if</span> (blk_blk == arg_blk_blk) 
01862         {
01863             bn += bm::set_array_size;
01864             <span class="keywordflow">continue</span>;
01865         }
01866 
01867         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j = 0; j &lt; bm::set_array_size; ++j, ++bn)
01868         {
01869             <span class="keyword">const</span> bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
01870             <span class="keyword">const</span> bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
01871 
01872             <span class="keywordflow">if</span> (blk == arg_blk) <span class="keywordflow">continue</span>;
01873 
01874             <span class="comment">// If one block is zero we check if the other one has at least </span>
01875             <span class="comment">// one bit ON</span>
01876 
01877             <span class="keywordflow">if</span> (!blk || !arg_blk)  
01878             {
01879                 <span class="keyword">const</span> bm::word_t*  pblk;
01880                 <span class="keywordtype">bool</span> is_gap;
01881 
01882                 <span class="keywordflow">if</span> (blk)
01883                 {
01884                     pblk = blk;
01885                     res = 1;
01886                     is_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*<span class="keyword">this</span>), blk, bn);
01887                 }
01888                 <span class="keywordflow">else</span>
01889                 {
01890                     pblk = arg_blk;
01891                     res = -1;
01892                     is_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(<a class="code" href="a00048.html">bvect</a>, arg_blk, bn);
01893                 }
01894 
01895                 <span class="keywordflow">if</span> (is_gap)
01896                 {
01897                     <span class="keywordflow">if</span> (!<a class="code" href="a00096.html#ga17">gap_is_all_zero</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(pblk), bm::gap_max_bits))
01898                     {
01899                         <span class="keywordflow">return</span> res;
01900                     }
01901                 }
01902                 <span class="keywordflow">else</span>
01903                 {
01904                     bm::wordop_t* blk1 = (<a class="code" href="a00092.html#a31">wordop_t</a>*)pblk;
01905                     bm::wordop_t* blk2 = 
01906                         (<a class="code" href="a00092.html#a31">wordop_t</a>*)(pblk + bm::set_block_size);
01907                     <span class="keywordflow">if</span> (!<a class="code" href="a00097.html#ga19">bit_is_all_zero</a>(blk1, blk2))
01908                     {
01909                         <span class="keywordflow">return</span> res;
01910                     }
01911                 }
01912 
01913                 <span class="keywordflow">continue</span>;
01914             }
01915 
01916             <span class="keywordtype">bool</span> arg_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(<a class="code" href="a00048.html">bvect</a>, arg_blk, bn);
01917             <span class="keywordtype">bool</span> gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*<span class="keyword">this</span>), blk, bn);
01918 
01919             <span class="keywordflow">if</span> (arg_gap != gap)
01920             {
01921                 bm::wordop_t temp_blk[bm::set_block_size_op]; 
01922                 bm::wordop_t* blk1;
01923                 bm::wordop_t* blk2;
01924 
01925                 <span class="keywordflow">if</span> (gap)
01926                 {
01927                     <a class="code" href="a00096.html#ga10">gap_convert_to_bitset</a>((bm::word_t*)temp_blk, 
01928                                             <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
01929 
01930                     blk1 = (bm::wordop_t*)temp_blk;
01931                     blk2 = (bm::wordop_t*)arg_blk;
01932                 }
01933                 <span class="keywordflow">else</span>
01934                 {
01935                     <a class="code" href="a00096.html#ga10">gap_convert_to_bitset</a>((bm::word_t*)temp_blk, 
01936                                             <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
01937 
01938                     blk1 = (bm::wordop_t*)blk;
01939                     blk2 = (bm::wordop_t*)temp_blk;
01940 
01941                 }                        
01942                 res = <a class="code" href="a00097.html#ga11">bitcmp</a>(blk1, blk2, bm::set_block_size_op);  
01943 
01944             }
01945             <span class="keywordflow">else</span>
01946             {
01947                 <span class="keywordflow">if</span> (gap)
01948                 {
01949                     res = <a class="code" href="a00096.html#ga2">gapcmp</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
01950                 }
01951                 <span class="keywordflow">else</span>
01952                 {
01953                     res = <a class="code" href="a00097.html#ga11">bitcmp</a>((bm::wordop_t*)blk, 
01954                                     (bm::wordop_t*)arg_blk, 
01955                                     bm::set_block_size_op);
01956                 }
01957             }
01958 
01959             <span class="keywordflow">if</span> (res != 0)
01960             {
01961                 <span class="keywordflow">return</span> res;
01962             }
01963         
01964 
01965         } <span class="comment">// for j</span>
01966 
01967     } <span class="comment">// for i</span>
01968 
01969     <span class="keywordflow">return</span> 0;
01970 }
01971 
01972 
01973 <span class="comment">// -----------------------------------------------------------------------</span>
01974 
01975 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> Alloc, <span class="keyword">typename</span> MS&gt; 
01976 <span class="keywordtype">void</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::calc_stat</a>(<span class="keyword">typename</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;</a>::statistics* st)<span class="keyword"> const</span>
01977 <span class="keyword"></span>{
01978     st-&gt;bit_blocks = st-&gt;gap_blocks 
01979                    = st-&gt;max_serialize_mem 
01980                    = st-&gt;memory_used = 0;
01981 
01982     ::memcpy(st-&gt;gap_levels, 
01983              blockman_.glen(), <span class="keyword">sizeof</span>(<a class="code" href="a00092.html#a19">gap_word_t</a>) * bm::gap_levels);
01984 
01985     <span class="keywordtype">unsigned</span> empty_blocks = 0;
01986     <span class="keywordtype">unsigned</span> blocks_memory = 0;
01987     <a class="code" href="a00092.html#a19">gap_word_t</a>* gapl_ptr = st-&gt;gap_length;
01988 
01989     st-&gt;max_serialize_mem = <span class="keyword">sizeof</span>(<a class="code" href="a00092.html#a9">id_t</a>) * 4;
01990 
01991     <span class="keywordtype">unsigned</span> block_idx = 0;
01992 
01993     <span class="comment">// Walk the blocks, calculate statistics.</span>
01994     <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; blockman_.top_block_size(); ++i)
01995     {
01996         <span class="keyword">const</span> bm::word_t* <span class="keyword">const</span>* blk_blk = blockman_.get_topblock(i);
01997 
01998         <span class="keywordflow">if</span> (!blk_blk) 
01999         {
02000             block_idx += bm::set_array_size;
02001             st-&gt;max_serialize_mem += <span class="keyword">sizeof</span>(unsigned) + 1;
02002             <span class="keywordflow">continue</span>;
02003         }
02004 
02005         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j = 0;j &lt; bm::set_array_size; ++j, ++block_idx)
02006         {
02007             <span class="keyword">const</span> bm::word_t* blk = blk_blk[j];
02008             <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a2">IS_VALID_ADDR</a>(blk))
02009             {
02010                 st-&gt;max_serialize_mem += empty_blocks &lt;&lt; 2;
02011                 empty_blocks = 0;
02012 
02013                 <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, blk, block_idx)) <span class="comment">// gap block</span>
02014                 {
02015                     ++(st-&gt;gap_blocks);
02016 
02017                     bm::gap_word_t* gap_blk = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk);
02018 
02019                     <span class="keywordtype">unsigned</span> mem_used = 
02020                         <a class="code" href="a00096.html#ga20">bm::gap_capacity</a>(gap_blk, blockman_.glen()) 
02021                         * <span class="keyword">sizeof</span>(gap_word_t);
02022 
02023                     *gapl_ptr = <a class="code" href="a00096.html#ga19">gap_length</a>(gap_blk);
02024 
02025                     st-&gt;max_serialize_mem += *gapl_ptr * <span class="keyword">sizeof</span>(gap_word_t);
02026                     blocks_memory += mem_used;
02027 
02028                     ++gapl_ptr;
02029                 }
02030                 <span class="keywordflow">else</span> <span class="comment">// bit block</span>
02031                 {
02032                     ++(st-&gt;bit_blocks);
02033                     <span class="keywordtype">unsigned</span> mem_used = <span class="keyword">sizeof</span>(bm::word_t) * bm::set_block_size;
02034                     st-&gt;max_serialize_mem += mem_used;
02035                     blocks_memory += mem_used;
02036                 }
02037             }
02038             <span class="keywordflow">else</span>
02039             {
02040                 ++empty_blocks;
02041             }
02042         }
02043     }  
02044 
02045 
02046     st-&gt;max_serialize_mem += st-&gt;max_serialize_mem / 10; <span class="comment">// 10% increment</span>
02047 
02048     <span class="comment">// Calc size of different odd and temporary things.</span>
02049 
02050     st-&gt;memory_used += <span class="keyword">sizeof</span>(*this) - <span class="keyword">sizeof</span>(blockman_);
02051     st-&gt;memory_used += blockman_.mem_used();
02052     st-&gt;memory_used += blocks_memory;
02053 }
02054 
02055 
02056 <span class="comment">// -----------------------------------------------------------------------</span>
02057 
02058 
02059 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
02060 <span class="keywordtype">bool</span> bvector&lt;Alloc, MS&gt;::set_bit_no_check(bm::id_t n, <span class="keywordtype">bool</span> val)
02061 {
02062     <span class="comment">// calculate logical block number</span>
02063     <span class="keywordtype">unsigned</span> nblock = unsigned(n &gt;&gt;  bm::set_block_shift); 
02064 
02065     <span class="keywordtype">int</span> block_type;
02066 
02067     bm::word_t* blk = 
02068         blockman_.check_allocate_block(nblock, 
02069                                         val,
02070                                         <a class="code" href="a00048.html#a51">get_new_blocks_strat</a>(), 
02071                                         &amp;block_type);
02072 
02073     <span class="keywordflow">if</span> (!blk) return false;
02074 
02075     <span class="comment">// calculate word number in block and bit</span>
02076     <span class="keywordtype">unsigned</span> nbit   = <span class="keywordtype">unsigned</span>(n &amp; bm::set_block_mask); 
02077 
02078     if (block_type == 1) <span class="comment">// gap</span>
02079     {
02080         <span class="keywordtype">unsigned</span> is_set;
02081         <span class="keywordtype">unsigned</span> new_block_len;
02082         
02083         new_block_len = 
02084             <a class="code" href="a00096.html#ga4">gap_set_value</a>(val, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), nbit, &amp;is_set);
02085         <span class="keywordflow">if</span> (is_set)
02086         {
02087             <a class="code" href="a00074.html#a5">BMCOUNT_ADJ</a>(val)
02088 
02089             unsigned threshold = 
02090             bm::gap_limit(BMGAP_PTR(blk), blockman_.glen());
02091 
02092             if (new_block_len &gt; threshold) 
02093             {
02094                 extend_gap_block(nblock, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02095             }
02096             <span class="keywordflow">return</span> <span class="keyword">true</span>;
02097         }
02098     }
02099     <span class="keywordflow">else</span>  <span class="comment">// bit block</span>
02100     {
02101         <span class="keywordtype">unsigned</span> nword  = unsigned(nbit &gt;&gt; bm::set_word_shift); 
02102         nbit &amp;= bm::set_word_mask;
02103 
02104         bm::word_t* word = blk + nword;
02105         bm::word_t  mask = (((bm::word_t)1) &lt;&lt; nbit);
02106 
02107         <span class="keywordflow">if</span> (val)
02108         {
02109             <span class="keywordflow">if</span> ( ((*word) &amp; mask) == 0 )
02110             {
02111                 *word |= mask; <span class="comment">// set bit</span>
02112                 <a class="code" href="a00074.html#a1">BMCOUNT_INC</a>;
02113                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
02114             }
02115         }
02116         <span class="keywordflow">else</span>
02117         {
02118             <span class="keywordflow">if</span> ((*word) &amp; mask)
02119             {
02120                 *word &amp;= ~mask; <span class="comment">// clear bit</span>
02121                 <a class="code" href="a00074.html#a2">BMCOUNT_DEC</a>;
02122                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
02123             }
02124         }
02125     }
02126     <span class="keywordflow">return</span> <span class="keyword">false</span>;
02127 }
02128 
02129 <span class="comment">// -----------------------------------------------------------------------</span>
02130 
02131 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
<a name="l02132"></a><a class="code" href="a00048.html#a52">02132</a> <span class="keywordtype">void</span> <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::stat</a>(<span class="keywordtype">unsigned</span> blocks)<span class="keyword"> const</span>
02133 <span class="keyword"></span>{
02134     <span class="keyword">register</span> bm::id_t <a class="code" href="a00048.html#a26">count</a> = 0;
02135     <span class="keywordtype">int</span> printed = 0;
02136 
02137     <span class="keywordtype">int</span> total_gap_eff = 0;
02138 
02139     <span class="keywordflow">if</span> (!blocks)
02140     {
02141         blocks = bm::set_total_blocks;
02142     }
02143 
02144     <span class="keywordtype">unsigned</span> nb;
02145     <span class="keywordflow">for</span> (nb = 0; nb &lt; blocks; ++nb)
02146     {
02147         <span class="keyword">register</span> <span class="keyword">const</span> bm::word_t* blk = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb);
02148 
02149         <span class="keywordflow">if</span> (blk == 0)
02150         {
02151            <span class="keywordflow">continue</span>;
02152         }
02153 
02154         <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(blk))
02155         {
02156            <span class="keywordflow">if</span> (blockman_.is_block_gap(nb)) <span class="comment">// gap block</span>
02157            {
02158                printf(<span class="stringliteral">"[Alert!%i]"</span>, nb);
02159                assert(0);
02160            }
02161            
02162            <span class="keywordtype">unsigned</span> start = nb; 
02163            <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> i = nb+1; i &lt; bm::set_total_blocks; ++i, ++nb)
02164            {
02165                blk = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb);
02166                <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(blk))
02167                {
02168                  <span class="keywordflow">if</span> (blockman_.is_block_gap(nb)) <span class="comment">// gap block</span>
02169                  {
02170                      printf(<span class="stringliteral">"[Alert!%i]"</span>, nb);
02171                      assert(0);
02172                      --nb;
02173                      <span class="keywordflow">break</span>;
02174                  }
02175 
02176                }
02177                <span class="keywordflow">else</span>
02178                {
02179                   --nb;
02180                   <span class="keywordflow">break</span>;
02181                }
02182            }
02183 
02184            printf(<span class="stringliteral">"{F.%i:%i}"</span>,start, nb);
02185            ++printed;
02186         }
02187         <span class="keywordflow">else</span>
02188         {
02189             <span class="keywordflow">if</span> (blockman_.is_block_gap(nb)) <span class="comment">// gap block</span>
02190             {
02191                <span class="keywordtype">unsigned</span> bc = <a class="code" href="a00096.html#ga1">gap_bit_count</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02192                <span class="comment">/*unsigned sum = */</span><a class="code" href="a00096.html#ga13">gap_control_sum</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02193                <span class="keywordtype">unsigned</span> level = <a class="code" href="a00096.html#ga22">gap_level</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02194                 count += bc;
02195                <span class="keywordtype">unsigned</span> len = <a class="code" href="a00096.html#ga19">gap_length</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk))-1;
02196                <span class="keywordtype">unsigned</span> raw_size=bc*2;
02197                <span class="keywordtype">unsigned</span> cmr_len=len*2;
02198                <span class="keywordtype">int</span> mem_eff = raw_size - cmr_len;
02199                total_gap_eff += mem_eff;
02200                
02201                printf(<span class="stringliteral">"[ GAP %i=%i:%i-%i(%i) ]"</span>, nb, bc, level, len, mem_eff);
02202                 ++printed;
02203             }
02204             <span class="keywordflow">else</span> <span class="comment">// bitset</span>
02205             {
02206                 <span class="keyword">const</span> bm::word_t* blk_end = blk + bm::set_block_size;
02207                 <span class="keywordtype">unsigned</span> bc = <a class="code" href="a00097.html#ga13">bit_block_calc_count</a>(blk, blk_end);
02208 
02209                 <span class="keywordtype">unsigned</span> zw = 0;
02210                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; bm::set_block_size; ++i) 
02211                 {
02212                     zw += (blk[i] == 0);
02213                 }
02214 
02215                 count += bc;
02216                 printf(<span class="stringliteral">"( BIT %i=%i[%i] )"</span>, nb, bc, zw);
02217                 ++printed;
02218                 
02219             }
02220         }
02221         <span class="keywordflow">if</span> (printed == 10)
02222         {
02223             printed = 0;
02224             printf(<span class="stringliteral">"\n"</span>);
02225         }
02226     } <span class="comment">// for nb</span>
02227     printf(<span class="stringliteral">"\n"</span>);
02228     printf(<span class="stringliteral">"gap_efficiency=%i\n"</span>, total_gap_eff); 
02229 
02230 }
02231 
02232 <span class="comment">//---------------------------------------------------------------------</span>
02233 
02234 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
02235 bm::id_t <a class="code" href="a00048.html">bvector&lt;Alloc, MS&gt;::check_or_next</a>(bm::id_t prev)<span class="keyword"> const</span>
02236 <span class="keyword"></span>{
02237     <span class="keywordflow">for</span> (;;)
02238     {
02239         <span class="keywordtype">unsigned</span> nblock = unsigned(prev &gt;&gt; bm::set_block_shift); 
02240         <span class="keywordflow">if</span> (nblock &gt;= bm::set_total_blocks) 
02241             break;
02242 
02243         if (blockman_.is_subblock_null(nblock &gt;&gt; bm::set_array_shift))
02244         {
02245             prev += (bm::set_blkblk_mask + 1) -
02246                             (prev &amp; bm::set_blkblk_mask);
02247         }
02248         <span class="keywordflow">else</span>
02249         {
02250             <span class="keywordtype">unsigned</span> nbit = unsigned(prev &amp; bm::set_block_mask);
02251             <span class="keywordtype">int</span> no_more_blocks;
02252             <span class="keyword">const</span> bm::word_t* block = 
02253                 blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock, &amp;no_more_blocks);
02254 
02255             <span class="keywordflow">if</span> (no_more_blocks) 
02256             {
02257                 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(block == 0);
02258                 <span class="keywordflow">break</span>;
02259             }
02260 
02261             <span class="keywordflow">if</span> (block)
02262             {
02263                 <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(block)) return prev;
02264                 if (BM_IS_GAP(blockman_, block, nblock))
02265                 {
02266                     <span class="keywordflow">if</span> (bm::gap_find_in_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block),
02267                                                 nbit,
02268                                                 &amp;prev))
02269                     {
02270                         <span class="keywordflow">return</span> prev;
02271                     }
02272                 }
02273                 <span class="keywordflow">else</span>
02274                 {
02275                     <span class="keywordflow">if</span> (bm::bit_find_in_block(block, nbit, &amp;prev)) 
02276                     {
02277                         <span class="keywordflow">return</span> prev;
02278                     }
02279                 }
02280             }
02281             <span class="keywordflow">else</span>
02282             {
02283                 prev += (bm::set_block_mask + 1) - 
02284                             (prev &amp; bm::set_block_mask);
02285             }
02286 
02287         }
02288         <span class="keywordflow">if</span> (!prev) break;
02289     }
02290 
02291     return 0;
02292 }
02293 
02294 
02295 <span class="comment">//---------------------------------------------------------------------</span>
02296 
02297 template&lt;class Alloc, class MS&gt; 
02298 bm::id_t bvector&lt;Alloc, MS&gt;::check_or_next_extract(bm::id_t prev)
02299 {
02300     <span class="keywordflow">for</span> (;;)
02301     {
02302         <span class="keywordtype">unsigned</span> nblock = unsigned(prev &gt;&gt; bm::set_block_shift); 
02303         <span class="keywordflow">if</span> (nblock &gt;= bm::set_total_blocks) break;
02304 
02305         if (blockman_.is_subblock_null(nblock &gt;&gt; bm::set_array_shift))
02306         {
02307             prev += (bm::set_blkblk_mask + 1) -
02308                             (prev &amp; bm::set_blkblk_mask);
02309         }
02310         <span class="keywordflow">else</span>
02311         {
02312             <span class="keywordtype">unsigned</span> nbit = unsigned(prev &amp; bm::set_block_mask);
02313 
02314             <span class="keywordtype">int</span> no_more_blocks;
02315             bm::word_t* block = 
02316                 blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock, &amp;no_more_blocks);
02317 
02318             <span class="keywordflow">if</span> (no_more_blocks) 
02319             {
02320                 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(block == 0);
02321                 <span class="keywordflow">break</span>;
02322             }
02323 
02324 
02325             <span class="keywordflow">if</span> (block)
02326             {
02327                 <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(block))
02328                 {
02329                     <a class="code" href="a00048.html#a20">set</a>(prev, <span class="keyword">false</span>);
02330                     <span class="keywordflow">return</span> prev;
02331                 }
02332                 <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, block, nblock))
02333                 {
02334                     <span class="keywordtype">unsigned</span> is_set;
02335                     <span class="keywordtype">unsigned</span> new_block_len = 
02336                         <a class="code" href="a00096.html#ga4">gap_set_value</a>(0, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block), nbit, &amp;is_set);
02337                     <span class="keywordflow">if</span> (is_set) {
02338                         <a class="code" href="a00074.html#a2">BMCOUNT_DEC</a>
02339                         <span class="keywordtype">unsigned</span> threshold = 
02340                             <a class="code" href="a00096.html#ga21">bm::gap_limit</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block), blockman_.glen());
02341                         <span class="keywordflow">if</span> (new_block_len &gt; threshold) 
02342                         {
02343                             extend_gap_block(nblock, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block));
02344                         }
02345                         <span class="keywordflow">return</span> prev;
02346                     } <span class="keywordflow">else</span> {
02347                         <span class="keywordflow">if</span> (bm::gap_find_in_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block),
02348                                                     nbit,
02349                                                     &amp;prev))
02350                         {
02351                             <a class="code" href="a00048.html#a20">set</a>(prev, <span class="keyword">false</span>);
02352                             <span class="keywordflow">return</span> prev;
02353                         }
02354                     }
02355                 }
02356                 <span class="keywordflow">else</span> <span class="comment">// bit block</span>
02357                 {
02358                     <span class="keywordflow">if</span> (bm::bit_find_in_block(block, nbit, &amp;prev)) 
02359                     {
02360                         <a class="code" href="a00074.html#a2">BMCOUNT_DEC</a>
02361 
02362                         <span class="keywordtype">unsigned</span> nbit = 
02363                             unsigned(prev &amp; bm::set_block_mask); 
02364                         <span class="keywordtype">unsigned</span> nword = 
02365                             unsigned(nbit &gt;&gt; bm::set_word_shift);
02366                         nbit &amp;= bm::set_word_mask;
02367                         bm::word_t* word = block + nword;
02368                         bm::word_t  mask = ((bm::word_t)1) &lt;&lt; nbit;
02369                         *word &amp;= ~mask;
02370 
02371                         <span class="keywordflow">return</span> prev;
02372                     }
02373                 }
02374             }
02375             <span class="keywordflow">else</span>
02376             {
02377                 prev += (bm::set_block_mask + 1) - 
02378                             (prev &amp; bm::set_block_mask);
02379             }
02380 
02381         }
02382         <span class="keywordflow">if</span> (!prev) break;
02383     }
02384 
02385     return 0;
02386 }
02387 
02388 <span class="comment">//---------------------------------------------------------------------</span>
02389 
02390 template&lt;class Alloc, class MS&gt; 
02391 <span class="keywordtype">void</span> bvector&lt;Alloc, MS&gt;::combine_operation(
02392                                   const bm::bvector&lt;Alloc, MS&gt;&amp; <a class="code" href="a00048.html">bvect</a>, 
02393                                   bm::operation                 opcode)
02394 {
02395     <span class="keyword">typedef</span> void (*block_bit_op)(bm::word_t*, <span class="keyword">const</span> bm::word_t*);
02396     <span class="keyword">typedef</span> void (*block_bit_op_next)(bm::word_t*, 
02397                                         <span class="keyword">const</span> bm::word_t*, 
02398                                         bm::word_t*, 
02399                                         <span class="keyword">const</span> bm::word_t*);
02400 
02401     <span class="keywordtype">unsigned</span> top_blocks = blockman_.top_block_size();
02402     <span class="keywordtype">unsigned</span> bvect_top_blocks = <a class="code" href="a00088.html#a1">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.top_block_size();
02403 
02404     <span class="keywordflow">if</span> (size_ == <a class="code" href="a00088.html#a1">bvect</a>.size_) 
02405     {
02406         <a class="code" href="a00077.html#a0">BM_ASSERT</a>( top_blocks &gt;= bvect_top_blocks);
02407     }
02408     <span class="keywordflow">else</span>
02409     <span class="keywordflow">if</span> (size_ &lt; <a class="code" href="a00088.html#a1">bvect</a>.size_) <span class="comment">// this vect shorter than the arg.</span>
02410     {
02411         size_ = <a class="code" href="a00088.html#a1">bvect</a>.<a class="code" href="a00048.html#r2">size_</a>;
02412         <span class="comment">// stretch our capacity</span>
02413         blockman_.reserve_top_blocks(bvect_top_blocks);
02414         top_blocks = blockman_.top_block_size();
02415     }
02416     <span class="keywordflow">else</span> 
02417     <span class="keywordflow">if</span> (size_ &gt; <a class="code" href="a00088.html#a1">bvect</a>.size_) <span class="comment">// this vector larger</span>
02418     {
02419         <span class="keywordflow">if</span> (opcode == BM_AND) <span class="comment">// clear the tail with zeros</span>
02420         {
02421             <a class="code" href="a00048.html#a21">set_range</a>(<a class="code" href="a00088.html#a1">bvect</a>.size_, size_ - 1, <span class="keyword">false</span>);
02422             <span class="keywordflow">if</span> (bvect_top_blocks &lt; top_blocks)
02423             {
02424                 <span class="comment">// not to scan blocks we already swiped</span>
02425                 top_blocks = bvect_top_blocks;
02426             }
02427         }
02428     }
02429 
02430     block_bit_op      bit_func;
02431     <span class="keywordflow">switch</span> (opcode)
02432     {
02433     <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a1">BM_AND</a>:
02434         bit_func = <a class="code" href="a00097.html#ga21">bit_block_and</a>;
02435         <span class="keywordflow">break</span>;
02436     <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a2">BM_OR</a>:
02437         bit_func = <a class="code" href="a00097.html#ga30">bit_block_or</a>;
02438         <span class="keywordflow">break</span>;
02439     <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a3">BM_SUB</a>:
02440         bit_func = <a class="code" href="a00097.html#ga32">bit_block_sub</a>;
02441         <span class="keywordflow">break</span>;
02442     <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a4">BM_XOR</a>:
02443         bit_func = <a class="code" href="a00097.html#ga34">bit_block_xor</a>;
02444         <span class="keywordflow">break</span>;
02445     }           
02446     
02447     
02448     bm::word_t*** blk_root = blockman_.blocks_root();
02449     <span class="keywordtype">unsigned</span> block_idx = 0;
02450     <span class="keywordtype">unsigned</span> i, j;
02451 
02452     <a class="code" href="a00077.html#a13">BM_SET_MMX_GUARD</a>
02453 
02454     <span class="keywordflow">for</span> (i = 0; i &lt; blockman_.top_block_size(); ++i)
02455     {
02456         bm::word_t** blk_blk = blk_root[i];
02457 
02458         <span class="keywordflow">if</span> (blk_blk == 0) <span class="comment">// not allocated</span>
02459         {
02460             <span class="keyword">const</span> bm::word_t* <span class="keyword">const</span>* bvbb = 
02461                             <a class="code" href="a00088.html#a1">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.get_topblock(i);
02462             <span class="keywordflow">if</span> (bvbb == 0) 
02463             {
02464                 <span class="comment">// skip it because 0 OP 0 = 0</span>
02465                 block_idx += bm::set_array_size;
02466                 <span class="keywordflow">continue</span>; 
02467             }
02468             <span class="comment">// 0 - self, non-zero argument</span>
02469             <span class="keywordflow">for</span> (j = 0; j &lt; bm::set_array_size; ++j,++block_idx)
02470             {
02471                 <span class="keyword">const</span> bm::word_t* arg_blk = 
02472                     <a class="code" href="a00088.html#a1">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.<a class="code" href="a00048.html#a61">get_block</a>(i, j);
02473                 <span class="keywordflow">if</span> (arg_blk != 0)
02474                 {
02475                     <span class="keywordtype">bool</span> arg_gap = 
02476                         <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(<a class="code" href="a00088.html#a1">bvect</a>.blockman_, arg_blk, block_idx);
02477                     <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(block_idx, 0, 0, 
02478                                                 arg_blk, arg_gap, 
02479                                                 opcode);
02480                 }
02481 
02482             } <span class="comment">// for j</span>
02483             <span class="keywordflow">continue</span>;
02484         }
02485 
02486         <span class="keywordflow">for</span> (j = 0; j &lt; bm::set_array_size; ++j, ++block_idx)
02487         {
02488             
02489             bm::word_t* blk = blk_blk[j];
02490             <span class="keyword">const</span> bm::word_t* arg_blk = <a class="code" href="a00088.html#a1">bvect</a>.<a class="code" href="a00048.html#r0">blockman_</a>.<a class="code" href="a00048.html#a61">get_block</a>(i, j);
02491 
02492             <span class="keywordflow">if</span> (arg_blk || blk)
02493             {
02494                 <span class="keywordtype">bool</span> arg_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(<a class="code" href="a00088.html#a1">bvect</a>.blockman_, arg_blk, block_idx);
02495                 <span class="keywordtype">bool</span> gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>((*this).blockman_, blk, block_idx);
02496                 
02497                 <span class="comment">// Optimization branch. Statistically two bit blocks</span>
02498                 <span class="comment">// are bumping into each other quite frequently and</span>
02499                 <span class="comment">// this peace of code tend to be executed often and </span>
02500                 <span class="comment">// program does not go into nested calls.</span>
02501                 <span class="comment">// But logically this branch can be eliminated without</span>
02502                 <span class="comment">// loosing any functionality.</span>
02503 <span class="comment">/*                   </span>
02504 <span class="comment">                if (!gap &amp;&amp; !arg_gap)</span>
02505 <span class="comment">                {</span>
02506 <span class="comment">                    if (IS_VALID_ADDR(blk) &amp;&amp; arg_blk)</span>
02507 <span class="comment">                    {</span>
02508 <span class="comment">                    </span>
02509 <span class="comment">                        if (bit_func2 &amp;&amp; (j &lt; bm::set_array_size-1))</span>
02510 <span class="comment">                        {</span>
02511 <span class="comment">                            bm::word_t* blk2 = blk_blk[j+1];</span>
02512 <span class="comment">                            const bm::word_t* arg_blk2 = bvect.get_block(i, j+1);</span>
02513 <span class="comment">                            </span>
02514 <span class="comment">                            bool arg_gap2 = BM_IS_GAP(bvect, arg_blk2, block_idx + 1);</span>
02515 <span class="comment">                            bool gap2 = BM_IS_GAP((*this), blk2, block_idx + 1);</span>
02516 <span class="comment">                            </span>
02517 <span class="comment">                            if (!gap2 &amp;&amp; !arg_gap2 &amp;&amp; blk2 &amp;&amp; arg_blk2)</span>
02518 <span class="comment">                            {</span>
02519 <span class="comment">                                bit_func2(blk, arg_blk, blk2, arg_blk2);</span>
02520 <span class="comment">                                ++j;</span>
02521 <span class="comment">                                ++block_idx;</span>
02522 <span class="comment">                                continue;</span>
02523 <span class="comment">                            }</span>
02524 <span class="comment">                            </span>
02525 <span class="comment">                        }</span>
02526 <span class="comment">                        </span>
02527 <span class="comment">                        bit_func(blk, arg_blk);</span>
02528 <span class="comment">                        continue;</span>
02529 <span class="comment">                    }</span>
02530 <span class="comment">                } // end of optimization branch...</span>
02531 <span class="comment">*/</span>                   
02532                 <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(block_idx, gap, blk, 
02533                                             arg_blk, arg_gap,
02534                                             opcode);
02535             }
02536 
02537         } <span class="comment">// for j</span>
02538 
02539     } <span class="comment">// for i</span>
02540 
02541 }
02542 
02543 
02544 <span class="comment">//---------------------------------------------------------------------</span>
02545 
02546 
02547 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
02548 <span class="keywordtype">void</span> bvector&lt;Alloc, MS&gt;::combine_operation_with_block(<span class="keywordtype">unsigned</span> nb,
02549                                     <span class="keywordtype">unsigned</span> gap,
02550                                     bm::word_t* blk,
02551                                     <span class="keyword">const</span> bm::word_t* arg_blk,
02552                                     <span class="keywordtype">int</span> arg_gap,
02553                                     bm::operation opcode)
02554 {
02555     <span class="keywordflow">if</span> (!blk &amp;&amp; arg_gap &amp;&amp; <a class="code" href="a00048.html#a51">get_new_blocks_strat</a>() == BM_GAP) {
02556         blk = 
02557             blockman_.check_allocate_block(nb, 
02558                                         0,
02559                                         BM_GAP, 
02560                                         (<span class="keywordtype">int</span>*)&amp;gap,
02561                                         <span class="keyword">false</span> <span class="comment">/*no null return*/</span>);
02562     }
02563 
02564         <span class="keywordflow">if</span> (gap) <span class="comment">// our block GAP-type</span>
02565         {
02566             <span class="keywordflow">if</span> (arg_gap)  <span class="comment">// both blocks GAP-type</span>
02567             {
02568                 <a class="code" href="a00092.html#a19">gap_word_t</a> tmp_buf[bm::gap_max_buff_len * 3]; <span class="comment">// temporary result</span>
02569             
02570                 <a class="code" href="a00092.html#a19">gap_word_t</a>* res;
02571                 <span class="keywordflow">switch</span> (opcode)
02572                 {
02573                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a1">BM_AND</a>:
02574                     res = <a class="code" href="a00096.html#ga28">gap_operation_and</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02575                                             <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk), 
02576                                             tmp_buf);
02577                     <span class="keywordflow">break</span>;
02578                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a2">BM_OR</a>:
02579                     res = <a class="code" href="a00096.html#ga30">gap_operation_or</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02580                                         <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk), 
02581                                         tmp_buf);
02582                     <span class="keywordflow">break</span>;
02583                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a3">BM_SUB</a>:
02584                     res = <a class="code" href="a00096.html#ga31">gap_operation_sub</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02585                                             <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk), 
02586                                             tmp_buf);
02587                     <span class="keywordflow">break</span>;
02588                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a4">BM_XOR</a>:
02589                     res = <a class="code" href="a00096.html#ga29">gap_operation_xor</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02590                                             <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk), 
02591                                             tmp_buf);
02592                     <span class="keywordflow">break</span>;
02593                 <span class="keywordflow">default</span>:
02594                     assert(0);
02595                     res = 0;
02596                 }
02597 
02598                 assert(res == tmp_buf);
02599                 <span class="keywordtype">unsigned</span> res_len = <a class="code" href="a00096.html#ga19">bm::gap_length</a>(res);
02600 
02601                 assert(!(res == tmp_buf &amp;&amp; res_len == 0));
02602 
02603                 <span class="comment">// if as a result of the operation gap block turned to zero</span>
02604                 <span class="comment">// we can now replace it with NULL</span>
02605                 <span class="keywordflow">if</span> (<a class="code" href="a00096.html#ga17">gap_is_all_zero</a>(res, bm::gap_max_bits))
02606                 {
02607                     blockman_.set_block(nb, 0);
02608                     blockman_.set_block_bit(nb);
02609                     blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_gap_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02610                                                             blockman_.glen());
02611                     <span class="keywordflow">return</span>;
02612                 }
02613 
02614                 <span class="comment">// mutation check</span>
02615 
02616                 <span class="keywordtype">int</span> level = <a class="code" href="a00096.html#ga22">gap_level</a>(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02617                 <span class="keywordtype">unsigned</span> threshold = blockman_.glen(level)-4;
02618                 <span class="keywordtype">int</span> new_level = <a class="code" href="a00096.html#ga24">gap_calc_level</a>(res_len, blockman_.glen());
02619 
02620                 <span class="keywordflow">if</span> (new_level == -1)
02621                 {
02622                     blockman_.convert_gap2bitset(nb, res);
02623                     <span class="keywordflow">return</span>;
02624                 }
02625 
02626                 <span class="keywordflow">if</span> (res_len &gt; threshold)
02627                 {
02628                     <a class="code" href="a00096.html#ga23">set_gap_level</a>(res, new_level);
02629                     <a class="code" href="a00092.html#a19">gap_word_t</a>* new_blk = 
02630                         blockman_.allocate_gap_block(new_level, res);
02631 
02632                     bm::word_t* p = (bm::word_t*)new_blk;
02633                     <a class="code" href="a00077.html#a9">BMSET_PTRGAP</a>(p);
02634 
02635                     blockman_.set_block_ptr(nb, p);
02636                     blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_gap_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), 
02637                                                             blockman_.glen());
02638                     <span class="keywordflow">return</span>;
02639                 }
02640 
02641                 <span class="comment">// gap opeartion result is in the temporary buffer</span>
02642                 <span class="comment">// we copy it back to the gap_block</span>
02643 
02644                 <a class="code" href="a00096.html#ga23">set_gap_level</a>(tmp_buf, level);
02645                 ::memcpy(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk), tmp_buf, res_len * <span class="keyword">sizeof</span>(<a class="code" href="a00092.html#a19">gap_word_t</a>));
02646 
02647                 <span class="keywordflow">return</span>;
02648             }
02649             <span class="keywordflow">else</span> <span class="comment">// argument is BITSET-type (own block is GAP)</span>
02650             {
02651                 <span class="comment">// since we can not combine blocks of mixed type</span>
02652                 <span class="comment">// we need to convert our block to bitset</span>
02653                 
02654                 <span class="keywordflow">if</span> (arg_blk == 0)  <span class="comment">// Combining against an empty block</span>
02655                 {
02656                 <span class="keywordflow">if</span> (opcode == BM_OR  || 
02657                     opcode == BM_SUB || 
02658                     opcode == BM_XOR)
02659                 {
02660                     <span class="keywordflow">return</span>; <span class="comment">// nothing to do</span>
02661                 }
02662                     
02663                 <span class="keywordflow">if</span> (opcode == BM_AND) <span class="comment">// ("Value" AND  0) == 0</span>
02664                 {
02665                     blockman_.set_block_ptr(nb, 0);
02666                     blockman_.set_block_bit(nb);
02667                     blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().
02668                                     free_gap_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk),
02669                                                 blockman_.glen());
02670                     <span class="keywordflow">return</span>;
02671                 }
02672                 }
02673 
02674                 blk = blockman_.convert_gap2bitset(nb, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
02675             }
02676         } 
02677         <span class="keywordflow">else</span> <span class="comment">// our block is BITSET-type</span>
02678         {
02679             <span class="keywordflow">if</span> (arg_gap) <span class="comment">// argument block is GAP-type</span>
02680             {
02681             <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a2">IS_VALID_ADDR</a>(blk))
02682             {
02683                 <span class="comment">// special case, maybe we can do the job without </span>
02684                 <span class="comment">// converting the GAP argument to bitblock</span>
02685                 <span class="keywordflow">switch</span> (opcode)
02686                 {
02687                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a2">BM_OR</a>:
02688                         <a class="code" href="a00096.html#ga8">gap_add_to_bitset</a>(blk, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
02689                         <span class="keywordflow">return</span>;                         
02690                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a3">BM_SUB</a>:
02691                         <a class="code" href="a00096.html#ga6">gap_sub_to_bitset</a>(blk, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
02692                         <span class="keywordflow">return</span>;
02693                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a4">BM_XOR</a>:
02694                         <a class="code" href="a00096.html#ga7">gap_xor_to_bitset</a>(blk, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
02695                         <span class="keywordflow">return</span>;
02696                 <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a1">BM_AND</a>:
02697                         <a class="code" href="a00096.html#ga9">gap_and_to_bitset</a>(blk, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk));
02698                         <span class="keywordflow">return</span>;
02699                         
02700                 } <span class="comment">// switch</span>
02701                 }
02702                 
02703                 <span class="comment">// the worst case we need to convert argument block to </span>
02704                 <span class="comment">// bitset type.</span>
02705 
02706                 <a class="code" href="a00092.html#a19">gap_word_t</a>* temp_blk = (<a class="code" href="a00092.html#a19">gap_word_t</a>*) blockman_.check_allocate_tempblock();
02707                 arg_blk = 
02708                     <a class="code" href="a00096.html#ga12">gap_convert_to_bitset_smart</a>((bm::word_t*)temp_blk, 
02709                                                 <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk), 
02710                                                 bm::gap_max_bits);
02711             
02712             }   
02713         }
02714     
02715         <span class="comment">// Now here we combine two plain bitblocks using supplied bit function.</span>
02716         bm::word_t* dst = blk;
02717 
02718         bm::word_t* ret; 
02719         <span class="keywordflow">if</span> (dst == 0 &amp;&amp; arg_blk == 0)
02720         {
02721             <span class="keywordflow">return</span>;
02722         }
02723 
02724         <span class="keywordflow">switch</span> (opcode)
02725         {
02726         <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a1">BM_AND</a>:
02727             ret = <a class="code" href="a00097.html#ga26">bit_operation_and</a>(dst, arg_blk);
02728             <span class="keywordflow">goto</span> copy_block;
02729         <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a4">BM_XOR</a>:
02730             ret = <a class="code" href="a00097.html#ga35">bit_operation_xor</a>(dst, arg_blk);
02731             <span class="keywordflow">if</span> (ret &amp;&amp; (ret == arg_blk) &amp;&amp; <a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(dst))
02732             {
02733                 ret = blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().alloc_bit_block();
02734 <span class="preprocessor">#ifdef BMVECTOPT</span>
02735 <span class="preprocessor"></span>            <a class="code" href="a00079.html#a0">VECT_XOR_ARR_2_MASK</a>(ret, 
02736                                 arg_blk, 
02737                                 arg_blk + bm::set_block_size, 
02738                                 bm::all_bits_mask);
02739 <span class="preprocessor">#else</span>
02740 <span class="preprocessor"></span>                bm::wordop_t* dst_ptr = (<a class="code" href="a00092.html#a31">wordop_t</a>*)ret;
02741                 <span class="keyword">const</span> bm::wordop_t* wrd_ptr = (<a class="code" href="a00092.html#a31">wordop_t</a>*) arg_blk;
02742                 <span class="keyword">const</span> bm::wordop_t* wrd_end = 
02743                 (<a class="code" href="a00092.html#a31">wordop_t</a>*) (arg_blk + bm::set_block_size);
02744 
02745                 <span class="keywordflow">do</span>
02746                 {
02747                     dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
02748                     dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
02749                     dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
02750                     dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
02751 
02752                     dst_ptr+=4;
02753                     wrd_ptr+=4;
02754 
02755                 } <span class="keywordflow">while</span> (wrd_ptr &lt; wrd_end);
02756 <span class="preprocessor">#endif</span>
02757 <span class="preprocessor"></span>                <span class="keywordflow">break</span>;
02758             }
02759             <span class="keywordflow">goto</span> copy_block;
02760         <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a2">BM_OR</a>:
02761             ret = <a class="code" href="a00097.html#ga31">bit_operation_or</a>(dst, arg_blk);
02762         copy_block:
02763             <span class="keywordflow">if</span> (ret &amp;&amp; (ret == arg_blk) &amp;&amp; !<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(ret))
02764             {
02765             ret = blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().alloc_bit_block();
02766             <a class="code" href="a00097.html#ga20">bit_block_copy</a>(ret, arg_blk);
02767             }
02768             <span class="keywordflow">break</span>;
02769 
02770         <span class="keywordflow">case</span> <a class="code" href="a00092.html#a159a3">BM_SUB</a>:
02771             ret = <a class="code" href="a00097.html#ga33">bit_operation_sub</a>(dst, arg_blk);
02772             <span class="keywordflow">if</span> (ret &amp;&amp; ret == arg_blk)
02773             {
02774                 ret = blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().alloc_bit_block();
02775 <span class="preprocessor">#ifdef BMVECTOPT</span>
02776 <span class="preprocessor"></span>                <a class="code" href="a00079.html#a1">VECT_ANDNOT_ARR_2_MASK</a>(ret, 
02777                                     arg_blk,
02778                                     arg_blk + bm::set_block_size,
02779                                     bm::all_bits_mask);
02780 <span class="preprocessor">#else</span>
02781 <span class="preprocessor"></span>
02782                 bm::wordop_t* dst_ptr = (<a class="code" href="a00092.html#a31">wordop_t</a>*)ret;
02783                 <span class="keyword">const</span> bm::wordop_t* wrd_ptr = (<a class="code" href="a00092.html#a31">wordop_t</a>*) arg_blk;
02784                 <span class="keyword">const</span> bm::wordop_t* wrd_end = 
02785                 (<a class="code" href="a00092.html#a31">wordop_t</a>*) (arg_blk + bm::set_block_size);
02786 
02787                 <span class="keywordflow">do</span>
02788                 {
02789                     dst_ptr[0] = bm::all_bits_mask &amp; ~wrd_ptr[0];
02790                     dst_ptr[1] = bm::all_bits_mask &amp; ~wrd_ptr[1];
02791                     dst_ptr[2] = bm::all_bits_mask &amp; ~wrd_ptr[2];
02792                     dst_ptr[3] = bm::all_bits_mask &amp; ~wrd_ptr[3];
02793 
02794                     dst_ptr+=4;
02795                     wrd_ptr+=4;
02796 
02797                 } <span class="keywordflow">while</span> (wrd_ptr &lt; wrd_end);
02798 <span class="preprocessor">#endif</span>
02799 <span class="preprocessor"></span>            }
02800             <span class="keywordflow">break</span>;
02801         <span class="keywordflow">default</span>:
02802             assert(0);
02803             ret = 0;
02804         }
02805 
02806         <span class="keywordflow">if</span> (ret != dst) <span class="comment">// block mutation</span>
02807         {
02808             blockman_.set_block(nb, ret);
02809             blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_bit_block(dst);
02810         }
02811 }
02812 
02813 <span class="comment">//---------------------------------------------------------------------</span>
02814 
02815 <span class="keyword">template</span>&lt;<span class="keyword">class</span> Alloc, <span class="keyword">class</span> MS&gt; 
02816 <span class="keywordtype">void</span> bvector&lt;Alloc, MS&gt;::set_range_no_check(bm::id_t left,
02817                                             bm::id_t right,
02818                                             <span class="keywordtype">bool</span>     value)
02819 {
02820     <span class="comment">// calculate logical number of start and destination blocks</span>
02821     <span class="keywordtype">unsigned</span> nblock_left  = unsigned(left  &gt;&gt;  bm::set_block_shift);
02822     <span class="keywordtype">unsigned</span> nblock_right = unsigned(right &gt;&gt;  bm::set_block_shift);
02823 
02824     bm::word_t* block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nblock_left);
02825     <span class="keywordtype">bool</span> left_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(blockman_, block, nblock_left);
02826 
02827     <span class="keywordtype">unsigned</span> nbit_left  = unsigned(left  &amp; bm::set_block_mask); 
02828     <span class="keywordtype">unsigned</span> nbit_right = unsigned(right &amp; bm::set_block_mask); 
02829 
02830     <span class="keywordtype">unsigned</span> r = 
02831         (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
02832 
02833         bm::gap_word_t tmp_gap_blk[5] = {0,};
02834 
02835     <span class="comment">// Set bits in the starting block</span>
02836 
02837     <span class="keywordtype">unsigned</span> nb;
02838     <span class="keywordflow">if</span> ((nbit_left == 0) &amp;&amp; (r == bm::bits_in_block - 1)) <span class="comment">// full block</span>
02839     {
02840         nb = nblock_left;
02841     }
02842     <span class="keywordflow">else</span>
02843     {
02844         <a class="code" href="a00096.html#ga15">gap_init_range_block</a>(tmp_gap_blk,
02845                             nbit_left, r, value, bm::bits_in_block);
02846 
02847         <a class="code" href="a00048.html#a62">combine_operation_with_block</a>(nblock_left, 
02848                                     left_gap, 
02849                                     block,
02850                                     (bm::word_t*) tmp_gap_blk,
02851                                     1,
02852                                     value ? BM_OR : BM_AND);
02853 
02854         <span class="keywordflow">if</span> (nblock_left == nblock_right)  <span class="comment">// in one block</span>
02855             return;
02856         nb = nblock_left+1;
02857     }
02858 
02859     <span class="comment">// Set (or clear) all full blocks between left and right</span>
02860     
02861     <span class="keywordtype">unsigned</span> nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
02862             
02863     if (value)
02864     {
02865         <span class="keywordflow">for</span> (; nb &lt; nb_to; ++nb)
02866         {
02867             block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb);
02868             <span class="keywordflow">if</span> (<a class="code" href="a00077.html#a3">IS_FULL_BLOCK</a>(block)) 
02869                 continue;
02870 
02871             <span class="keywordtype">bool</span> is_gap = BM_IS_GAP(blockman_, block, nb);
02872 
02873             blockman_.set_block(nb, FULL_BLOCK_ADDR);
02874             blockman_.set_block_bit(nb);
02875             
02876             if (is_gap)
02877             {
02878                 blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_gap_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block), 
02879                                                             blockman_.glen());
02880             }
02881             <span class="keywordflow">else</span>
02882             {
02883                 blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_bit_block(block);
02884             }
02885             
02886         } <span class="comment">// for</span>
02887     }
02888     <span class="keywordflow">else</span> <span class="comment">// value == 0</span>
02889     {
02890         <span class="keywordflow">for</span> (; nb &lt; nb_to; ++nb)
02891         {
02892             block = blockman_.<a class="code" href="a00048.html#a61">get_block</a>(nb);
02893             <span class="keywordflow">if</span> (block == 0)  <span class="comment">// nothing to do</span>
02894                 continue;
02895 
02896             blockman_.set_block(nb, 0);
02897             blockman_.set_block_bit(nb);
02898 
02899             <span class="keywordtype">bool</span> is_gap = BM_IS_GAP(blockman_, block, nb);
02900 
02901             if (is_gap) 
02902             {
02903                 blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_gap_block(<a class="code" href="a00077.html#a8">BMGAP_PTR</a>(block),
02904                                                             blockman_.glen());
02905             }
02906             <span class="keywordflow">else</span>
02907             {
02908                 blockman_.<a class="code" href="a00048.html#a17">get_allocator</a>().free_bit_block(block);
02909             }
02910 
02911 
02912         } <span class="comment">// for</span>
02913     } <span class="comment">// if value else </span>
02914 
02915     <span class="keywordflow">if</span> (nb_to &gt; nblock_right)
02916         return;
02917 
02918     block = blockman_.get_block(nblock_right);
02919     <span class="keywordtype">bool</span> right_gap = BM_IS_GAP(blockman_, block, nblock_right);
02920 
02921     gap_init_range_block(tmp_gap_blk, 
02922                             0, nbit_right, value, bm::bits_in_block);
02923 
02924     combine_operation_with_block(nblock_right, 
02925                                     right_gap, 
02926                                     block,
02927                                     (bm::word_t*) tmp_gap_blk,
02928                                     1,
02929                                     value ? BM_OR : BM_AND);
02930 
02931 }
02932 
02933 <span class="comment">//---------------------------------------------------------------------</span>
02934 
02935 
02936 } <span class="comment">// namespace</span>
02937 
02938 #include "bmundef.h"
02939 
02940 #endif
02941 
02942 
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Thu Apr 20 13:28:46 2006 for BitMagic by&nbsp;
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.1 </small></address>
</body>
</html>