Class: LogicTools::NodeNary

Inherits:
Node
  • Object
show all
Extended by:
Forwardable
Defined in:
lib/logic_tools/logictree.rb

Overview

Represents an operator node with multiple children.

Direct Known Subclasses

NodeAnd, NodeOr

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Node

#each_line, #each_maxterm, #each_minterm, #eql?, #get_variables, #hash, #inspect, #simplify, #size, #to_cover, #to_std_conjunctive, #to_std_disjunctive, #to_sum_product

Instance Attribute Details

#op ⇒ Object (readonly)

Returns the value of attribute op.



436
437
438
 
# File 'lib/logic_tools/logictree.rb', line 436

def op
  @op
end

Class Method Details

.make(op, *children) ⇒ Object

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



457
458
459
460
461
462
463
464
465
466
 
# File 'lib/logic_tools/logictree.rb', line 457

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

Instance Method Details

#==(node) ⇒ Object

Compares with node.



530
531
532
533
534
535
536
537
538
539
540
 
# File 'lib/logic_tools/logictree.rb', line 530

def ==(node) # :nodoc:
    return false unless node.is_a?(Node)
    return false unless self.op == node.op
    return false unless self.size == node.size
    # There is no find_with_index!
    # return ! @children.find_with_index {|child,i| child != node[i] }
    @children.each_with_index do |child,i|
        return false if child != node[i]
    end
    return true
end

#add(child) ⇒ Object

Adds a child.



477
478
479
480
481
482
483
 
# File 'lib/logic_tools/logictree.rb', line 477

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) ⇒ Boolean

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.

Returns:

  • (Boolean) 


567
568
569
570
571
572
573
574
575
576
577
578
579
580
 
# File 'lib/logic_tools/logictree.rb', line 567

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

#distribute(dop, node) ⇒ Object

Creates a new tree where the current node is distributed over node

according to the +dop+ operator.



698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
 
# File 'lib/logic_tools/logictree.rb', line 698

def distribute(dop,node) # :nodoc:
    # print "distrubte with self=#{self} and node=#{node}\n"
    fop = dop == :and ? :or : :and
    # print "dop=#{dop} fop=#{fop} self.op=#{@op}\n"
    if (@op == dop) then
        # Self operator is dop: merge node in self
        return NodeNary.make(dop,*self,node).flatten
    else
        # self operator if fop
        if (node.op == fop) then
            # print "(a+b)(c+d) case\n"
            # node operator is also fop: (a+b)(c+d) or ab+cd case
            nchildren = []
            self.each do |child0|
                node.each do |child1|
                    # print "child0=#{child0}, child1=#{child1}\n"
                    nchildren << 
                        NodeNary.make(dop, child0, child1).flatten
                    # print "nchildren=#{nchildren}\n"
                end
            end
            return NodeNary.make(fop,*nchildren).flatten
        else
            # print "(a+b)c case\n"
            # node operator is not fop: (a+b)c or ab+c case
            nchildren = self.map do |child|
                NodeNary.make(dop,child,node).flatten
            end
            # print "nchildren=#{nchildren}\n"
            return NodeNary.make(fop,*nchildren).flatten
        end
    end
end

#each(&blk) ⇒ Object

Iterates over the children.



486
487
488
489
490
491
492
493
 
# File 'lib/logic_tools/logictree.rb', line 486

def each(&blk) # :nodoc:
    # No block given? Return an enumerator.
    return to_enum(:each) unless blk

    # Block given? Apply it.
    @children.each(&blk)
    return self
end

#flatten ⇒ Object

Flatten ands, ors and nots.



671
672
673
674
675
676
677
678
679
 
# File 'lib/logic_tools/logictree.rb', line 671

def flatten # :nodoc:
    return NodeNary.make(@op,*(@children.reduce([]) do |nchildren,child|
        if (child.op == self.op) then
            nchildren.push(*child)
        else
            nchildren << child
        end
    end)).reduce
end

#flatten_deep ⇒ Object

Creates a new tree where all the and, or and not operators

from the current node are flattened.

Default: simply duplicate.



685
686
687
688
689
690
691
692
693
694
 
# File 'lib/logic_tools/logictree.rb', line 685

def flatten_deep # :nodoc:
    return NodeNary.make(@op,*(@children.reduce([]) do |nchildren,child|
        child = child.flatten_deep
        if (child.op == self.op) then
            nchildren.push(*child)
        else
            nchildren << child
        end
    end)).reduce
end

#get_variablesRecurse ⇒ Object

Gets the variables, recursively, without postprocessing.

Returns the variables into sets of arrays with possible doublon



523
524
525
526
527
 
# File 'lib/logic_tools/logictree.rb', line 523

def get_variablesRecurse() # :nodoc:
    return @children.reduce([]) do |res,child|
        res.concat(child.get_variablesRecurse)
    end
end

#include?(tree) ⇒ Boolean

Tells if self includes tree.

NOTE: * This is a tree inclusion, not a logical inclusion.
      * It is assumed that the trees are sorted.

Returns:

  • (Boolean) 


546
547
548
549
550
551
552
553
554
555
556
557
558
559
 
# File 'lib/logic_tools/logictree.rb', line 546

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? ⇒ Boolean

Tells if the node is a parent.

Returns:

  • (Boolean) 


469
470
471
 
# File 'lib/logic_tools/logictree.rb', line 469

def is_parent?
    return true
end

#reduce ⇒ Object

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

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



616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
 
# File 'lib/logic_tools/logictree.rb', line 616

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 ⇒ Object

Creates a new node whose childrens are sorted.



496
497
498
 
# File 'lib/logic_tools/logictree.rb', line 496

def sort
    return NodeNary.make(@op,*@children.sort_by {|child| child.to_sym })
end

#to_sym ⇒ Object

Converts to a symbol.



515
516
517
518
 
# File 'lib/logic_tools/logictree.rb', line 515

def to_sym # :nodoc:
    @sym = self.to_s.to_sym unless @sym
    return @sym
end

#uniq(&blk) ⇒ Object

Creates a new node without duplicate in the children.



501
502
503
504
505
506
507
508
509
510
511
512
 
# File 'lib/logic_tools/logictree.rb', line 501

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