=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