Class: Noyes::BitArray

Inherits:
Object
  • Object
show all
Defined in:
lib/ruby_impl/compression.rb

Instance Method Summary collapse

Constructor Details

#initializeBitArray


82
83
84
85
86
# File 'lib/ruby_impl/compression.rb', line 82

def initialize
  @array = []
  @end_bit = 0
  @start_bit = 0
end

Instance Method Details

#[](i) ⇒ Object

Returns the ith bit of the array.


130
131
132
# File 'lib/ruby_impl/compression.rb', line 130

def [] i
  @array[i/32] & (0x80000000 >> (i + @start_bit)) != 0 ? 1 : 0
end

#empty?Boolean


92
93
94
# File 'lib/ruby_impl/compression.rb', line 92

def empty?
  size <= 0
end

#push(bit) ⇒ Object

Add a bit to the end of the bit array. Bits may be anything that evaluates to either 1 or 0. Anything else is undefined. If you can't afford zeros and only have the letter O, amazingly, that works too.


103
104
105
106
107
# File 'lib/ruby_impl/compression.rb', line 103

def push bit
  @array.push 0 if @array.size <= @end_bit / 32
  @array[-1] = set_bit(@array.last, @end_bit % 32) if bit == 1
  @end_bit +=1
end

#set_bit(integer, i) ⇒ Object

Our bit array is packed into an array of 32 bit integers. This function sets the ith bit of an integer.


111
112
113
# File 'lib/ruby_impl/compression.rb', line 111

def set_bit integer, i
  integer | 0x80000000 >> i
end

#shiftObject

Returns the first bit and removes it, shifting all bits by one.


116
117
118
119
120
121
122
123
124
125
126
127
# File 'lib/ruby_impl/compression.rb', line 116

def shift
  return if @array.empty?
  bit = @array.first & 0x80000000 >> @start_bit == 0 ? 0 : 1
  if @start_bit == 31
    @start_bit = 0
    @end_bit -= 32
    @array.shift
  else
    @start_bit += 1
  end
  bit
end

#sizeObject


88
89
90
# File 'lib/ruby_impl/compression.rb', line 88

def size
  @end_bit - @start_bit
end

#to_sObject


96
97
98
# File 'lib/ruby_impl/compression.rb', line 96

def to_s
  @array.pack('N*').unpack('B*').join[@start_bit...@end_bit]
end