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

- File List
- Globals

# bmvmin.h

Go to the documentation of this file.

    00001 #ifndef BMVMIN__H__INCLUDED__
    00002 #define BMVMIN__H__INCLUDED__
    00003 /*
    00004 Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
    00005
    00006 Permission is hereby granted, free of charge, to any person
    00007 obtaining a copy of this software and associated documentation
    00008 files (the "Software"), to deal in the Software without restriction,
    00009 including without limitation the rights to use, copy, modify, merge,
    00010 publish, distribute, sublicense, and/or sell copies of the Software,
    00011 and to permit persons to whom the Software is furnished to do so,
    00012 subject to the following conditions:
    00013
    00014 The above copyright notice and this permission notice shall be included
    00015 in all copies or substantial portions of the Software.
    00016
    00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    00018 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    00019 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    00020 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
    00021 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    00022 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    00023 OTHER DEALINGS IN THE SOFTWARE.
    00024
    00025 For more information please visit:  http://bmagic.sourceforge.net
    00026
    00027 */
    00028
    00029 #ifdef _MSC_VER
    00030 #pragma warning( push )
    00031 #pragma warning( disable : 4100)
    00032 #endif
    00033
    00034 namespace bm
    00035 {
    00036
    00037
    00038 #define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
    00039 #define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
    00040
    00041 /*! @defgroup mset Small sets functionality
    00042  *  Templates in this group are used to keep block types in BM library.
    00043  *  Classes of this group can tune bvector template (MS parameter)
    00044  *  for best performance or minimal memory usage.
    00045  *  @ingroup bmagic
    00046  *  @{
    00047  */
    00048
    00049
    00050 /*!
    00051     @brief Template class implements memory saving set functionality
    00052
    00053     Template can be used as template parameter for bvector if we
    00054     want to tune bvector for minimal memory consumption.
    00055
    00056     @sa bvmini
    00057 */
    00058 template <class A, size_t N> class miniset
    00059 {
    00060 public:
    00061
    00062     miniset()
    00063         : m_buf(0),
    00064           m_type(1)
    00065     {}
    00066
    00067     miniset(const miniset& mset)
    00068     {
    00069         if (mset.m_buf)
    00070         {
    00071             if (mset.m_type)
    00072                 init_gapbuf(mset.m_buf);
    00073             else
    00074                 init_bitbuf(mset.m_buf);
    00075         }
    00076         else
    00077         {
    00078             m_type = mset.m_type;
    00079             m_buf = 0;
    00080         }
    00081     }
    00082
    00083     ~miniset()
    00084     {
    00085         if (m_buf)
    00086         {
    00087             A::deallocate(m_buf, m_type ?
    00088                 (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
    00089                 :
    00090                 (BM_MINISET_ARRSIZE(N)));
    00091         }
    00092     }
    00093
    00094     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
    00095     unsigned test(bm::id_t n) const
    00096     {
    00097         return
    00098             !m_buf ? 0
    00099             :
    00100             m_type ?
    00101               gap_test((gap_word_t*)m_buf, n)
    00102               :
    00103               m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
    00104     }
    00105
    00106     void set(bm::id_t n, bool val=true)
    00107     {
    00108         if (m_type == 0)
    00109         {
    00110             if (!m_buf)
    00111             {
    00112                 if (!val) return;
    00113                 init_bitbuf(0);
    00114             }
    00115
    00116             unsigned nword  = n >> bm::set_word_shift;
    00117             unsigned mask = unsigned(1) << (n & bm::set_word_mask);
    00118
    00119             val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
    00120         }
    00121         else
    00122         {
    00123             if (!m_buf)
    00124             {
    00125                 if (!val) return;
    00126                 init_gapbuf(0);
    00127             }
    00128
    00129             unsigned is_set;
    00130             unsigned new_block_len =
    00131                 gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
    00132
    00133             if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
    00134             {
    00135                 convert_buf();
    00136             }
    00137         }
    00138     }
    00139
    00140     unsigned mem_used() const
    00141     {
    00142         return sizeof(*this) +
    00143                m_buf ?
    00144                  (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
    00145                         : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
    00146                 : 0;
    00147     }
    00148
    00149     void swap(miniset& mset)
    00150     {
    00151         bm::word_t* buftmp = m_buf;
    00152         m_buf = mset.m_buf;
    00153         mset.m_buf = buftmp;
    00154         unsigned typetmp = m_type;
    00155         m_type = mset.m_type;
    00156         mset.m_type = typetmp;
    00157     }
    00158
    00159
    00160 private:
    00161
    00162     void init_bitbuf(bm::word_t* buf)
    00163     {
    00164         unsigned arr_size = BM_MINISET_ARRSIZE(N);
    00165         m_buf = A::allocate(arr_size, 0);
    00166         if (buf)
    00167         {
    00168             ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
    00169         }
    00170         else
    00171         {
    00172             ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
    00173         }
    00174         m_type = 0;
    00175     }
    00176
    00177     void init_gapbuf(bm::word_t* buf)
    00178     {
    00179         unsigned arr_size =
    00180             BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
    00181         m_buf = A::allocate(arr_size, 0);
    00182         if (buf)
    00183         {
    00184             ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
    00185         }
    00186         else
    00187         {
    00188             *m_buf = 0;
    00189             gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
    00190         }
    00191         m_type = 1;
    00192     }
    00193
    00194     void convert_buf()
    00195     {
    00196         unsigned arr_size = BM_MINISET_ARRSIZE(N);
    00197         bm::word_t* buf = A::allocate(arr_size, 0);
    00198
    00199         gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
    00200         arr_size =
    00201             BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
    00202         A::deallocate(m_buf, arr_size);
    00203         m_buf = buf;
    00204         m_type = 0;
    00205     }
    00206
    00207 private:
    00208     bm::word_t*   m_buf;      //!< Buffer pointer
    00209     unsigned      m_type;     //!< buffer type (0-bit, 1-gap)
    00210 };
    00211
    00212
    00213 /*!
    00214     @brief Mini bitvector used in bvector template to keep block type flags
    00215
    00216     Template is used as a default template parameter MS for bvector
    00217     Offers maximum performance comparing to miniset.
    00218
    00219     @sa miniset
    00220 */
    00221 template<size_t N> class bvmini
    00222 {
    00223 public:
    00224
    00225     bvmini(int start_strategy = 0)
    00226     {
    00227         ::memset(m_buf, 0, sizeof(m_buf));
    00228     }
    00229
    00230     bvmini(const bvmini& mset)
    00231     {
    00232         ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
    00233     }
    00234
    00235
    00236     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
    00237     unsigned test(bm::id_t n) const
    00238     {
    00239         return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
    00240     }
    00241
    00242     void set(bm::id_t n, bool val=true)
    00243     {
    00244         unsigned nword  = n >> bm::set_word_shift;
    00245         unsigned mask = unsigned(1) << (n & bm::set_word_mask);
    00246
    00247         val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
    00248     }
    00249
    00250     unsigned mem_used() const
    00251     {
    00252         return sizeof(*this);
    00253     }
    00254
    00255     void swap(bvmini& mset)
    00256     {
    00257         for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
    00258         {
    00259             bm::word_t tmp = m_buf[i];
    00260             m_buf[i] = mset.m_buf[i];
    00261             mset.m_buf[i] = tmp;
    00262         }
    00263     }
    00264
    00265 private:
    00266     bm::word_t   m_buf[BM_MINISET_ARRSIZE(N)];
    00267 };
    00268
    00269
    00270 /*!@} */
    00271
    00272 /*!
    00273     @brief Bitvector class with very limited functionality.
    00274
    00275     Class implements simple bitset and used for internal
    00276     and testing purposes.
    00277 */
    00278 template<class A> class bvector_mini
    00279 {
    00280 public:
    00281     bvector_mini(unsigned size)
    00282       : m_buf(0),
    00283         m_size(size)
    00284     {
    00285         unsigned arr_size = (size / 32) + 1;
    00286         m_buf = A::allocate(arr_size, 0);
    00287         ::memset(m_buf, 0, arr_size * sizeof(unsigned));
    00288     }
    00289     bvector_mini(const bvector_mini& bvect)
    00290        : m_size(bvect.m_size)
    00291     {
    00292         unsigned arr_size = (m_size / 32) + 1;
    00293         m_buf = A::allocate(arr_size, 0);
    00294         ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));
    00295     }
    00296
    00297     ~bvector_mini()
    00298     {
    00299         A::deallocate(m_buf, (m_size / 32) + 1);
    00300     }
    00301
    00302     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
    00303     int is_bit_true(unsigned pos) const
    00304     {
    00305         unsigned char  mask = (unsigned char)((char)0x1 << (pos & 7));
    00306         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); // m_buf + (pos/8)
    00307
    00308         return (*offs) & mask;
    00309     }
    00310
    00311     /// Sets bit number pos to 1
    00312     void set_bit(unsigned pos)
    00313     {
    00314         unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
    00315         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
    00316         *offs |= mask;
    00317     }
    00318
    00319
    00320     /// Sets bit number pos to 0
    00321     void clear_bit(unsigned pos)
    00322     {
    00323         unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
    00324         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
    00325
    00326         *offs &= ~mask;
    00327     }
    00328
    00329     /// Counts number of bits ON
    00330     unsigned bit_count() const
    00331     {
    00332         register unsigned count = 0;
    00333         const unsigned* end = m_buf + (m_size / 32)+1;
    00334
    00335         for (unsigned* start = m_buf; start < end; ++start)
    00336         {
    00337             register unsigned value = *start;
    00338             for (count += (value!=0); value &= value - 1; ++count);
    00339         }
    00340         return count;
    00341     }
    00342
    00343     /// Comparison.
    00344     int compare(const bvector_mini& bvect)
    00345     {
    00346         unsigned cnt1 = bit_count();
    00347         unsigned cnt2 = bvect.bit_count();
    00348
    00349         if (!cnt1 && !cnt2) return 0;
    00350
    00351         unsigned cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
    00352
    00353         if (!cnt_min) return cnt1 ? 1 : -1;
    00354
    00355         unsigned idx1 = get_first();
    00356         unsigned idx2 = bvect.get_first();
    00357
    00358         for (unsigned i = 0; i < cnt_min; ++i)
    00359         {
    00360             if (idx1 != idx2)
    00361             {
    00362                 return idx1 < idx2 ? 1 : -1;
    00363             }
    00364             idx1 = get_next(idx1);
    00365             idx2 = bvect.get_next(idx2);
    00366         }
    00367
    00368         //BM_ASSERT(idx1==0 || idx2==0);
    00369
    00370         if (idx1 != idx2)
    00371         {
    00372             if (!idx1) return -1;
    00373             if (!idx2) return  1;
    00374             return idx1 < idx2 ? 1 : -1;
    00375         }
    00376
    00377         return 0;
    00378     }
    00379
    00380
    00381     /// Returns index of the first ON bit
    00382     unsigned get_first() const
    00383     {
    00384         unsigned pos = 0;
    00385         const unsigned char* ptr = (unsigned char*) m_buf;
    00386
    00387         for (unsigned i = 0; i < (m_size/8)+1; ++i)
    00388         {
    00389             register unsigned char w = ptr[i];
    00390
    00391
    00392             if (w != 0)
    00393             {
    00394                 while ((w & 1) == 0)
    00395                 {
    00396                     w >>= 1;
    00397                     ++pos;
    00398                 }
    00399                 return pos;
    00400             }
    00401             pos += sizeof(unsigned char) * 8;
    00402         }
    00403         return 0;
    00404     }
    00405
    00406
    00407     /// Returns index of next bit, which is ON
    00408     unsigned get_next(unsigned idx) const
    00409     {
    00410         register unsigned i;
    00411
    00412         for (i = idx+1; i < m_size; ++i)
    00413         {
    00414             unsigned char* offs = (unsigned char*)m_buf + (i >> 3);
    00415             if (*offs)
    00416             {
    00417                 unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
    00418
    00419                 if (*offs & mask)
    00420                 {
    00421                     return i;
    00422                 }
    00423             }
    00424             else
    00425             {
    00426                 i += 7;
    00427             }
    00428         }
    00429         return 0;
    00430     }
    00431
    00432
    00433     void combine_and(const bvector_mini& bvect)
    00434     {
    00435         const unsigned* end = m_buf + (m_size / 32)+1;
    00436
    00437         const unsigned* src = bvect.get_buf();
    00438
    00439         for (unsigned* start = m_buf; start < end; ++start)
    00440         {
    00441             *start &= *src++;
    00442         }
    00443     }
    00444
    00445     void combine_xor(const bvector_mini& bvect)
    00446     {
    00447         const unsigned* end = m_buf + (m_size / 32)+1;
    00448
    00449         const unsigned* src = bvect.get_buf();
    00450
    00451         for (unsigned* start = m_buf; start < end; ++start)
    00452         {
    00453             *start ^= *src++;
    00454         }
    00455     }
    00456
    00457
    00458     void combine_or(const bvector_mini& bvect)
    00459     {
    00460         const unsigned* end = m_buf + (m_size / 32)+1;
    00461
    00462         const unsigned* src = bvect.get_buf();
    00463
    00464         for (unsigned* start = m_buf; start < end; ++start)
    00465         {
    00466             *start |= *src++;
    00467         }
    00468     }
    00469
    00470     void combine_sub(const bvector_mini& bvect)
    00471     {
    00472         const unsigned* end = m_buf + (m_size / 32)+1;
    00473
    00474         const unsigned* src = bvect.get_buf();
    00475
    00476         for (unsigned* start = m_buf; start < end; ++start)
    00477         {
    00478             *start &= ~(*src++);
    00479         }
    00480     }
    00481
    00482     const unsigned* get_buf() const { return m_buf; }
    00483     unsigned mem_used() const
    00484     {
    00485         return sizeof(bvector_mini) + (m_size / 32) + 1;
    00486     }
    00487
    00488     void swap(bvector_mini& bvm)
    00489     {
    00490         BM_ASSERT(m_size == bvm.m_size);
    00491         bm::word_t* buftmp = m_buf;
    00492         m_buf = bvm.m_buf;
    00493         bvm.m_buf = buftmp;
    00494     }
    00495
    00496 private:
    00497     bm::word_t*   m_buf;
    00498     unsigned      m_size;
    00499 };
    00500
    00501
    00502
    00503 } // namespace bm
    00504
    00505 #ifdef _MSC_VER
    00506 #pragma warning( pop )
    00507 #endif
    00508
    00509 #endif