Class: LogicTools::Cube

Inherits:
Object
  • Object
show all
Defined in:
lib/logic_tools/logiccover.rb,
lib/logic_tools/logicsimplify_es.rb

Overview

– Enhances the Cube class with methods for applying the Espresso algorithm. ++

Direct Known Subclasses

VoidCube

Instance Method Summary collapse

Constructor Details

#initialize(bits, safe = true) ⇒ Cube

Creates a new cube from a bit string bits.

NOTE: If +safe+ is set to false, +bits+ is not checked nor cloned.



42
43
44
45
46
47
48
49
50
51
52
 
# 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

Instance Method Details

#<=>(cube) ⇒ Object

:nodoc:



120
121
122
 
# File 'lib/logic_tools/logiccover.rb', line 120

def <=>(cube) #:nodoc:
    @bits <=> cube.bits
end

#==(cube) ⇒ Object Also known as: eql?

Compares with another cube.



116
117
118
 
# File 'lib/logic_tools/logiccover.rb', line 116

def ==(cube) # :nodoc:
    @bits == cube.bits
end

#[](i) ⇒ Object

Gets the char value of bit i.



136
137
138
 
# File 'lib/logic_tools/logiccover.rb', line 136

def [](i)
    @bits[i]
end

#[]=(i, b) ⇒ Object

Sets the char value of bit i to b.



146
147
148
149
150
 
# 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) ⇒ Object

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).



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# 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) ⇒ Boolean

Checks if self can be merged with cube

Returns:

  • (Boolean) 


208
209
210
211
212
213
214
215
216
217
218
219
 
# 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

#clone ⇒ Object Also known as: dup

duplicates the cube.



130
131
132
 
# File 'lib/logic_tools/logiccover.rb', line 130

def clone # :nodoc:
    Cube.new(@bits)
end

#consensus(cube) ⇒ Object

Computes the consensus with another cube.

Returns the concensus cube if any.



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# 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) ⇒ Object

Computes the distance with another cube.



76
77
78
79
80
81
 
# 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_byte(&blk) ⇒ Object

Iterates over the bits of the cube as bytes.

Returns an enumerator if no block given.



91
92
93
94
95
96
97
 
# 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) ⇒ Object Also known as: each

Iterates over the bits of the cube as chars.



100
101
102
103
104
105
106
 
# 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

#each_minterm ⇒ Object

Iterates over the minterms included by the cube.

The minterm are represented by bit strings.

Returns an iterator if no block is given.



293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
 
# 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) ⇒ Object

Evaluates the corresponding function’s value for a binary input.

+input+ is assumed to be an integer.
Returns the evaluation result as a boolean.



63
64
65
66
67
68
69
70
71
72
73
 
# 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) ⇒ Object

Gets the byte value of bit i.



141
142
143
 
# File 'lib/logic_tools/logiccover.rb', line 141

def getbyte(i)
    @bits.getbyte(i)
end

#hash ⇒ Object

Gets the hash of a cube



125
126
127
 
# File 'lib/logic_tools/logiccover.rb', line 125

def hash
    @bits.hash
end

#include?(cube) ⇒ Boolean

Tells if cube is included.

Returns:

  • (Boolean) 


280
281
282
283
284
285
286
 
# 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) ⇒ Object

Creates the intersection between self and another cube.

Return a new cube giving the intersection, or nil if there is none.



255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
 
# 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) ⇒ Boolean

Checks if self intersects with another cube.

Returns:

  • (Boolean) 


243
244
245
246
247
248
249
250
 
# 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) ⇒ Object

Merges self with cube if possible.

Returns the merge result as a new cube, or nil in case of failure.



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
 
# 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) ⇒ Object

Sets the byte value of bit i to b.

NOTE: does not check b, so please use with caution.



155
156
157
 
# File 'lib/logic_tools/logiccover.rb', line 155

def setbyte(i,b)
    @bits.setbyte(i,b)
end

#sharp(cube) ⇒ Object

Computes the sharp operation with another cube.

Returns the resulting list of cubes as an array.

(NOTE: not as a cover).



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# 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

#to_s ⇒ Object

Converts to a string.



84
85
86
 
# File 'lib/logic_tools/logiccover.rb', line 84

def to_s # :nodoc:
    @bits.clone
end

#width ⇒ Object

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



55
56
57
 
# File 'lib/logic_tools/logiccover.rb', line 55

def width
    return @bits.length
end