src/openbabel/bitvec.cpp

/**********************************************************************
bitvec.cpp - Fast and efficient bitstring class.
 
Copyright (C) 1998-2001 by OpenEye Scientific Software, Inc.
Some portions Copyright (C) 2001-2005 by Geoffrey R. Hutchison
 
This file is part of the Open Babel project.
For more information, see <http://openbabel.sourceforge.net/>
 
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.
***********************************************************************/

#include "bitvec.hpp"
#include "oberror.hpp"

using namespace std;

namespace OpenBabel
{

extern OBMessageHandler obErrorLog;

/*! \class OBBitVec
    \brief Fast and efficient bitstring class

The OBBitVec class is a fast and efficient bitstring class that is
handy to use as a truth table. Truth tables are an easy way to store
whether a list of items has a particular propery. Instances of
OBBitVec can by dynamically resized, and have a number of overloaded
operators that make code simple and readable. The following examples
demonstrate uses of the OBBitVec class:
\code
OBBitVec bv1,bv2,bv3;
bv1.SetBitOn(5);
bv2.SetBitOff(200);
bv1 |= bv2;
bv1 = bv1 & bv2;
if (bv1.Empty()) //Empty() returns true if no bits are set on
{
cout << "bv1 = " << bv1 << endl;
}

int bit;
for (bit = bv1.NextBit(0);bit != bv1.EndBit();bit = bv1.NextBit(bit))
{
cout << "the next bit turned on is " << bit << endl;
}
\endcode
 */

static int bitsoff[SETWORD] =
    {
        0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFC,0xFFFFFFF8,0xFFFFFFF0,0xFFFFFFE0,0xFFFFFFC0,
        0xFFFFFF80,0xFFFFFF00,0xFFFFFE00,0xFFFFFC00,0xFFFFF800,0xFFFFF000,0xFFFFE000,
        0xFFFFC000,0xFFFF8000,0xFFFF0000,0xFFFE0000,0xFFFC0000,0xFFF80000,0xFFF00000,
        0xFFE00000,0xFFC00000,0xFF800000,0xFF000000,0xFE000000,0xFC000000,0xF8000000,
        0xF0000000,0xE0000000,0xC0000000,0x80000000
    };

#ifndef LowBit
#define LowBit(set, bit)\
  {register int m;\
   if (set != 0)\
   {\
      bit = 31;\
      if (set != 0x80000000) {\
      if ((m = (set & 0x0000ffff))) {set = m; bit -= 16;}\
      if ((m = (set & 0x00ff00ff))) {set = m; bit -= 8;}\
      if ((m = (set & 0x0f0f0f0f))) {set = m; bit -= 4;}\
      if ((m = (set & 0x33333333))) {set = m; bit -= 2;}\
      if ((m = (set & 0x55555555))) {set = m; bit -= 1;}}}\
   else bit = -1;}
#endif

OBBitVec::OBBitVec(const OBBitVec &bv)
{
    _size = 0;
    (*this) = bv;
}

void OBBitVec::SetBitOn(int bit)
{
    int word = bit/SETWORD;
    bit = bit%SETWORD;

    //if (word+1 >= GetSize()) Resize((word+1)*SETWORD);
    if (word >= _size)
        Resize((word+1)*SETWORD);
    _set[word] |= (1<<bit);
}

void OBBitVec::SetRangeOn(int lobit, int hibit)
{
    int i;

    if (lobit > hibit)
        return;
    else if (lobit == hibit)
        SetBitOn(hibit);
    else
    {
        int loword = lobit / SETWORD;
        int hiword = hibit / SETWORD;
        int lobitp = lobit % SETWORD;
        int hibitp = hibit % SETWORD;

        if (hiword >= _size)
            Resize((hiword+1) * SETWORD);

        if (loword == hiword)
        {
            for ( i = lobitp ; i <= hibitp ; i++ )
                _set[loword] |= (1<<i);
        }
        else
        {
            for ( i = lobitp ; i < SETWORD ; i++ )
                _set[loword] |= (1<<i);
            for ( i = loword + 1 ; i < hiword ; i++ )
                _set[i] = 0xFFFFFFFF;
            for ( i = 0 ; i <= hibitp ; i++ )
                _set[hiword] |= (1<<i);
        }
    }
}

void OBBitVec::SetBitOff(int bit)
{
    int word = bit/SETWORD;
    bit = bit%SETWORD;
    _set[word] &= (~(1 << bit));
}

void OBBitVec::SetRangeOff(int lobit, int hibit)
{
    int i;

    if (lobit > hibit)
        return;
    else if (lobit == hibit)
        SetBitOff(hibit);
    else
    {
        int loword = lobit / SETWORD;
        int hiword = hibit / SETWORD;
        int lobitp = lobit % SETWORD;
        int hibitp = hibit % SETWORD;

        if (hiword >= _size)
        {
            hiword = _size - 1;
            hibitp = SETWORD - 1;
        }

        if (loword == hiword)
        {
            for ( i = lobitp ; i <= hibitp ; i++ )
                _set[loword] &= (~(1<<i));
        }
        else
        {
            for ( i = lobitp ; i < SETWORD ; i++ )
                _set[loword] &= (~(1<<i));
            for ( i = loword + 1 ; i < hiword ; i++ )
                _set[i] = 0x00000000;
            for ( i = 0 ; i <= hibitp ; i++ )
                _set[hiword] &= (~(1<<i));
        }
    }
}

int OBBitVec::NextBit(int last)
{
    unsigned s;
    register int bit,wrdcnt;
    last++;

    wrdcnt = last/SETWORD;

    if (wrdcnt >= _size)
        return(-1);

    if (_set[wrdcnt] != 0)
    {
        s = (_set[wrdcnt]) & bitsoff[last - (wrdcnt*SETWORD)];
        if (s)
        {
            LowBit(s,bit);
            if (bit != -1)
                return(bit + (wrdcnt*SETWORD));
        }
    }
    wrdcnt++;

    while(wrdcnt < _size)
    {
        if (this->_set[wrdcnt] != 0)
        {
            s = this->_set[wrdcnt];
            LowBit(s, bit);

            if (bit != -1)
                return(bit+(wrdcnt*SETWORD));
        }
        wrdcnt++;
    }

    return(-1);
}

bool OBBitVec::Resize(int maxbits)
{
    if(!maxbits)
        return(false);
    unsigned int maxword = maxbits/SETWORD;
    if (maxbits%SETWORD)
        maxword++;
    if (maxword >= _set.size())
    {
        _set.resize(maxword);
        _size = _set.size();
    }

    return(true);
}

OBBitVec &OBBitVec::operator= (const OBBitVec &bv)
{
    if (_size != bv._size)
        Resize(bv._size*SETWORD);

    int i;
    for ( i = 0 ; i < bv._size ; i++ )
        _set[i] = bv._set[i];
    for ( ; i < _size ; i++ )
        _set[i] = 0;

    return(*this);
}

OBBitVec &OBBitVec::operator&= ( OBBitVec &bv)
{
    int i;
    int min = (bv._size < _size) ? bv._size : _size;

    for (i = 0;i < min;i++)
        _set[i] &= bv._set[i];
    for (;i < _size;i++)
        _set[i] = 0;

    return(*this);
}

OBBitVec &OBBitVec::operator|= (OBBitVec &bv)
{
    if (_size != bv._size)
    {
        if (_size < bv._size)
            Resize(bv._size*SETWORD);
        else
            bv.Resize(_size*SETWORD);
    }
    for (int i = 0;i < _size;i++)
        _set[i] |= bv._set[i];

    return(*this);
}

OBBitVec &OBBitVec::operator^= (OBBitVec &bv)
{
    int i;
    if (_size != bv._size)
    {
        if (_size < bv._size)
            Resize(bv._size*SETWORD);
        else
            bv.Resize(_size*SETWORD);
    }
    for (i = 0;i < _size;i++)
        _set[i] ^= bv._set[i];

    return(*this);
}

OBBitVec &OBBitVec::operator-= (OBBitVec &bv)
{
    if (GetSize() != bv._size)
      obErrorLog.ThrowError(__FUNCTION__, "Subtracting sets of != size", obDebug);
    else
    {
        OBBitVec tmp;
        tmp = *this ^ bv;
        *this &= tmp;
    }
    return(*this);
}

OBBitVec &OBBitVec::operator+= (OBBitVec &bv)
{
    int old_size = _size;
    Resize(_size*SETWORD+bv._size*SETWORD);
    for (int i = 0;i < bv._size;i++)
        _set[i+old_size] = bv._set[i];
    return(*this);
}

OBBitVec operator| (OBBitVec &bv1,OBBitVec &bv2)
{
    OBBitVec bv;
    bv = bv1;
    bv |= bv2;

    return(bv);
}

OBBitVec operator& (OBBitVec &bv1, OBBitVec &bv2)
{
    OBBitVec bv;
    bv = bv1;
    bv &= bv2;

    return(bv);
}

OBBitVec operator^ (OBBitVec &bv1, OBBitVec &bv2)
{
    OBBitVec bv;
    bv = bv1;
    bv ^= bv2;
    return(bv);
}

bool operator== (const OBBitVec &bv1,const OBBitVec &bv2)
{
    if (bv1._size != bv2._size)
        return(false);

    int i;
    for (i = 0;i < bv1._size;i++)
        if (bv1._set[i] != bv2._set[i])
            return(false);

    return(true);
}

OBBitVec operator- (OBBitVec &bv1,OBBitVec &bv2)
{
    OBBitVec bv;
    bv = bv1 ^ bv2;
    bv &= bv1;
    return(bv);
}

istream& operator>> ( istream &is, OBBitVec &bv )
{
    size_t startpos = 0, endpos = 0;
    vector<string> tokens;
    string line;

    getline(is,line);

    for (;;)
    {
        startpos = line.find_first_not_of(" \t\n",startpos);
        endpos   = line.find_first_of(" \t\n",startpos);

        if (endpos < line.size() && startpos <= line.size())
            tokens.push_back(line.substr(startpos,endpos-startpos));
        else
            break;

        startpos = endpos + 1;
    }

    for (unsigned int i = 0 ; i < tokens.size() ; i++ )
    {
        if ( tokens[i] == "[" )
            continue;
        else if ( tokens[i] == "]" )
            break;

        int bit = atoi(tokens[i].c_str());

        if (bit >= 0)
            bv.SetBitOn(bit);
        else
          {
#ifdef HAVE_SSTREAM
                    stringstream errorMsg;
#else
                    strstream errorMsg;
#endif
            errorMsg << "Negative Bit: " << bit << endl;
            obErrorLog.ThrowError(__FUNCTION__, errorMsg.str(), obDebug);
          }
    }

    return is;
}

ostream& operator<< ( ostream &os, const  OBBitVec& bv)
{
    os << "[ " << flush;

    int i,j;
    for (i = 0;i < bv._size;i++)
        for (j = 0;j < SETWORD;j++)
            if (bv._set[i]>>(j%SETWORD)&1)
                os << (j+(i*SETWORD)) << ' ' << flush;

    os << "]" << flush;
    return(os);
}

void OBBitVec::Fold(int nbits)
{
    int nwords = nbits/SETWORD;

    if (_size < nwords)
    {
        _set.resize(nwords);
        _size = nwords;
        return;
    }

    int i,idx = nwords;
    for (i = 0,idx=nwords;idx < _size;idx++)
    {
        _set[i] |= _set[idx];
        if (i+1 < nwords)
            i++;
        else
            i = 0;
    }
    _set.resize(nwords);
    _size = nwords;
}

void OBBitVec::FromVecInt(vector<int> &v)
{
    vector<int>::iterator i;
    int max = 0;

    for (i = v.begin();i != v.end();i++)
        if (*i > max)
            max = *i;

    Resize(max/SETWORD);
    for (i = v.begin();i != v.end();i++)
        SetBitOn(*i);
}

void OBBitVec::FromString(string &line, int bits)
{
    size_t startpos = 0, endpos = 0;
    vector<string> tokens;

    Resize(bits);
    Clear();

    for (;;)
    {
        startpos = line.find_first_not_of(" \t\n",startpos);
        endpos   = line.find_first_of(" \t\n",startpos);

        if (endpos < line.size() && startpos <= line.size())
            tokens.push_back(line.substr(startpos,endpos-startpos));
        else
            break;

        startpos = endpos + 1;
    }

    for (unsigned int i = 0 ; i < tokens.size() ; i++ )
    {
        if ( tokens[i] == "[" )
            continue;
        else if ( tokens[i] == "]" )
            break;

        int bit = atoi(tokens[i].c_str());

        if (bit >= 0)
            SetBitOn(bit);
        else
          {
#ifdef HAVE_SSTREAM
            stringstream errorMsg;
#else
            strstream errorMsg;
#endif
            errorMsg << "Negative Bit: " << bit << endl;
            obErrorLog.ThrowError(__FUNCTION__, errorMsg.str(), obDebug);
          }
    }
}

void OBBitVec::ToVecInt(vector<int> &v)
{
    v.clear();
    v.reserve(CountBits());
    for (int i = NextBit(-1);i != -1;i = NextBit(i))
        v.push_back(i);
}

void OBBitVec::Clear()
{
    vector<int>::iterator i;
    for (i = _set.begin();i != _set.end();i++)
        *i = 0;
}

int OBBitVec::CountBits()
{
    int i,count=0;
    for (i = NextBit(-1);i != -1;i = NextBit(i))
        count++;

    return(count);
}

bool OBBitVec::IsEmpty()
{
    vector<int>::iterator i;
    for (i = _set.begin();i != _set.end();i++)
        if (*i)
            return(false);

    return(true);
}

double Tanimoto(OBBitVec &bv1,OBBitVec &bv2)
{
    OBBitVec bvtmp;
    double andbits,orbits;

    bvtmp = bv1 & bv2;
    andbits = (double)bvtmp.CountBits();
    bvtmp = bv1 | bv2;
    orbits  = (double)bvtmp.CountBits();

    return(andbits/orbits);
}

} // end namespace OpenBabel

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

