=begin
$Id: unittest_bitvector.rb,v 1.5 2003/01/23 17:42:40 knu Exp $
Unit test for XX.
Part of Yoda (Yet another jOb Distributing And queueing system).
(c) Copyright 2000, Robert Feldt, feldt@ce.chalmers.se
This software is distributed under a license. See LICENSE in the Yoda main
directory for more information.
=end
require 'test/unit'
require 'test/unit/ui/console/testrunner'
require 'bitvector'
class Test_BitVector < Test::Unit::TestCase
def setup
@be = BitVector.new(4) # 0000
@bf = BitVector.new(4) # 1111
@bf.flip
@b1 = BitVector.new(4) # 1100
@b1.set(2,1)
@b1.set(3,1)
@b2 = BitVector.new(4) # 1010
@b2.set(1,1)
@b2.set(3,1)
@bl = BitVector.new(7) # 1001100
@bl.set(6,1)
@bl.set(3,1)
@bl.set(2,1)
end
def assert_is_bitvector(obj)
assert_equal(BitVector, obj.class)
end
def test_01_initialize_and_length
assert_is_bitvector(@b1)
assert_equal(4, @b1.length)
assert_equal(4, @b2.length)
assert_equal(7, @bl.length)
assert_equal(98765, BitVector.new(98765).length)
end
def test_02_clone_and_equal
b1c = @b1.clone
assert_is_bitvector(b1c)
assert(@b1.id != b1c.id)
assert(@b1.equal?(b1c))
assert(@b1 == b1c)
assert(!@b2.equal?(b1c))
assert(@b2 != b1c)
end
def test_03_concat_and_inspect
bc = @b1.concat(@b2)
assert_is_bitvector(bc)
assert_equal(@b1.length+@b2.length, bc.length)
assert_equal(@b1.inspect+@b2.inspect, bc.inspect)
assert((bc.id != @b1.id) && (bc.id != @b2.id))
assert_raises(TypeError) {@b1.concat([])}
end
def test_04_reverse
assert_equal(@be, @be.reverse)
assert_equal(@bf, @bf.reverse)
assert_equal(@b1, @b1.reverse.reverse)
assert_equal(@b2, @b2.reverse.reverse)
assert_equal("0011", @b1.reverse.inspect)
assert_equal("0101", @b2.reverse.inspect)
assert_equal("0011001", @bl.reverse.inspect)
end
def test_05_empty
assert(@be.empty?)
assert(!(@bf.empty?))
assert((@bf.empty).empty?)
# Interval emptying
b = BitVector.new(10)
b.fill
b.empty(7)
assert_equal("1101111111", b.inspect)
b.empty(4,0)
assert_equal("1101111111", b.inspect)
b.empty(4,1)
assert_equal("1101101111", b.inspect)
b.empty(0...2)
assert_equal("1101101100", b.inspect)
b.empty(-7..-3)
assert_equal("1100000100", b.inspect)
assert_raises(RangeError) {b.empty(-18..-5)}
end
def test_06_fill_and_full
assert(!(@be.full?))
assert(@bf.full?)
assert((@be.fill).full?)
# Interval fills
b = BitVector.new(10)
b.fill(5)
assert_equal("0000100000", b.inspect)
b.fill(4,0)
assert_equal("0000100000", b.inspect)
b.fill(4,2)
assert_equal("0000110000", b.inspect)
b.fill(1..2)
assert_equal("0000110110", b.inspect)
b.fill(-7..-3)
assert_equal("0011111110", b.inspect)
assert_raises(RangeError) {b.fill(-18..-5)}
end
def test_07_primes
# Test primes < 20
assert_equal("10100010100010101100", BitVector.new(20).primes.inspect)
end
def test_08_equal
assert(@b1.equal?(@b1))
assert(@b1 == @b1)
assert(!@b2.equal?(@b1))
assert(@b2 != @b1)
assert(@bl != @b1)
assert(@b1 != @bl)
end
def test_09_compare
assert_equal(1, @b1.compare(@b2)) # -4 > -6
assert_equal(-1, @b2.compare(@b1)) # -6 < -4
assert_equal(0, @b1 <=> @b1)
assert_equal(1, @b1 <=> @b2)
assert_equal(-1, @b2 <=> @b1)
assert_equal(1, @be <=> @bf) # 0 > -1
end
def test_10_lexicompare
assert_equal(1, @b1.lexicompare(@b2)) # 12 > 10
assert_equal(-1, @b2.lexicompare(@b1)) # 10 < 12
assert_equal(-1, @be.lexicompare(@bf)) # 0 < 15
end
def test_11_to_bin_str
assert_equal("1100", @b1.to_bin_str)
assert_equal("C", @b1.to_hex_str)
assert_equal("-4", @b1.to_dec_str)
assert_equal("2,3", @b1.to_enum_str)
assert_equal("1001100", @bl.to_bin_str)
assert_equal("4C", @bl.to_hex_str)
assert_equal("2,3,6", @bl.to_enum_str)
end
def test_12_on_and_off
assert_equal("1101", @b1.on(0).inspect)
assert_equal("1111", @b1.on(1).inspect)
assert_equal("1011", @b1.off(2).inspect)
assert_equal("0011", @b1.off(3).inspect)
assert_equal("1011", @b1.on(3).inspect)
assert_equal("1111", @b1.on(2).inspect)
assert_equal("1101", @b1.off(1).inspect)
assert_equal("1100", @b1.off(0).inspect)
end
def test_13_bit_flip
assert_equal(1, @b1.bit_flip(0))
assert_equal("1101", @b1.inspect)
assert_equal(0, @b1.bit_flip(2))
assert_equal("1001", @b1.inspect)
assert_equal(0, @b1.bit_flip(12))
end
def test_14_bit_and_test
assert_equal(1, @bl.bit(6))
assert_equal(0, @bl.bit(0))
assert_equal(true, @bl.test?(6))
assert_equal(false, @bl.test?(0))
end
def test_15_set
@b1.set(0,1)
assert_equal("1101", @b1.inspect)
@b2.set(3,0)
assert_equal("0010", @b2.inspect)
@bl.set(0,1)
assert_equal("1001101", @bl.inspect)
@bl.set(6,0)
assert_equal("0001101", @bl.inspect)
assert_raises(IndexError) {@bl.set(7,0)}
assert_raises(IndexError) {@bl.set(-1,0)}
end
def test_16_union
u1 = @b1.union(@b2)
assert_is_bitvector(u1)
assert_equal("1110", u1.inspect)
u2 = @b1|@b2
assert_is_bitvector(u2)
assert_equal("1110", u2.inspect)
assert_raises(ArgumentError) {@b1|@bl}
end
def test_17_intersection
i1 = @b1.intersection(@b2)
assert_is_bitvector(i1)
assert_equal("1000", i1.inspect)
i2 = @b1&@b2
assert_is_bitvector(i2)
assert_equal("1000", i2.inspect)
assert_raises(ArgumentError) {@b1&@bl}
end
def test_18_difference
d1 = @b1.difference(@b2)
assert_is_bitvector(d1)
assert_equal("0100", d1.inspect)
assert_raises(ArgumentError) {@b1.difference(@bl)}
d1 = @b2.difference(@b1)
assert_is_bitvector(d1)
assert_equal("0010", d1.inspect)
assert_raises(ArgumentError) {@b2.difference(@bl)}
end
def test_19_exclusive_or
e1 = @b1.exclusive_or(@b2)
assert_is_bitvector(e1)
assert_equal("0110", e1.inspect)
e2 = @b1^@b2
assert_is_bitvector(e2)
assert_equal("0110", e2.inspect)
assert_raises(ArgumentError) {@b1^@bl}
end
def test_20_complement
assert_equal("0011", @b1.complement.inspect)
assert_equal("0110011", @bl.complement.inspect)
assert_equal("0110011", (~@bl).inspect)
end
def test_21_subset_and_superset
@b2.set(2,1) # 1110
assert(@b1.subset?(@b2))
assert(!@b2.subset?(@b1))
assert(!@b1.superset?(@b2))
assert(@b2.superset?(@b1))
end
def test_22_norm
assert_equal(2, @b1.norm)
assert_equal(2, @b2.norm)
assert_equal(3, @bl.norm)
assert_equal(4, @bl.complement.norm)
end
def test_23_min_and_max
assert_equal(2, @b1.min)
assert_equal(3, @b1.max)
assert_equal(1, @b2.min)
assert_equal(3, @b2.max)
assert_equal(2, @bl.min)
assert_equal(6, @bl.max)
end
def test_24_aset
@bl[6] = 0
assert_equal("0001100", @bl.inspect)
@bl[2] = false
assert_equal("0001000", @bl.inspect)
@bl[0] = 1
assert_equal("0001001", @bl.inspect)
@bl[4] = true
assert_equal("0011001", @bl.inspect)
@bl[5..6] = true
assert_equal("1111001", @bl.inspect)
@bl[4...6] = 0
assert_equal("1001001", @bl.inspect)
@bl[-5...-1] = 1
assert_equal("1111101", @bl.inspect)
assert_raises(RangeError) {@bl[-8..-5] = false}
@bl[0,3] = false
assert_equal("1111000", @bl.inspect)
@bl[4,1] = 0
assert_equal("1101000", @bl.inspect)
@bl[5,0] = 0
assert_equal("1101000", @bl.inspect)
@bl[0,7] = true
assert_equal("1111111", @bl.inspect)
assert_raises(IndexError) {@bl[10**300] = false}
end
def test_25_new_string
b = BitVector.from_bin(7, "1001100")
assert_equal(7, b.length)
assert_equal("1001100", b.inspect)
b = BitVector.from_dec(7, "76")
assert_equal(7, b.length)
assert_equal("1001100", b.inspect)
b = BitVector.from_hex(7, "4C")
assert_equal(7, b.length)
assert_equal("1001100", b.inspect)
b = BitVector.from_enum(7, "2,3,6")
assert_equal(7, b.length)
assert_equal("1001100", b.inspect)
b = BitVector.from_enum(10, "6,2-3")
assert_equal(10, b.length)
assert_equal("0001001100", b.inspect)
b = BitVector.from_bin(2, "10101")
assert_equal(2, b.length)
assert_equal("01", b.inspect)
end
def test_26_new_fixnum
b = BitVector.new(nil, 76)
assert_equal(31, b.length)
assert_equal(("0" * (31-7)) + "1001100", b.inspect)
b = BitVector.new(false, 76)
assert_equal(31, b.length)
assert_equal(("0" * (31-7)) + "1001100", b.inspect)
b = BitVector.new(true, 76)
assert_equal(32, b.length)
assert_equal(("0" * (32-7)) + "1001100", b.inspect)
end
def test_27_new_bignum
b = BitVector.new(10, (256**20-1))
assert_equal(10, b.length)
assert_equal("1"*10, b.inspect)
b = BitVector.new(nil, (256**20-1))
assert_equal(8*20, b.length)
assert_equal("1"*160, b.inspect)
end
def test_28_new_int
b = BitVector.new(7, 76)
assert_equal(7, b.length)
assert_equal("1001100", b.inspect)
b = BitVector.new(nil, 76)
assert_equal(31, b.length)
assert_equal(("0" * (31-7)) + "1001100", b.inspect)
b = BitVector.new(false, 76)
assert_equal(31, b.length)
assert_equal(("0" * (31-7)) + "1001100", b.inspect)
b = BitVector.new(true, 76)
assert_equal(32, b.length)
assert_equal(("0" * (32-7)) + "1001100", b.inspect)
end
def test_29_msb_and_lsb
assert_equal(0, @b1.lsb)
@b1.lsb = 1
assert_equal(1, @b1.lsb)
assert_equal(1, @b1.msb)
@b1.msb = 0
assert_equal(0, @b1.msb)
end
def test_30_rotate_left_and_right
assert_equal(1, @b1.rotate_left)
assert_equal("1001", @b1.inspect)
assert_equal(0, @b2.rotate_right)
assert_equal("0101", @b2.inspect)
end
def test_31_shift_left_and_right
assert_equal(1, @b1.shift_left(1))
assert_equal("1001", @b1.inspect)
assert_equal(0, @b2.shift_right(0))
assert_equal("0101", @b2.inspect)
end
def test_32_move_left_and_right
@b1 << 1
assert_equal("1000", @b1.inspect)
@b1 << 1
assert_equal("0000", @b1.inspect)
@b2 >> 1
assert_equal("0101", @b2.inspect)
@b2 >> 10
assert_equal("0000", @b2.inspect)
end
def test_33_succ_and_pred
assert_equal("1101", @b1.succ.inspect)
assert_equal("1001", @b2.pred.inspect)
end
def test_34_marshaling
d1 = Marshal.dump(@b1)
b1c = Marshal.load(d1)
assert_is_bitvector(b1c)
assert(b1c == @b1)
assert_equal(4, b1c.length)
assert_equal("1100", b1c.inspect)
b = BitVector.new(32*100+1)
d = Marshal.dump(b)
bc = Marshal.load(d)
assert_equal(3201, bc.length)
assert(("0"*3201) == bc.inspect)
end
def test_35_new_clone
b = BitVector.new(@b1)
assert(b == @b1)
assert_equal(4, b.length)
assert_equal("1100", b.inspect)
end
def test_36_substitute
@b1.substitute(@b2, 1, 2, 1, 3)
assert_equal(5, @b1.length)
assert_equal("11010", @b1.inspect)
@bl.substitute(@b1, 7, 0, 0, 5)
assert_equal(12, @bl.length, @bl.inspect)
assert_equal("110101001100", @bl.inspect)
assert_raises(IndexError) {@b1.substitute(@b2, -1, 0, 0, 0)}
assert_raises(IndexError) {@b1.substitute(@b2, 0, 0, -1, 0)}
end
def test_37_to_i
assert_equal(12-16, @b1.to_i)
assert_equal(10-16, @b2.to_i)
assert_equal(76-128, @bl.to_i)
assert_equal(12, BitVector.from_bin(5, "01100").to_i)
assert_equal(10, BitVector.from_bin(5, "01010").to_i)
assert_equal(76, BitVector.from_bin(8, "01001100").to_i)
assert_equal(2**160-1, BitVector.from_bin(161, "0" + ("1"*160)).to_i)
end
def test_38_ones_and_zeroes
assert_equal([2,3], @b1.ones)
assert_equal([1,3], @b2.ones)
assert_equal([2,3,6], @bl.ones)
assert_equal([0,1], @b1.zeroes)
assert_equal([0,2], @b2.zeroes)
assert_equal([0,1,4,5], @bl.zeroes)
b = BitVector.new(10000).randomize
assert_equal(b.norm, b.ones.length)
assert_equal(10000-b.norm, b.zeroes.length)
end
def test_39_randomize
b = BitVector.new(10)
b.randomize
b.empty
b.randomize(0...5, 1.0)
assert_equal("0000011111", b.inspect)
b.randomize(0, 2, 1.0)
assert_equal("0000011100", b.inspect)
b.randomize(9, 1.0)
assert_equal("1000011100", b.inspect)
b.randomize(-2...-1, 1.0)
assert_equal("1100011100", b.inspect)
assert_raises(RangeError) {b.randomize(-18..-5)}
assert_raises(IndexError) {b.randomize(-1)}
assert_raises(IndexError) {b.randomize(b.length)}
# Randomize a large number of times and make sure no bit gets unfair
# treatment...
counts = Hash.new(10)
b.empty
10000.times {
prev = b.clone
b.randomize(0.5)
(b ^ prev).ones.each {|differing_bit| counts[differing_bit]+=1}
}
# Very unlikely that number of alterations of a bit in 10000 randomizations
# is outside [4820,5180] (binomial distribution). NOTE: It can happen
# though (about once in 10000 test runs...)
counts.each {|bit, count|
assert(count.between?(4820,5180), "Bit #{bit} altered #{count} times. THIS IS UNLIKELY BUT MIGHT HAPPEN WITHOUT THERE BEING AN ERROR!")
}
end
def test_40_aref
assert_equal(0, @bl[0])
assert_equal("1001100", @bl.inspect)
assert_equal(1, @bl[6])
assert_equal("1001100", @bl.inspect)
b = @bl[0,7]
assert_equal(@bl.inspect, b.inspect)
assert_equal("1001100", @bl.inspect)
b = @bl[4..6]
assert_is_bitvector(b)
assert_equal("100", b.inspect)
assert_equal("1001100", @bl.inspect)
b = @bl[4...6]
assert_equal("00", b.inspect)
assert_equal("1001100", @bl.inspect)
b = @bl[-5...-3]
assert_equal("11", b.inspect)
b = @bl[0,3]
assert_equal("100", b.inspect)
b = @bl[4,1]
assert_equal(Fixnum, b.class)
assert_equal(0, b)
b = @bl[6,1]
assert_equal(Fixnum, b.class)
assert_equal(1, b)
b = @bl[6,0]
assert_equal(nil, b)
assert_raises(IndexError) {@bl[-1]}
assert_raises(IndexError) {@bl[@bl.length]}
assert_raises(IndexError) {@bl[10**300]}
end
def test_41_resize
assert_equal(4, @b1.length)
assert_equal(19, @b1.resize(19).length)
assert_equal(2, @b1.resize(2).length)
assert_equal(0, @b1.resize(0).length)
assert_equal(7, @bl.length)
assert_equal(49, @bl.resize(49).length)
assert_equal(2, @bl.resize(2).length)
assert_equal(0, @bl.resize(0).length)
assert_raises(ArgumentError) {@bl.resize(-1)}
assert_raises(ArgumentError) {@bl.resize(10**300)}
end
def test_42_from_int
b = BitVector.from_int(86,8)
assert_is_bitvector(b)
assert_equal(8, b.length)
assert_equal("01010110", b.inspect)
b = BitVector.from_int(86)
assert_is_bitvector(b)
assert_equal(8, b.length) # 7 bits needed but extra to mark as positive
assert_equal("01010110", b.inspect)
b = BitVector.from_int(-4)
assert_equal(3, b.length) # One extra bit since negative
assert_equal("100", b.inspect);
b = BitVector.from_int(-(2**32))
assert_equal(33, b.length) # One extra bit since negative
end
def test_43_add
b1 = BitVector.from_bin(8, "01100101") # 1+4+32+64 = 101
b2 = BitVector.from_bin(8, "01010110") # 2+4+16+64 = 86
s = b1+b2 # 187
assert_is_bitvector(s)
assert_equal(b1.length, s.length)
assert_equal(b1.to_uint+b2.to_uint, s.to_uint)
assert_equal(187, s.to_uint)
assert_equal(0, BitVector.carry)
b1 = BitVector.from_bin(8, "11100101") # 1+4+32+64+128 = 229
b2 = BitVector.from_bin(8, "01010110") # 2+4+16+64 = 86
s = b1+b2 # 229+86 = 315 but we get a carry
# and 59 (315-256)
assert_equal(59, s.to_i)
assert_equal(1, BitVector.carry)
b1 = BitVector.from_bin(8, "11100101") # 1+4+32+64+128 = 229
b2 = 86 # 86
s = b1+b2 # 229+86 = 315 but we get a carry
# and 59 (315-256)
assert_equal(59, s.to_i)
assert_equal(1, BitVector.carry)
assert_equal(226, (BitVector.from_bin(8,"11100101")+(-3)).to_uint)
end
def test_43_sub
b1 = BitVector.from_bin(8, "01100101") # 1+4+32+64 = 101
b2 = BitVector.from_bin(8, "01010110") # 2+4+16+64 = 86
s = b1-b2 # 15
assert_is_bitvector(s)
assert_equal(b1.length, s.length)
assert_equal(b1.to_uint-b2.to_uint, s.to_uint)
assert_equal(15, s.to_uint)
assert_equal(0, BitVector.carry)
b1 = BitVector.from_bin(8, "11100101") # 1+4+32+64+128 = 229
b2 = 86 # 86
s = b1-b2
assert_equal(143, s.to_uint)
assert_equal(0, BitVector.carry)
assert_equal(232, (BitVector.from_bin(8,"11100101")-(-3)).to_uint)
end
def test_44_negate
assert_equal(-27, (-BitVector.from_int(27,8)).to_i)
assert_equal(27, (-(-BitVector.from_int(27,8))).to_i)
end
def test_45_to_uint
assert_equal(12, @b1.to_uint)
assert_equal(10, @b2.to_uint)
assert_equal(76, @bl.to_uint)
assert_equal(2**33-1, BitVector.from_bin(33, "1"*33).to_uint)
assert_equal(2**160-1, BitVector.from_bin(160, "1"*160).to_uint)
assert_equal(2**160-1, BitVector.from_bin(161, "0" + ("1"*160)).to_uint)
assert_equal(2*(2**160-1),
BitVector.from_bin(162, "0" + ("1"*160) + "0").to_uint)
end
def test_46_abs
assert_equal(27, (-BitVector.from_int(27,8)).abs.to_i)
end
def test_47_sign
assert_equal(-1, (BitVector.from_int(-1, 8)).sign)
assert_equal(0, (BitVector.from_int(0, 8)).sign)
assert_equal(1, (BitVector.from_int(1, 8)).sign)
assert_equal(-1, (BitVector.from_int(-100, 8)).sign)
assert_equal(1, (BitVector.from_int(100, 8)).sign)
assert_equal(-1, @b1.sign)
assert_equal(-1, @b2.sign)
assert_equal(-1, @bl.sign)
assert_equal(1, (-@b1).sign)
assert_equal(1, (-@b2).sign)
assert_equal(1, (-@bl).sign)
end
def test_48_multiply
assert_equal(24, (p = @b1*@b2).to_i) # -4*-6
assert_equal(8, p.length)
assert_equal(120,
(p = BitVector.from_int(12,8)*BitVector.from_int(10,8)).to_i)
assert_equal(16, p.length)
end
def test_49_divide
assert_equal(1, (q = @b2/@b1).to_i) # -6/-4
assert_equal(4, q.length)
assert_equal(12,
(p = BitVector.from_int(120,8)/BitVector.from_int(10,8)).to_i)
assert_equal(8, p.length)
end
def test_50_strange_gc_bug
# This bug showed up at some time during development. Unclear what causes/
# caused it.
a = BitVector.new(10000).randomize
a = nil
GC.start
a = BitVector.new(10000).randomize # => [BUG] segmentation fault
end
def test_51_aset_bitvector
@be[1..2] = @bf[-4..-3] # Note that it is faster to use substitute...
assert_equal("0110", @be.inspect)
@bl[0,4] = @b2
assert_equal("1001010", @bl.inspect)
assert_raises(RangeError) {@bl[0,1] = @be[3..4]}
end
end
syntax highlighted by Code2HTML, v. 0.9.1