← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/bmagic/jaunty

« back to all changes in this revision

Viewing changes to html/a00103.html

  • Committer: Bazaar Package Importer
  • Author(s): Andres Salomon
  • Date: 2008-01-05 23:58:56 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20080105235856-2kmxhxkz14qjy9ia
Tags: 3.5.0-1
* New upstream release.
* Add tcpp.dpatch.  This stops tests/stress/t.cpp from including
  ncbi_pch.hpp.  As far as I can tell, NCBI is not used at all, I have
  no idea where that came from..
* Silence some lintian warnings; binary-arch-rules-but-pkg-is-arch-indep
  and ancient-standards-version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
html/a00103.html
1
1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2
2
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
3
 
<title>BitMagic: bmalgo.h Source File</title>
 
3
<title>BitMagic: bm::first_bit_table&lt; T &gt; Struct Template Reference</title>
4
4
<link href="doxygen.css" rel="stylesheet" type="text/css">
5
5
</head><body>
6
6
<!-- Generated by Doxygen 1.4.1 -->
7
7
<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>
8
8
<div class="nav">
9
 
<a class="el" href="dir_000000.html">src</a></div>
10
 
<h1>bmalgo.h</h1><a href="a00075.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment">00001 <span class="comment">/*</span>
11
 
00002 <span class="comment">Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)</span>
12
 
00003 <span class="comment"></span>
13
 
00004 <span class="comment">Permission is hereby granted, free of charge, to any person </span>
14
 
00005 <span class="comment">obtaining a copy of this software and associated documentation </span>
15
 
00006 <span class="comment">files (the "Software"), to deal in the Software without restriction, </span>
16
 
00007 <span class="comment">including without limitation the rights to use, copy, modify, merge, </span>
17
 
00008 <span class="comment">publish, distribute, sublicense, and/or sell copies of the Software, </span>
18
 
00009 <span class="comment">and to permit persons to whom the Software is furnished to do so, </span>
19
 
00010 <span class="comment">subject to the following conditions:</span>
20
 
00011 <span class="comment"></span>
21
 
00012 <span class="comment">The above copyright notice and this permission notice shall be included </span>
22
 
00013 <span class="comment">in all copies or substantial portions of the Software.</span>
23
 
00014 <span class="comment"></span>
24
 
00015 <span class="comment">THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, </span>
25
 
00016 <span class="comment">EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES </span>
26
 
00017 <span class="comment">OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. </span>
27
 
00018 <span class="comment">IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, </span>
28
 
00019 <span class="comment">DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, </span>
29
 
00020 <span class="comment">ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR </span>
30
 
00021 <span class="comment">OTHER DEALINGS IN THE SOFTWARE.</span>
31
 
00022 <span class="comment"></span>
32
 
00023 <span class="comment">For more information please visit:  http://bmagic.sourceforge.net</span>
33
 
00024 <span class="comment"></span>
34
 
00025 <span class="comment">*/</span>
35
 
00026 
36
 
00027 <span class="preprocessor">#ifndef BMALGO__H__INCLUDED__</span>
37
 
00028 <span class="preprocessor"></span><span class="preprocessor">#define BMALGO__H__INCLUDED__</span>
38
 
00029 <span class="preprocessor"></span>
39
 
00030 <span class="preprocessor">#include "<a class="code" href="a00074.html">bm.h</a>"</span>
40
 
00031 <span class="preprocessor">#include "<a class="code" href="a00078.html">bmfunc.h</a>"</span>
41
 
00032 <span class="preprocessor">#include "<a class="code" href="a00077.html">bmdef.h</a>"</span>
42
 
00033 
43
 
00034 <span class="keyword">namespace </span>bm
44
 