Revision:	741
Committed:	Wed Nov 16 19:42:11 2005 UTC (19 years, 5 months ago) by tim
File size:	12099 byte(s)
Log Message:	adding openbabel
#	User	Rev	Content
1	tim	741	/**********************************************************************
2			bitvec.cpp - Fast and efficient bitstring class.
3
4			Copyright (C) 1998-2001 by OpenEye Scientific Software, Inc.
5			Some portions Copyright (C) 2001-2005 by Geoffrey R. Hutchison
6
7			This file is part of the Open Babel project.
8			For more information, see <http://openbabel.sourceforge.net/>
9
10			This program is free software; you can redistribute it and/or modify
11			it under the terms of the GNU General Public License as published by
12			the Free Software Foundation version 2 of the License.
13
14			This program is distributed in the hope that it will be useful,
15			but WITHOUT ANY WARRANTY; without even the implied warranty of
16			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17			GNU General Public License for more details.
18			***********************************************************************/
19
20			#include "bitvec.hpp"
21			#include "oberror.hpp"
22
23			using namespace std;
24
25			namespace OpenBabel
26			{
27
28			extern OBMessageHandler obErrorLog;
29
30			/*! \class OBBitVec
31			\brief Fast and efficient bitstring class
32
33			The OBBitVec class is a fast and efficient bitstring class that is
34			handy to use as a truth table. Truth tables are an easy way to store
35			whether a list of items has a particular propery. Instances of
36			OBBitVec can by dynamically resized, and have a number of overloaded
37			operators that make code simple and readable. The following examples
38			demonstrate uses of the OBBitVec class:
39			\code
40			OBBitVec bv1,bv2,bv3;
41			bv1.SetBitOn(5);
42			bv2.SetBitOff(200);
43			bv1 \|= bv2;
44			bv1 = bv1 & bv2;
45			if (bv1.Empty()) //Empty() returns true if no bits are set on
46			{
47			cout << "bv1 = " << bv1 << endl;
48			}
49
50			int bit;
51			for (bit = bv1.NextBit(0);bit != bv1.EndBit();bit = bv1.NextBit(bit))
52			{
53			cout << "the next bit turned on is " << bit << endl;
54			}
55			\endcode
56			*/
57
58			static int bitsoff[SETWORD] =
59			{
60			0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFC,0xFFFFFFF8,0xFFFFFFF0,0xFFFFFFE0,0xFFFFFFC0,
61			0xFFFFFF80,0xFFFFFF00,0xFFFFFE00,0xFFFFFC00,0xFFFFF800,0xFFFFF000,0xFFFFE000,
62			0xFFFFC000,0xFFFF8000,0xFFFF0000,0xFFFE0000,0xFFFC0000,0xFFF80000,0xFFF00000,
63			0xFFE00000,0xFFC00000,0xFF800000,0xFF000000,0xFE000000,0xFC000000,0xF8000000,
64			0xF0000000,0xE0000000,0xC0000000,0x80000000
65			};
66
67			#ifndef LowBit
68			#define LowBit(set, bit)\
69			{register int m;\
70			if (set != 0)\
71			{\
72			bit = 31;\
73			if (set != 0x80000000) {\
74			if ((m = (set & 0x0000ffff))) {set = m; bit -= 16;}\
75			if ((m = (set & 0x00ff00ff))) {set = m; bit -= 8;}\
76			if ((m = (set & 0x0f0f0f0f))) {set = m; bit -= 4;}\
77			if ((m = (set & 0x33333333))) {set = m; bit -= 2;}\
78			if ((m = (set & 0x55555555))) {set = m; bit -= 1;}}}\
79			else bit = -1;}
80			#endif
81
82			OBBitVec::OBBitVec(const OBBitVec &bv)
83			{
84			_size = 0;
85			(*this) = bv;
86			}
87
88			void OBBitVec::SetBitOn(int bit)
89			{
90			int word = bit/SETWORD;
91			bit = bit%SETWORD;
92
93			//if (word+1 >= GetSize()) Resize((word+1)*SETWORD);
94			if (word >= _size)
95			Resize((word+1)*SETWORD);
96			_set[word] \|= (1<<bit);
97			}
98
99			void OBBitVec::SetRangeOn(int lobit, int hibit)
100			{
101			int i;
102
103			if (lobit > hibit)
104			return;
105			else if (lobit == hibit)
106			SetBitOn(hibit);
107			else
108			{
109			int loword = lobit / SETWORD;
110			int hiword = hibit / SETWORD;
111			int lobitp = lobit % SETWORD;
112			int hibitp = hibit % SETWORD;
113
114			if (hiword >= _size)
115			Resize((hiword+1) * SETWORD);
116
117			if (loword == hiword)
118			{
119			for ( i = lobitp ; i <= hibitp ; i++ )
120			_set[loword] \|= (1<<i);
121			}
122			else
123			{
124			for ( i = lobitp ; i < SETWORD ; i++ )
125			_set[loword] \|= (1<<i);
126			for ( i = loword + 1 ; i < hiword ; i++ )
127			_set[i] = 0xFFFFFFFF;
128			for ( i = 0 ; i <= hibitp ; i++ )
129			_set[hiword] \|= (1<<i);
130			}
131			}
132			}
133
134			void OBBitVec::SetBitOff(int bit)
135			{
136			int word = bit/SETWORD;
137			bit = bit%SETWORD;
138			_set[word] &= (~(1 << bit));
139			}
140
141			void OBBitVec::SetRangeOff(int lobit, int hibit)
142			{
143			int i;
144
145			if (lobit > hibit)
146			return;
147			else if (lobit == hibit)
148			SetBitOff(hibit);
149			else
150			{
151			int loword = lobit / SETWORD;
152			int hiword = hibit / SETWORD;
153			int lobitp = lobit % SETWORD;
154			int hibitp = hibit % SETWORD;
155
156			if (hiword >= _size)
157			{
158			hiword = _size - 1;
159			hibitp = SETWORD - 1;
160			}
161
162			if (loword == hiword)
163			{
164			for ( i = lobitp ; i <= hibitp ; i++ )
165			_set[loword] &= (~(1<<i));
166			}
167			else
168			{
169			for ( i = lobitp ; i < SETWORD ; i++ )
170			_set[loword] &= (~(1<<i));
171			for ( i = loword + 1 ; i < hiword ; i++ )
172			_set[i] = 0x00000000;
173			for ( i = 0 ; i <= hibitp ; i++ )
174			_set[hiword] &= (~(1<<i));
175			}
176			}
177			}
178
179			int OBBitVec::NextBit(int last)
180			{
181			unsigned s;
182			register int bit,wrdcnt;
183			last++;
184
185			wrdcnt = last/SETWORD;
186
187			if (wrdcnt >= _size)
188			return(-1);
189
190			if (_set[wrdcnt] != 0)
191			{
192			s = (_set[wrdcnt]) & bitsoff[last - (wrdcnt*SETWORD)];
193			if (s)
194			{
195			LowBit(s,bit);
196			if (bit != -1)
197			return(bit + (wrdcnt*SETWORD));
198			}
199			}
200			wrdcnt++;
201
202			while(wrdcnt < _size)
203			{
204			if (this->_set[wrdcnt] != 0)
205			{
206			s = this->_set[wrdcnt];
207			LowBit(s, bit);
208
209			if (bit != -1)
210			return(bit+(wrdcnt*SETWORD));
211			}
212			wrdcnt++;
213			}
214
215			return(-1);
216			}
217
218			bool OBBitVec::Resize(int maxbits)
219			{
220			if(!maxbits)
221			return(false);
222			unsigned int maxword = maxbits/SETWORD;
223			if (maxbits%SETWORD)
224			maxword++;
225			if (maxword >= _set.size())
226			{
227			_set.resize(maxword);
228			_size = _set.size();
229			}
230
231			return(true);
232			}
233
234			OBBitVec &OBBitVec::operator= (const OBBitVec &bv)
235			{
236			if (_size != bv._size)
237			Resize(bv._size*SETWORD);
238
239			int i;
240			for ( i = 0 ; i < bv._size ; i++ )
241			_set[i] = bv._set[i];
242			for ( ; i < _size ; i++ )
243			_set[i] = 0;
244
245			return(*this);
246			}
247
248			OBBitVec &OBBitVec::operator&= ( OBBitVec &bv)
249			{
250			int i;
251			int min = (bv._size < _size) ? bv._size : _size;
252
253			for (i = 0;i < min;i++)
254			_set[i] &= bv._set[i];
255			for (;i < _size;i++)
256			_set[i] = 0;
257
258			return(*this);
259			}
260
261			OBBitVec &OBBitVec::operator\|= (OBBitVec &bv)
262			{
263			if (_size != bv._size)
264			{
265			if (_size < bv._size)
266			Resize(bv._size*SETWORD);
267			else
268			bv.Resize(_size*SETWORD);
269			}
270			for (int i = 0;i < _size;i++)
271			_set[i] \|= bv._set[i];
272
273			return(*this);
274			}
275
276			OBBitVec &OBBitVec::operator^= (OBBitVec &bv)
277			{
278			int i;
279			if (_size != bv._size)
280			{
281			if (_size < bv._size)
282			Resize(bv._size*SETWORD);
283			else
284			bv.Resize(_size*SETWORD);
285			}
286			for (i = 0;i < _size;i++)
287			_set[i] ^= bv._set[i];
288
289			return(*this);
290			}
291
292			OBBitVec &OBBitVec::operator-= (OBBitVec &bv)
293			{
294			if (GetSize() != bv._size)
295			obErrorLog.ThrowError(__FUNCTION__, "Subtracting sets of != size", obDebug);
296			else
297			{
298			OBBitVec tmp;
299			tmp = *this ^ bv;
300			*this &= tmp;
301			}
302			return(*this);
303			}
304
305			OBBitVec &OBBitVec::operator+= (OBBitVec &bv)
306			{
307			int old_size = _size;
308			Resize(_sizeSETWORD+bv._sizeSETWORD);
309			for (int i = 0;i < bv._size;i++)
310			_set[i+old_size] = bv._set[i];
311			return(*this);
312			}
313
314			OBBitVec operator\| (OBBitVec &bv1,OBBitVec &bv2)
315			{
316			OBBitVec bv;
317			bv = bv1;
318			bv \|= bv2;
319
320			return(bv);
321			}
322
323			OBBitVec operator& (OBBitVec &bv1, OBBitVec &bv2)
324			{
325			OBBitVec bv;
326			bv = bv1;
327			bv &= bv2;
328
329			return(bv);
330			}
331
332			OBBitVec operator^ (OBBitVec &bv1, OBBitVec &bv2)
333			{
334			OBBitVec bv;
335			bv = bv1;
336			bv ^= bv2;
337			return(bv);
338			}
339
340			bool operator== (const OBBitVec &bv1,const OBBitVec &bv2)
341			{
342			if (bv1._size != bv2._size)
343			return(false);
344
345			int i;
346			for (i = 0;i < bv1._size;i++)
347			if (bv1._set[i] != bv2._set[i])
348			return(false);
349
350			return(true);
351			}
352
353			OBBitVec operator- (OBBitVec &bv1,OBBitVec &bv2)
354			{
355			OBBitVec bv;
356			bv = bv1 ^ bv2;
357			bv &= bv1;
358			return(bv);
359			}
360
361			istream& operator>> ( istream &is, OBBitVec &bv )
362			{
363			size_t startpos = 0, endpos = 0;
364			vector<string> tokens;
365			string line;
366
367			getline(is,line);
368
369			for (;;)
370			{
371			startpos = line.find_first_not_of(" \t\n",startpos);
372			endpos = line.find_first_of(" \t\n",startpos);
373
374			if (endpos < line.size() && startpos <= line.size())
375			tokens.push_back(line.substr(startpos,endpos-startpos));
376			else
377			break;
378
379			startpos = endpos + 1;
380			}
381
382			for (unsigned int i = 0 ; i < tokens.size() ; i++ )
383			{
384			if ( tokens[i] == "[" )
385			continue;
386			else if ( tokens[i] == "]" )
387			break;
388
389			int bit = atoi(tokens[i].c_str());
390
391			if (bit >= 0)
392			bv.SetBitOn(bit);
393			else
394			{
395			#ifdef HAVE_SSTREAM
396			stringstream errorMsg;
397			#else
398			strstream errorMsg;
399			#endif
400			errorMsg << "Negative Bit: " << bit << endl;
401			obErrorLog.ThrowError(__FUNCTION__, errorMsg.str(), obDebug);
402			}
403			}
404
405			return is;
406			}
407
408			ostream& operator<< ( ostream &os, const OBBitVec& bv)
409			{
410			os << "[ " << flush;
411
412			int i,j;
413			for (i = 0;i < bv._size;i++)
414			for (j = 0;j < SETWORD;j++)
415			if (bv._set[i]>>(j%SETWORD)&1)
416			os << (j+(i*SETWORD)) << ' ' << flush;
417
418			os << "]" << flush;
419			return(os);
420			}
421
422			void OBBitVec::Fold(int nbits)
423			{
424			int nwords = nbits/SETWORD;
425
426			if (_size < nwords)
427			{
428			_set.resize(nwords);
429			_size = nwords;
430			return;
431			}
432
433			int i,idx = nwords;
434			for (i = 0,idx=nwords;idx < _size;idx++)
435			{
436			_set[i] \|= _set[idx];
437			if (i+1 < nwords)
438			i++;
439			else
440			i = 0;
441			}
442			_set.resize(nwords);
443			_size = nwords;
444			}
445
446			void OBBitVec::FromVecInt(vector<int> &v)
447			{
448			vector<int>::iterator i;
449			int max = 0;
450
451			for (i = v.begin();i != v.end();i++)
452			if (*i > max)
453			max = *i;
454
455			Resize(max/SETWORD);
456			for (i = v.begin();i != v.end();i++)
457			SetBitOn(*i);
458			}
459
460			void OBBitVec::FromString(string &line, int bits)
461			{
462			size_t startpos = 0, endpos = 0;
463			vector<string> tokens;
464
465			Resize(bits);
466			Clear();
467
468			for (;;)
469			{
470			startpos = line.find_first_not_of(" \t\n",startpos);
471			endpos = line.find_first_of(" \t\n",startpos);
472
473			if (endpos < line.size() && startpos <= line.size())
474			tokens.push_back(line.substr(startpos,endpos-startpos));
475			else
476			break;
477
478			startpos = endpos + 1;
479			}
480
481			for (unsigned int i = 0 ; i < tokens.size() ; i++ )
482			{
483			if ( tokens[i] == "[" )
484			continue;
485			else if ( tokens[i] == "]" )
486			break;
487
488			int bit = atoi(tokens[i].c_str());
489
490			if (bit >= 0)
491			SetBitOn(bit);
492			else
493			{
494			#ifdef HAVE_SSTREAM
495			stringstream errorMsg;
496			#else
497			strstream errorMsg;
498			#endif
499			errorMsg << "Negative Bit: " << bit << endl;
500			obErrorLog.ThrowError(__FUNCTION__, errorMsg.str(), obDebug);
501			}
502			}
503			}
504
505			void OBBitVec::ToVecInt(vector<int> &v)
506			{
507			v.clear();
508			v.reserve(CountBits());
509			for (int i = NextBit(-1);i != -1;i = NextBit(i))
510			v.push_back(i);
511			}
512
513			void OBBitVec::Clear()
514			{
515			vector<int>::iterator i;
516			for (i = _set.begin();i != _set.end();i++)
517			*i = 0;
518			}
519
520			int OBBitVec::CountBits()
521			{
522			int i,count=0;
523			for (i = NextBit(-1);i != -1;i = NextBit(i))
524			count++;
525
526			return(count);
527			}
528
529			bool OBBitVec::IsEmpty()
530			{
531			vector<int>::iterator i;
532			for (i = _set.begin();i != _set.end();i++)
533			if (*i)
534			return(false);
535
536			return(true);
537			}
538
539			double Tanimoto(OBBitVec &bv1,OBBitVec &bv2)
540			{
541			OBBitVec bvtmp;
542			double andbits,orbits;
543
544			bvtmp = bv1 & bv2;
545			andbits = (double)bvtmp.CountBits();
546			bvtmp = bv1 \| bv2;
547			orbits = (double)bvtmp.CountBits();
548
549			return(andbits/orbits);
550			}
551
552			} // end namespace OpenBabel
553
554			//! \file bitvec.cpp
555			//! \brief Fast and efficient bitstring class
556