From 017a7e74ba0757d00197643926536cd36ff88357 Mon Sep 17 00:00:00 2001
From: martinahansen <martinahansen@74ccb610-7750-0410-82ae-013aeee3265d>
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.5