00035 {
45
 
00036 <span class="comment"></span>
46
 
00037 <span class="comment">/*! \defgroup setalgo Set algorithms </span>
47
 
00038 <span class="comment"> *  Set algorithms </span>
48
 
00039 <span class="comment"> *  \ingroup bmagic</span>
49
 
00040 <span class="comment"> */</span>
50
 
00041 <span class="comment"></span>
51
 
00042 <span class="comment">/*! \defgroup distance Distance metrics </span>
52
 
00043 <span class="comment"> *  Algorithms to compute binary distance metrics</span>
53
 
00044 <span class="comment"> *  \ingroup setalgo</span>
54
 
00045 <span class="comment"> */</span>
55
 
00046 
56
 
00047 <span class="comment"></span>
57
 
00048 <span class="comment">/*! </span>
58
 
00049 <span class="comment">    \brief    Distance metrics codes defined for vectors A and B</span>
59
 
00050 <span class="comment">    \ingroup  distance</span>
60
 
00051 <span class="comment">*/</span>
61
 
<a name="l00052"></a><a class="code" href="a00101.html#ga5">00052</a> <span class="keyword">enum</span> distance_metric
62
 
00053 {
63
 
00054     COUNT_AND,       <span class="comment">//!&lt; (A &amp; B).count()</span>
64
 
00055 <span class="comment"></span>    COUNT_XOR,       <span class="comment">//!&lt; (A ^ B).count()</span>
65
 
00056 <span class="comment"></span>    COUNT_OR,        <span class="comment">//!&lt; (A | B).count()</span>
66
 
00057 <span class="comment"></span>    COUNT_SUB_AB,    <span class="comment">//!&lt; (A - B).count()</span>
67
 
00058 <span class="comment"></span>    COUNT_SUB_BA,    <span class="comment">//!&lt; (B - A).count()</span>
68
 
00059 <span class="comment"></span>    COUNT_A,         <span class="comment">//!&lt; A.count()</span>
69
 
00060 <span class="comment"></span>    COUNT_B          <span class="comment">//!&lt; B.count()</span>
70
 
00061 <span class="comment"></span>};
71
 
00062 <span class="comment"></span>
72
 
00063 <span class="comment">/*! </span>
73
 
00064 <span class="comment">    \brief Distance metric descriptor, holds metric code and result.</span>
74
 
00065 <span class="comment">    \sa distance_operation</span>
75
 
00066 <span class="comment">*/</span>
76
 
00067 
77
 
<a name="l00068"></a><a class="code" href="a00065.html">00068</a> <span class="keyword">struct </span><a class="code" href="a00065.html">distance_metric_descriptor</a>
78
 
00069 {
79
 
<a name="l00070"></a><a class="code" href="a00065.html#o0">00070</a>      <a class="code" href="a00101.html#ga5">distance_metric</a>   <a class="code" href="a00065.html#o0">metric</a>;
80
 
<a name="l00071"></a><a class="code" href="a00065.html#o1">00071</a>      bm::id_t          <a class="code" href="a00065.html#o1">result</a>;
81
 
00072      
82
 
<a name="l00073"></a><a class="code" href="a00065.html#a0">00073</a>      <a class="code" href="a00065.html#a1">distance_metric_descriptor</a>(distance_metric m)
83
 
00074      : <a class="code" href="a00065.html#o0">metric</a>(m),
84
 
00075        <a class="code" href="a00065.html#o1">result</a>(0)
85
 
00076     {}
86
 
<a name="l00077"></a><a class="code" href="a00065.html#a1">00077</a>     <a class="code" href="a00065.html#a1">distance_metric_descriptor</a>()
87
 
00078     : <a class="code" href="a00065.html#o0">metric</a>(bm::<a class="code" href="a00101.html#gga5a37">COUNT_XOR</a>),
88
 
00079       <a class="code" href="a00065.html#o1">result</a>(0)
89
 
00080     {}
90
 
00081     <span class="comment"></span>
91
 
00082 <span class="comment">    /*! </span>
92
 
00083 <span class="comment">        \brief Sets metric result to 0</span>
93
 
00084 <span class="comment">    */</span>
94
 
<a name="l00085"></a><a class="code" href="a00065.html#a2">00085</a>     <span class="keywordtype">void</span> <a class="code" href="a00065.html#a2">reset</a>()
95
 
00086     {
96
 
00087         <a class="code" href="a00065.html#o1">result</a> = 0;
97
 
00088     }
98
 
00089 };
99
 
00090 
100
 
00091 <span class="comment"></span>
101
 
00092 <span class="comment">/*!</span>
102
 
00093 <span class="comment">    \brief Internal function computes different distance metrics.</span>
103
 
00094 <span class="comment">    \internal </span>
104
 
00095 <span class="comment">    \ingroup  distance</span>
105
 
00096 <span class="comment">     </span>
106
 
00097 <span class="comment">*/</span>
107
 
00098 <span class="keyword">inline</span>
108
 
<a name="l00099"></a><a class="code" href="a00092.html#a146">00099</a> <span class="keywordtype">void</span> <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(<span class="keyword">const</span> bm::word_t* blk,
109
 
00100                                         <span class="keywordtype">unsigned</span> gap,
110
 
00101                                         <span class="keyword">const</span> bm::word_t* arg_blk,
111
 
00102                                         <span class="keywordtype">int</span> arg_gap,
112
 
00103                                         bm::word_t* temp_blk,
113
 
00104                                         <a class="code" href="a00065.html">distance_metric_descriptor</a>* dmit,
114
 
00105                                         <a class="code" href="a00065.html">distance_metric_descriptor</a>* dmit_end)
115
 
00106                                             
116
 
00107 {
117
 
00108      <a class="code" href="a00092.html#a19">gap_word_t</a>* res=0;
118
 
00109      
119
 
00110      <a class="code" href="a00092.html#a19">gap_word_t</a>* g1 = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk);
120
 
00111      <a class="code" href="a00092.html#a19">gap_word_t</a>* g2 = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(arg_blk);
121
 
00112      
122
 
00113      <span class="keywordflow">if</span> (gap) <span class="comment">// first block GAP-type</span>
123
 
00114      {
124
 
00115          <span class="keywordflow">if</span> (arg_gap)  <span class="comment">// both blocks GAP-type</span>
125
 
00116          {
126
 
00117              <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>
127
 
00118              
128
 
00119              <span class="keywordflow">for</span> (<a class="code" href="a00065.html">distance_metric_descriptor</a>* it = dmit;it &lt; dmit_end; ++it)
129
 
00120              {
130
 
00121                  <a class="code" href="a00065.html">distance_metric_descriptor</a>&amp; dmd = *it;
131
 
00122                  
132
 
00123                  <span class="keywordflow">switch</span> (dmd.<a class="code" href="a00065.html#o0">metric</a>)
133
 
00124                  {
134
 
00125                  <span class="keywordflow">case</span> bm::COUNT_AND:
135
 
00126                      res = <a class="code" href="a00096.html#ga28">gap_operation_and</a>(g1, g2, tmp_buf);
136
 
00127                      <span class="keywordflow">break</span>;
137
 
00128                  <span class="keywordflow">case</span> bm::COUNT_OR:
138
 
00129                      res = <a class="code" href="a00096.html#ga30">gap_operation_or</a>(g1, g2, tmp_buf);
139
 
00130                      <span class="keywordflow">break</span>;
140
 
00131                  <span class="keywordflow">case</span> bm::COUNT_SUB_AB:
141
 
00132                      res = <a class="code" href="a00096.html#ga31">gap_operation_sub</a>(g1, g2, tmp_buf); 
142
 
00133                      <span class="keywordflow">break</span>;
143
 
00134                  <span class="keywordflow">case</span> bm::COUNT_SUB_BA:
144
 
00135                      res = <a class="code" href="a00096.html#ga31">gap_operation_sub</a>(g2, g1, tmp_buf); 
145
 
00136                      <span class="keywordflow">break</span>;
146
 
00137                  <span class="keywordflow">case</span> bm::COUNT_XOR:
147
 
00138                      res = <a class="code" href="a00096.html#ga29">gap_operation_xor</a>(g1, g2, tmp_buf); 
148
 
00139                     <span class="keywordflow">break</span>;
149
 
00140                  <span class="keywordflow">case</span> bm::COUNT_A:
150
 
00141                     res = g1;
151
 
00142                     <span class="keywordflow">break</span>;
152
 
00143                  <span class="keywordflow">case</span> bm::COUNT_B:
153
 
00144                     res = g2;
154
 
00145                     <span class="keywordflow">break</span>;
155
 
00146                  } <span class="comment">// switch</span>
156
 
00147                  
157
 
00148                  <span class="keywordflow">if</span> (res)
158
 
00149                      dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(res);
159
 
00150                     
160
 
00151              } <span class="comment">// for it</span>
161
 
00152              
162
 
00153              <span class="keywordflow">return</span>;
163
 
00154 
164
 
00155          }
165
 
00156          <span class="keywordflow">else</span> <span class="comment">// first block - GAP, argument - BITSET</span>
166
 
00157          {
167
 
00158              <span class="keywordflow">for</span> (<a class="code" href="a00065.html">distance_metric_descriptor</a>* it = dmit;it &lt; dmit_end; ++it)
168
 
00159              {
169
 
00160                  <a class="code" href="a00065.html">distance_metric_descriptor</a>&amp; dmd = *it;
170
 
00161                  
171
 
00162                  <span class="keywordflow">switch</span> (dmd.<a class="code" href="a00065.html#o0">metric</a>)
172
 
00163                  {
173
 
00164                  <span class="keywordflow">case</span> bm::COUNT_AND:
174
 
00165                      <span class="keywordflow">if</span> (arg_blk)
175
 
00166                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga6">gap_bitset_and_count</a>(arg_blk, g1);
176
 
00167                      <span class="keywordflow">break</span>;
177
 
00168                  <span class="keywordflow">case</span> bm::COUNT_OR:
178
 
00169                      <span class="keywordflow">if</span> (!arg_blk)
179
 
00170                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g1);
180
 
00171                      <span class="keywordflow">else</span>
181
 
00172                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga9">gap_bitset_or_count</a>(arg_blk, g1); 
182
 
00173                      <span class="keywordflow">break</span>;
183
 
00174                  <span class="keywordflow">case</span> bm::COUNT_SUB_AB:
184
 
00175                      <a class="code" href="a00096.html#ga10">gap_convert_to_bitset</a>((bm::word_t*) temp_blk, g1);
185
 
00176                      dmd.<a class="code" href="a00065.html#o1">result</a> += 
186
 
00177                        <a class="code" href="a00097.html#ga28">bit_operation_sub_count</a>((bm::word_t*)temp_blk, 
187
 
00178                           ((bm::word_t*)temp_blk) + bm::set_block_size,
188
 
00179                            arg_blk);
189
 
00180                  
190
 
00181                      <span class="keywordflow">break</span>;
191
 
00182                  <span class="keywordflow">case</span> bm::COUNT_SUB_BA:
192
 
00183                      dmd.<a class="code" href="a00065.html#o0">metric</a> = bm::COUNT_SUB_AB; <span class="comment">// recursive call to SUB_AB</span>
193
 
00184                      <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(arg_blk,
194
 
00185                                                         arg_gap,
195
 
00186                                                         blk,
196
 
00187                                                         gap,
197
 
00188                                                         temp_blk,
198
 
00189                                                         it, it+1);
199
 
00190                      dmd.<a class="code" href="a00065.html#o0">metric</a> = bm::COUNT_SUB_BA; <span class="comment">// restore status quo</span>
200
 
00191                      <span class="keywordflow">break</span>;
201
 
00192                  <span class="keywordflow">case</span> bm::COUNT_XOR:
202
 
00193                      <span class="keywordflow">if</span> (!arg_blk)
203
 
00194                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g1);
204
 
00195                      <span class="keywordflow">else</span>
205
 
00196                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga8">gap_bitset_xor_count</a>(arg_blk, g1);
206
 
00197                      <span class="keywordflow">break</span>;
207
 
00198                  <span class="keywordflow">case</span> bm::COUNT_A:
208
 
00199                     <span class="keywordflow">if</span> (g1)
209
 
00200                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g1);
210
 
00201                     <span class="keywordflow">break</span>;
211
 
00202                  <span class="keywordflow">case</span> bm::COUNT_B:
212
 
00203                     <span class="keywordflow">if</span> (arg_blk)
213
 
00204                     {
214
 
00205                         dmd.<a class="code" href="a00065.html#o1">result</a> += 
215
 
00206                           <a class="code" href="a00097.html#ga13">bit_block_calc_count</a>(arg_blk, 
216
 
00207                                                arg_blk + bm::set_block_size);
217
 
00208                     }
218
 
00209                     <span class="keywordflow">break</span>;
219
 
00210                  } <span class="comment">// switch</span>
220
 
00211                                      
221
 
00212              } <span class="comment">// for it</span>
222
 
00213              
223
 
00214              <span class="keywordflow">return</span>;
224
 
00215          
225
 
00216          }
226
 
00217      } 
227
 
00218      <span class="keywordflow">else</span> <span class="comment">// first block is BITSET-type</span>
228
 
