code_ruby/lib/maasha/bitarray.rb

   1 # Copyright (C) 2007-2011 Martin A. Hansen.
   2
   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.
   7
   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.
  12
  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.
  16
  17 # http://www.gnu.org/copyleft/gpl.html
  18
  19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  20
  21 # This software is part of the Biopieces framework (www.biopieces.org).
  22
  23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  24
  25 require 'narray'
  26 require 'pp'
  27
  28 BitsInChar = 8
  29
  30 # Error class for all exceptions to do with BitArray.
  31 class BitArrayError < StandardError; end
  32
  33 # Class containing methods for creating and manipulating a bit array.
  34 class BitArray
  35   attr_accessor :byte_array
  36   attr_reader   :size
  37
  38   # Method to initialize a new bit array of a given size in bits.
  39   def initialize(size)
  40     @size        = size
  41     @byte_array  = init_byte_array
  42     @count_array = init_count_array
  43   end
  44
  45   # Method that sets all bits in the bit array.
  46   def fill!
  47     self.byte_array.fill!(~0)
  48
  49     self
  50   end
  51
  52   # Method that unsets all bits in the bit array.
  53   def clear!
  54     self.byte_array.fill!(0)
  55
  56     self
  57   end
  58
  59   # Method to set a bit to 1 at a given position in the bit array.
  60   def bit_set(pos)
  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
  63
  64     @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] | bit_pos(pos)
  65   end
  66
  67   # Method to set a bit to 0 at a given position in the bit array.
  68   def bit_unset(pos)
  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
  71
  72     mask = bit_pos(pos)
  73     mask = ~mask
  74
  75     @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] & mask
  76   end
  77
  78   # Method to check if a bit at a given position in the bit array is set.
  79   def bit_set?(pos)
  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
  82
  83     (@byte_array[byte_pos(pos)] & bit_pos(pos)) != 0
  84   end
  85
  86   # Method that returns the number of bits set "on" in a bit array.
  87   def bits_on
  88     index = NArray.sint(*self.byte_array.shape)
  89     index[] = self.byte_array
  90     NArray.to_na(@count_array)[index].sum
  91   end
  92
  93   # Method that returns the number of bits set "off" in a bit array.
  94   def bits_off
  95     @size - bits_on
  96   end
  97
  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
 101   def &(ba)
 102     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 103
 104     self.byte_array = self.byte_array & ba.byte_array
 105
 106     self
 107   end
 108
 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
 112   def |(ba)
 113     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 114
 115     self.byte_array = self.byte_array | ba.byte_array
 116
 117     self
 118   end
 119
 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
 123   def ^(ba)
 124     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 125
 126     self.byte_array = self.byte_array ^ ba.byte_array
 127
 128     self
 129   end
 130
 131   # Method to flip all bits in a bit array. All set bits become unset and visa versa.
 132   def ~
 133     self.byte_array = ~(self.byte_array)
 134
 135     self
 136   end
 137
 138   # Method to convert a bit array to a string.
 139   def to_s
 140     string = ""
 141
 142     (0 ... @size).each do |pos|
 143       if self.bit_set? pos
 144         string << "1"
 145       else
 146         string << "0"
 147       end
 148     end
 149
 150     string
 151   end
 152
 153   alias :to_string :to_s
 154
 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
 161
 162     byte_start = start / BitsInChar
 163     byte_stop  = stop  / BitsInChar
 164
 165     bits_start = start % BitsInChar
 166     bits_stop  = stop  % BitsInChar
 167
 168     mask = (2 ** BitsInChar) - 1  # 11111111
 169
 170     if byte_start == byte_stop
 171       self.byte_array[byte_start] |= ((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
 172     else
 173       if bits_start != 0
 174         self.byte_array[byte_start] |= (mask >> bits_start)
 175         byte_start += 1
 176       end
 177
 178       self.byte_array[byte_stop] |= (mask << (BitsInChar - bits_stop - 1))
 179
 180       if byte_start != byte_stop
 181         self.byte_array[byte_start ... byte_stop] = mask
 182       end
 183     end
 184
 185     stop - start + 1
 186   end
 187
 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
 194
 195     byte_start = start / BitsInChar
 196     byte_stop  = stop  / BitsInChar
 197
 198     bits_start = start % BitsInChar
 199     bits_stop  = stop  % BitsInChar
 200
 201     mask = (2 ** BitsInChar) - 1  # 11111111
 202
 203     if byte_start == byte_stop
 204       self.byte_array[byte_start] &= ~((mask >> bits_start) & (mask << (BitsInChar - bits_stop - 1)))
 205     else
 206       if bits_start != 0
 207         self.byte_array[byte_start] &= ~(mask >> bits_start)
 208         byte_start += 1
 209       end
 210
 211       self.byte_array[byte_stop] &= ~(mask << (BitsInChar - bits_stop - 1))
 212
 213       if byte_start != byte_stop
 214         self.byte_array[byte_start ... byte_stop] = ~mask
 215       end
 216     end
 217
 218     stop - start + 1
 219   end
 220
 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
 224   def each_interval
 225     intervals = []
 226     bit_start = 0
 227     bit_stop  = 0
 228
 229     while bit_start < self.size
 230       bit_start += 1 while bit_start < self.size and not self.bit_set?(bit_start)
 231
 232       if bit_start < self.size
 233         bit_stop = bit_start
 234         bit_stop  += 1 while bit_stop < self.size and self.bit_set?(bit_stop)
 235
 236         if block_given?
 237           yield bit_start, bit_stop - 1
 238         else
 239           intervals << [bit_start, bit_stop - 1]
 240         end
 241
 242         bit_start = bit_stop + 1
 243       end
 244     end
 245
 246     return intervals unless block_given?
 247   end
 248
 249   private
 250
 251   # Method to initialize the byte array (string) that constitutes the bit array.
 252   def init_byte_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
 255
 256     NArray.byte(((@size - 1) / BitsInChar) + 1)
 257   end
 258
 259   # Method that returns an array where the element index value is
 260   # the number of bits set for that index value.
 261   def init_count_array
 262     count_array = []
 263
 264     (0 ... (2 ** BitsInChar)).each do |i|
 265       count_array << bits_in_char(i)
 266     end
 267
 268     count_array
 269   end
 270
 271   # Method that returns the number of set bits in a char.
 272   def bits_in_char(char)
 273     bits = 0
 274
 275     (0 ... BitsInChar).each do |pos|
 276       bits += 1 if ((char & bit_pos(pos)) != 0)
 277     end
 278
 279     bits
 280   end
 281
 282   # Method that returns the byte position in the byte array for a given bit position.
 283   def byte_pos(pos)
 284     pos / BitsInChar
 285   end
 286
 287   # Method that returns the bit position in a byte.
 288   def bit_pos(pos)
 289     1 << (BitsInChar - 1 - (pos % BitsInChar))
 290   end
 291 end
 292