Simplifier.cs source code in C# .NET

                        Code:
                         / 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Common / Utils / Boolean / Simplifier.cs / 1305376 / Simplifier.cs
                        
                        
                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
 
namespace System.Data.Common.Utils.Boolean
{ 
    // Simplifier visitor for Boolean expressions. Performs the following 
    // simplifications bottom-up:
    // - Eliminate True and False (A Or False iff. A, A And True iff. A) 
    // - Resolve tautology (A Or !A iff. True, True Or A iff. True) and
    // contradiction (A And !A iff. False, False And A iff. False)
    // - Flatten nested negations (!!A iff. A)
    // - Evaluate bound literals (!True iff. False, etc.) 
    // - Flatten unary/empty And/Or expressions
    internal class Simplifier : BasicVisitor 
    { 
        internal static readonly Simplifier Instance = new Simplifier();
 
        protected Simplifier()
        {
        }
 
        internal override BoolExpr VisitNot(NotExpr expression)
        { 
            BoolExpr child = expression.Child.Accept(this); 
            switch (child.ExprType)
            { 
                case ExprType.Not:
                    return ((NotExpr)child).Child;
                case ExprType.True: return FalseExpr.Value;
                case ExprType.False: return TrueExpr.Value; 
                default: return base.VisitNot(expression);
            } 
        } 

        internal override BoolExpr VisitAnd(AndExpr expression) 
        {
            return SimplifyTree(expression);
        }
 
        internal override BoolExpr VisitOr(OrExpr expression)
        { 
            return SimplifyTree(expression); 
        }
 
