bmvmin.h
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:12k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: bmvmin.h,v $
  4.  * PRODUCTION Revision 1000.0  2004/04/21 16:01:02  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [CATCHUP_003] Dev-tree R1.1
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /*
  10. Copyright (c) 2002 Anatoliy Kuznetsov.
  11. Permission is hereby granted, free of charge, to any person 
  12. obtaining a copy of this software and associated documentation 
  13. files (the "Software"), to deal in the Software without restriction, 
  14. including without limitation the rights to use, copy, modify, merge, 
  15. publish, distribute, sublicense, and/or sell copies of the Software, 
  16. and to permit persons to whom the Software is furnished to do so, 
  17. subject to the following conditions:
  18. The above copyright notice and this permission notice shall be included 
  19. in all copies or substantial portions of the Software.
  20. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
  21. EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
  22. OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
  23. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
  24. DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
  25. ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
  26. OTHER DEALINGS IN THE SOFTWARE.
  27. */
  28. #ifndef BMVMIN__H__INCLUDED__
  29. #define BMVMIN__H__INCLUDED__
  30. namespace bm
  31. {
  32. #define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
  33. #define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
  34. /*! @defgroup mset Small sets functionality
  35.  *  Templates in this group are used to keep block types in BM library.
  36.  *  Classes of this group can tune bvector template (MS parameter)
  37.  *  for best performance or minimal memory usage.
  38.  *  @{
  39.  */
  40. /*!
  41.     @brief Template class implements memory saving set functionality
  42.     
  43.     Template can be used as template parameter for bvector if we 
  44.     want to tune bvector for minimal memory consumption.
  45.     @sa bvmini
  46. */
  47. template <class A, size_t N> class miniset
  48. {
  49. public:
  50.     miniset() 
  51.         : m_buf(0),
  52.           m_type(1)
  53.     {}
  54.     miniset(const miniset& mset)
  55.     {
  56.         if (mset.m_buf)
  57.         {
  58.             if (mset.m_type)
  59.                 init_gapbuf(mset.m_buf);
  60.             else
  61.                 init_bitbuf(mset.m_buf);
  62.         }
  63.         else
  64.         {
  65.             m_type = mset.m_type;
  66.             m_buf = 0;
  67.         }
  68.     }
  69.     ~miniset()
  70.     {
  71.         if (m_buf)
  72.         {
  73.             A::deallocate(m_buf, m_type ? 
  74.                 (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
  75.                 : 
  76.                 (BM_MINISET_ARRSIZE(N)));
  77.         }
  78.     }
  79.     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
  80.     unsigned test(bm::id_t n) const 
  81.     { 
  82.         return
  83.             !m_buf ? 0 
  84.             :
  85.             m_type ? 
  86.               gap_test((gap_word_t*)m_buf, n)
  87.               : 
  88.               m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
  89.     }
  90.     void set(bm::id_t n, bool val=true)
  91.     {
  92.         if (m_type == 0)
  93.         {
  94.             if (!m_buf)
  95.             {
  96.                 if (!val) return;
  97.                 init_bitbuf(0);
  98.             }
  99.             unsigned nword  = n >> bm::set_word_shift; 
  100.             unsigned mask = unsigned(1) << (n & bm::set_word_mask);
  101.             val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
  102.         }
  103.         else
  104.         {
  105.             if (!m_buf)
  106.             {
  107.                 if (!val) return;
  108.                 init_gapbuf(0);
  109.             }
  110.             
  111.             unsigned is_set;
  112.             unsigned new_block_len = 
  113.                 gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
  114.             if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
  115.             {
  116.                 convert_buf();
  117.             }
  118.         }
  119.     }
  120.     unsigned mem_used() const
  121.     {
  122.         return sizeof(*this) +
  123.                m_buf ? 
  124.                  (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
  125.                         : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
  126.                 : 0; 
  127.     }
  128.     void swap(miniset& mset)
  129.     {
  130.         bm::word_t* buftmp = m_buf;
  131.         m_buf = mset.m_buf;
  132.         mset.m_buf = buftmp;
  133.         unsigned typetmp = m_type;
  134.         m_type = mset.m_type;
  135.         mset.m_type = typetmp;
  136.     }
  137. private:
  138.     void init_bitbuf(bm::word_t* buf)
  139.     {
  140.         unsigned arr_size = BM_MINISET_ARRSIZE(N);
  141.         m_buf = A::allocate(arr_size, 0);
  142.         if (buf)
  143.         {
  144.             ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
  145.         }
  146.         else
  147.         {
  148.             ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
  149.         }
  150.         m_type = 0;
  151.     }
  152.     void init_gapbuf(bm::word_t* buf)
  153.     {
  154.         unsigned arr_size = 
  155.             BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
  156.         m_buf = A::allocate(arr_size, 0);
  157.         if (buf)
  158.         {
  159.             ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
  160.         }
  161.         else
  162.         {
  163.             *m_buf = 0;
  164.             gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
  165.         }
  166.         m_type = 1;
  167.     }
  168.     void convert_buf()
  169.     {
  170.         unsigned arr_size = BM_MINISET_ARRSIZE(N);
  171.         bm::word_t* buf = A::allocate(arr_size, 0);
  172.         gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
  173.         arr_size = 
  174.             BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
  175.         A::deallocate(m_buf, arr_size);
  176.         m_buf = buf;
  177.         m_type = 0;
  178.     }
  179. private:
  180.     bm::word_t*   m_buf;      //!< Buffer pointer
  181.     unsigned      m_type;     //!< buffer type (0-bit, 1-gap)
  182. };
  183. /*!
  184.     @brief Mini bitvector used in bvector template to keep block type flags
  185.     
  186.     Template is used as a default template parameter MS for bvector  
  187.     Offers maximum performance comparing to miniset.
  188.     @sa miniset
  189. */
  190. template<size_t N> class bvmini
  191. {
  192. public:
  193.     bvmini(int start_strategy = 0) 
  194.     {
  195.         ::memset(m_buf, 0, sizeof(m_buf));
  196.     }
  197.     bvmini(const bvmini& mset)
  198.     {
  199.         ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
  200.     }
  201.     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
  202.     unsigned test(bm::id_t n) const 
  203.     { 
  204.         return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
  205.     }
  206.     void set(bm::id_t n, bool val=true)
  207.     {
  208.         unsigned nword  = n >> bm::set_word_shift; 
  209.         unsigned mask = unsigned(1) << (n & bm::set_word_mask);
  210.         val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
  211.     }
  212.     unsigned mem_used() const
  213.     {
  214.         return sizeof(*this);
  215.     }
  216.     void swap(bvmini& mset)
  217.     {
  218.         for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
  219.         {
  220.             bm::word_t tmp = m_buf[i];
  221.             m_buf[i] = mset.m_buf[i];
  222.             mset.m_buf[i] = tmp;
  223.         }
  224.     }
  225. private:
  226.     bm::word_t   m_buf[BM_MINISET_ARRSIZE(N)];
  227. };
  228. /*!@} */
  229. /*!
  230.     @brief Bitvector class with very limited functionality.
  231.     Class implements simple bitset and used for internal 
  232.     and testing purposes. 
  233. */
  234. template<class A> class bvector_mini
  235. {
  236. public:
  237.     bvector_mini(unsigned size) 
  238.       : m_buf(0),
  239.         m_size(size)
  240.     {
  241.         unsigned arr_size = (size / 32) + 1; 
  242.         m_buf = A::allocate(arr_size, 0);
  243.         ::memset(m_buf, 0, arr_size * sizeof(unsigned));
  244.     }
  245.     bvector_mini(const bvector_mini& bvect)
  246.        : m_size(bvect.m_size)
  247.     {
  248.         unsigned arr_size = (m_size / 32) + 1;
  249.         m_buf = A::allocate(arr_size, 0);
  250.         ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));        
  251.     }
  252.     ~bvector_mini()
  253.     {
  254.         A::deallocate(m_buf, (m_size / 32) + 1); 
  255.     }
  256.     /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
  257.     int is_bit_true(unsigned pos) const
  258.     {
  259.         unsigned char  mask = (unsigned char)((char)0x1 << (pos & 7));
  260.         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); // m_buf + (pos/8)
  261.         return (*offs) & mask;
  262.     }
  263.     /// Sets bit number pos to 1
  264.     void set_bit(unsigned pos)
  265.     {
  266.         unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
  267.         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
  268.         *offs |= mask;
  269.     }
  270.     /// Sets bit number pos to 0
  271.     void clear_bit(unsigned pos)
  272.     {
  273.         unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
  274.         unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
  275.         *offs &= ~mask;
  276.     }
  277.     /// Counts number of bits ON 
  278.     unsigned bit_count() const
  279.     {
  280.         register unsigned count = 0;
  281.         const unsigned* end = m_buf + (m_size / 32)+1;    
  282.         for (unsigned* start = m_buf; start < end; ++start)
  283.         {
  284.             register unsigned value = *start;
  285.             for (count += (value!=0); value &= value - 1; ++count);
  286.         }
  287.         return count;
  288.     }
  289.     /// Comparison.
  290.     int compare(const bvector_mini& bvect)
  291.     {
  292.         unsigned cnt1 = bit_count();
  293.         unsigned cnt2 = bvect.bit_count();
  294.         if (!cnt1 && !cnt2) return 0;
  295.         unsigned cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
  296.         if (!cnt_min) return cnt1 ? 1 : -1;
  297.         unsigned idx1 = get_first();
  298.         unsigned idx2 = bvect.get_first();
  299.         for (unsigned i = 0; i < cnt_min; ++i)
  300.         {
  301.             if (idx1 != idx2)
  302.             {
  303.                 return idx1 < idx2 ? 1 : -1;
  304.             }
  305.             idx1 = get_next(idx1);
  306.             idx2 = bvect.get_next(idx2);
  307.         }
  308.         BM_ASSERT(idx1==0 || idx2==0);
  309.         if (idx1 != idx2)
  310.         {
  311.             if (!idx1) return -1;
  312.             if (!idx2) return  1;
  313.             return idx1 < idx2 ? 1 : -1;
  314.         }
  315.         return 0;
  316.     }
  317.     /// Returns index of the first ON bit
  318.     unsigned get_first() const
  319.     {
  320.         unsigned pos = 0;
  321.         const unsigned char* ptr = (unsigned char*) m_buf;
  322.         for (unsigned i = 0; i < (m_size/8)+1; ++i)
  323.         {
  324.             register unsigned char w = ptr[i];
  325.             if (w != 0)
  326.             {
  327.                 while ((w & 1) == 0)
  328.                 {
  329.                     w >>= 1;
  330.                     ++pos;
  331.                 }
  332.                 return pos;
  333.             }
  334.             pos += sizeof(unsigned char) * 8;
  335.         }
  336.         return 0;
  337.     }
  338.     /// Returns index of next bit, which is ON
  339.     unsigned get_next(unsigned idx) const
  340.     {
  341.         register unsigned i;
  342.         for (i = idx+1; i < m_size; ++i)
  343.         {
  344.             unsigned char* offs = (unsigned char*)m_buf + (i >> 3); 
  345.             if (*offs)
  346.             {
  347.                 unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
  348.                 if (*offs & mask)
  349.                 {
  350.                     return i;
  351.                 }
  352.             }
  353.             else
  354.             {
  355.                 i += 7;
  356.             }
  357.         }
  358.         return 0;
  359.     }
  360.     void combine_and(const bvector_mini& bvect)
  361.     {
  362.         const unsigned* end = m_buf + (m_size / 32)+1;
  363.     
  364.         const unsigned* src = bvect.get_buf();
  365.         for (unsigned* start = m_buf; start < end; ++start)
  366.         {
  367.             *start &= *src++;
  368.         }
  369.     }
  370.     void combine_xor(const bvector_mini& bvect)
  371.     {
  372.         const unsigned* end = m_buf + (m_size / 32)+1;
  373.     
  374.         const unsigned* src = bvect.get_buf();
  375.         for (unsigned* start = m_buf; start < end; ++start)
  376.         {
  377.             *start ^= *src++;
  378.         }
  379.     }
  380.     void combine_or(const bvector_mini& bvect)
  381.     {
  382.         const unsigned* end = m_buf + (m_size / 32)+1;
  383.     
  384.         const unsigned* src = bvect.get_buf();
  385.         for (unsigned* start = m_buf; start < end; ++start)
  386.         {
  387.             *start |= *src++;
  388.         }
  389.     }
  390.     void combine_sub(const bvector_mini& bvect)
  391.     {
  392.         const unsigned* end = m_buf + (m_size / 32)+1;
  393.     
  394.         const unsigned* src = bvect.get_buf();
  395.         for (unsigned* start = m_buf; start < end; ++start)
  396.         {
  397.             *start &= ~(*src++);
  398.         }
  399.     }
  400.     const unsigned* get_buf() const { return m_buf; }
  401.     unsigned mem_used() const
  402.     {
  403.         return sizeof(bvector_mini) + (m_size / 32) + 1;
  404.     }
  405.     void swap(bvector_mini& bvm)
  406.     {
  407.         BM_ASSERT(m_size == bvm.m_size);
  408.         bm::word_t* buftmp = m_buf;
  409.         m_buf = bvm.m_buf;
  410.         bvm.m_buf = buftmp;
  411.     }
  412. private:
  413.     bm::word_t*   m_buf;
  414.     unsigned      m_size;
  415. };
  416. } // namespace bm
  417. #endif