1 # Copyright (C) 2007-2011 Martin A. Hansen.
3 # This program is free software; you can redistribute it and/or
4 # modify it under the terms of the GNU General Public License
5 # as published by the Free Software Foundation; either version 2
6 # of the License, or (at your option) any later version.
8 # This program is distributed in the hope that it will be useful,
9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 # GNU General Public License for more details.
13 # You should have received a copy of the GNU General Public License
14 # along with this program; if not, write to the Free Software
15 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 # http://www.gnu.org/copyleft/gpl.html
19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
21 # This software is part of the Biopieces framework (www.biopieces.org).
23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
30 # Error class for all exceptions to do with BitArray.
31 class BitArrayError < StandardError; end
33 # Class containing methods for creating and manipulating a bit array.
35 attr_accessor :byte_array
38 # Method to initialize a new bit array of a given size in bits.
41 @byte_array = init_byte_array
42 @count_array = init_count_array
45 # Method that sets all bits in the bit array.
47 self.byte_array.fill!(~0)
52 # Method that unsets all bits in the bit array.
54 self.byte_array.fill!(0)
59 # Method to set a bit to 1 at a given position in the bit array.
61 raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
62 raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
64 @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] | bit_pos(pos)
67 # Method to set a bit to 0 at a given position in the bit array.
69 raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
70 raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
75 @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] & mask
78 # Method to check if a bit at a given position in the bit array is set.
80 raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
81 raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
83 (@byte_array[byte_pos(pos)] & bit_pos(pos)) != 0
86 # Method that returns the number of bits set "on" in a bit array.
88 index = NArray.sint(*self.byte_array.shape)
89 index[] = self.byte_array
90 NArray.to_na(@count_array)[index].sum
93 # Method that returns the number of bits set "off" in a bit array.
98 # Method to run bitwise AND (&) on two bit arrays and return the
99 # result in the first bit array. Bits are copied if they exists in BOTH operands.
100 # 00111100 & 00001101 = 00001100
102 raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
104 self.byte_array = self.byte_array & ba.byte_array
109 # Method to run bitwise OR (|) on two bit arrays and return the
110 # result in the first bit array. Bits are copied if they exists in EITHER operands.
111 # 00111100 | 00001101 = 00111101
113 raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
115 self.byte_array = self.byte_array | ba.byte_array
120 # Method to run bitwise XOR (^) on two bit arrays and return the
121 # result in the first bit array. Bits are copied if they exists in ONE BUT NOT BOTH operands.
122 # 00111100 ^ 00001101 = 00110001
124 raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
126 self.byte_array = self.byte_array ^ ba.byte_array
131 # Method to flip all bits in a bit array. All set bits become unset and visa versa.
133 self.byte_array = ~(self.byte_array)
138 # Method to convert a bit array to a string.
142 (0 ... @size).each do |pos|
153 alias :to_string :to_s
155 # Method to set the bits to "on" in an interval in a bit array.
156 # Returns the number of bits set.
157 def interval_set(start, stop)
158 raise BitArrayError, "interval start < 0 (#{start} < 0)" if start < 0
159 raise BitArrayError, "interval stop > bit array size - 1 (#{stop} > #{self.size - 1})" if stop > self.size - 1
160 raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start
162 byte_start = start / BitsInChar
163 byte_stop = stop / BitsInChar
165 bits_start = start % BitsInChar
166 bits_stop = stop % BitsInChar
168 mask = (2 ** BitsInChar) - 1 # 11111111
170 if byte_start == byte_stop
171 self.byte_array[byte_start] |= ((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
174 self.byte_array[byte_start] |= (mask >> bits_start)
178 self.byte_array[byte_stop] |= (mask << (BitsInChar - bits_stop - 1))
180 if byte_start != byte_stop
181 self.byte_array[byte_start ... byte_stop] = mask
188 # Method to set the bits to "off" in an interval in a bit array.
189 # Returns the number of bits unset.
190 def interval_unset(start, stop)
191 raise BitArrayError, "interval start < 0 (#{start} < 0)" if start < 0
192 raise BitArrayError, "interval stop > bit array size - 1 (#{stop} > #{self.size - 1})" if stop > self.size - 1
193 raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start
195 byte_start = start / BitsInChar
196 byte_stop = stop / BitsInChar
198 bits_start = start % BitsInChar
199 bits_stop = stop % BitsInChar
201 mask = (2 ** BitsInChar) - 1 # 11111111
203 if byte_start == byte_stop
204 self.byte_array[byte_start] &= ~((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
207 self.byte_array[byte_start] &= ~(mask >> bits_start)
211 self.byte_array[byte_stop] &= ~(mask << (BitsInChar - bits_stop - 1))
213 if byte_start != byte_stop
214 self.byte_array[byte_start ... byte_stop] = ~mask
221 # Method to locate intervals of bits set to "on" in a bit array.
222 # BitArray.each_interval -> Array
223 # BitArray.each_interval { |start, stop| } -> Fixnum
229 while bit_start < self.size
230 bit_start += 1 while bit_start < self.size and not self.bit_set?(bit_start)
232 if bit_start < self.size
234 bit_stop += 1 while bit_stop < self.size and self.bit_set?(bit_stop)
237 yield bit_start, bit_stop - 1
239 intervals << [bit_start, bit_stop - 1]
242 bit_start = bit_stop + 1
246 return intervals unless block_given?
251 # Method to initialize the byte array (string) that constitutes the bit array.
253 raise BitArrayError, "Size must be an integer, not #{@size}" unless @size.is_a? Fixnum
254 raise BitArrayError, "Size must be positive, not #{@size}" unless @size > 0
256 NArray.byte(((@size - 1) / BitsInChar) + 1)
259 # Method that returns an array where the element index value is
260 # the number of bits set for that index value.
264 (0 ... (2 ** BitsInChar)).each do |i|
265 count_array << bits_in_char(i)
271 # Method that returns the number of set bits in a char.
272 def bits_in_char(char)
275 (0 ... BitsInChar).each do |pos|
276 bits += 1 if ((char & bit_pos(pos)) != 0)
282 # Method that returns the byte position in the byte array for a given bit position.
287 # Method that returns the bit position in a byte.
289 1 << (BitsInChar - 1 - (pos % BitsInChar))