        private BoolExpr SimplifyTree(TreeExpr tree)
        {
            bool isAnd = ExprType.And == tree.ExprType;
            Debug.Assert(isAnd || ExprType.Or == tree.ExprType); 

            // Get list of simplified children, flattening nested And/Or expressions 
            List> simplifiedChildren = new List>(tree.Children.Count); 
            foreach (BoolExpr child in tree.Children)
            { 
                BoolExpr simplifiedChild = child.Accept(this);
                // And(And(A, B), C) iff. And(A, B, C)
                // Or(Or(A, B), C) iff. Or(A, B, C)
                if (simplifiedChild.ExprType == tree.ExprType) 
                {
                    simplifiedChildren.AddRange(((TreeExpr)simplifiedChild).Children); 
                } 
                else
                { 
                    simplifiedChildren.Add(simplifiedChild);
                }
            }
 
            // Track negated children separately to identify tautologies and contradictions
            Dictionary, bool> negatedChildren = new Dictionary, bool>(tree.Children.Count); 
            List> otherChildren = new List>(tree.Children.Count); 
            foreach (BoolExpr simplifiedChild in simplifiedChildren)
            { 
                switch (simplifiedChild.ExprType)
                {
                    case ExprType.Not:
                        negatedChildren[((NotExpr)simplifiedChild).Child] = true; 
                        break;
                    case ExprType.False: 
                        // False And A --> False 
                        if (isAnd) { return FalseExpr.Value; }
                        // False || A --> A (omit False from child collections) 
                        break;
                    case ExprType.True:
                        // True Or A --> True
                        if (!isAnd) { return TrueExpr.Value; } 
                        // True And A --> A (omit True from child collections)
                        break; 
                    default: 
                        otherChildren.Add(simplifiedChild);
                        break; 
                }
            }
            List> children = new List>();
            foreach (BoolExpr child in otherChildren) 
            {
                if (negatedChildren.ContainsKey(child)) 
                { 
                    // A && !A --> False, A || !A --> True
                    if (isAnd) { return FalseExpr.Value; } 
                    else { return TrueExpr.Value; }
                }
                children.Add(child);
            } 
            foreach (BoolExpr child in negatedChildren.Keys)
            { 
                children.Add(child.MakeNegated()); 
            }
            if (0 == children.Count) 
            {
                // And() iff. True
                if (isAnd) { return TrueExpr.Value; }
                // Or() iff. False 
                else { return FalseExpr.Value; }
            } 
            else if (1 == children.Count) 
            {
                // Or(A) iff. A, And(A) iff. A 
                return children[0];
            }
            else
            { 
                // Construct simplified And/Or expression
                TreeExpr result; 
                if (isAnd) { result = new AndExpr(children); } 
                else { result = new OrExpr(children); }
                return result; 
            }
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
 
namespace System.Data.Common.Utils.Boolean
{ 
    // Simplifier visitor for Boolean expressions. Performs the following 
    // simplifications bottom-up:
    // - Eliminate True and False (A Or False iff. A, A And True iff. A) 
    // - Resolve tautology (A Or !A iff. True, True Or A iff. True) and
    // contradiction (A And !A iff. False, False And A iff. False)
    // - Flatten nested negations (!!A iff. A)
    // - Evaluate bound literals (!True iff. False, etc.) 
    // - Flatten unary/empty And/Or expressions
    internal class Simplifier : BasicVisitor 
    { 
        internal static readonly Simplifier Instance = new Simplifier();
 
        protected Simplifier()
        {
        }
 
        internal override BoolExpr VisitNot(NotExpr expression)
        { 
            BoolExpr child = expression.Child.Accept(this); 
            switch (child.ExprType)
            { 
                case ExprType.Not:
                    return ((NotExpr)child).Child;
                case ExprType.True: return FalseExpr.Value;
                case ExprType.False: return TrueExpr.Value; 
                default: return base.VisitNot(expression);
            } 
        } 

        internal override BoolExpr VisitAnd(AndExpr expression) 
        {
            return SimplifyTree(expression);
        }
 
        internal override BoolExpr VisitOr(OrExpr expression)
        { 
            return SimplifyTree(expression); 
        }
 
        private BoolExpr SimplifyTree(TreeExpr tree)
        {
            bool isAnd = ExprType.And == tree.ExprType;
            Debug.Assert(isAnd || ExprType.Or == tree.ExprType); 

            // Get list of simplified children, flattening nested And/Or expressions 
            List> simplifiedChildren = new List>(tree.Children.Count); 
            foreach (BoolExpr child in tree.Children)
            { 
                BoolExpr simplifiedChild = child.Accept(this);
                // And(And(A, B), C) iff. And(A, B, C)
                // Or(Or(A, B), C) iff. Or(A, B, C)
                if (simplifiedChild.ExprType == tree.ExprType) 
                {
                    simplifiedChildren.AddRange(((TreeExpr)simplifiedChild).Children); 
                } 
                else
                { 
                    simplifiedChildren.Add(simplifiedChild);
                }
            }
 
            // Track negated children separately to identify tautologies and contradictions
            Dictionary, bool> negatedChildren = new Dictionary, bool>(tree.Children.Count); 
            List> otherChildren = new List>(tree.Children.Count); 
            foreach (BoolExpr simplifiedChild in simplifiedChildren)
            { 
                switch (simplifiedChild.ExprType)
                {
                    case ExprType.Not:
                        negatedChildren[((NotExpr)simplifiedChild).Child] = true; 
                        break;
                    case ExprType.False: 
                        // False And A --> False 
                        if (isAnd) { return FalseExpr.Value; }
                        // False || A --> A (omit False from child collections) 
                        break;
                    case ExprType.True:
                        // True Or A --> True
                        if (!isAnd) { return TrueExpr.Value; } 
                        // True And A --> A (omit True from child collections)
                        break; 
                    default: 
                        otherChildren.Add(simplifiedChild);
                        break; 
                }
            }
            List> children = new List>();
            foreach (BoolExpr child in otherChildren) 
            {
                if (negatedChildren.ContainsKey(child)) 
                { 
                    // A && !A --> False, A || !A --> True
                    if (isAnd) { return FalseExpr.Value; } 
                    else { return TrueExpr.Value; }
                }
                children.Add(child);
            } 
            foreach (BoolExpr child in negatedChildren.Keys)
            { 
                children.Add(child.MakeNegated()); 
            }
            if (0 == children.Count) 
            {
                // And() iff. True
                if (isAnd) { return TrueExpr.Value; }
                // Or() iff. False 
                else { return FalseExpr.Value; }
            } 
            else if (1 == children.Count) 
            {
                // Or(A) iff. A, And(A) iff. A 
                return children[0];
            }
            else
            { 
                // Construct simplified And/Or expression
                TreeExpr result; 
                if (isAnd) { result = new AndExpr(children); } 
                else { result = new OrExpr(children); }
                return result; 
            }
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
Simplifier.cs source code in C# .NET

Source code for the .NET framework in C#

Code:

Link Menu
