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:

Attributes

bits[R]

The bit string defining the cube.

Should not be modified directly, hence set as protected.

Public Class Methods

new(bits, safe = true) click to toggle source

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

[](i) click to toggle source

Gets the char value of bit i.

# File lib/logic_tools/logiccover.rb, line 136
def [](i)
    @bits[i]
end
[]=(i,b) click to toggle source

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
blocking_matrix(off) click to toggle source

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
can_merge?(cube) click to toggle source

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
consensus(cube) click to toggle source

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
distance(cube) click to toggle source

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
each(&blk)
Alias for: each_char
each_byte(&blk) click to toggle source

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
each_char(&blk) click to toggle source

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
Also aliased as: each
each_minterm() { |clone| ... } click to toggle source

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
eval_input(input) click to toggle source

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
getbyte(i) click to toggle source

Gets the byte value of bit i.

# File lib/logic_tools/logiccover.rb, line 141
def getbyte(i)
    @bits.getbyte(i)
end
hash() click to toggle source

Gets the hash of a cube

# File lib/logic_tools/logiccover.rb, line 125
def hash
    @bits.hash
end
include?(cube) click to toggle source

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
intersect(cube) click to toggle source

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
intersects?(cube) click to toggle source

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
merge(cube) click to toggle source

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
setbyte(i,b) click to toggle source

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
sharp(cube) click to toggle source

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
width() click to toggle source

Gets the width (number of variables of the boolean space).

# File lib/logic_tools/logiccover.rb, line 55
def width
    return @bits.length
end