00219      {     
229
 
00220          <span class="keywordflow">if</span> (arg_gap) <span class="comment">// second argument block is GAP-type</span>
230
 
00221          {
231
 
00222              <span class="keywordflow">for</span> (<a class="code" href="a00065.html">distance_metric_descriptor</a>* it = dmit;it &lt; dmit_end; ++it)
232
 
00223              {
233
 
00224                  <a class="code" href="a00065.html">distance_metric_descriptor</a>&amp; dmd = *it;
234
 
00225                  
235
 
00226                  <span class="keywordflow">switch</span> (dmd.<a class="code" href="a00065.html#o0">metric</a>)
236
 
00227                  {
237
 
00228                  <span class="keywordflow">case</span> bm::COUNT_AND:
238
 
00229                      <span class="keywordflow">if</span> (blk) 
239
 
00230                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga6">gap_bitset_and_count</a>(blk, g2);                         
240
 
00231                      <span class="keywordflow">break</span>;
241
 
00232                  <span class="keywordflow">case</span> bm::COUNT_OR:
242
 
00233                      <span class="keywordflow">if</span> (!blk)
243
 
00234                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g2);
244
 
00235                      <span class="keywordflow">else</span>
245
 
00236                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga9">gap_bitset_or_count</a>(blk, g2);
246
 
00237                      <span class="keywordflow">break</span>;
247
 
00238                  <span class="keywordflow">case</span> bm::COUNT_SUB_AB:
248
 
00239                      <span class="keywordflow">if</span> (blk)
249
 
00240                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga7">gap_bitset_sub_count</a>(blk, g2);
250
 
00241                      <span class="keywordflow">break</span>;
251
 
00242                  <span class="keywordflow">case</span> bm::COUNT_SUB_BA:
252
 
00243                      dmd.<a class="code" href="a00065.html#o0">metric</a> = bm::COUNT_SUB_AB; <span class="comment">// recursive call to SUB_AB</span>
253
 
00244                      <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(arg_blk,
254
 
00245                                                         arg_gap,
255
 
00246                                                         blk,
256
 
00247                                                         gap,
257
 
00248                                                         temp_blk,
258
 
00249                                                         it, it+1);
259
 
00250                      dmd.<a class="code" href="a00065.html#o0">metric</a> = bm::COUNT_SUB_BA; <span class="comment">// restore status quo</span>
260
 
00251                      <span class="keywordflow">break</span>;
261
 
00252                  <span class="keywordflow">case</span> bm::COUNT_XOR:
262
 
00253                      <span class="keywordflow">if</span> (!blk)
263
 
00254                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g2);
264
 
00255                      <span class="keywordflow">else</span>
265
 
00256                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga8">gap_bitset_xor_count</a>(blk, g2); 
266
 
00257                     <span class="keywordflow">break</span>;
267
 
00258                  <span class="keywordflow">case</span> bm::COUNT_A:
268
 
00259                     <span class="keywordflow">if</span> (blk)
269
 
00260                     {
270
 
00261                         dmd.<a class="code" href="a00065.html#o1">result</a> += 
271
 
00262                             <a class="code" href="a00097.html#ga13">bit_block_calc_count</a>(blk, 
272
 
00263                                                  blk + bm::set_block_size);
273
 
00264                     }
274
 
00265                     <span class="keywordflow">break</span>;
275
 
00266                  <span class="keywordflow">case</span> bm::COUNT_B:
276
 
00267                     <span class="keywordflow">if</span> (g2)
277
 
00268                         dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00096.html#ga1">gap_bit_count</a>(g2);
278
 
00269                     <span class="keywordflow">break</span>;
279
 
00270                  } <span class="comment">// switch</span>
280
 
00271                                      
281
 
00272              } <span class="comment">// for it</span>
282
 
00273              
283
 
00274              <span class="keywordflow">return</span>;
284
 
00275          }
285
 
00276      }
286
 
00277 
287
 
00278      <span class="comment">// --------------------------------------------</span>
288
 
00279      <span class="comment">//</span>
289
 
00280      <span class="comment">// Here we combine two plain bitblocks </span>
290
 
00281 
291
 
00282      <span class="keyword">const</span> bm::word_t* blk_end;
292
 
00283      <span class="keyword">const</span> bm::word_t* arg_end;
293
 
00284 
294
 
00285      blk_end = blk + (bm::set_block_size);
295
 
00286      arg_end = arg_blk + (bm::set_block_size);
296
 
00287 
297
 
00288 
298
 
00289      <span class="keywordflow">for</span> (<a class="code" href="a00065.html">distance_metric_descriptor</a>* it = dmit; it &lt; dmit_end; ++it)
299
 
00290      {
300
 
00291          <a class="code" href="a00065.html">distance_metric_descriptor</a>&amp; dmd = *it;
301
 
00292 
302
 
00293          <span class="keywordflow">switch</span> (dmd.<a class="code" href="a00065.html#o0">metric</a>)
303
 
00294          {
304
 
00295          <span class="keywordflow">case</span> bm::COUNT_AND:
305
 
00296              dmd.<a class="code" href="a00065.html#o1">result</a> += 
306
 
00297                 <a class="code" href="a00097.html#ga27">bit_operation_and_count</a>(blk, blk_end, arg_blk);
307
 
00298              <span class="keywordflow">break</span>;
308
 
00299          <span class="keywordflow">case</span> bm::COUNT_OR:
309
 
00300              dmd.<a class="code" href="a00065.html#o1">result</a> += 
310
 
00301                 <a class="code" href="a00097.html#ga29">bit_operation_or_count</a>(blk, blk_end, arg_blk);
311
 
00302              <span class="keywordflow">break</span>;
312
 
00303          <span class="keywordflow">case</span> bm::COUNT_SUB_AB:
313
 
00304              dmd.<a class="code" href="a00065.html#o1">result</a> += 
314
 
00305                 <a class="code" href="a00097.html#ga28">bit_operation_sub_count</a>(blk, blk_end, arg_blk);
315
 
00306              <span class="keywordflow">break</span>;
316
 
00307          <span class="keywordflow">case</span> bm::COUNT_SUB_BA:
317
 
00308              dmd.<a class="code" href="a00065.html#o1">result</a> += 
318
 
00309                 <a class="code" href="a00097.html#ga28">bit_operation_sub_count</a>(arg_blk, arg_end, blk);
319
 
00310              <span class="keywordflow">break</span>;
320
 
00311          <span class="keywordflow">case</span> bm::COUNT_XOR:
321
 
00312              dmd.<a class="code" href="a00065.html#o1">result</a> += 
322
 
00313                 <a class="code" href="a00097.html#ga36">bit_operation_xor_count</a>(blk, blk_end, arg_blk);
323
 
00314              <span class="keywordflow">break</span>;
324
 
00315          <span class="keywordflow">case</span> bm::COUNT_A:
325
 
00316             <span class="keywordflow">if</span> (blk)
326
 
00317                 dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga13">bit_block_calc_count</a>(blk, blk_end);
327
 
00318             <span class="keywordflow">break</span>;
328
 
00319          <span class="keywordflow">case</span> bm::COUNT_B:
329
 
00320             <span class="keywordflow">if</span> (arg_blk)
330
 
00321                 dmd.<a class="code" href="a00065.html#o1">result</a> += <a class="code" href="a00097.html#ga13">bit_block_calc_count</a>(arg_blk, arg_end);
331
 
00322             <span class="keywordflow">break</span>;
332
 
00323          } <span class="comment">// switch</span>
333
 
00324 
334
 
00325      } <span class="comment">// for it</span>
335
 
00326      
336
 
00327      
337
 
00328 
338
 
00329 }
339
 
00330 <span class="comment"></span>
340
 
00331 <span class="comment">/*!</span>
341
 
00332 <span class="comment">    \brief Distance computing template function.</span>
342
 
00333 <span class="comment"></span>
343
 
00334 <span class="comment">    Function receives two bitvectors and an array of distance metrics</span>
344
 
00335 <span class="comment">    (metrics pipeline). Function computes all metrics saves result into</span>
345
 
00336 <span class="comment">    corresponding pipeline results (distance_metric_descriptor::result)</span>
346
 
00337 <span class="comment">    An important detail is that function reuses metric descriptors, </span>
347
 
00338 <span class="comment">    incrementing received values. It allows you to accumulate results </span>
348
 
00339 <span class="comment">    from different calls in the pipeline.</span>
349
 
00340 <span class="comment">    </span>
350
 
00341 <span class="comment">    \param bv1      - argument bitvector 1 (A)</span>
351
 
00342 <span class="comment">    \param bv2      - argument bitvector 2 (B)</span>
352
 
00343 <span class="comment">    \param dmit     - pointer to first element of metric descriptors array</span>
353
 
00344 <span class="comment">                      Input-Output parameter, receives metric code as input,</span>
354
 
00345 <span class="comment">                      computation is added to "result" field</span>
355
 
00346 <span class="comment">    \param dmit_end - pointer to (last+1) element of metric descriptors array</span>
356
 
00347 <span class="comment">    \ingroup  distance</span>
357
 
00348 <span class="comment">    </span>
358
 
00349 <span class="comment">*/</span>
359
 
00350 
360
 
00351 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
361
 
<a name="l00352"></a><a class="code" href="a00101.html#ga0">00352</a> <span class="keywordtype">void</span> <a class="code" href="a00101.html#ga0">distance_operation</a>(<span class="keyword">const</span> BV&amp; bv1, 
362
 
00353                         <span class="keyword">const</span> BV&amp; bv2, 
363
 
00354                         distance_metric_descriptor* dmit,
364
 
00355                         distance_metric_descriptor* dmit_end)
365
 
