class LogicTools::NodeNary

Represents an operator node with multiple children.

Attributes

op[R]

Public Class Methods

make(op,*children) click to toggle source

Creates a node with operator op and children (factory method).

# File lib/logic_tools/logictree.rb, line 469
def NodeNary.make(op,*children)
    case op
    when :or 
        return NodeOr.new(*children)
    when :and
        return NodeAnd.new(*children)
    else 
        raise ArgumentError.new("Not a valid operator: #{op}")
    end
end

Public Instance Methods

add(child) click to toggle source

Adds a child.

# File lib/logic_tools/logictree.rb, line 489
def add(child)
    unless child.is_a?(Node) then
        raise ArgumentError.new("Not a valid class for a child: "+
                                "#{child.class}")
    end
    @children << child
end
cover?(tree) click to toggle source

Tells if self covers tree.

NOTE: * It is assumed that the trees are sorted.

* There might still be cover even when the result is false.
  For exact cover checking, please use the LogicTools::Cover
  class.
# File lib/logic_tools/logictree.rb, line 579
def cover?(tree)
    # Different operators, no probable cover.
    return false if self.op != tree.op
    # Check for equality with one child.
    return true unless tree.each.with_index.find do |child,i|
        child != @children[i]
    end
    # Check each child.
    @children.each do |child|
        return true if ( child.op == self.op and child.cover?(tree) )
    end
    # Do not include.
    return false
end
include?(tree) click to toggle source

Tells if self includes tree.

NOTE: * This is a tree inclusion, not a logical inclusion.

* It is assumed that the trees are sorted.
# File lib/logic_tools/logictree.rb, line 558
def include?(tree)
    # Check from current node.
    if self.op == tree.op and self.size >= tree.size then
        return true unless tree.each.with_index.find do |child,i|
            child != @children[i]
        end
    end
    # Check each child.
    @children.each do |child|
        return true if child.include?(tree)
    end
    # Do not include.
    return false
end
is_parent?() click to toggle source

Tells if the node is a parent.

# File lib/logic_tools/logictree.rb, line 481
def is_parent?
    return true
end
reduce() click to toggle source

Reduces a node: remove its redundancies using the absbortion rules.

– TODO consider the X~X and X+~X cases.

# File lib/logic_tools/logictree.rb, line 628
def reduce
    # print "reducing #{self}\n"
    # The operator used for the factors
    fop = @op == :and ? :or : :and
    # Gather the terms to sorted nodes
    terms = @children.map do |child|
        child.op == fop ? child.sort : child
    end
    nchildren = []
    # Keep only the terms that do not contain another one
    # TODO: this loop could be faster I think...
    terms.each_with_index do |term0,i|
        skipped = false
        terms.each_with_index do |term1,j|
            next if (term0 == term1) # Same term, duplicates will be
                                     # removed after
            # Checks the X~X or X+~X cases.
            if ( term0.op == :not and term0.child == term1 ) or
               ( term1.op == :not and term1.child == term0 ) then
                # Reduceable to 0 or 1
                return self.op == :and ? NodeFalse.new : NodeTrue.new
            end
            # Checks the covering.
            next if (term0.op != term1.op) # Different operators
            # if (term0.include?(term1) and term0 != term1) then
            #     # term0 contains term1 but is different, skip it
            #     skipped = true
            #     break
            # end
            if term0.op == :and and term1.cover?(term0) then
                # print "#{term1} is covering #{term0}\n"
                # term1 covers term0 skip term0 for AND.
                skipped = true
                # break
            elsif term0.op == :or and term0.cover?(term1) then
                # print "#{term0} is covering #{term1}\n"
                # term0 covers term1 skip term0 for OR.
                skipped = true
                # break
            end
        end
        nchildren << term0 unless skipped # Term has not been skipped
    end
    # Avoid duplicates
    nchildren.uniq!
    # print "reduced nchildren=#{nchildren}\n"
    # Generate the result
    if (nchildren.size == 1)
        return nchildren[0]
    else
        return NodeNary.make(@op,*nchildren)
    end
end
sort() click to toggle source

Creates a new node whose childrens are sorted.

# File lib/logic_tools/logictree.rb, line 508
def sort
    return NodeNary.make(@op,*@children.sort_by {|child| child.to_sym })
end
uniq(&blk) click to toggle source

Creates a new node without duplicate in the children.

# File lib/logic_tools/logictree.rb, line 513
def uniq(&blk)
    if blk then
        nchildren = @children.uniq(&blk)
    else
        nchildren = @children.uniq { |child| child.to_sym }
    end
    if nchildren.size == 1 then
        return nchildren[0]
    else
        return NodeNary.make(@op,*nchildren)
    end
end