- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# sample7.cpp

Go to the documentation of this file.

    00001 /*
    00002 Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
    00003
    00004 Permission is hereby granted, free of charge, to any person
    00005 obtaining a copy of this software and associated documentation
    00006 files (the "Software"), to deal in the Software without restriction,
    00007 including without limitation the rights to use, copy, modify, merge,
    00008 publish, distribute, sublicense, and/or sell copies of the Software,
    00009 and to permit persons to whom the Software is furnished to do so,
    00010 subject to the following conditions:
    00011
    00012 The above copyright notice and this permission notice shall be included
    00013 in all copies or substantial portions of the Software.
    00014
    00015 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    00016 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    00017 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    00018 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
    00019 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    00020 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    00021 OTHER DEALINGS IN THE SOFTWARE.
    00022 */
    00023
    00024 /* @example sample7.cpp
    00025  This example demonstrates using of memory save mode of bitset operations.
    00026
    00027 For more information please visit:  http://bmagic.sourceforge.net
    00028
    00029 */
    00030
    00031 /* @file
    00032     @ingroup mset
    00033 */
    00034
    00035 #include <iostream>
    00036 #include <stdlib.h>
    00037 #include <stdio.h>
    00038 #include <time.h>
    00039
    00040 // Example disabled as deprecated...
    00041
    00042 int main()
    00043 {
    00044     return 1;
    00045 }
    00046
    00047 /*
    00048
    00049 // BM library version 3.1.3 and later can keep internal bit flags in pointers.
    00050 // This is efficient but not completely portable hack.
    00051 // For compatibility it can be disabled it by defining BM_DISBALE_BIT_IN_PTR.
    00052 // If you do not disable bits in pointer the second template parameter of bvector
    00053 // is simply ignored and portion of this example is becoming irrelevant.
    00054 #define BM_DISBALE_BIT_IN_PTR
    00055 #include "bm.h"
    00056
    00057 using namespace std;
    00058
    00059 // Customized bitvector uses standard memory allocator and uses
    00060 // an alternative implementation of internal set. Saves memory when we
    00061 // work with sparse or dense bitsets.
    00062 typedef bm::bvector<bm::standard_allocator,
    00063                     bm::miniset<bm::block_allocator, bm::set_total_blocks> > bvect;
    00064
    00065
    00066 const unsigned setscount = 10000;
    00067 const unsigned randombits = 150;
    00068 const unsigned maxbit = 100000000;
    00069
    00070 bvect*  bitsets[setscount];
    00071
    00072 // ---------------------------------------------------------
    00073
    00074 void CreateSets()
    00075 {
    00076     unsigned mu = 0;
    00077     for (unsigned i = 0; i < setscount; ++i)
    00078     {
    00079         if ((i % 100) == 0) { cout << "."; cout.flush(); }
    00080         // create bitvector using in GAP mode using an alternative
    00081         // GAP levels table (minimalistic).
    00082         bitsets[i] =
    00083             new bvect(bm::BM_GAP, bm::gap_len_table_min<true>::_len, maxbit);
    00084         bvect& bv = *bitsets[i];
    00085         bvect::statistics st;
    00086         bv.calc_stat(&st);
    00087         mu += st.memory_used;
    00088     }
    00089     cout << endl << "Created " << setscount << " sets." << endl;
    00090     cout << "Used " << mu / (1024*1024)<< " MB." << endl;
    00091 }
    00092
    00093 // ---------------------------------------------------------
    00094
    00095 void FillSets()
    00096 {
    00097     unsigned mu, bit_blocks, gap_blocks;
    00098     cout << "Filling sets...";
    00099     mu = bit_blocks = gap_blocks = 0;
    00100     for (unsigned i = 0; i < setscount; ++i)
    00101     {
    00102         if ((i % 100) == 0) { cout << "."; cout.flush(); }
    00103         if ((i % 3) == 0) continue;
    00104         bvect& bv = *bitsets[i];
    00105         unsigned bn = 0;
    00106         for (unsigned j = 0; j < randombits; j+=3)
    00107         {
    00108             bn += (maxbit / randombits) + rand() % 10;
    00109             if (bn > maxbit) bn = rand() % maxbit;
    00110
    00111             bv[bn] = true;
    00112             bv[bn+1] = true;
    00113             bv[bn+2] = true;
    00114         }
    00115         bvect::statistics st;
    00116         bv.calc_stat(&st);
    00117         mu += st.memory_used;
    00118         bit_blocks += st.bit_blocks;
    00119         gap_blocks += st.gap_blocks;
    00120     }
    00121     cout << endl << "Used " << mu / (1024*1024)<< " MB." << endl;
    00122
    00123     cout << "BIT Blocks=" << bit_blocks << endl;
    00124     cout << "GAP Blocks=" << gap_blocks << endl;
    00125 }
    00126
    00127 // ---------------------------------------------------------
    00128
    00129 void EnumerateSets()
    00130 {
    00131     cout << "Enumerating sets...";
    00132     unsigned bitcnt = 0;
    00133     for (unsigned i = 0; i < setscount; ++i)
    00134     {
    00135         if ((i % 100) == 0) { cout << "."; cout.flush(); }
    00136         bvect& bv = *bitsets[i];
    00137
    00138         bvect::enumerator en = bv.first();
    00139         bvect::enumerator en_end = bv.end();
    00140
    00141         for (;en < en_end; ++en)
    00142         {
    00143             ++bitcnt;
    00144         }
    00145     }
    00146     cout << endl << bitcnt << endl;
    00147 }
    00148
    00149 // ---------------------------------------------------------
    00150
    00151 void DestroySets()
    00152 {
    00153     for (unsigned i = 0; i < setscount; ++i)
    00154     {
    00155         delete bitsets[i];
    00156     }
    00157 }
    00158
    00159 // ---------------------------------------------------------
    00160
    00161 void OrSets()
    00162 {
    00163     bvect res;
    00164     cout << "Calculating Or...";
    00165     for (unsigned i = 0; i < setscount; ++i)
    00166     {
    00167         if ((i % 100) == 0) { cout << "."; cout.flush(); }
    00168         const bvect& bv = *bitsets[i];
    00169
    00170         res |= bv;
    00171     }
    00172     cout << endl << res.count() << endl;
    00173 }
    00174
    00175 // ---------------------------------------------------------
    00176
    00177
    00178
    00179 int main(void)
    00180 {
    00181     time_t start_time = time(0);
    00182
    00183     CreateSets();
    00184     FillSets();
    00185     EnumerateSets();
    00186     OrSets();
    00187
    00188     time_t end_time = time(0);
    00189     time_t elapsed = end_time - start_time;
    00190     cout << "elapsed=" << elapsed << endl;
    00191     unsigned ops;
    00192     if (elapsed)
    00193         ops = setscount / elapsed;
    00194     else
    00195         ops = setscount;
    00196
    00197     cout << "Time = " << (end_time - start_time) << endl;
    00198     cout << "Operations per second:" << ops << endl;
    00199
    00200     DestroySets();
    00201
    00202     return 0;
    00203 }
    00204 */
    00205