libopenbabel-dev 2.3.0+dfsg-3ubuntu3 / usr / include / openbabel-2.0 / openbabel / bitvec.h

/**********************************************************************
bitvec.h - Vector of bits.

Copyright (C) 1998-2001 by OpenEye Scientific Software, Inc.
Some portions Copyright (C) 2001-2006 by Geoffrey R. Hutchison

This file is part of the Open Babel project.
For more information, see <http://openbabel.org/>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation version 2 of the License.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
***********************************************************************/

#ifndef OB_BITVEC_H
#define OB_BITVEC_H

#include <openbabel/babelconfig.h>

#include <vector>
#include <string>

#ifndef USE_64BIT_INTEGER
// For 32-bit architecture
#define SETWORD 32
// SETWORD = 2 ^ WORDROLL
#define WORDROLL 5
// WORDMASK = SETWORD - 1
#define WORDMASK 31
#else
// For 64-bit architecture
#define SETWORD 64
// SETWORD = 2 ^ WORDROLL
#define WORDROLL 6
// WORDMASK = SETWORD - 1
#define WORDMASK 63
#endif // 64 bit

#define WORDSIZE_OF_BITSIZE( bit_size ) ( ( bit_size >> WORDROLL ) + (( bit_size & WORDMASK ) ? 1 : 0) )

#ifndef STARTWORDS
#define STARTWORDS 10
#endif // STARTWORDS

