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?, #eval_input, #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.



448
449
450
 
# File 'lib/logic_tools/logictree.rb', line 448

def op
  @op
end

Class Method Details

.make(op, *children) ⇒ Object

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



469
470
471
472
473
474
475
476
477
478
 
# 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

Instance Method Details

#==(node) ⇒ Object

Compares with node.



542
543
544
545
546
547
548
549
550
551
552
 
# File 'lib/logic_tools/logictree.rb', line 542

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.



489
490
491
492
493
494
495
 
# 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) ⇒ 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) 


579
580
581
582
583
584
585
586
587
588
589
590
591
592
 
# 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

#distribute(dop, node) ⇒ Object

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

according to the +dop+ operator.



715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
 
# File 'lib/logic_tools/logictree.rb', line 715

def distribute(dop,node) # :nodoc:
    # print "distribute 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.



498
499
500
501
502
503
504
505
 
# File 'lib/logic_tools/logictree.rb', line 498

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.



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

def flatten # :nodoc:
    # print "flatten with #{self}\n"
    res = NodeNary.make(@op,*(@children.reduce([]) do |nchildren,child|
        if (child.op == self.op) then
            # nchildren.push(*child)
            nchildren.push(*child.each)
        else
            nchildren << child
        end
    end)).reduce
    # print "result #{res}\n"
    return res
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.



701
702
703
704
705
706
707
708
709
710
711
 
# File 'lib/logic_tools/logictree.rb', line 701

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)
            nchildren.push(*child.each)
        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



535
536
537
538
539
 
# File 'lib/logic_tools/logictree.rb', line 535

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) 


558
559
560
561
562
563
564
565
566
567
568
569
570
571
 
# 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? ⇒ Boolean

Tells if the node is a parent.

Returns:

  • (Boolean) 


481
482
483
 
# File 'lib/logic_tools/logictree.rb', line 481

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.



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
671
672
673
674
675
676
677
678
679
680
 
# 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 ⇒ Object

Creates a new node whose childrens are sorted.



508
509
510
 
# File 'lib/logic_tools/logictree.rb', line 508

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

#to_sym ⇒ Object

Converts to a symbol.



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

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.



513
514
515
516
517
518
519
520
521
522
523
524
 
# 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