00356 {
366
 
00357     <span class="keyword">const</span> <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman1 = bv1.get_blocks_manager();
367
 
00358     <span class="keyword">const</span> <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman2 = bv2.get_blocks_manager();
368
 
00359     
369
 
00360     bm::word_t* temp_blk = 0;
370
 
00361     
371
 
00362     {
372
 
00363         <span class="keywordflow">for</span> (distance_metric_descriptor* it = dmit; it &lt; dmit_end; ++it)
373
 
00364         {
374
 
00365             <span class="keywordflow">if</span> (it-&gt;metric == bm::COUNT_SUB_AB || 
375
 
00366                 it-&gt;metric == bm::COUNT_SUB_BA)
376
 
00367             {
377
 
00368                 temp_blk = bv1.allocate_tempblock();
378
 
00369                 <span class="keywordflow">break</span>;
379
 
00370             }
380
 
00371         }
381
 
00372     }
382
 
00373     
383
 
00374   
384
 
00375     bm::word_t*** blk_root = bman1.get_rootblock();
385
 
00376     <span class="keywordtype">unsigned</span> block_idx = 0;
386
 
00377     <span class="keywordtype">unsigned</span> i, j;
387
 
00378     
388
 
00379     <span class="keyword">const</span> bm::word_t* blk;
389
 
00380     <span class="keyword">const</span> bm::word_t* arg_blk;
390
 
00381     <span class="keywordtype">bool</span>  blk_gap;
391
 
00382     <span class="keywordtype">bool</span>  arg_gap;
392
 
00383 
393
 
00384     <a class="code" href="a00077.html#a13">BM_SET_MMX_GUARD</a>
394
 
00385 
395
 
00386     <span class="keywordflow">for</span> (i = 0; i &lt; bman1.top_block_size(); ++i)
396
 
00387     {
397
 
00388         bm::word_t** blk_blk = blk_root[i];
398
 
00389 
399
 
00390         <span class="keywordflow">if</span> (blk_blk == 0) <span class="comment">// not allocated</span>
400
 
00391         {
401
 
00392             <span class="keyword">const</span> bm::word_t* <span class="keyword">const</span>* bvbb = bman2.get_topblock(i);
402
 
00393             <span class="keywordflow">if</span> (bvbb == 0) 
403
 
00394             {
404
 
00395                 block_idx += bm::set_array_size;
405
 
00396                 <span class="keywordflow">continue</span>;
406
 
00397             }
407
 
00398 
408
 
00399             blk = 0;
409
 
00400             blk_gap = <span class="keyword">false</span>;
410
 
00401 
411
 
00402             <span class="keywordflow">for</span> (j = 0; j &lt; bm::set_array_size; ++j,++block_idx)
412
 
00403             {                
413
 
00404                 arg_blk = bman2.get_block(i, j);
414
 
00405                 arg_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(bman2, arg_blk, block_idx);
415
 
00406 
416
 
00407                 <span class="keywordflow">if</span> (!arg_blk) 
417
 
00408                     <span class="keywordflow">continue</span>;
418
 
00409                 <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(blk, blk_gap,
419
 
00410                                                    arg_blk, arg_gap,
420
 
00411                                                    temp_blk,
421
 
00412                                                    dmit, dmit_end);
422
 
00413             } <span class="comment">// for j</span>
423
 
00414             <span class="keywordflow">continue</span>;
424
 
00415         }
425
 
00416 
426
 
00417         <span class="keywordflow">for</span> (j = 0; j &lt; bm::set_array_size; ++j, ++block_idx)
427
 
00418         {
428
 
00419             blk = blk_blk[j];
429
 
00420             arg_blk = bman2.get_block(i, j);
430
 
00421 
431
 
00422             <span class="keywordflow">if</span> (blk == 0 &amp;&amp; arg_blk == 0)
432
 
00423                 <span class="keywordflow">continue</span>;
433
 
00424                 
434
 
00425             arg_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(bman2, arg_blk, block_idx);
435
 
00426             blk_gap = <a class="code" href="a00077.html#a10">BM_IS_GAP</a>(bman1, blk, block_idx);
436
 
00427             
437
 
00428             <a class="code" href="a00092.html#a146">combine_count_operation_with_block</a>(blk, blk_gap,
438
 
00429                                                arg_blk, arg_gap,
439
 
00430                                                temp_blk,
440
 
00431                                                dmit, dmit_end);
441
 
00432             
442
 
00433 
443
 
00434         } <span class="comment">// for j</span>
444
 
00435 
445
 
00436     } <span class="comment">// for i</span>
446
 
00437     
447
 
00438     <span class="keywordflow">if</span> (temp_blk)
448
 
00439     {
449
 
00440         bv1.free_tempblock(temp_blk);
450
 
00441     }
451
 
00442 
452
 
00443 }
453
 
00444 
454
 
00445 
455
 
00446 <span class="comment"></span>
456
 
00447 <span class="comment">/*!</span>
457
 
00448 <span class="comment">   \brief Computes bitcount of AND operation of two bitsets</span>
458
 
00449 <span class="comment">   \param bv1 - Argument bit-vector.</span>
459
 
00450 <span class="comment">   \param bv2 - Argument bit-vector.</span>
460
 
00451 <span class="comment">   \return bitcount of the result</span>
461
 
00452 <span class="comment">   \ingroup  distance</span>
462
 
00453 <span class="comment">*/</span>
463
 
00454 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
464
 
<a name="l00455"></a><a class="code" href="a00101.html#ga1">00455</a> bm::id_t <a class="code" href="a00101.html#ga1">count_and</a>(<span class="keyword">const</span> BV&amp; bv1, <span class="keyword">const</span> BV&amp; bv2)
465
 
00456 {
466
 
00457     distance_metric_descriptor dmd(bm::COUNT_AND);
467
 
00458     
468
 
00459     <a class="code" href="a00101.html#ga0">distance_operation</a>(bv1, bv2, &amp;dmd, &amp;dmd+1);
469
 
00460     <span class="keywordflow">return</span> dmd.<a class="code" href="a00065.html#o1">result</a>;
470
 
00461 }
471
 
00462 
472
 
00463 <span class="comment"></span>
473
 
00464 <span class="comment">/*!</span>
474
 
00465 <span class="comment">   \brief Computes bitcount of XOR operation of two bitsets</span>
475
 
00466 <span class="comment">   \param bv1 - Argument bit-vector.</span>
476
 
00467 <span class="comment">   \param bv2 - Argument bit-vector.</span>
477
 
00468 <span class="comment">   \return bitcount of the result</span>
478
 
00469 <span class="comment">   \ingroup  distance</span>
479
 
00470 <span class="comment">*/</span>
480
 
00471 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
481
 
<a name="l00472"></a><a class="code" href="a00101.html#ga2">00472</a> bm::id_t <a class="code" href="a00101.html#ga2">count_xor</a>(<span class="keyword">const</span> BV&amp; bv1, <span class="keyword">const</span> BV&amp; bv2)
482
 
00473 {
483
 
00474     distance_metric_descriptor dmd(bm::COUNT_XOR);
484
 
00475     
485
 
00476     <a class="code" href="a00101.html#ga0">distance_operation</a>(bv1, bv2, &amp;dmd, &amp;dmd+1);
486
 
00477     <span class="keywordflow">return</span> dmd.<a class="code" href="a00065.html#o1">result</a>;
487
 
00478 }
488
 
00479 
489
 
00480 <span class="comment"></span>
490
 
00481 <span class="comment">/*!</span>
491
 
00482 <span class="comment">   \brief Computes bitcount of SUB operation of two bitsets</span>
492
 
00483 <span class="comment">   \param bv1 - Argument bit-vector.</span>
493
 
00484 <span class="comment">   \param bv2 - Argument bit-vector.</span>
494
 
00485 <span class="comment">   \return bitcount of the result</span>
495
 
00486 <span class="comment">   \ingroup  distance</span>
496
 
00487 <span class="comment">*/</span>
497
 
00488 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
498
 
<a name="l00489"></a><a class="code" href="a00101.html#ga3">00489</a> bm::id_t <a class="code" href="a00101.html#ga3">count_sub</a>(<span class="keyword">const</span> BV&amp; bv1, <span class="keyword">const</span> BV&amp; bv2)
499
 
00490 {
500
 
00491     distance_metric_descriptor dmd(bm::COUNT_SUB_AB);
501
 
00492     
502
 
00493     <a class="code" href="a00101.html#ga0">distance_operation</a>(bv1, bv2, &amp;dmd, &amp;dmd+1);
503
 
00494     <span class="keywordflow">return</span> dmd.<a class="code" href="a00065.html#o1">result</a>;
504
 
00495 }
505
 
00496 
506
 
00497 <span class="comment"></span>
507
 
