1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
// -*- c++ -*-
/// @file BitVector.h
/*
* Copyright 2001 Marko Mkel <msmakela@tcs.hut.fi>
*
* 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; either version 2
* of the License, or (at your option) any later version.
*
* 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.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifndef BITVECTOR_H_
# define BITVECTOR_H_
# ifdef __GNUC__
# pragma interface
# endif // __GNUC__
# include <limits.h>
# include <string.h>
/** Binary digit (bit) vector */
class BitVector
{
public:
/** machine word */
typedef unsigned long word_t;
/** Constructor
* @param size number of elements in the vector
*/
explicit BitVector (unsigned size = 0) :
m_size (0), m_allocated (1), m_bits (new word_t[1]) {
*m_bits = 0;
setSize (size);
}
/** Copy constructor */
explicit BitVector (const class BitVector& old) :
m_size (old.m_size), m_allocated (old.m_allocated), m_bits (0) {
memcpy (m_bits = new word_t[m_allocated], old.m_bits,
m_allocated * sizeof (word_t));
}
private:
/** Assignment operator */
class BitVector& operator= (const class BitVector& old);
public:
/** Destructor */
~BitVector () { delete[] m_bits; }
/** Equality comparison
* @param other other bit vector to compare this against
* @return true if the bit vectors are identical,
* treating missing bits as unset
*/
bool operator== (const class BitVector& other) const {
unsigned tsize = getNumWords (m_size), osize = getNumWords (other.m_size);
if (tsize < osize) {
if (memcmp (m_bits, other.m_bits, tsize * sizeof (word_t)))
return false;
for (register const word_t* bits = other.m_bits + osize;
bits-- > other.m_bits + tsize; )
if (*bits)
return false;
}
else {
if (memcmp (m_bits, other.m_bits, osize * sizeof (word_t)))
return false;
for (register const word_t* bits = m_bits + tsize;
bits-- > m_bits + osize; )
if (*bits)
return false;
}
return true;
}
/** Determine the number of words the specified amount of bits occupy */
static unsigned getNumWords (unsigned bits) {
const unsigned bitsPerWord = CHAR_BIT * sizeof (word_t);
return (bits + bitsPerWord - 1) / bitsPerWord;
}
/** Set the size of the vector
* @param size the new size of the vector
*/
void setSize (unsigned size) {
const unsigned numWords = getNumWords (size);
if (m_allocated < numWords) {
while (m_allocated < numWords)
m_allocated <<= 1;
word_t* bits = new word_t[m_allocated];
const unsigned init = getNumWords (m_size);
memcpy (bits, m_bits, init * sizeof *m_bits);
memset (bits + init, 0, (m_allocated - init) * sizeof *m_bits);
delete[] m_bits;
m_bits = bits;
}
m_size = size;
}
/** Determine the size of the vector
* @return the size of the vector
*/
unsigned getSize () const { return m_size; }
/** Read a binary digit
* @param i zero-based index of the element
* @return value of the ternary digit
*/
bool operator[] (unsigned i) const {
return i < m_size &&
m_bits[i / (CHAR_BIT * sizeof (word_t))] &
(word_t (1) << (i % (CHAR_BIT * sizeof (word_t))));
}
/** Set a binary digit
* @param i zero-based index of the element
*/
void assign_true (unsigned i) {
if (i >= m_size)
setSize (i + 1);
m_bits[i / (CHAR_BIT * sizeof (word_t))] |=
word_t (1) << (i % (CHAR_BIT * sizeof (word_t)));
}
/** Clear a binary digit
* @param i zero-based index of the element
*/
void assign_false (unsigned i) {
m_bits[i / (CHAR_BIT * sizeof (word_t))] &=
~(word_t (1) << (i % (CHAR_BIT * sizeof (word_t))));
}
/** Determine whether the whole vector is filled with zero bits
* @return 0 if all bits in the vector are clear;
* index of a nonzero entry + 1 otherwise
*/
unsigned nonzero () const {
if (!m_size)
return 0;
return findNext (0);
}
/** Find the next index at which there is a set bit
* @param i the starting index (counting forward)
* @return 0 if all following bits in the vector are clear;
* index of the next nonzero entry + 1 otherwise
*/
unsigned findNext (unsigned i) const {
if (i >= m_size)
return 0;
register const word_t* w = &m_bits[i / (CHAR_BIT * sizeof (word_t))];
register word_t bit = 1 << (i % (CHAR_BIT * sizeof (word_t)));
if (*w >= bit) {
// found in the same word
do
if (*w & bit)
return i + 1;
while (i++, bit <<= 1);
}
const word_t* const w_end = m_bits + getNumWords (m_size);
// search in the remaining words
while (++w < w_end) {
if (!*w) continue;
for (i = 1, bit = 1; !(*w & bit); bit <<= 1, i++);
return i + (w - m_bits) * CHAR_BIT * sizeof (word_t);
}
return 0;
}
private:
/** Number of elements in the vector */
unsigned m_size;
/** Size of the allocated vector in words */
unsigned m_allocated;
/** The vector */
word_t* m_bits;
};
#endif // BITVECTOR_H_
|
