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.



438
439
440
 
# File 'lib/logic_tools/logictree.rb', line 438

def op
  @op
end

Class Method Details

.make(op, *children) ⇒ Object

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



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

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.



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

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.



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

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) 


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

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.



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
731
732
 
# File 'lib/logic_tools/logictree.rb', line 700

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.



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

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.



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

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.



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

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



525
526
527
528
529
 
# File 'lib/logic_tools/logictree.rb', line 525

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) 


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

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) 


471
472
473
 
# File 'lib/logic_tools/logictree.rb', line 471

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.



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
669
670
 
# File 'lib/logic_tools/logictree.rb', line 618

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.



498
499
500
 
# File 'lib/logic_tools/logictree.rb', line 498

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

#to_sym ⇒ Object

Converts to a symbol.



517
518
519
520
 
# File 'lib/logic_tools/logictree.rb', line 517

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.



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

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