00498 <span class="comment">/*!    </span>
508
 
00499 <span class="comment">   \brief Computes bitcount of OR operation of two bitsets</span>
509
 
00500 <span class="comment">   \param bv1 - Argument bit-vector.</span>
510
 
00501 <span class="comment">   \param bv2 - Argument bit-vector.</span>
511
 
00502 <span class="comment">   \return bitcount of the result</span>
512
 
00503 <span class="comment">   \ingroup  distance</span>
513
 
00504 <span class="comment">*/</span>
514
 
00505 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
515
 
<a name="l00506"></a><a class="code" href="a00101.html#ga4">00506</a> bm::id_t <a class="code" href="a00101.html#ga4">count_or</a>(<span class="keyword">const</span> BV&amp; bv1, <span class="keyword">const</span> BV&amp; bv2)
516
 
00507 {
517
 
00508     distance_metric_descriptor dmd(bm::COUNT_OR);
518
 
00509     
519
 
00510     <a class="code" href="a00101.html#ga0">distance_operation</a>(bv1, bv2, &amp;dmd, &amp;dmd+1);
520
 
00511     <span class="keywordflow">return</span> dmd.<a class="code" href="a00065.html#o1">result</a>;
521
 
00512 }
522
 
00513 
523
 
00514 <span class="comment"></span>
524
 
00515 <span class="comment">/**</span>
525
 
00516 <span class="comment">    \brief Internal algorithms scans the input for the block range limit</span>
526
 
00517 <span class="comment">    \internal</span>
527
 
00518 <span class="comment">*/</span>
528
 
00519 <span class="keyword">template</span>&lt;<span class="keyword">class</span> It&gt;
529
 
<a name="l00520"></a><a class="code" href="a00092.html#a152">00520</a> It <a class="code" href="a00092.html#a152">block_range_scan</a>(It  first, It last, <span class="keywordtype">unsigned</span> nblock, <span class="keywordtype">unsigned</span>* max_id)
530
 
00521 {
531
 
00522     It right;
532
 
00523     <span class="keywordflow">for</span> (right = first; right != last; ++right)
533
 
00524     {
534
 
00525         <span class="keywordtype">unsigned</span> v = unsigned(*right);
535
 
00526         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(v &lt; bm::id_max);
536
 
00527         <span class="keywordflow">if</span> (v &gt;= *max_id)
537
 
00528             *max_id = v;
538
 
00529         <span class="keywordtype">unsigned</span> nb = v &gt;&gt; bm::set_block_shift;
539
 
00530         <span class="keywordflow">if</span> (nb != nblock)
540
 
00531             <span class="keywordflow">break</span>;
541
 
00532     }
542
 
00533     <span class="keywordflow">return</span> right;
543
 
00534 }
544
 
00535 <span class="comment"></span>
545
 
00536 <span class="comment">/**</span>
546
 
00537 <span class="comment">    \brief OR Combine bitvector and the iterable sequence </span>
547
 
00538 <span class="comment"></span>
548
 
00539 <span class="comment">    Algorithm combines bvector with sequence of integers </span>
549
 
00540 <span class="comment">    (represents another set). When the agrument set is sorted </span>
550
 
00541 <span class="comment">    this method can give serious increase in performance.</span>
551
 
00542 <span class="comment">    </span>
552
 
00543 <span class="comment">    \param bv     - destination bitvector</span>
553
 
00544 <span class="comment">    \param first  - first element of the iterated sequence</span>
554
 
00545 <span class="comment">    \param last   - last element of the iterated sequence</span>
555
 
00546 <span class="comment">    </span>
556
 
00547 <span class="comment">    \ingroup setalgo</span>
557
 
00548 <span class="comment">*/</span>
558
 
00549 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV, <span class="keyword">class</span> It&gt;
559
 
<a name="l00550"></a><a class="code" href="a00100.html#ga0">00550</a> <span class="keywordtype">void</span> <a class="code" href="a00100.html#ga0">combine_or</a>(BV&amp; bv, It  first, It last)
560
 
00551 {
561
 
00552     <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman = bv.get_blocks_manager();
562
 
00553     <span class="keywordtype">unsigned</span> max_id = bv.size();
563
 
00554 
564
 
00555     <span class="keywordflow">while</span> (first &lt; last)
565
 
00556     {
566
 
00557         <span class="keywordtype">unsigned</span> nblock = unsigned((*first) &gt;&gt; bm::set_block_shift);     
567
 
00558         It right = <a class="code" href="a00092.html#a152">block_range_scan</a>(first, last, nblock, &amp;max_id);
568
 
00559 
569
 
00560         <span class="keywordflow">if</span> (max_id &gt;= bv.size())
570
 
00561             bv.resize(max_id + 1);
571
 
00562 
572
 
00563         <span class="comment">// now we have one in-block array of bits to set</span>
573
 
00564         
574
 
00565         label1:
575
 
00566         
576
 
00567         <span class="keywordtype">int</span> block_type;
577
 
00568         bm::word_t* blk = 
578
 
00569             bman.check_allocate_block(nblock, 
579
 
00570                                       <span class="keyword">true</span>, 
580
 
00571                                       bv.get_new_blocks_strat(), 
581
 
00572                                       &amp;block_type);
582
 
00573         <span class="keywordflow">if</span> (!blk) 
583
 
00574             <span class="keywordflow">continue</span>;
584
 
00575                         
585
 
00576         <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
586
 
00577         {            
587
 
00578             bm::gap_word_t* gap_blk = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk);
588
 
00579             <span class="keywordtype">unsigned</span> threshold = <a class="code" href="a00096.html#ga21">bm::gap_limit</a>(gap_blk, bman.glen());
589
 
00580             
590
 
00581             <span class="keywordflow">for</span> (; first &lt; right; ++first)
591
 
00582             {
592
 
00583                 <span class="keywordtype">unsigned</span> is_set;
593
 
00584                 <span class="keywordtype">unsigned</span> nbit   = (*first) &amp; bm::set_block_mask; 
594
 
00585                 
595
 
00586                 <span class="keywordtype">unsigned</span> new_block_len =
596
 
00587                     <a class="code" href="a00096.html#ga4">gap_set_value</a>(<span class="keyword">true</span>, gap_blk, nbit, &amp;is_set);
597
 
00588                 <span class="keywordflow">if</span> (new_block_len &gt; threshold) 
598
 
00589                 {
599
 
00590                     bman.extend_gap_block(nblock, gap_blk);
600
 
00591                     ++first;
601
 
00592                     <span class="keywordflow">goto</span> label1;  <span class="comment">// block pointer changed - goto reset</span>
602
 
00593                 }
603
 
00594             }
604
 
00595         }
605
 
00596         <span class="keywordflow">else</span> <span class="comment">// bit block</span>
606
 
00597         {
607
 
00598             <span class="keywordflow">for</span> (; first &lt; right; ++first)
608
 
00599             {
609
 
00600                 <span class="keywordtype">unsigned</span> nbit   = unsigned(*first &amp; bm::set_block_mask); 
610
 
00601                 <span class="keywordtype">unsigned</span> nword  = unsigned(nbit &gt;&gt; bm::set_word_shift); 
611
 
00602                 nbit &amp;= bm::set_word_mask;
612
 
00603                 blk[nword] |= (bm::word_t)1 &lt;&lt; nbit;
613
 
00604             } <span class="comment">// for</span>
614
 
00605         }
615
 
00606     } <span class="comment">// while</span>
616
 
00607     
617
 
00608     bv.forget_count();
618
 
00609 }
619
 
00610 
620
 
00611 <span class="comment"></span>
621
 
00612 <span class="comment">/**</span>
622
 
00613 <span class="comment">    \brief XOR Combine bitvector and the iterable sequence </span>
623
 
00614 <span class="comment"></span>
624
 
00615 <span class="comment">    Algorithm combines bvector with sequence of integers </span>
625
 
00616 <span class="comment">    (represents another set). When the agrument set is sorted </span>
626
 
00617 <span class="comment">    this method can give serious increase in performance.</span>
627
 
00618 <span class="comment">    </span>
628
 
00619 <span class="comment">    \param bv     - destination bitvector</span>
629
 
00620 <span class="comment">    \param first  - first element of the iterated sequence</span>
630
 
00621 <span class="comment">    \param last   - last element of the iterated sequence</span>
631
 
00622 <span class="comment">    </span>
632
 
00623 <span class="comment">    \ingroup setalgo</span>
633
 
00624 <span class="comment">*/</span>
634
 
00625 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV, <span class="keyword">class</span> It&gt;
635
 
<a name="l00626"></a><a class="code" href="a00100.html#ga1">00626</a> <span class="keywordtype">void</span> <a class="code" href="a00100.html#ga1">combine_xor</a>(BV&amp; bv, It  first, It last)
636
 
