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: bmvmin.h Source File</title>
3
<title>BitMagic: bm::operation_functions< T > Struct Template Reference</title>
4
4
<link href="doxygen.css" rel="stylesheet" type="text/css">
6
6
<!-- Generated by Doxygen 1.4.1 -->
7
7
<div class="qindex"><a class="qindex" href="index.html">Main 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 Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="dirs.html">Directories</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a> | <a class="qindex" href="examples.html">Examples</a></div>
9
<a class="el" href="dir_000000.html">src</a></div>
10
<h1>bmvmin.h</h1><a href="a00081.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>
36
00027 <span class="preprocessor">#ifndef BMVMIN__H__INCLUDED__</span>
37
00028 <span class="preprocessor"></span><span class="preprocessor">#define BMVMIN__H__INCLUDED__</span>
38
00029 <span class="preprocessor"></span>
39
00030 <span class="keyword">namespace </span>bm
43
<a name="l00034"></a><a class="code" href="a00081.html#a0">00034</a> <span class="preprocessor">#define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])</span>
44
<a name="l00035"></a><a class="code" href="a00081.html#a1">00035</a> <span class="preprocessor"></span><span class="preprocessor">#define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))</span>
45
00036 <span class="preprocessor"></span><span class="comment"></span>
46
00037 <span class="comment">/*! @defgroup mset Small sets functionality</span>
47
00038 <span class="comment"> * Templates in this group are used to keep block types in BM library.</span>
48
00039 <span class="comment"> * Classes of this group can tune bvector template (MS parameter)</span>
49
00040 <span class="comment"> * for best performance or minimal memory usage.</span>
50
00041 <span class="comment"> * @ingroup bmagic</span>
51
00042 <span class="comment"> * @{</span>
52
00043 <span class="comment"> */</span>
54
00045 <span class="comment"></span>
55
00046 <span class="comment">/*!</span>
56
00047 <span class="comment"> @brief Template class implements memory saving set functionality</span>
57
00048 <span class="comment"> </span>
58
00049 <span class="comment"> Template can be used as template parameter for bvector if we </span>
59
00050 <span class="comment"> want to tune bvector for minimal memory consumption.</span>
60
00051 <span class="comment"></span>
61
00052 <span class="comment"> @sa bvmini</span>
62
00053 <span class="comment">*/</span>
63
<a name="l00054"></a><a class="code" href="a00072.html">00054</a> <span class="keyword">template</span> <<span class="keyword">class</span> A, size_t N> <span class="keyword">class </span><a class="code" href="a00072.html">miniset</a>
65
00056 <span class="keyword">public</span>:
67
<a name="l00058"></a><a class="code" href="a00072.html#a0">00058</a> <a class="code" href="a00072.html#a0">miniset</a>()
72
<a name="l00063"></a><a class="code" href="a00072.html#a1">00063</a> <a class="code" href="a00072.html#a0">miniset</a>(<span class="keyword">const</span> <a class="code" href="a00072.html">miniset</a>& mset)
74
00065 <span class="keywordflow">if</span> (mset.m_buf)
76
00067 <span class="keywordflow">if</span> (mset.m_type)
77
00068 init_gapbuf(mset.m_buf);
78
00069 <span class="keywordflow">else</span>
79
00070 init_bitbuf(mset.m_buf);
81
00072 <span class="keywordflow">else</span>
83
00074 m_type = mset.m_type;
88
<a name="l00079"></a><a class="code" href="a00072.html#a2">00079</a> <a class="code" href="a00072.html#a2">~miniset</a>()
90
00081 <span class="keywordflow">if</span> (m_buf)
92
00083 A::deallocate(m_buf, m_type ?
93
00084 (<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t)))
95
00086 (<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N)));
98
00089 <span class="comment"></span>
99
00090 <span class="comment"> /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
100
<a name="l00091"></a><a class="code" href="a00072.html#a3">00091</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <a class="code" href="a00072.html#a3">test</a>(bm::id_t n)<span class="keyword"> const </span>
101
00092 <span class="keyword"> </span>{
102
00093 <span class="keywordflow">return</span>
106
00097 <a class="code" href="a00096.html#ga0">gap_test</a>((<a class="code" href="a00092.html#a19">gap_word_t</a>*)m_buf, n)
108
00099 m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
111
<a name="l00102"></a><a class="code" href="a00072.html#a4">00102</a> <span class="keywordtype">void</span> <a class="code" href="a00072.html#a4">set</a>(bm::id_t n, <span class="keywordtype">bool</span> val=<span class="keyword">true</span>)
113
00104 <span class="keywordflow">if</span> (m_type == 0)
115
00106 <span class="keywordflow">if</span> (!m_buf)
117
00108 <span class="keywordflow">if</span> (!val) <span class="keywordflow">return</span>;
118
00109 init_bitbuf(0);
121
00112 <span class="keywordtype">unsigned</span> nword = n >> bm::set_word_shift;
122
00113 <span class="keywordtype">unsigned</span> mask = unsigned(1) << (n & bm::set_word_mask);
124
00115 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
126
00117 <span class="keywordflow">else</span>
128
00119 <span class="keywordflow">if</span> (!m_buf)
130
00121 <span class="keywordflow">if</span> (!val) <span class="keywordflow">return</span>;
131
00122 init_gapbuf(0);
134
00125 <span class="keywordtype">unsigned</span> is_set;
135
00126 <span class="keywordtype">unsigned</span> new_block_len =
136
00127 <a class="code" href="a00096.html#ga4">gap_set_value</a>(val, (<a class="code" href="a00092.html#a19">gap_word_t</a>*)m_buf, n, &is_set);
138
00129 <span class="keywordflow">if</span> (new_block_len > <span class="keywordtype">unsigned</span>(<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a>-4))
145
<a name="l00136"></a><a class="code" href="a00072.html#a5">00136</a> <span class="keywordtype">unsigned</span> <a class="code" href="a00072.html#a5">mem_used</a>()<span class="keyword"> const</span>
146
00137 <span class="keyword"> </span>{
147
00138 <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(*this) +
149
00140 (m_type ? (<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> * <span class="keyword">sizeof</span>(<a class="code" href="a00092.html#a19">gap_word_t</a>))
150
00141 : (<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N) * <span class="keyword">sizeof</span>(bm::word_t)))
154
<a name="l00145"></a><a class="code" href="a00072.html#a6">00145</a> <span class="keywordtype">void</span> <a class="code" href="a00072.html#a6">swap</a>(<a class="code" href="a00072.html">miniset</a>& mset)
156
00147 bm::word_t* buftmp = m_buf;
157
00148 m_buf = mset.m_buf;
158
00149 mset.m_buf = buftmp;
159
00150 <span class="keywordtype">unsigned</span> typetmp = m_type;
160
00151 m_type = mset.m_type;
161
00152 mset.m_type = typetmp;
165
00156 <span class="keyword">private</span>:
167
00158 <span class="keywordtype">void</span> init_bitbuf(bm::word_t* buf)
169
00160 <span class="keywordtype">unsigned</span> arr_size = <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N);
170
00161 m_buf = A::allocate(arr_size, 0);
171
00162 <span class="keywordflow">if</span> (buf)
173
00164 ::memcpy(m_buf, buf, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
175
00166 <span class="keywordflow">else</span>
177
00168 ::memset(m_buf, 0, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
182
00173 <span class="keywordtype">void</span> init_gapbuf(bm::word_t* buf)
184
00175 <span class="keywordtype">unsigned</span> arr_size =
185
00176 <a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t));
186
00177 m_buf = A::allocate(arr_size, 0);
187
00178 <span class="keywordflow">if</span> (buf)
189
00180 ::memcpy(m_buf, buf, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
191
00182 <span class="keywordflow">else</span>
194
00185 <a class="code" href="a00096.html#ga14">gap_set_all</a>((gap_word_t*)m_buf, bm::gap_max_bits, 0);
199
00190 <span class="keywordtype">void</span> convert_buf()
201
00192 <span class="keywordtype">unsigned</span> arr_size = <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N);
202
00193 bm::word_t* buf = A::allocate(arr_size, 0);
204
00195 <a class="code" href="a00096.html#ga10">gap_convert_to_bitset</a>(buf, (gap_word_t*) m_buf, arr_size);
206
00197 <a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t));
207
00198 A::deallocate(m_buf, arr_size);
212
00203 <span class="keyword">private</span>:
213
00204 bm::word_t* m_buf; <span class="comment">//!< Buffer pointer</span>
214
00205 <span class="comment"></span> <span class="keywordtype">unsigned</span> m_type; <span class="comment">//!< buffer type (0-bit, 1-gap)</span>
215
00206 <span class="comment"></span>};
217
00208 <span class="comment"></span>
218
00209 <span class="comment">/*!</span>
219
00210 <span class="comment"> @brief Mini bitvector used in bvector template to keep block type flags</span>
220
00211 <span class="comment"> </span>
221
00212 <span class="comment"> Template is used as a default template parameter MS for bvector </span>
222
00213 <span class="comment"> Offers maximum performance comparing to miniset.</span>
223
00214 <span class="comment"></span>
224
00215 <span class="comment"> @sa miniset</span>
225
00216 <span class="comment">*/</span>
226
<a name="l00217"></a><a class="code" href="a00059.html">00217</a> <span class="keyword">template</span><size_t N> <span class="keyword">class </span><a class="code" href="a00059.html">bvmini</a>
228
00219 <span class="keyword">public</span>:
230
<a name="l00221"></a><a class="code" href="a00059.html#a0">00221</a> <a class="code" href="a00059.html#a0">bvmini</a>(<span class="keywordtype">int</span> start_strategy = 0)
232
00223 ::memset(m_buf, 0, <span class="keyword">sizeof</span>(m_buf));
235
<a name="l00226"></a><a class="code" href="a00059.html#a1">00226</a> <a class="code" href="a00059.html#a0">bvmini</a>(<span class="keyword">const</span> <a class="code" href="a00059.html">bvmini</a>& mset)
237
00228 ::memcpy(m_buf, mset.m_buf, <span class="keyword">sizeof</span>(m_buf));
240
00231 <span class="comment"></span>
241
00232 <span class="comment"> /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
242
<a name="l00233"></a><a class="code" href="a00059.html#a2">00233</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <a class="code" href="a00059.html#a2">test</a>(bm::id_t n)<span class="keyword"> const </span>
243
00234 <span class="keyword"> </span>{
244
00235 <span class="keywordflow">return</span> m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
247
<a name="l00238"></a><a class="code" href="a00059.html#a3">00238</a> <span class="keywordtype">void</span> <a class="code" href="a00059.html#a3">set</a>(bm::id_t n, <span class="keywordtype">bool</span> val=<span class="keyword">true</span>)
249
00240 <span class="keywordtype">unsigned</span> nword = n >> bm::set_word_shift;
250
00241 <span class="keywordtype">unsigned</span> mask = unsigned(1) << (n & bm::set_word_mask);
252
00243 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
255
<a name="l00246"></a><a class="code" href="a00059.html#a4">00246</a> <span class="keywordtype">unsigned</span> <a class="code" href="a00059.html#a4">mem_used</a>()<span class="keyword"> const</span>
256
00247 <span class="keyword"> </span>{
257
00248 <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(*this);
260
<a name="l00251"></a><a class="code" href="a00059.html#a5">00251</a> <span class="keywordtype">void</span> <a class="code" href="a00059.html#a5">swap</a>(<a class="code" href="a00059.html">bvmini</a>& mset)
262
00253 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N); ++i)
264
00255 bm::word_t tmp = m_buf[i];
265
00256 m_buf[i] = mset.m_buf[i];
266
00257 mset.m_buf[i] = tmp;
270
00261 <span class="keyword">private</span>:
271
00262 bm::word_t m_buf[<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N)];
274
00265 <span class="comment"></span>
275
00266 <span class="comment">/*!@} */</span>
276
00267 <span class="comment"></span>
277
00268 <span class="comment">/*!</span>
278
00269 <span class="comment"> @brief Bitvector class with very limited functionality.</span>
279
00270 <span class="comment"></span>
280
00271 <span class="comment"> Class implements simple bitset and used for internal </span>
281
00272 <span class="comment"> and testing purposes. </span>
282
00273 <span class="comment">*/</span>
283
<a name="l00274"></a><a class="code" href="a00058.html">00274</a> <span class="keyword">template</span><<span class="keyword">class</span> A> <span class="keyword">class </span><a class="code" href="a00058.html">bvector_mini</a>
285
00276 <span class="keyword">public</span>:
286
<a name="l00277"></a><a class="code" href="a00058.html#a0">00277</a> <a class="code" href="a00058.html#a0">bvector_mini</a>(<span class="keywordtype">unsigned</span> size)
290
00281 <span class="keywordtype">unsigned</span> arr_size = (size / 32) + 1;
291
00282 m_buf = A::allocate(arr_size, 0);
292
00283 ::memset(m_buf, 0, arr_size * <span class="keyword">sizeof</span>(unsigned));
294
<a name="l00285"></a><a class="code" href="a00058.html#a1">00285</a> <a class="code" href="a00058.html#a0">bvector_mini</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
295
00286 : m_size(<a class="code" href="a00048.html">bvect</a>.m_size)
297
00288 <span class="keywordtype">unsigned</span> arr_size = (m_size / 32) + 1;
298
00289 m_buf = A::allocate(arr_size, 0);
299
00290 ::memcpy(m_buf, <a class="code" href="a00048.html">bvect</a>.m_buf, arr_size * <span class="keyword">sizeof</span>(unsigned));
302
<a name="l00293"></a><a class="code" href="a00058.html#a2">00293</a> <a class="code" href="a00058.html#a2">~bvector_mini</a>()
304
00295 A::deallocate(m_buf, (m_size / 32) + 1);
306
00297 <span class="comment"></span>
307
00298 <span class="comment"> /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
308
<a name="l00299"></a><a class="code" href="a00058.html#a3">00299</a> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="a00058.html#a3">is_bit_true</a>(<span class="keywordtype">unsigned</span> pos)<span class="keyword"> const</span>
309
00300 <span class="keyword"> </span>{
310
00301 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> mask = (<span class="keywordtype">unsigned</span> char)((char)0x1 << (pos & 7));
311
00302 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos >> 3); <span class="comment">// m_buf + (pos/8)</span>
313
00304 <span class="keywordflow">return</span> (*offs) & mask;
315
00306 <span class="comment"></span>
316
00307 <span class="comment"> /// Sets bit number pos to 1</span>
317
<a name="l00308"></a><a class="code" href="a00058.html#a4">00308</a> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a4">set_bit</a>(<span class="keywordtype">unsigned</span> pos)
319
00310 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> mask = (<span class="keywordtype">unsigned</span> char)(0x1 << (pos & 7));
320
00311 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos >> 3);
324
00315 <span class="comment"></span>
325
00316 <span class="comment"> /// Sets bit number pos to 0</span>
326
<a name="l00317"></a><a class="code" href="a00058.html#a5">00317</a> <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a5">clear_bit</a>(<span class="keywordtype">unsigned</span> pos)
328
00319 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> mask = (<span class="keywordtype">unsigned</span> char)(0x1 << (pos & 7));
329
00320 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos >> 3);
331
00322 *offs &= ~mask;
333
00324 <span class="comment"></span>
334
00325 <span class="comment"> /// Counts number of bits ON </span>
335
<a name="l00326"></a><a class="code" href="a00058.html#a6">00326</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a6">bit_count</a>()<span class="keyword"> const</span>
336
00327 <span class="keyword"> </span>{
337
00328 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> count = 0;
338
00329 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
340
00331 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start < end; ++start)
342
00333 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> value = *start;
343
00334 <span class="keywordflow">for</span> (count += (value!=0); value &= value - 1; ++count);
345
00336 <span class="keywordflow">return</span> count;
347
00338 <span class="comment"></span>
348
00339 <span class="comment"> /// Comparison.</span>
349
<a name="l00340"></a><a class="code" href="a00058.html#a7">00340</a> <span class="comment"></span> <span class="keywordtype">int</span> <a class="code" href="a00058.html#a7">compare</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
351
00342 <span class="keywordtype">unsigned</span> cnt1 = <a class="code" href="a00058.html#a6">bit_count</a>();
352
00343 <span class="keywordtype">unsigned</span> cnt2 = <a class="code" href="a00048.html">bvect</a>.bit_count();
354
00345 <span class="keywordflow">if</span> (!cnt1 && !cnt2) <span class="keywordflow">return</span> 0;
356
00347 <span class="keywordtype">unsigned</span> cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
358
00349 <span class="keywordflow">if</span> (!cnt_min) <span class="keywordflow">return</span> cnt1 ? 1 : -1;
360
00351 <span class="keywordtype">unsigned</span> idx1 = <a class="code" href="a00058.html#a8">get_first</a>();
361
00352 <span class="keywordtype">unsigned</span> idx2 = <a class="code" href="a00048.html">bvect</a>.get_first();
363
00354 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < cnt_min; ++i)
365
00356 <span class="keywordflow">if</span> (idx1 != idx2)
367
00358 <span class="keywordflow">return</span> idx1 < idx2 ? 1 : -1;
369
00360 idx1 = <a class="code" href="a00058.html#a9">get_next</a>(idx1);
370
00361 idx2 = <a class="code" href="a00048.html">bvect</a>.get_next(idx2);
373
00364 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(idx1==0 || idx2==0);
375
00366 <span class="keywordflow">if</span> (idx1 != idx2)
377
00368 <span class="keywordflow">if</span> (!idx1) <span class="keywordflow">return</span> -1;
378
00369 <span class="keywordflow">if</span> (!idx2) <span class="keywordflow">return</span> 1;
379
00370 <span class="keywordflow">return</span> idx1 < idx2 ? 1 : -1;
382
00373 <span class="keywordflow">return</span> 0;
385
00376 <span class="comment"></span>
386
00377 <span class="comment"> /// Returns index of the first ON bit</span>
387
<a name="l00378"></a><a class="code" href="a00058.html#a8">00378</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a8">get_first</a>()<span class="keyword"> const</span>
388
00379 <span class="keyword"> </span>{
389
00380 <span class="keywordtype">unsigned</span> pos = 0;
390
00381 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* ptr = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*) m_buf;
392
00383 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < (m_size/8)+1; ++i)
394
00385 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> w = ptr[i];
397
00388 <span class="keywordflow">if</span> (w != 0)
399
00390 <span class="keywordflow">while</span> ((w & 1) == 0)
404
00395 <span class="keywordflow">return</span> pos;
406
00397 pos += <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> char) * 8;
408
00399 <span class="keywordflow">return</span> 0;
411
00402 <span class="comment"></span>
412
00403 <span class="comment"> /// Returns index of next bit, which is ON</span>
413
<a name="l00404"></a><a class="code" href="a00058.html#a9">00404</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a9">get_next</a>(<span class="keywordtype">unsigned</span> idx)<span class="keyword"> const</span>
414
00405 <span class="keyword"> </span>{
415
00406 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> i;
417
00408 <span class="keywordflow">for</span> (i = idx+1; i < m_size; ++i)
419
00410 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (i >> 3);
420
00411 <span class="keywordflow">if</span> (*offs)
422
00413 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> mask = (<span class="keywordtype">unsigned</span> char)((char)0x1 << (i & 7));
424
00415 <span class="keywordflow">if</span> (*offs & mask)
426
00417 <span class="keywordflow">return</span> i;
429
00420 <span class="keywordflow">else</span>
434
00425 <span class="keywordflow">return</span> 0;
438
<a name="l00429"></a><a class="code" href="a00058.html#a10">00429</a> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a10">combine_and</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
440
00431 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
442
00433 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
444
00435 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start < end; ++start)
446
00437 *start &= *src++;
450
<a name="l00441"></a><a class="code" href="a00058.html#a11">00441</a> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a11">combine_xor</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
452
00443 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
454
00445 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
456
00447 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start < end; ++start)
458
00449 *start ^= *src++;
463
<a name="l00454"></a><a class="code" href="a00058.html#a12">00454</a> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a12">combine_or</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
465
00456 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
467
00458 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
469
00460 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start < end; ++start)
471
00462 *start |= *src++;
475
<a name="l00466"></a><a class="code" href="a00058.html#a13">00466</a> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a13">combine_sub</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>& <a class="code" href="a00048.html">bvect</a>)
477
00468 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
479
00470 <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
481
00472 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start < end; ++start)
483
00474 *start &= ~(*src++);
487
<a name="l00478"></a><a class="code" href="a00058.html#a14">00478</a> <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* <a class="code" href="a00058.html#a14">get_buf</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> m_buf; }
488
<a name="l00479"></a><a class="code" href="a00058.html#a15">00479</a> <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a15">mem_used</a>()<span class="keyword"> const</span>
489
00480 <span class="keyword"> </span>{
490
00481 <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(<a class="code" href="a00058.html">bvector_mini</a>) + (m_size / 32) + 1;
493
<a name="l00484"></a><a class="code" href="a00058.html#a16">00484</a> <span class="keywordtype">void</span> <a class="code" href="a00058.html#a16">swap</a>(<a class="code" href="a00058.html">bvector_mini</a>& bvm)
495
00486 <a class="code" href="a00077.html#a0">BM_ASSERT</a>(m_size == bvm.m_size);
496
00487 bm::word_t* buftmp = m_buf;
497
00488 m_buf = bvm.m_buf;
498
00489 bvm.m_buf = buftmp;
501
00492 <span class="keyword">private</span>:
502
00493 bm::word_t* m_buf;
503
00494 <span class="keywordtype">unsigned</span> m_size;
508
00499 } <span class="comment">// namespace bm</span>
510
00501 <span class="preprocessor">#endif</span>
511
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Thu Apr 20 13:28:46 2006 for BitMagic by
9
<a class="el" href="a00129.html">bm</a>::<a class="el" href="a00109.html">operation_functions</a></div>
10
<h1>bm::operation_functions< T > Struct Template Reference</h1><code>#include <<a class="el" href="a00141.html">bmfunc.h</a>></code>
12
<table border="0" cellpadding="0" cellspacing="0">
14
<tr><td colspan="2"><br><h2>Static Public Member Functions</h2></td></tr>
15
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a1">gap_operation_to_bitset_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#e0">gap_op_to_bit</a> (unsigned i)</td></tr>
17
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a2">gap_operation_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#e1">gap_operation</a> (unsigned i)</td></tr>
19
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a3">bit_operation_count_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#e2">bit_operation_count</a> (unsigned i)</td></tr>
21
<tr><td colspan="2"><br><h2>Static Public Attributes</h2></td></tr>
22
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a1">gap_operation_to_bitset_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#s0">gap2bit_table_</a> [bm::set_END]</td></tr>
24
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a2">gap_operation_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#s1">gapop_table_</a> [bm::set_END]</td></tr>
26
<tr><td class="memItemLeft" nowrap align="right" valign="top">static <a class="el" href="a00129.html#a3">bit_operation_count_func_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00109.html#s2">bit_op_count_table_</a> [bm::set_END]</td></tr>
29
<h3>template<bool T><br>
30
struct bm::operation_functions< T ></h3>
32
<hr><h2>Member Function Documentation</h2>
33
<a class="anchor" name="e2" doxytag="bm::operation_functions::bit_operation_count"></a><p>
34
<table class="mdTable" cellpadding="2" cellspacing="0">
37
<table cellpadding="0" cellspacing="0" border="0">
39
<td class="mdPrefix" colspan="4">
40
template<bool T> </td>
43
<td class="md" nowrap valign="top">static <a class="el" href="a00129.html#a3">bit_operation_count_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::bit_operation_count </td>
44
<td class="md" valign="top">( </td>
45
<td class="md" nowrap valign="top">unsigned </td>
46
<td class="mdname1" valign="top" nowrap> <em>i</em> </td>
47
<td class="md" valign="top"> ) </td>
48
<td class="md" nowrap><code> [inline, static]</code></td>
54
<table cellspacing="5" cellpadding="0" border="0">
64
Definition at line <a class="el" href="a00141.html#l04329">4329</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
66
References <a class="el" href="a00141.html#l04358">bm::operation_functions< T >::bit_op_count_table_</a>. </td>
69
<a class="anchor" name="e0" doxytag="bm::operation_functions::gap_op_to_bit"></a><p>
70
<table class="mdTable" cellpadding="2" cellspacing="0">
73
<table cellpadding="0" cellspacing="0" border="0">
75
<td class="mdPrefix" colspan="4">
76
template<bool T> </td>
79
<td class="md" nowrap valign="top">static <a class="el" href="a00129.html#a1">gap_operation_to_bitset_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::gap_op_to_bit </td>
80
<td class="md" valign="top">( </td>
81
<td class="md" nowrap valign="top">unsigned </td>
82
<td class="mdname1" valign="top" nowrap> <em>i</em> </td>
83
<td class="md" valign="top"> ) </td>
84
<td class="md" nowrap><code> [inline, static]</code></td>
90
<table cellspacing="5" cellpadding="0" border="0">
100
Definition at line <a class="el" href="a00141.html#l04317">4317</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
102
References <a class="el" href="a00141.html#l04337">bm::operation_functions< T >::gap2bit_table_</a>. </td>
105
<a class="anchor" name="e1" doxytag="bm::operation_functions::gap_operation"></a><p>
106
<table class="mdTable" cellpadding="2" cellspacing="0">
109
<table cellpadding="0" cellspacing="0" border="0">
111
<td class="mdPrefix" colspan="4">
112
template<bool T> </td>
115
<td class="md" nowrap valign="top">static <a class="el" href="a00129.html#a2">gap_operation_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::gap_operation </td>
116
<td class="md" valign="top">( </td>
117
<td class="md" nowrap valign="top">unsigned </td>
118
<td class="mdname1" valign="top" nowrap> <em>i</em> </td>
119
<td class="md" valign="top"> ) </td>
120
<td class="md" nowrap><code> [inline, static]</code></td>
126
<table cellspacing="5" cellpadding="0" border="0">
136
Definition at line <a class="el" href="a00141.html#l04323">4323</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
138
References <a class="el" href="a00141.html#l04347">bm::operation_functions< T >::gapop_table_</a>. </td>
141
<hr><h2>Field Documentation</h2>
142
<a class="anchor" name="s2" doxytag="bm::operation_functions::bit_op_count_table_"></a><p>
143
<table class="mdTable" cellpadding="2" cellspacing="0">
146
<table cellpadding="0" cellspacing="0" border="0">
148
<td class="mdPrefix" colspan="4">
149
template<bool T> </td>
152
<td class="md" nowrap valign="top"><a class="el" href="a00129.html#a3">bit_operation_count_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::<a class="el" href="a00109.html#s2">bit_op_count_table_</a><code> [static]</code> </td>
158
<table cellspacing="5" cellpadding="0" border="0">
166
<b>Initial value:</b><div class="fragment"><pre class="fragment"> {
173
&<a class="code" href="a00134.html#ga37">bit_operation_and_count</a>,
174
&<a class="code" href="a00134.html#ga50">bit_operation_xor_count</a>,
175
&<a class="code" href="a00134.html#ga42">bit_operation_or_count</a>,
176
&<a class="code" href="a00134.html#ga39">bit_operation_sub_count</a>,
177
&<a class="code" href="a00134.html#ga40">bit_operation_sub_count_inv</a>,
183
Definition at line <a class="el" href="a00141.html#l04358">4358</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
185
Referenced by <a class="el" href="a00141.html#l04329">bm::operation_functions< T >::bit_operation_count()</a>. </td>
188
<a class="anchor" name="s0" doxytag="bm::operation_functions::gap2bit_table_"></a><p>
189
<table class="mdTable" cellpadding="2" cellspacing="0">
192
<table cellpadding="0" cellspacing="0" border="0">
194
<td class="mdPrefix" colspan="4">
195
template<bool T> </td>
198
<td class="md" nowrap valign="top"><a class="el" href="a00129.html#a1">gap_operation_to_bitset_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::<a class="el" href="a00109.html#s0">gap2bit_table_</a><code> [static]</code> </td>
204
<table cellspacing="5" cellpadding="0" border="0">
212
<b>Initial value:</b><div class="fragment"><pre class="fragment"> {
213
&gap_and_to_bitset<bm::gap_word_t>,
214
&gap_add_to_bitset<bm::gap_word_t>,
215
&gap_sub_to_bitset<bm::gap_word_t>,
216
&gap_xor_to_bitset<bm::gap_word_t>,
221
Definition at line <a class="el" href="a00141.html#l04337">4337</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
223
Referenced by <a class="el" href="a00141.html#l04317">bm::operation_functions< T >::gap_op_to_bit()</a>. </td>
226
<a class="anchor" name="s1" doxytag="bm::operation_functions::gapop_table_"></a><p>
227
<table class="mdTable" cellpadding="2" cellspacing="0">
230
<table cellpadding="0" cellspacing="0" border="0">
232
<td class="mdPrefix" colspan="4">
233
template<bool T> </td>
236
<td class="md" nowrap valign="top"><a class="el" href="a00129.html#a2">gap_operation_func_type</a> <a class="el" href="a00109.html">bm::operation_functions</a>< T >::<a class="el" href="a00109.html#s1">gapop_table_</a><code> [static]</code> </td>
242
<table cellspacing="5" cellpadding="0" border="0">
250
<b>Initial value:</b><div class="fragment"><pre class="fragment"> {
251
&<a class="code" href="a00133.html#ga29">gap_operation_and</a>,
252
&<a class="code" href="a00133.html#ga33">gap_operation_or</a>,
253
&<a class="code" href="a00133.html#ga34">gap_operation_sub</a>,
254
&<a class="code" href="a00133.html#ga31">gap_operation_xor</a>,
259
Definition at line <a class="el" href="a00141.html#l04347">4347</a> of file <a class="el" href="a00141.html">bmfunc.h</a>.
261
Referenced by <a class="el" href="a00141.html#l04323">bm::operation_functions< T >::gap_operation()</a>. </td>
264
<hr>The documentation for this struct was generated from the following file:<ul>
265
<li><a class="el" href="a00141.html">bmfunc.h</a></ul>
266
<hr size="1"><address style="align: right;"><small>Generated on Sun Aug 5 14:12:40 2007 for BitMagic by
512
267
<a href="http://www.doxygen.org/index.html">
513
268
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.1 </small></address>