Class: LilUtils::Misc::BitVector

Inherits:
Object
  • Object
show all
Defined in:
lib/lilutils/misc/bit_vector.rb

Overview

Class to implement a bit vector that uses an array of Fixnums as its storage. Implements the basic bit vector operations as specified.

Constant Summary collapse

BITS_PER_ITEM = 
0.size * 8

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ BitVector

Returns a new instance of BitVector.

Raises:

  • (ArgumentError) 


9
10
11
12
13
 
# File 'lib/lilutils/misc/bit_vector.rb', line 9

def initialize(size)
  raise ArgumentError, "size must be positive" if size <= 0
  @size  = size
  @array = Array.new((size*1.0/BITS_PER_ITEM).ceil) { |i| 0 } #=> array contains required # of Fixnums, initialized to zero
end

Instance Method Details

#clear(i) ⇒ Object

Clears the given bit (i.e. makes it 0).

Parameters:

  • i (Fixnum) —

    Represents the index of given bit, must be from 0 to @size-1

Returns:

  • nothing

Raises:

  • (ArgumentError) 


36
37
38
39
 
# File 'lib/lilutils/misc/bit_vector.rb', line 36

def clear(i)
  raise ArgumentError, "argument (#{i}) should be between 0 and #{@size}" if i < 0 or i >= @size
  @array[get_index(i)] &= ~(1 << get_shift(i))
end

#set(i) ⇒ Object

Sets the ‘i’th bit of this Bit Vector.

Parameters:

  • i (Fixnum) —

    Represents the index of given, must be from 0 to @size-1

Returns:

  • nothing

Raises:

  • (ArgumentError) —

    if 0 < i <= n



19
20
21
22
 
# File 'lib/lilutils/misc/bit_vector.rb', line 19

def set(i)
  raise ArgumentError, "argument (#{i}) should be between 0 and #{@size}" if i < 0 or i >= @size
  @array[get_index(i)] |= (1 << get_shift(i))
end

#test(i) ⇒ Fixnum

Tests whether ith bit of this Bit Vector is set

Parameters:

  • i (Fixnum) —

    Represents the index of given bit, must be from 0 to @size-1

Returns:

  • (Fixnum) —

    1 if ith bit is set, 0 otherwise

Raises:

  • (ArgumentError) 


28
29
30
31
 
# File 'lib/lilutils/misc/bit_vector.rb', line 28

def test(i)
  raise ArgumentError, "argument (#{i}) should be between 0 and #{@size}" if i < 0 or i >= @size
  (@array[get_index(i)] & (1 << (get_shift(i))))>>(get_shift(i))
end