00627 {
637
 
00628     <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman = bv.get_blocks_manager();
638
 
00629     <span class="keywordtype">unsigned</span> max_id = bv.size();
639
 
00630 
640
 
00631     <span class="keywordflow">while</span> (first &lt; last)
641
 
00632     {
642
 
00633         <span class="keywordtype">unsigned</span> nblock = unsigned((*first) &gt;&gt; bm::set_block_shift);     
643
 
00634         It right = <a class="code" href="a00092.html#a152">block_range_scan</a>(first, last, nblock, &amp;max_id);
644
 
00635 
645
 
00636         <span class="keywordflow">if</span> (max_id &gt;= bv.size())
646
 
00637             bv.resize(max_id + 1);
647
 
00638 
648
 
00639         <span class="comment">// now we have one in-block array of bits to set</span>
649
 
00640         
650
 
00641         label1:
651
 
00642         
652
 
00643         <span class="keywordtype">int</span> block_type;
653
 
00644         bm::word_t* blk = 
654
 
00645             bman.check_allocate_block(nblock, 
655
 
00646                                       <span class="keyword">true</span>, 
656
 
00647                                       bv.get_new_blocks_strat(), 
657
 
00648                                       &amp;block_type,
658
 
00649                                       <span class="keyword">false</span> <span class="comment">/* no null return */</span>);
659
 
00650         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(blk); 
660
 
00651                         
661
 
00652         <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
662
 
00653         {
663
 
00654             bm::gap_word_t* gap_blk = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk);
664
 
00655             <span class="keywordtype">unsigned</span> threshold = <a class="code" href="a00096.html#ga21">bm::gap_limit</a>(gap_blk, bman.glen());
665
 
00656             
666
 
00657             <span class="keywordflow">for</span> (; first &lt; right; ++first)
667
 
00658             {
668
 
00659                 <span class="keywordtype">unsigned</span> is_set;
669
 
00660                 <span class="keywordtype">unsigned</span> nbit   = (*first) &amp; bm::set_block_mask; 
670
 
00661                 
671
 
00662                 is_set = <a class="code" href="a00096.html#ga0">gap_test</a>(gap_blk, nbit);
672
 
00663                 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(is_set &lt;= 1);
673
 
00664                 is_set ^= 1; 
674
 
00665                 
675
 
00666                 <span class="keywordtype">unsigned</span> new_block_len =
676
 
00667                     <a class="code" href="a00096.html#ga4">gap_set_value</a>(is_set, gap_blk, nbit, &amp;is_set);
677
 
00668                 <span class="keywordflow">if</span> (new_block_len &gt; threshold) 
678
 
00669                 {
679
 
00670                     bman.extend_gap_block(nblock, gap_blk);
680
 
00671                     ++first;
681
 
00672                     <span class="keywordflow">goto</span> label1;  <span class="comment">// block pointer changed - goto reset</span>
682
 
00673                 }
683
 
00674             }
684
 
00675         }
685
 
00676         <span class="keywordflow">else</span> <span class="comment">// bit block</span>
686
 
00677         {
687
 
00678             <span class="keywordflow">for</span> (; first &lt; right; ++first)
688
 
00679             {
689
 
00680                 <span class="keywordtype">unsigned</span> nbit   = unsigned(*first &amp; bm::set_block_mask); 
690
 
00681                 <span class="keywordtype">unsigned</span> nword  = unsigned(nbit &gt;&gt; bm::set_word_shift); 
691
 
00682                 nbit &amp;= bm::set_word_mask;
692
 
00683                 blk[nword] ^= (bm::word_t)1 &lt;&lt; nbit;
693
 
00684             } <span class="comment">// for</span>
694
 
00685         }
695
 
00686     } <span class="comment">// while</span>
696
 
00687     
697
 
00688     bv.forget_count();
698
 
00689 }
699
 
00690 
700
 
00691 
701
 
00692 <span class="comment"></span>
702
 
00693 <span class="comment">/**</span>
703
 
00694 <span class="comment">    \brief SUB Combine bitvector and the iterable sequence </span>
704
 
00695 <span class="comment"></span>
705
 
00696 <span class="comment">    Algorithm combines bvector with sequence of integers </span>
706
 
00697 <span class="comment">    (represents another set). When the agrument set is sorted </span>
707
 
00698 <span class="comment">    this method can give serious increase in performance.</span>
708
 
00699 <span class="comment">    </span>
709
 
00700 <span class="comment">    \param bv     - destination bitvector</span>
710
 
00701 <span class="comment">    \param first  - first element of the iterated sequence</span>
711
 
00702 <span class="comment">    \param last   - last element of the iterated sequence</span>
712
 
00703 <span class="comment">    </span>
713
 
00704 <span class="comment">    \ingroup setalgo</span>
714
 
00705 <span class="comment">*/</span>
715
 
00706 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV, <span class="keyword">class</span> It&gt;
716
 
<a name="l00707"></a><a class="code" href="a00100.html#ga2">00707</a> <span class="keywordtype">void</span> <a class="code" href="a00100.html#ga2">combine_sub</a>(BV&amp; bv, It  first, It last)
717
 
00708 {
718
 
00709     <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman = bv.get_blocks_manager();
719
 
00710     <span class="keywordtype">unsigned</span> max_id = bv.size();
720
 
00711 
721
 
00712     <span class="keywordflow">while</span> (first &lt; last)
722
 
00713     {
723
 
00714         <span class="keywordtype">unsigned</span> nblock = unsigned((*first) &gt;&gt; bm::set_block_shift);     
724
 
00715         It right = <a class="code" href="a00092.html#a152">block_range_scan</a>(first, last, nblock, &amp;max_id);
725
 
00716 
726
 
00717         <span class="keywordflow">if</span> (max_id &gt;= bv.size())
727
 
00718             bv.resize(max_id + 1);
728
 
00719 
729
 
00720         <span class="comment">// now we have one in-block array of bits to set</span>
730
 
00721         
731
 
00722         label1:
732
 
00723         
733
 
00724         <span class="keywordtype">int</span> block_type;
734
 
00725         bm::word_t* blk = 
735
 
00726             bman.check_allocate_block(nblock, 
736
 
00727                                       <span class="keyword">false</span>, 
737
 
00728                                       bv.get_new_blocks_strat(), 
738
 
00729                                       &amp;block_type);
739
 
00730 
740
 
00731         <span class="keywordflow">if</span> (!blk)
741
 
00732             <span class="keywordflow">continue</span>;
742
 
00733                         
743
 
00734         <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
744
 
00735         {
745
 
00736             bm::gap_word_t* gap_blk = <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk);
746
 
00737             <span class="keywordtype">unsigned</span> threshold = <a class="code" href="a00096.html#ga21">bm::gap_limit</a>(gap_blk, bman.glen());
747
 
00738             
748
 
00739             <span class="keywordflow">for</span> (; first &lt; right; ++first)
749
 
00740             {
750
 
00741                 <span class="keywordtype">unsigned</span> is_set;
751
 
00742                 <span class="keywordtype">unsigned</span> nbit   = (*first) &amp; bm::set_block_mask; 
752
 
00743                 
753
 
00744                 is_set = <a class="code" href="a00096.html#ga0">gap_test</a>(gap_blk, nbit);
754
 
00745                 <span class="keywordflow">if</span> (!is_set)
755
 
00746                     <span class="keywordflow">continue</span>;
756
 
00747                 
757
 
00748                 <span class="keywordtype">unsigned</span> new_block_len =
758
 
00749                     <a class="code" href="a00096.html#ga4">gap_set_value</a>(<span class="keyword">false</span>, gap_blk, nbit, &amp;is_set);
759
 
00750                 <span class="keywordflow">if</span> (new_block_len &gt; threshold) 
760
 
00751                 {
761
 
00752                     bman.extend_gap_block(nblock, gap_blk);
762
 
00753                     ++first;
763
 
00754                     <span class="keywordflow">goto</span> label1;  <span class="comment">// block pointer changed - goto reset</span>
764
 
00755                 }
765
 
00756             }
766
 
00757         }
767
 
00758         <span class="keywordflow">else</span> <span class="comment">// bit block</span>
768
 
00759         {
769
 
00760             <span class="keywordflow">for</span> (; first &lt; right; ++first)
770
 
00761             {
771
 
00762                 <span class="keywordtype">unsigned</span> nbit   = unsigned(*first &amp; bm::set_block_mask); 
772
 
00763                 <span class="keywordtype">unsigned</span> nword  = unsigned(nbit &gt;&gt; bm::set_word_shift); 
773
 
00764                 nbit &amp;= bm::set_word_mask;
774
 
00765                 blk[nword] &amp;= ~((bm::word_t)1 &lt;&lt; nbit);
775
 
00766             } <span class="comment">// for</span>
776
 
00767         }
777
 
00768     } <span class="comment">// while</span>
778
 
