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
  27 BitsInChar = 8
  28
  29 # Error class for all exceptions to do with BitArray.
  30 class BitArrayError < StandardError; end
  31
  32 # Class containing methods for creating and manipulating a bit array.
  33 class BitArray
  34   attr_accessor :byte_array
  35   attr_reader   :size
  36
  37   # Method to initialize a new bit array of a given size in bits.
  38   def initialize(size)
  39     @size        = size
  40     @byte_array  = init_byte_array
  41     @count_array = init_count_array
  42   end
  43
  44   # Method that sets all bits in the bit array.
  45   def fill!
  46     self.byte_array.fill!(~0)
  47
  48     self
  49   end
  50
  51   # Method that unsets all bits in the bit array.
  52   def clear!
  53     self.byte_array.fill!(0)
  54
  55     self
  56   end
  57
  58   # Method to set a bit to 1 at a given position in the bit array.
  59   def bit_set(pos)
  60     raise BitArrayError, "Position #{pos} must be an integer."              unless pos.is_a? Fixnum
  61     raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size}" unless (0 ... @size ).include? pos
  62
  63     @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] | bit_pos(pos)
  64   end
  65
  66   # Method to set a bit to 0 at a given position in the bit array.
  67   def bit_unset(pos)
  68     raise BitArrayError, "Position #{pos} must be an integer."              unless pos.is_a? Fixnum
  69     raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size}" unless (0 ... @size ).include? pos
  70
  71     mask = bit_pos(pos)
  72     mask = ~mask
  73
  74     @byte_array[byte_pos(pos)] = @byte_array[byte_pos(pos)] & mask
  75   end
  76
  77   # Method to check if a bit at a given position in the bit array is set.
  78   def bit_set?(pos)
  79     raise BitArrayError, "Position #{pos} must be an integer."              unless pos.is_a? Fixnum
  80     raise BitArrayError, "Position #{pos} outside of range: 0 ... #{@size}" unless (0 ... @size ).include? pos
  81
  82     (@byte_array[byte_pos(pos)] & bit_pos(pos)) != 0
  83   end
  84
  85   # Method that returns the number of bits set "on" in a bit array.
  86   def bits_on
  87     bits_on = 0
  88
  89     self.byte_array.each do |byte|
  90       bits_on += @count_array[byte]
  91     end
  92
  93     bits_on
  94   end
  95
  96   # Method that returns the number of bits set "off" in a bit array.
  97   def bits_off
  98     @size - bits_on
  99   end
 100
 101   # Method to run bitwise AND (&) on two bit arrays and return the
 102   # result in the first bit array. Bits are copied if they exists in BOTH operands.
 103   # 00111100 & 00001101 = 00001100
 104   def &(ba)
 105     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 106
 107     self.byte_array = self.byte_array & ba.byte_array
 108
 109     self
 110   end
 111
 112   # Method to run bitwise OR (|) on two bit arrays and return the
 113   # result in the first bit array. Bits are copied if they exists in EITHER operands.
 114   # 00111100 | 00001101 = 00111101
 115   def |(ba)
 116     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 117
 118     self.byte_array = self.byte_array | ba.byte_array
 119
 120     self
 121   end
 122
 123   # Method to run bitwise XOR (^) on two bit arrays and return the
 124   # result in the first bit array. Bits are copied if they exists in ONE BUT NOT BOTH operands.
 125   # 00111100 ^ 00001101 = 00110001
 126   def ^(ba)
 127     raise BitArrayError, "uneven size of bit arrays: #{self.size} != #{ba.size}" if self.size != ba.size
 128
 129     self.byte_array = self.byte_array ^ ba.byte_array
 130
 131     self
 132   end
 133
 134   # Method to flip all bits in a bit array. All set bits become unset and visa versa.
 135   def ~
 136     self.byte_array = ~(self.byte_array)
 137
 138     self
 139   end
 140
 141   # Method to convert a bit array to a string.
 142   def to_s
 143     string = ""
 144
 145     (0 ... @size).each do |pos|
 146       if self.bit_set? pos
 147         string << "1"
 148       else
 149         string << "0"
 150       end
 151     end
 152
 153     string
 154   end
 155
 156   alias :to_string :to_s
 157
 158   private
 159
 160   # Method to initialize the byte array (string) that constitutes the bit array.
 161   def init_byte_array
 162     raise BitArrayError, "Size must be an integer, not #{@size}" unless @size.is_a? Fixnum
 163     raise BitArrayError, "Size must be positive, not #{@size}"   unless @size > 0
 164
 165     NArray.byte(((@size - 1) / BitsInChar) + 1)
 166   end
 167
 168   # Method that returns an array where the element index value is
 169   # the number of bits set for that index value.
 170   def init_count_array
 171     count_array = []
 172
 173     (0 ... (2 ** BitsInChar)).each do |i|
 174       count_array << bits_in_char(i)
 175     end
 176
 177     count_array
 178   end
 179
 180   # Method that returns the number of set bits in a char.
 181   def bits_in_char(char)
 182     bits = 0
 183
 184     (0 ... BitsInChar).each do |pos|
 185       bits += 1 if ((char & bit_pos(pos)) != 0)
 186     end
 187
 188     bits
 189   end
 190
 191   # Method that returns the byte position in the byte array for a given bit position.
 192   def byte_pos(pos)
 193     pos / BitsInChar
 194   end
 195
 196   # Method that returns the bit position in a byte.
 197   def bit_pos(pos)
 198     1 << (BitsInChar - 1 - (pos % BitsInChar))
 199   end
 200 end
 201