class LogicTools::Cube
Represents a boolean cube.
NOTE: cubes are crutial for the performance of the implementation of the simplifying algorithm. Hence they are internally represented as strings, since they are much more memory efficient and usually faster than arrays.
Then there are two interfaces:
-
The standard interface is based on strings and substrings only and is safe but slow.
It includes the '[]' and '[]=' operators for accessing one bit, and
each_char
(or simply each) for iterating over the bits.With this interface, “0” stands for false, “1” for true and “-” for don't care.
-
The fast interface is based on bytes of a string, is fast but unsafe (it does not check the bits).
It includes getbyte and setbyte for accessing one bit, and
each_byte
for iterating over the bits.With this interface, 48 stands for false, 49 for true and 45 for don't care.
Attributes
The bit string defining the cube.
Should not be modified directly, hence set as protected.
Public Class Methods
Creates a new cube from a bit string bits
.
NOTE: If safe
is set to false, bits
is not checked nor cloned.
# File lib/logic_tools/logiccover.rb, line 42 def initialize(bits, safe = true) if safe then bits = bits.to_s unless bits.match(/^[01-]*$/) raise "Invalid bit string for describing a cube: "+ bits end @bits = bits.clone else @bits = bits.to_s end end
Public Instance Methods
Gets the char value of bit i
.
# File lib/logic_tools/logiccover.rb, line 136 def [](i) @bits[i] end
Sets the char value of bit i
to b
.
# File lib/logic_tools/logiccover.rb, line 146 def []=(i,b) raise "Invalid bit value: #{b}" unless ["0","1","-"].include?(b) # Update the bit string @bits[i] = b end
Computes the blocking matrix relatively to an off
cover.
NOTE: * The blocking matrix's first row gives the column number
of each litteral of the cube. * The blocking matrix's other rows represents the cubes of the off cover. * The block matrix's cells are set to "1" if corresponding +self+ litteral has a different polarity (1,0 or 0,1) than the corresponding off cover's cube and set to "0" otherwise (including the "-" cases).
# File lib/logic_tools/logicsimplify_es.rb, line 28 def blocking_matrix(off) # Create the result matrix. blocking = [] # Get the column number of the litterals of self. # litterals = @bits.size.times.find_all {|i| @bits[i] != "-" } litterals = @bits.size.times.find_all {|i| @bits.getbyte(i) != 45 } # This is the first row of the blocking matrix. blocking << litterals # Build the other rows: one per cube of the off cover. off.each_cube do |cube| # print "for off cube=#{cube}\n" # Create the new row: by default blocking. row = "0" * litterals.size blocking << row # Fill it litterals.each.with_index do |col,i| # if cube[col] != "-" and @bits[col] != cube[col] then if cube.getbyte(col) != 45 and @bits.getbyte(col) != cube.getbyte(col) then # Non blocking, put a "1". # row[i] = "1" row.setbyte(i,49) end end # print "blocking row=#{row}\n" end # Returns the resulting matrix return blocking end
Checks if self
can be merged with cube
# File lib/logic_tools/logiccover.rb, line 208 def can_merge?(cube) found = false # 0 to 1 or 1 to 0 pattern found @bits.each_byte.with_index do |bit,i| if (bit != cube.getbyte(i)) then # Found one different bit return false if found # But there were already one found = true end end # Can be merged return true end
Computes the consensus with another cube
.
Returns the concensus cube if any.
# File lib/logic_tools/logiccover.rb, line 162 def consensus(cube) # Step 1: compute the distance between the cubes. dist = self.distance(cube) # Step 2: depending on the distance. return nil if (dist != 1) # Distance is not 1: no consensus # Distance is 1, the consensus is a single cube # built by setting to "-" the opposite variable, and # keeping all the other. cbits = "-" * cube.width @bits.each_byte.with_index do |bit,i| # if bit != "-" then if bit != 45 then # cbits[i] = bit if (cube[i] == "-" or cube[i] == bit) cbits.setbyte(i,bit) if (cube.getbyte(i) == 45 or cube.getbyte(i) == bit) else # cbits[i] = cube[i] cbits.setbyte(i,cube.getbyte(i)) end end return Cube.new(cbits,false) # No need to clone cbits. end
Computes the distance with another cube
.
# File lib/logic_tools/logiccover.rb, line 76 def distance(cube) return @bits.each_byte.with_index.count do |b,i| # b != "-" and cube[i] != "-" and b != cube[i] b != 45 and cube.getbyte(i) != 45 and b != cube.getbyte(i) end end
Iterates over the bits of the cube as bytes.
Returns an enumerator if no block given.
# File lib/logic_tools/logiccover.rb, line 91 def each_byte(&blk) # No block given? Return an enumerator. return to_enum(:each_byte) unless block_given? # Block given? Apply it on each bit. @bits.each_byte(&blk) end
Iterates over the bits of the cube as chars.
# File lib/logic_tools/logiccover.rb, line 100 def each_char(&blk) # No block given? Return an enumerator. return to_enum(:each_char) unless block_given? # Block given? Apply it on each bit. @bits.each_char(&blk) end
Iterates over the minterms included by the cube.
The minterm are represented by bit strings.
Returns an iterator if no block is given.
# File lib/logic_tools/logiccover.rb, line 293 def each_minterm # No block given? Return an enumerator. return to_enum(:each_minterm) unless block_given? # Block given? Apply it. # Locate the "-" in the bit: they are the source of alternatives # free_cols = @bits.size.times.find_all {|i| @bits[i] == "-" } free_cols = @bits.size.times.find_all {|i| @bits.getbyte(i) == 45 } # Generate each possible min term if (free_cols.empty?) then # Only one minterm yield(@bits.clone) else # There are several minterms (2 ** (free_cols.size)).times do |sel| # Generate the minterm corresponding combination +sel+. minterm = @bits.clone free_cols.each.with_index do |col,i| if (sel & (2 ** i) == 0) then # The column is to 0 # minterm[col] = "0" minterm.setbyte(col,48) else # The column is to 1 # minterm[col] = "1" minterm.setbyte(col,49) end end # The minterm is ready, use it. yield(minterm) end end end
Evaluates the corresponding function's value for a binary input
.
input
is assumed to be an integer. Returns the evaluation result as a boolean.
# File lib/logic_tools/logiccover.rb, line 63 def eval_input(input) result = true @bits.each_byte.with_index do |bit,i| if bit == 49 then result &= ((input & (2**i)) != 0) elsif bit == 48 then result &= ((input & (2**i)) == 0) end end return result end
Gets the byte value of bit i
.
# File lib/logic_tools/logiccover.rb, line 141 def getbyte(i) @bits.getbyte(i) end
Gets the hash of a cube
# File lib/logic_tools/logiccover.rb, line 125 def hash @bits.hash end
Tells if cube
is included.
# File lib/logic_tools/logiccover.rb, line 280 def include?(cube) # Look for a proof of non inclusion. ! @bits.each_byte.with_index.find do |bit,i| # bit != "-" and cube[i] != bit bit != 45 and cube.getbyte(i) != bit end end
Creates the intersection between self
and another cube
.
Return a new cube giving the intersection, or nil if there is none.
# File lib/logic_tools/logiccover.rb, line 255 def intersect(cube) return nil unless cube # No cube: intersection is empty. cbits = "-" * self.width # Cubes intersects if they do not include any 0,1 or 1,0 pattern. @bits.each_byte.with_index do |bit,i| # if bit == "-" then if bit == 45 then # cbits[i] = cube[i] cbits.setbyte(i,cube.getbyte(i)) # elsif cube[i] == "-" then elsif cube.getbyte(i) == 45 then # cbits[i] = bit cbits.setbyte(i,bit) elsif bit != cube.getbyte(i) then # No intersection. return nil else # cbits[i] = bit cbits.setbyte(i,bit) end end return Cube.new(cbits,false) # No need to duplicate cbits. end
Checks if self
intersects with another cube
.
# File lib/logic_tools/logiccover.rb, line 243 def intersects?(cube) return nil unless cube # No cube: intersection is empty. # Cubes intersects if they do not include any 0,1 or 1,0 pattern. return (not @bits.each_byte.with_index.find do |bit,i| # bit != "-" and cube[i] != "-" and bit != cube[i] bit != 45 and cube.getbyte(i) != 45 and bit != cube.getbyte(i) end) end
Merges self
with cube
if possible.
Returns the merge result as a new cube, or nil in case of failure.
# File lib/logic_tools/logiccover.rb, line 224 def merge(cube) # Create the bit string of the result. cbits = "-" * self.width found = false # 0 to 1 or 1 to 0 pattern found @bits.each_byte.with_index do |bit,i| if (bit != cube.getbyte(i)) then # Found one different bit return nil if found # But there were already one found = true else # cbits[i] = bit cbits.setbyte(i,bit) end end # Can be merged return Cube.new(cbits,false) # No need to clone cbits. end
Sets the byte value of bit i
to b
.
NOTE: does not check b, so please use with caution.
# File lib/logic_tools/logiccover.rb, line 155 def setbyte(i,b) @bits.setbyte(i,b) end
Computes the sharp operation with another cube
.
Returns the resulting list of cubes as an array.
(NOTE: not as a cover).
# File lib/logic_tools/logiccover.rb, line 190 def sharp(cube) result = [] # There is one such cube per litteral which is in # self but not in cube. @bits.each_byte.with_index do |bit,i| # next if (cube[i] == "-" or cube[i] == bit) next if (cube.getbyte(i) == 45 or cube.getbyte(i) == bit) cbits = @bits.clone # cbits[i] = (cube[i] == "0") ? "1" : "0" cbits.setbyte(i, (cube.getbyte(i) == 48) ? 49 : 48) result << Cube.new(cbits,false) # No need to clone cbits end # Remove duplicate cubes before ending. result.uniq! return result end
Gets the width (number of variables of the boolean space).
# File lib/logic_tools/logiccover.rb, line 55 def width return @bits.length end