namespace OpenBabel
  {
  /// A speed-optimized vector of bits
  /** This class implements a fast vector of bits
      using internally a vector of processor native
	  unsigned words.
	  Any bits which are out of reach of the current
	  size are considered to be zero.
	  Streamlined, corrected and documented
	   by kshepherd1@users.sourceforge.net
  */
  class OBERROR OBBitVec
    {
    public:
	  typedef std::vector<unsigned> word_vector;

	private:
	  /// The number of <b>words</b> currently stored ( NOT bit count )
      size_t _size; //was unsigned
	  /// A vector of words used to store the bit values
      word_vector	_set;

    public:
	  /// Construct a bit vector of the default size
	  /** Construct a bit vector of STARTWORDS size,
	      cleared to all zero bits.
	  */
      OBBitVec()
	  :_set(STARTWORDS, 0)
        { _size = _set.size(); }
	  /// Construct a bit vector of maxbits bits
	  /** Construct a bit vector with a size in bits
	      of \p size_in_bits rounded up to the nearest word
		  and cleared to all zero bits.
		  \param[in]	size_in_bits The number of bits for which to reserve space
	  */
      OBBitVec(unsigned size_in_bits)
	  :_set(WORDSIZE_OF_BITSIZE(size_in_bits), 0)
        { _size = _set.size(); }
      /// Copy constructor (result has same number of bits)
	  /** Construct a bit vector which is an exact
	      duplicate of \p bv.
		  \param[in]	bv The other bit vector to copy to this
	  */
      OBBitVec(const OBBitVec & bv)
	  :_size(0)
	  	{ (*this) = bv; }
	  /// Set the \p bit_offset 'th bit to 1
      void SetBitOn(unsigned bit_offset);
	  /// Set the \p bit_offset 'th bit to 0
      void SetBitOff(unsigned bit_offset);
	  /// Set the range of bits from \p lo_bit_offset to \p hi_bit_offset to 1
      void SetRangeOn(unsigned lo_bit_offset, unsigned hi_bit_offset);
	  /// Set the range of bits from \p lo_bit_offset to \p hi_bit_offset to 0
      void SetRangeOff(unsigned lo_bit_offset, unsigned hi_bit_offset);
	  /// Reduce the size of the vector by or-ing the excess bits over the start
      void Fold(unsigned new_bit_size);
      /// Find the first true bit at or after \p bit_offset
      /** Searches the vector for the first true value, starting at the \p bit_offset 'th bit
          \param[in] bit_offset the first bit to consider
		  \return the bit offset of the first true bit at or after \p bit_offset, or -1 if there is none
	  */
      int FirstBit(unsigned bit_offset = 0) const
        {
          return (BitIsSet(bit_offset) ? 0  : NextBit(bit_offset));
        }
      /// Find the next true bit after \p last_bit_offset
      int NextBit(int last_bit_offset) const;
      /// Return the bit offset of the last bit (for iterating) i.e. -1
      int EndBit() const {  return -1; }
      /// Return the number of words ( NOT the number of bits ).
      size_t GetSize() const    { return(_size);    }
      /// Return the number of bits which are set to 1 in the vector
      unsigned CountBits() const;

      /// \deprecated Use IsEmpty() instead.
      bool Empty() const   { return(IsEmpty()); }
	  /// Are there no bits set to 1 in this vector?
      bool IsEmpty() const;
      /// Reserve space for \p size_in_bits bits
	  /** Reserve space for \p size_in_bits bits rounded up
	      \param[in] size_in_bits the number of bits
	      \return true if enlargement was necessary, false otherwise
	  */
      bool Resize(unsigned size_in_bits)
	  	{
		return ResizeWords( WORDSIZE_OF_BITSIZE(size_in_bits) );
		}
      /// Reserve space for \p size_in_words words
	  /** Reserve space for \p size_in_words words
	      \param[in] size_in_words the number of words
	      \return true if enlargement was necessary, false otherwise
	  */
	  bool ResizeWords(unsigned size_in_words)
	  	{
		if (size_in_words <= _size)
		  return false;
		_set.resize(size_in_words, 0); // increase the vector with zeroed bits
		_size = _set.size();
		return true;
		}
      /// Asks if the \p bit_offset 'th bit is set
	  /** Is the \p bit_offset 'th bit set ?
          \param[in] bit_offset a zero based offset into the bit vector
		  \return true if it is set, false otherwise
	  */
      bool BitIsSet(unsigned bit_offset) const
        {
		  bool rtn = false;
		  unsigned word_offset = bit_offset >> WORDROLL;
		  if (word_offset < GetSize())
		  	{
			  bit_offset &= WORDMASK;
			  rtn = (( _set[word_offset] >> bit_offset ) & 1);
			}
          return rtn;
        }
      /// \deprecated Use BitIsSet(unsigned bit_offset) instead.
      bool BitIsOn(int bit_offset) const
        { return BitIsSet((unsigned)bit_offset); }

      /// Sets the bits listed as bit offsets
	  void FromVecInt(const std::vector<int> & bit_offsets);
      /// Sets the bits listed as a string of integers
	  void FromString(const std::string & line, int bits);
      /// List the offsets of the bits which are set
	  void ToVecInt(std::vector<int> & bit_offsets) const;
	  /// Set all bits to zero
      void Clear();
      /// Inverts every bit in the vector
	  /** Inverts the entire vector.
	      Note that this may give unexpected results, as the vector
		  can be considered to end in an arbitrary number of zero bits.
	  */
      void Negate()
        {
		  for (word_vector::iterator wx = _set.begin(), wy = _set.end(); wx != wy; ++wx)
		    * wx = ~(* wx);
        }
      /// Return a copy of the internal vector of words, at the end of \p vec
	  /** Copy the internal word vector.
	      The copy is appended to \p vec.
		  \param[out] vec a vector of words to which to append the data
	  */
      void GetWords(word_vector & vec)
        {
		vec.insert(vec.end(), _set.begin(),_set.end());
        }

      /// Assignment operator
      OBBitVec & operator= (const OBBitVec & bv);
      /// And-equals operator
      OBBitVec & operator&= (const OBBitVec & bv);
      /// Or-equals operator
      OBBitVec & operator|= (const OBBitVec & bv);
      /// Or-equals operator for integer
	  /** Or the bit at offset \p bit_offset with 1
	  */
      OBBitVec & operator|= (int bit_offset)
        {
          SetBitOn(bit_offset);
          return(*this);
        }
      /// Exclusive-or-equals operator
      OBBitVec & operator^= (const OBBitVec & bv);
      /// Minus-equals operator
      OBBitVec & operator-= (const OBBitVec & bv);
      /// Plus-equals operator
      OBBitVec & operator+= (const OBBitVec & bv);
      /// Asks if the \p bit_offset 'th bit is set
	  /** Is the \p bit_offset 'th bit set ?
          \param[in] bit_offset a zero based offset into the bit vector
		  \return true if it is set, false otherwise
	  */
      bool operator[] (int bit_offset) const
        { return BitIsSet(bit_offset); }

      /// Or operator
      friend OBERROR OBBitVec operator| (const OBBitVec & bv1, const OBBitVec & bv2);
      /// And operator
      friend OBERROR OBBitVec operator& (const OBBitVec & bv1,const OBBitVec & bv2);
      /// Exclusive-or operator
      friend OBERROR OBBitVec operator^ (const OBBitVec & bv1,const OBBitVec & bv2);
      /// Minus operator
      friend OBERROR OBBitVec operator- (const OBBitVec & bv1,const OBBitVec & bv2);
      /// Equivalency operator
      friend OBERROR bool operator== (const OBBitVec & bv1,const OBBitVec & bv2);
      /// Smaller-than operator
      friend OBERROR bool operator< (const OBBitVec & bv1, const OBBitVec & bv2);

      /// Input from a stream
      friend OBERROR std::istream& operator>> ( std::istream & is, OBBitVec & bv );
      /// Output to a stream
      friend OBERROR std::ostream& operator<< ( std::ostream & os, const OBBitVec & bv ) ;
    };

  /// The Tanimoto coefficient, which may be regarded as the proportion of the "on-bits" which are shared.
  OBERROR double Tanimoto(const OBBitVec & bv1, const OBBitVec & bv2);

  } // end namespace OpenBabel

#endif // OB_BITVEC_H

//! \file bitvec.h
//! \brief Fast and efficient bitstring class