Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Namespace Members | Data Fields | Globals | Examples

bmvmin.h

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

Generated on Sun Aug 5 14:12:26 2007 for BitMagic by  doxygen 1.4.1