00769     
779
 
00770     bv.forget_count();
780
 
00771 }
781
 
00772 <span class="comment"></span>
782
 
00773 <span class="comment">/**</span>
783
 
00774 <span class="comment">    \brief AND Combine bitvector and the iterable sequence </span>
784
 
00775 <span class="comment"></span>
785
 
00776 <span class="comment">    Algorithm combines bvector with sequence of integers </span>
786
 
00777 <span class="comment">    (represents another set). When the agrument set is sorted </span>
787
 
00778 <span class="comment">    this method can give serious increase in performance.</span>
788
 
00779 <span class="comment">    </span>
789
 
00780 <span class="comment">    \param bv     - destination bitvector</span>
790
 
00781 <span class="comment">    \param first  - first element of the iterated sequence</span>
791
 
00782 <span class="comment">    \param last   - last element of the iterated sequence</span>
792
 
00783 <span class="comment">    </span>
793
 
00784 <span class="comment">    \ingroup setalgo</span>
794
 
00785 <span class="comment">*/</span>
795
 
00786 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV, <span class="keyword">class</span> It&gt;
796
 
<a name="l00787"></a><a class="code" href="a00100.html#ga3">00787</a> <span class="keywordtype">void</span> <a class="code" href="a00100.html#ga3">combine_and</a>(BV&amp; bv, It  first, It last)
797
 
00788 {
798
 
00789     BV bv_tmp;
799
 
00790     <a class="code" href="a00100.html#ga0">combine_or</a>(bv_tmp, first, last);
800
 
00791     bv &amp;= bv_tmp;
801
 
00792 }
802
 
00793 <span class="comment"></span>
803
 
00794 <span class="comment">/*!</span>
804
 
00795 <span class="comment">    \brief Compute number of bit intervals (GAPs) in the bitvector</span>
805
 
00796 <span class="comment">    </span>
806
 
00797 <span class="comment">    Algorithm traverses bit vector and count number of uninterrupted</span>
807
 
00798 <span class="comment">    intervals of 1s and 0s.</span>
808
 
00799 <span class="comment">    &lt;pre&gt;</span>
809
 
00800 <span class="comment">    For example: </span>
810
 
00801 <span class="comment">      00001111100000 - gives us 3 intervals</span>
811
 
00802 <span class="comment">      10001111100000 - 4 intervals</span>
812
 
00803 <span class="comment">      00000000000000 - 1 interval</span>
813
 
00804 <span class="comment">      11111111111111 - 1 interval</span>
814
 
00805 <span class="comment">    &lt;/pre&gt;</span>
815
 
00806 <span class="comment">    \return Number of intervals</span>
816
 
00807 <span class="comment">    \ingroup setalgo</span>
817
 
00808 <span class="comment">*/</span>
818
 
00809 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV&gt;
819
 
<a name="l00810"></a><a class="code" href="a00100.html#ga4">00810</a> bm::id_t <a class="code" href="a00100.html#ga4">count_intervals</a>(<span class="keyword">const</span> BV&amp; bv)
820
 
00811 {
821
 
00812     <span class="keyword">const</span> <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman = bv.get_blocks_manager();
822
 
00813 
823
 
00814     bm::word_t*** blk_root = bman.get_rootblock();
824
 
00815     <span class="keyword">typename</span> BV::blocks_manager_type::block_count_change_func func(bman);
825
 
00816     <a class="code" href="a00092.html#a55">for_each_block</a>(blk_root, bman.top_block_size(), bm::set_array_size, func);
826
 
00817 
827
 
00818     <span class="keywordflow">return</span> func.count();        
828
 
00819 }
829
 
00820 <span class="comment"></span>
830
 
00821 <span class="comment">/*!</span>
831
 
00822 <span class="comment">    \brief Export bitset from an array of binary data representing</span>
832
 
00823 <span class="comment">    the bit vector. </span>
833
 
00824 <span class="comment"></span>
834
 
00825 <span class="comment">    Input array can be array of ints, chars or other native C types.</span>
835
 
00826 <span class="comment">    Method works with iterators, which makes it compatible with </span>
836
 
00827 <span class="comment">    STL containers and C arrays</span>
837
 
00828 <span class="comment"></span>
838
 
00829 <span class="comment">    \param bv     - destination bitvector</span>
839
 
00830 <span class="comment">    \param first  - first element of the iterated sequence</span>
840
 
00831 <span class="comment">    \param last   - last element of the iterated sequence</span>
841
 
00832 <span class="comment"></span>
842
 
00833 <span class="comment">    \ingroup setalgo</span>
843
 
00834 <span class="comment">*/</span>
844
 
00835 <span class="keyword">template</span>&lt;<span class="keyword">class</span> BV, <span class="keyword">class</span> It&gt;
845
 
<a name="l00836"></a><a class="code" href="a00100.html#ga5">00836</a> <span class="keywordtype">void</span> <a class="code" href="a00100.html#ga5">export_array</a>(BV&amp; bv, It first, It last)
846
 
