# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
require 'narray'
+require 'pp'
BitsInChar = 8
# Class containing methods for creating and manipulating a bit array.
class BitArray
attr_accessor :byte_array
- attr_reader :size
+ attr_reader :size
# Method to initialize a new bit array of a given size in bits.
def initialize(size)
@count_array = init_count_array
end
+ # Method that sets all bits in the bit array.
+ def fill!
+ self.byte_array.fill!(~0)
+
+ self
+ end
+
+ # Method that unsets all bits in the bit array.
+ def clear!
+ self.byte_array.fill!(0)
+
+ self
+ end
+
# Method to set a bit to 1 at a given position in the bit array.
def bit_set(pos)
- raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
- raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size}" unless (0 ... @size ).include? pos
+ raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
+ raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
@byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] | bit_pos(pos)
end
+ # Method to set a bit to 0 at a given position in the bit array.
+ def bit_unset(pos)
+ raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
+ raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
+
+ mask = bit_pos(pos)
+ mask = ~mask
+
+ @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] & mask
+ end
+
# Method to check if a bit at a given position in the bit array is set.
def bit_set?(pos)
- raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
- raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size}" unless (0 ... @size ).include? pos
+ raise BitArrayError, "Position #{pos} must be an integer." unless pos.is_a? Fixnum
+ raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size - 1}" unless (0 ... @size ).include? pos
- (@byte_array[byte_pos(pos)].ord & bit_pos(pos)) != 0
+ (@byte_array[byte_pos(pos)] & bit_pos(pos)) != 0
end
# Method that returns the number of bits set "on" in a bit array.
- def bits_on
- bits_on = 0
-
- (0 ... self.byte_array.size).each do |byte|
- bits_on += @count_array[self.byte_array[byte].ord]
- end
-
- bits_on
+ def bits_on
+ index = NArray.sint(*self.byte_array.shape)
+ index[] = self.byte_array
+ NArray.to_na(@count_array)[index].sum
end
# Method that returns the number of bits set "off" in a bit array.
end
# Method to run bitwise AND (&) on two bit arrays and return the
- # result in a new bit array. Bits are copied if they exists in BOTH operands.
+ # result in the first bit array. Bits are copied if they exists in BOTH operands.
# 00111100 & 00001101 = 00001100
def &(ba)
raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
- result = BitArray.new(ba.size)
-
- result.byte_array = self.byte_array & ba.byte_array
+ self.byte_array = self.byte_array & ba.byte_array
- result
+ self
end
# Method to run bitwise OR (|) on two bit arrays and return the
- # result in a new bit array. Bits are copied if they exists in EITHER operands.
+ # result in the first bit array. Bits are copied if they exists in EITHER operands.
# 00111100 | 00001101 = 00111101
def |(ba)
raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
- result = BitArray.new(ba.size)
-
- result.byte_array = self.byte_array | ba.byte_array
+ self.byte_array = self.byte_array | ba.byte_array
- result
+ self
end
# Method to run bitwise XOR (^) on two bit arrays and return the
- # result in a new bit array. Bits are copied if they exists in ONE BUT NOT BOTH operands.
+ # result in the first bit array. Bits are copied if they exists in ONE BUT NOT BOTH operands.
# 00111100 ^ 00001101 = 00110001
def ^(ba)
raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
- result = BitArray.new(ba.size)
+ self.byte_array = self.byte_array ^ ba.byte_array
- result.byte_array = self.byte_array ^ ba.byte_array
+ self
+ end
+
+ # Method to flip all bits in a bit array. All set bits become unset and visa versa.
+ def ~
+ self.byte_array = ~(self.byte_array)
- result
+ self
end
# Method to convert a bit array to a string.
alias :to_string :to_s
+ # Method to set the bits to "on" in an interval in a bit array.
+ # Returns the number of bits set.
+ def interval_set(start, stop)
+ raise BitArrayError, "interval start < 0 (#{start} < 0)" if start < 0
+ raise BitArrayError, "interval stop > bit array size - 1 (#{stop} > #{self.size - 1})" if stop > self.size - 1
+ raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start
+
+ byte_start = start / BitsInChar
+ byte_stop = stop / BitsInChar
+
+ bits_start = start % BitsInChar
+ bits_stop = stop % BitsInChar
+
+ mask = (2 ** BitsInChar) - 1 # 11111111
+
+ if byte_start == byte_stop
+ self.byte_array[byte_start] |= ((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
+ else
+ if bits_start != 0
+ self.byte_array[byte_start] |= (mask >> bits_start)
+ byte_start += 1
+ end
+
+ self.byte_array[byte_stop] |= (mask << (BitsInChar - bits_stop - 1))
+
+ if byte_start != byte_stop
+ self.byte_array[byte_start ... byte_stop] = mask
+ end
+ end
+
+ stop - start + 1
+ end
+
+ # Method to set the bits to "off" in an interval in a bit array.
+ # Returns the number of bits unset.
+ def interval_unset(start, stop)
+ raise BitArrayError, "interval start < 0 (#{start} < 0)" if start < 0
+ raise BitArrayError, "interval stop > bit array size - 1 (#{stop} > #{self.size - 1})" if stop > self.size - 1
+ raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start
+
+ byte_start = start / BitsInChar
+ byte_stop = stop / BitsInChar
+
+ bits_start = start % BitsInChar
+ bits_stop = stop % BitsInChar
+
+ mask = (2 ** BitsInChar) - 1 # 11111111
+
+ if byte_start == byte_stop
+ self.byte_array[byte_start] &= ~((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
+ else
+ if bits_start != 0
+ self.byte_array[byte_start] &= ~(mask >> bits_start)
+ byte_start += 1
+ end
+
+ self.byte_array[byte_stop] &= ~(mask << (BitsInChar - bits_stop - 1))
+
+ if byte_start != byte_stop
+ self.byte_array[byte_start ... byte_stop] = ~mask
+ end
+ end
+
+ stop - start + 1
+ end
+
+ # Method to locate intervals of bits set to "on" in a bit array.
+ # BitArray.each_interval -> Array
+ # BitArray.each_interval { |start, stop| } -> Fixnum
+ def each_interval
+ intervals = []
+ bit_start = 0
+ bit_stop = 0
+
+ while bit_start < self.size
+ bit_start += 1 while bit_start < self.size and not self.bit_set?(bit_start)
+
+ if bit_start < self.size
+ bit_stop = bit_start
+ bit_stop += 1 while bit_stop < self.size and self.bit_set?(bit_stop)
+
+ if block_given?
+ yield bit_start, bit_stop - 1
+ else
+ intervals << [bit_start, bit_stop - 1]
+ end
+
+ bit_start = bit_stop + 1
+ end
+ end
+
+ return intervals unless block_given?
+ end
+
private
# Method to initialize the byte array (string) that constitutes the bit array.
raise BitArrayError, "Size must be an integer, not #{@size}" unless @size.is_a? Fixnum
raise BitArrayError, "Size must be positive, not #{@size}" unless @size > 0
- byte_array = ""
- byte_array << 0.chr * (((@size - 1) / BitsInChar) + 1)
-
- byte_array
-
NArray.byte(((@size - 1) / BitsInChar) + 1)
end
projects / biopieces.git / blobdiff