From 017a7e74ba0757d00197643926536cd36ff88357 Mon Sep 17 00:00:00 2001 From: martinahansen Date: Wed, 19 Oct 2011 10:01:46 +0000 Subject: [PATCH] speed optimized interval_set and interval_unset in bitarray.rb - now evil fast git-svn-id: http://biopieces.googlecode.com/svn/trunk@1586 74ccb610-7750-0410-82ae-013aeee3265d --- code_ruby/lib/maasha/bitarray.rb | 64 ++++++++++++++++++-------- code_ruby/test/maasha/test_bitarray.rb | 25 +++++++--- 2 files changed, 62 insertions(+), 27 deletions(-) diff --git a/code_ruby/lib/maasha/bitarray.rb b/code_ruby/lib/maasha/bitarray.rb index 659a930..633c54a 100644 --- a/code_ruby/lib/maasha/bitarray.rb +++ b/code_ruby/lib/maasha/bitarray.rb @@ -155,43 +155,67 @@ class BitArray # 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 (#{stop} > #{self.size})" if stop > self.size - raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start + 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 - mask = (2 ** BitsInChar) - 1 # 11111111 + byte_start = start / BitsInChar + byte_stop = stop / BitsInChar bits_start = start % BitsInChar bits_stop = stop % BitsInChar - mask_start = mask >> bits_start - mask_stop = mask << (BitsInChar - bits_stop) - - self.byte_array[start / BitsInChar] |= mask_start if (stop / BitsInChar) != (start / BitsInChar) - self.byte_array[stop / BitsInChar] |= mask_stop + 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 - byte_start = (start + BitsInChar - bits_start) / BitsInChar - byte_stop = stop / BitsInChar + self.byte_array[byte_stop] |= (mask << (BitsInChar - bits_stop - 1)) - (byte_start ... byte_stop).each do |pos| - self.byte_array[pos] |= mask + if byte_start != byte_stop + self.byte_array[byte_start ... byte_stop] = mask + end end - stop - start + 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 (#{stop} > #{self.size})" if stop > self.size - raise BitArrayError, "interval stop < interval start (#{stop} < #{start})" if stop < start + 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 - (start ... stop).each do |pos| - self.bit_unset(pos) + 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 + stop - start + 1 end # Method to locate intervals of bits set to "on" in a bit array. diff --git a/code_ruby/test/maasha/test_bitarray.rb b/code_ruby/test/maasha/test_bitarray.rb index 6c410be..6ec38eb 100755 --- a/code_ruby/test/maasha/test_bitarray.rb +++ b/code_ruby/test/maasha/test_bitarray.rb @@ -163,27 +163,38 @@ class TestBitArray < Test::Unit::TestCase def test_interval_set_with_bad_interval_raises assert_raise(BitArrayError) { @ba.interval_set(-1, 4) } - assert_raise(BitArrayError) { @ba.interval_set(1, 14) } + assert_raise(BitArrayError) { @ba.interval_set(1, 10) } assert_raise(BitArrayError) { @ba.interval_set(4, 2) } end def test_interval_set_returns_correctly - @ba.interval_set(1, 9) - - assert_equal("0111111110", @ba.to_s) + @ba.interval_set(0, 0) + assert_equal("1000000000", @ba.to_s) + @ba.interval_set(9, 9) + assert_equal("1000000001", @ba.to_s) + @ba.interval_set(2, 7) + assert_equal("1011111101", @ba.to_s) + @ba.interval_set(1, 8) + assert_equal("1111111111", @ba.to_s) end def test_interval_unset_with_bad_interval_raises assert_raise(BitArrayError) { @ba.interval_unset(-1, 4) } - assert_raise(BitArrayError) { @ba.interval_unset(1, 14) } + assert_raise(BitArrayError) { @ba.interval_unset(1, 10) } assert_raise(BitArrayError) { @ba.interval_unset(4, 2) } end def test_interval_unset_returns_correctly ~@ba - @ba.interval_unset(1, 9) - assert_equal("1000000001", @ba.to_s) + @ba.interval_unset(0, 0) + assert_equal("0111111111", @ba.to_s) + @ba.interval_unset(9, 9) + assert_equal("0111111110", @ba.to_s) + @ba.interval_unset(2, 7) + assert_equal("0100000010", @ba.to_s) + @ba.interval_unset(1, 8) + assert_equal("0000000000", @ba.to_s) end def test_each_interval_returns_correctly -- 2.39.2