00837 {
847
 
00838     <span class="keyword">typename</span> BV::blocks_manager_type&amp; bman = bv.get_blocks_manager();
848
 
00839     <span class="keywordtype">unsigned</span> inp_word_size = <span class="keyword">sizeof</span>(*first);
849
 
00840     size_t array_size = last - first;
850
 
00841     size_t bit_cnt = array_size * inp_word_size * 8;
851
 
00842     <span class="keywordtype">int</span> block_type;
852
 
00843     bm::word_t tmp;
853
 
00844     <span class="keywordtype">unsigned</span> b1, b2, b3, b4;
854
 
00845 
855
 
00846     <span class="keywordflow">if</span> (bit_cnt &gt;= bv.size())
856
 
00847         bv.resize((bm::id_t)bit_cnt + 1);
857
 
00848     <span class="keywordflow">else</span> 
858
 
00849         bv.set_range((bm::id_t)bit_cnt, bv.size() - 1, <span class="keyword">false</span>);
859
 
00850     
860
 
00851     <span class="keywordflow">switch</span> (inp_word_size)
861
 
00852     {
862
 
00853     <span class="keywordflow">case</span> 1:
863
 
00854         {
864
 
00855             size_t word_cnt = array_size / 4;
865
 
00856             <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; bm::set_total_blocks; ++i)
866
 
00857             {
867
 
00858                 bm::word_t* blk = 
868
 
00859                     bman.check_allocate_block(i, 
869
 
00860                                               <span class="keyword">false</span>, 
870
 
00861                                               BM_BIT, 
871
 
00862                                               &amp;block_type,
872
 
00863                                               <span class="keyword">false</span> <span class="comment">/*no NULL ret*/</span>);
873
 
00864                 <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
874
 
00865                 {
875
 
00866                     blk = bman.convert_gap2bitset(i, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
876
 
00867                 }
877
 
00868                 
878
 
00869                 bm::word_t* wrd_ptr = blk;
879
 
00870                 <span class="keywordflow">if</span> (word_cnt &gt;= bm::set_block_size) {
880
 
00871                     bm::word_t* wrd_end = blk + bm::set_block_size;
881
 
00872                     <span class="keywordflow">do</span> {
882
 
00873                         b1 = *first++; b2 = *first++;
883
 
00874                         b3 = *first++; b4 = *first++;
884
 
00875                         tmp = b1 | (b2 &lt;&lt; 8) | (b3 &lt;&lt; 16) | (b4 &lt;&lt; 24);
885
 
00876                         *wrd_ptr++ = tmp;
886
 
00877                     } <span class="keywordflow">while</span> (wrd_ptr &lt; wrd_end);
887
 
00878                     word_cnt -= bm::set_block_size;
888
 
00879                 } 
889
 
00880                 <span class="keywordflow">else</span> 
890
 
00881                 {
891
 
00882                     size_t to_convert = last - first;
892
 
00883                     <span class="keywordflow">for</span> (size_t j = 0; j &lt; to_convert / 4; ++j)
893
 
00884                     {
894
 
00885                         b1 = *first++; b2 = *first++;
895
 
00886                         b3 = *first++; b4 = *first++;
896
 
00887                         tmp = b1 | (b2 &lt;&lt; 8) | (b3 &lt;&lt; 16) | (b4 &lt;&lt; 24);
897
 
00888                         *wrd_ptr++ = tmp;
898
 
00889                     }
899
 
00890                     <span class="keywordflow">while</span> (1)
900
 
00891                     {
901
 
00892                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
902
 
00893                         *wrd_ptr = *first++;
903
 
00894                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
904
 
00895                         *wrd_ptr |= (*first++) &lt;&lt; 8;
905
 
00896                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
906
 
00897                         *wrd_ptr |= (*first++) &lt;&lt; 16;
907
 
00898                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
908
 
00899                         *wrd_ptr |= (*first++) &lt;&lt; 24;
909
 
00900                         ++wrd_ptr;
910
 
00901                     }
911
 
00902                 }
912
 
00903                 <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
913
 
00904             } <span class="comment">// for</span>
914
 
00905         }
915
 
00906         <span class="keywordflow">break</span>;
916
 
00907     <span class="keywordflow">case</span> 2:
917
 
00908         {
918
 
00909             size_t word_cnt = array_size / 2;
919
 
00910             <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; bm::set_total_blocks; ++i)
920
 
00911             {
921
 
00912                 bm::word_t* blk = 
922
 
00913                     bman.check_allocate_block(i, 
923
 
00914                                               <span class="keyword">false</span>, 
924
 
00915                                               BM_BIT, 
925
 
00916                                               &amp;block_type,
926
 
00917                                               <span class="keyword">false</span> <span class="comment">/*no NULL ret*/</span>);
927
 
00918                 <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
928
 
00919                 {
929
 
00920                     blk = bman.convert_gap2bitset(i, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
930
 
00921                 }
931
 
00922                 
932
 
00923                 bm::word_t* wrd_ptr = blk;
933
 
00924                 <span class="keywordflow">if</span> (word_cnt &gt;= bm::set_block_size) {
934
 
00925                     bm::word_t* wrd_end = blk + bm::set_block_size;
935
 
00926                     <span class="keywordflow">do</span> {
936
 
00927                         b1 = *first++; b2 = *first++;
937
 
00928                         tmp = b1 | (b2 &lt;&lt; 16);
938
 
00929                         *wrd_ptr++ = tmp;
939
 
00930                     } <span class="keywordflow">while</span> (wrd_ptr &lt; wrd_end);
940
 
00931                     word_cnt -= bm::set_block_size;
941
 
00932                 } 
942
 
00933                 <span class="keywordflow">else</span> 
943
 
00934                 {
944
 
00935                     size_t to_convert = last - first;
945
 
00936                     <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j = 0; j &lt; to_convert / 2; ++j)
946
 
00937                     {
947
 
00938                         b1 = *first++; b2 = *first++;
948
 
00939                         tmp = b1 | (b2 &lt;&lt; 16);
949
 
00940                         *wrd_ptr++ = tmp;
950
 
00941                     }
951
 
00942                     <span class="keywordflow">while</span> (1)
952
 
00943                     {
953
 
00944                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
954
 
00945                         *wrd_ptr = *first++;
955
 
00946                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
956
 
00947                         *wrd_ptr |= (*first++) &lt;&lt; 16;
957
 
00948                         ++wrd_ptr;
958
 
00949                     }
959
 
00950                 }
960
 
00951                 <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
961
 
00952             } <span class="comment">// for</span>
962
 
00953         }
963
 
00954         <span class="keywordflow">break</span>;
964
 
00955     <span class="keywordflow">case</span> 4:
965
 
00956         {
966
 
00957             size_t word_cnt = array_size;
967
 
00958             <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; bm::set_total_blocks; ++i)
968
 
00959             {
969
 
00960                 bm::word_t* blk = 
970
 
00961                     bman.check_allocate_block(i, 
971
 
00962                                               <span class="keyword">false</span>, 
972
 
00963                                               BM_BIT, 
973
 
00964                                               &amp;block_type,
974
 
00965                                               <span class="keyword">false</span> <span class="comment">/*no NULL ret*/</span>);
975
 
00966                 <span class="keywordflow">if</span> (block_type == 1) <span class="comment">// gap</span>
976
 
00967                 {
977
 
00968                     blk = bman.convert_gap2bitset(i, <a class="code" href="a00077.html#a8">BMGAP_PTR</a>(blk));
978
 
00969                 }
979
 
00970                 
980
 
00971                 bm::word_t* wrd_ptr = blk;
981
 
00972                 <span class="keywordflow">if</span> (word_cnt &gt;= bm::set_block_size) {
982
 
00973                     bm::word_t* wrd_end = blk + bm::set_block_size;
983
 
00974                     <span class="keywordflow">do</span> {
984
 
00975                         *wrd_ptr++ = *first++;
985
 
00976                     } <span class="keywordflow">while</span> (wrd_ptr &lt; wrd_end);
986
 
00977                     word_cnt -= bm::set_block_size;
987
 
00978                 } 
988
 
00979                 <span class="keywordflow">else</span> 
989
 
00980                 {
990
 
00981                     <span class="keywordflow">while</span> (1)
991
 
00982                     {
992
 
00983                         <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
993
 
00984                         *wrd_ptr = *first++;
994
 
00985                         ++wrd_ptr;
995
 
00986                     }
996
 
00987                 }
997
 
00988                 <span class="keywordflow">if</span> (first == last) <span class="keywordflow">break</span>;
998
 
00989             } <span class="comment">// for</span>
999
 
00990         }
1000
 
00991         <span class="keywordflow">break</span>;
1001
 
00992     <span class="keywordflow">default</span>:
1002
 
00993         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(0);
1003
 
00994     } <span class="comment">// switch</span>
1004
 
00995 
1005
 
00996 }
1006
 
00997 
1007
 
00998 
1008
 
00999 } <span class="comment">// namespace bm</span>
1009
 
01000 
1010
 
01001 <span class="preprocessor">#include "<a class="code" href="a00080.html">bmundef.h</a>"</span>
1011
 
01002 
1012
 
01003 <span class="preprocessor">#endif</span>
1013
 
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Thu Apr 20 13:28:46 2006 for BitMagic by&nbsp;
 
9
<a class="el" href="a00129.html">bm</a>::<a class="el" href="a00103.html">first_bit_table</a></div>
 
10
<h1>bm::first_bit_table&lt; T &gt; Struct Template Reference<br>
 
11
<small>
 
12
[<a class="el" href="a00134.html">BIT functions</a>]</small>
 
13
</h1>Structure keeps index of first ON bit for every byte.  
 
14
<a href="#_details">More...</a>
 
15
<p>
 
16
<code>#include &lt;<a class="el" href="a00141.html">bmfunc.h</a>&gt;</code>
 
17
<p>
 
18
<table border="0" cellpadding="0" cellspacing="0">
 
19
<tr><td></td></tr>
 
20
<tr><td colspan="2"><br><h2>Static Public Attributes</h2></td></tr>
 
21
<tr><td class="memItemLeft" nowrap align="right" valign="top">static const char&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00103.html#s0">_idx</a> [256]</td></tr>
 
22
 
 
23
</table>
 
24
<hr><a name="_details"></a><h2>Detailed Description</h2>
 
25
<h3>template&lt;bool T&gt;<br>
 
26
 struct bm::first_bit_table&lt; T &gt;</h3>
 
27
 
 
28
Structure keeps index of first ON bit for every byte. 
 
29
<p>
 
30
 
 
31
<p>
 
32
Definition at line <a class="el" href="a00141.html#l00184">184</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.<hr><h2>Field Documentation</h2>
 
33
<a class="anchor" name="s0" doxytag="bm::first_bit_table::_idx"></a><p>
 
34
<table class="mdTable" cellpadding="2" cellspacing="0">
 
35
  <tr>
 
36
    <td class="mdRow">
 
37
      <table cellpadding="0" cellspacing="0" border="0">
 
38
        <tr>
 
39
          <td class="mdPrefix" colspan="4">
 
40
template&lt;bool T&gt; </td>
 
41
        </tr>
 
42
        <tr>
 
43
          <td class="md" nowrap valign="top">const char <a class="el" href="a00103.html">bm::first_bit_table</a>&lt; T &gt;::<a class="el" href="a00103.html#s0">_idx</a><code> [static]</code>          </td>
 
44
        </tr>
 
45
      </table>
 
46
    </td>
 
47
  </tr>
 
48
</table>
 
49
<table cellspacing="5" cellpadding="0" border="0">
 
50
  <tr>
 
51
    <td>
 
52
      &nbsp;
 
53
    </td>
 
54
    <td>
 
55
 
 
56
<p>
 
57
<b>Initial value:</b><div class="fragment"><pre class="fragment"> {
 
58
    -1,
 
59
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,
 
60
    1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1, 0,2,0,1,0,3,0,
 
61
    1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,
 
62
    0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,
 
63
    2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
 
64
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,
 
65
    1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,
 
66
    0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,
 
67
    3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 
 
68
}
 
69
</pre></div>
 
70
<p>
 
71
Definition at line <a class="el" href="a00141.html#l00190">190</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.    </td>
 
72
  </tr>
 
73
</table>
 
74
<hr>The documentation for this struct was generated from the following file:<ul>
 
75
<li><a class="el" href="a00141.html">bmfunc.h</a></ul>
 
76
<hr size="1"><address style="align: right;"><small>Generated on Sun Aug 5 14:12:40 2007 for BitMagic by&nbsp;
1014
77
<a href="http://www.doxygen.org/index.html">
1015
78
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.1 </small></address>
1016
79
</body>