Simplifier.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / Simplifier.cs / 2 / Simplifier.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Common.Utils; 
using System.Data.Mapping.ViewGeneration.Structures;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics; 
using System.Data.Metadata.Edm;
using System.Linq; 
 
namespace System.Data.Mapping.ViewGeneration {
 
    // This class simplifies an extent's view. Given a view, runs the TM/SP
    // rules to remove unnecessary self-joins or self-unions
    internal class Simplifier : InternalBase {
 
 		#region Constructor
		private Simplifier(CellNormalizer normalizer) { 
			m_normalizer = normalizer; 
		}
 		#endregion 

		#region Fields
 		private CellNormalizer m_normalizer;
 		#endregion 

		#region Exposed Methods 
        // effects: see CellTreeNode.Simplify below 
        internal static CellTreeNode Simplify(CellTreeNode rootNode, bool canBooleansOverlap) {
            Simplifier simplifier = new Simplifier(rootNode.CellNormalizer); 
            return simplifier.SimplifyTree(rootNode, canBooleansOverlap);
        }

 		// effects: Simplifies the tree rooted at rootNode and returns a new 
        // tree -- it ensures that the returned tree has at most one node for
        // any particular extent unless the tree has nodes of the same extent 
        // embedded two leaves below LASJ or LOJ, e.g., if we have a tree 
        // (where Ni indicates a node for extent i - one Ni can be different
        // from anohter Ni: 
        // [N0 IJ N1] LASJ N0 --> This will not be simplified
        // canBooleansOverlap indicates whether an original input cell
        // contributes to multiple nodes in this tree, e.g., V1 IJ V2 UNION V2 IJ V3
        private CellTreeNode SimplifyTree(CellTreeNode rootNode, bool canBooleansOverlap) { 

            if (rootNode is LeafCellTreeNode) { // View already simple! 
                return rootNode; 
            }
            Debug.Assert(rootNode.OpType == CellTreeOpType.LOJ || rootNode.OpType == CellTreeOpType.IJ || 
                         rootNode.OpType == CellTreeOpType.FOJ || rootNode.OpType == CellTreeOpType.Union ||
                         rootNode.OpType == CellTreeOpType.LASJ,
                         "Only handle these operations");
 
            // Before we apply any rule, check if we can improve the opportunity to
            // collapse the nodes 
            rootNode = RestructureTreeForMerges(rootNode); 

            List children = rootNode.Children; 
            Debug.Assert(children.Count > 0, "OpCellTreeNode has no children?");

            // Apply recursively
            for (int i = 0; i < children.Count; i++) { 
                children[i] = SimplifyTree(children[i], canBooleansOverlap);
            } 
 
            // Essentially, we have a node with IJ, LOJ, U or FOJ type that
            // has some children. Check if some of the children can be merged 
            // with one another using the corresponding TM/SP rule

            // Ops such as IJ, Union and FOJ are associative, i.e., A op (B
            // op C) is the same as (A op B) op C. This is not true for LOJ 
            // and LASJ
            bool isAssociativeOp = CellTreeNode.IsAssociativeOp(rootNode.OpType); 
            if (isAssociativeOp) { 
                // Group all the leaf cells of an extent together so that we can
                // later simply run through them without running nested loops 
                // We do not do this for LOJ/LASJ nodes since LOJ (LASJ) is not commutative
                // (or associative);
                children = GroupLeafChildrenByExtent(children);
            } else { 
                children = GroupNonAssociativeLeafChildren(children);
            } 
 
            // childrenSet keeps track of the children that need to be procesed/partitioned
            OpCellTreeNode newNode = new OpCellTreeNode(m_normalizer, rootNode.OpType); 
            CellTreeNode lastChild = null;
            bool skipRest = false;
            foreach (CellTreeNode child in children) {
                if (lastChild == null) { 
                    // First time in the loop. Just set lastChild
                    lastChild = child; 
                    continue; 
                }
 
                bool mergedOk = false;
                // try to merge lastChild and child
                if (false == skipRest && lastChild.OpType == CellTreeOpType.Leaf &&
                    child.OpType == CellTreeOpType.Leaf) { 
                    // Both are cell queries. Can try to merge them
                    // We do not add lastChild since it could merge 
                    // further. It will be added in a later loop or outside the loop 
                    mergedOk = TryMergeCellQueries(rootNode.OpType, canBooleansOverlap, ref lastChild, child);
                } 

                if (false == mergedOk) {
                    // No merge occurred. Simply add the previous child as it
                    // is (Note lastChild will be added in the next loop or if 
                    // the loop finishes, outside the loop
                    newNode.Add(lastChild); 
                    lastChild = child; 
                    if (false == isAssociativeOp) {
                        // LOJ is not associative: 
                        // (P loj PA) loj PO != P loj (PA loj PO). The RHS does not have
                        // Persons who have orders but no addresses
                        skipRest = true;
                    } 
                }
            } 
 
            newNode.Add(lastChild);
            CellTreeNode result = newNode.AssociativeFlatten(); 
            return result;
        }
        #endregion
 
        #region Private Methods
        // effects: Restructure tree so that it is better positioned for merges 
        private CellTreeNode RestructureTreeForMerges(CellTreeNode rootNode) { 
            List children = rootNode.Children;
            if (CellTreeNode.IsAssociativeOp(rootNode.OpType) == false || children.Count <= 1) { 
                return rootNode;
            }

            // If this node's operator is associative and each child's 
            // operator is also associative, check if there is a common set
            // of leaf nodes across all grandchildren 
 
            Set commonGrandChildren = GetCommonGrandChildren(children);
            if (commonGrandChildren == null) { 
                return rootNode;
            }

            CellTreeOpType commonChildOpType = children[0].OpType; 

            //  We do have the structure that we are looking for 
            // (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) becomes 
            // common op2 (gc2 op1 gc3 op1 gc4)
            // e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S) 
            // becomes A IJ B IJ ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))

            // From each child in children, get the nodes other than commonGrandChildren - these are gc2, gc3, ...
            // Each gc2 must be connected by op2 as before, i.e., ABC + ACD = A(BC + CD) 

            // All children must be OpCellTreeNodes! 
            List newChildren = new List(children.Count); 
            foreach (OpCellTreeNode child in children) {
                // Remove all children in child that belong to commonGrandChildren 
                // All grandChildren must be leaf nodes at this point
                List newGrandChildren = new List(child.Children.Count);
                foreach (LeafCellTreeNode grandChild in child.Children) {
                    if (commonGrandChildren.Contains(grandChild) == false) { 
                        newGrandChildren.Add(grandChild);
                    } 
                } 
                // In the above example, child.OpType is IJ
                Debug.Assert(child.OpType == commonChildOpType); 
                OpCellTreeNode newChild = new OpCellTreeNode(m_normalizer, child.OpType,
                                                             Helpers.AsSuperTypeList(newGrandChildren));
                newChildren.Add(newChild);
            } 
            // Connect gc2 op1 gc3 op1 gc4 - op1 is UNION in this
            // ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S)) 
            // rootNode.Type is UNION 
            CellTreeNode remainingNodes = new OpCellTreeNode(m_normalizer, rootNode.OpType,
                                                             Helpers.AsSuperTypeList(newChildren)); 
            // Take the common grandchildren and connect via commonChildType
            // i.e., A IJ B
            CellTreeNode commonNodes = new OpCellTreeNode(m_normalizer, commonChildOpType,
                                                            Helpers.AsSuperTypeList(commonGrandChildren)); 

            // Connect both by commonChildType 
            CellTreeNode result = new OpCellTreeNode(m_normalizer, commonChildOpType, 
                                                     new CellTreeNode[] { commonNodes, remainingNodes });
 
            result = result.AssociativeFlatten();
            return result;
        }
 
        // effects: Given a set of nodes, determines if all nodes are the exact same associative opType AND
        // there are leaf children that are common across the children "nodes". If there are any, 
        // returns them. Else return null 
        private static Set GetCommonGrandChildren(List nodes) {
            Set commonLeaves = null; 

            // We could make this general and apply recursively but we don't for now

            // Look for a tree of the form: (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) 
            // e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
            // Where op1 and op2 are associative and common, gc2 etc are leaf nodes 
            CellTreeOpType commonChildOpType = CellTreeOpType.Leaf; 

            foreach (CellTreeNode node in nodes) { 
                OpCellTreeNode opNode = node as OpCellTreeNode;
                if (opNode == null) {
                    return null;
                } 
                Debug.Assert(opNode.OpType != CellTreeOpType.Leaf, "Leaf type for op cell node?");
                // Now check for whether the op is associative and the same as the previous one 
                if (commonChildOpType == CellTreeOpType.Leaf) { 
                    commonChildOpType = opNode.OpType;
                } else if (CellTreeNode.IsAssociativeOp(opNode.OpType) == false || commonChildOpType != opNode.OpType) { 
                    return null;
                }

                // Make sure all the children are leaf children 
                Set nodeChildrenSet = new Set(LeafCellTreeNode.EqualityComparer);
                foreach (CellTreeNode grandChild in opNode.Children) { 
                    LeafCellTreeNode leafGrandChild = grandChild as LeafCellTreeNode; 
                    if (leafGrandChild == null) {
                        return null; 
                    }
                    nodeChildrenSet.Add(leafGrandChild);
                }
 
                if (commonLeaves == null) {
                    commonLeaves = nodeChildrenSet; 
                } else { 
                    commonLeaves.Intersect(nodeChildrenSet);
                } 
            }

            if (commonLeaves.Count == 0) {
                // No restructuring possible 
                return null;
            } 
            return commonLeaves; 
        }
        // effects: Given a list of node, produces a new list in which all 
        // leaf nodes of the same extent are adjacent to each other. Non-leaf
        // nodes are also adjacent to each other. CHANGE_[....]_IMPROVE: Merge with GroupByRightExtent
        private static List GroupLeafChildrenByExtent(List nodes) {
            // Keep track of leaf cells for each extent 
            KeyToListMap extentMap =
                new KeyToListMap(EqualityComparer.Default); 
 
            List newNodes = new List();
            foreach (CellTreeNode node in nodes) { 
                LeafCellTreeNode leafNode = node as LeafCellTreeNode;
                // All non-leaf nodes are added to the result now
                // leaf nodes are added outside the loop
                if (leafNode != null) { 
                    extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
                } else { 
                    newNodes.Add(node); 
                }
            } 
            // Go through the map and add the leaf children
            newNodes.AddRange(extentMap.AllValues);
            return newNodes;
        } 

        // effects: A restrictive version of GroupLeafChildrenByExtent -- 
        // only for LASJ and LOJ nodes (works for LOJ only when A LOJ B LOJ C 
        // s.t., B and C are subsets of A -- in our case that is how LOJs are constructed
        private static List GroupNonAssociativeLeafChildren(List nodes) { 
            // Keep track of leaf cells for each extent ignoring the 0th child
            KeyToListMap extentMap =
                new KeyToListMap(EqualityComparer.Default);
 
            List newNodes = new List();
            List nonLeafNodes = new List(); 
            // Add the 0th child 
            newNodes.Add(nodes[0]);
            for (int i = 1; i < nodes.Count; i++) { 
                CellTreeNode node = nodes[i];
                LeafCellTreeNode leafNode = node as LeafCellTreeNode;
                // All non-leaf nodes are added to the result now
                // leaf nodes are added outside the loop 
                if (leafNode != null) {
                    extentMap.Add(leafNode.RightCellQuery.Extent, leafNode); 
                } else { 
                    nonLeafNodes.Add(node);
                } 
            }
            // Go through the map and add the leaf children
            // If a group of nodes exists for the 0th node's extent -- place
            // that group first 
            LeafCellTreeNode firstNode = nodes[0] as LeafCellTreeNode;
            if (firstNode != null) { 
                EntitySetBase firstExtent = firstNode.RightCellQuery.Extent; 
                if (extentMap.ContainsKey(firstExtent)) {
                    newNodes.AddRange(extentMap.ListForKey(firstExtent)); 
                    // Remove this set from the map
                    extentMap.RemoveKey(firstExtent);
                }
            } 
            newNodes.AddRange(extentMap.AllValues);
            newNodes.AddRange(nonLeafNodes); 
            return newNodes; 
        }
 
        // requires: node1 and node2 are two children of the same parent
        // connected by opType
        // effects: Given two cell tree nodes, node1 and node2, runs the
        // TM/SP rule on them to merge them (if they belong to the same 
        // extent). Returns true if the merge succeeds
        private bool TryMergeCellQueries(CellTreeOpType opType, bool canBooleansOverlap, ref CellTreeNode node1, 
                                         CellTreeNode node2) { 

            LeafCellTreeNode leaf1 = node1 as LeafCellTreeNode; 
            LeafCellTreeNode leaf2 = node2 as LeafCellTreeNode;

            Debug.Assert(leaf1 != null, "Merge only possible on leaf nodes (1)");
            Debug.Assert(leaf2 != null, "Merge only possible on leaf nodes (2)"); 

            CellQuery node1Query = leaf1.RightCellQuery; 
            CellQuery node2Query = leaf2.RightCellQuery; 

            // Try to merge them using the TM/SP rule for opType 
            CellQuery mergedCellQuery;
            // Since we are always simplifying the cell queries of the right
            // side, we need to get the rightdomainmap
            if (false == node1Query.TryMerge(node2Query, opType, canBooleansOverlap, m_normalizer.MemberMaps.RightDomainMap, out mergedCellQuery)) { 
                return false;
            } 
 
            // Create a temporary node and add the two children
            // so that we can get the merged selectiondomains and attributes 
            // Note that temp.SelectionDomain below determines the domain
            // based on the opType, e.g., for IJ, it intersects the
            // multiconstants of all the children
            OpCellTreeNode temp = new OpCellTreeNode(m_normalizer, opType); 
            temp.Add(node1);
            temp.Add(node2); 
            // Note: We are losing the original cell number information here and the line number information 
            // But we will not raise any
 
            // We do not create CellExpressions with LOJ, FOJ - canBooleansOverlap is true for validation
            CellTreeOpType inputOpType = opType;
            if (canBooleansOverlap == false && (opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ)) {
                inputOpType = CellTreeOpType.IJ; 
            }
 
            LeftCellWrapper wrapper = new LeftCellWrapper(leaf1.LeftCellWrapper.SchemaContext, temp.Attributes, 
                                                          temp.LeftFragmentQuery,
                                                          mergedCellQuery, m_normalizer.MemberMaps, 
                                                          leaf1.LeftCellWrapper.Cells.Concat(leaf2.LeftCellWrapper.Cells));
            node1 = new LeafCellTreeNode(m_normalizer, wrapper, temp.RightFragmentQuery);
            return true;
        } 

        #endregion 
 
		#region String methods
		internal override void ToCompactString(StringBuilder builder) { 
			m_normalizer.MemberMaps.ProjectedSlotMap.ToCompactString(builder);
 		}
		#endregion
 
 	}
} 

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

using System.Data.Common.Utils; 
using System.Data.Mapping.ViewGeneration.Structures;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics; 
using System.Data.Metadata.Edm;
using System.Linq; 
 
namespace System.Data.Mapping.ViewGeneration {
 
    // This class simplifies an extent's view. Given a view, runs the TM/SP
    // rules to remove unnecessary self-joins or self-unions
    internal class Simplifier : InternalBase {
 
 		#region Constructor
		private Simplifier(CellNormalizer normalizer) { 
			m_normalizer = normalizer; 
		}
 		#endregion 

		#region Fields
 		private CellNormalizer m_normalizer;
 		#endregion 

		#region Exposed Methods 
        // effects: see CellTreeNode.Simplify below 
        internal static CellTreeNode Simplify(CellTreeNode rootNode, bool canBooleansOverlap) {
            Simplifier simplifier = new Simplifier(rootNode.CellNormalizer); 
            return simplifier.SimplifyTree(rootNode, canBooleansOverlap);
        }

 		// effects: Simplifies the tree rooted at rootNode and returns a new 
        // tree -- it ensures that the returned tree has at most one node for
        // any particular extent unless the tree has nodes of the same extent 
        // embedded two leaves below LASJ or LOJ, e.g., if we have a tree 
        // (where Ni indicates a node for extent i - one Ni can be different
        // from anohter Ni: 
        // [N0 IJ N1] LASJ N0 --> This will not be simplified
        // canBooleansOverlap indicates whether an original input cell
        // contributes to multiple nodes in this tree, e.g., V1 IJ V2 UNION V2 IJ V3
        private CellTreeNode SimplifyTree(CellTreeNode rootNode, bool canBooleansOverlap) { 

            if (rootNode is LeafCellTreeNode) { // View already simple! 
                return rootNode; 
            }
            Debug.Assert(rootNode.OpType == CellTreeOpType.LOJ || rootNode.OpType == CellTreeOpType.IJ || 
                         rootNode.OpType == CellTreeOpType.FOJ || rootNode.OpType == CellTreeOpType.Union ||
                         rootNode.OpType == CellTreeOpType.LASJ,
                         "Only handle these operations");
 
            // Before we apply any rule, check if we can improve the opportunity to
            // collapse the nodes 
            rootNode = RestructureTreeForMerges(rootNode); 

            List children = rootNode.Children; 
            Debug.Assert(children.Count > 0, "OpCellTreeNode has no children?");

            // Apply recursively
            for (int i = 0; i < children.Count; i++) { 
                children[i] = SimplifyTree(children[i], canBooleansOverlap);
            } 
 
            // Essentially, we have a node with IJ, LOJ, U or FOJ type that
            // has some children. Check if some of the children can be merged 
            // with one another using the corresponding TM/SP rule

            // Ops such as IJ, Union and FOJ are associative, i.e., A op (B
            // op C) is the same as (A op B) op C. This is not true for LOJ 
            // and LASJ
            bool isAssociativeOp = CellTreeNode.IsAssociativeOp(rootNode.OpType); 
            if (isAssociativeOp) { 
                // Group all the leaf cells of an extent together so that we can
                // later simply run through them without running nested loops 
                // We do not do this for LOJ/LASJ nodes since LOJ (LASJ) is not commutative
                // (or associative);
                children = GroupLeafChildrenByExtent(children);
            } else { 
                children = GroupNonAssociativeLeafChildren(children);
            } 
 
            // childrenSet keeps track of the children that need to be procesed/partitioned
            OpCellTreeNode newNode = new OpCellTreeNode(m_normalizer, rootNode.OpType); 
            CellTreeNode lastChild = null;
            bool skipRest = false;
            foreach (CellTreeNode child in children) {
                if (lastChild == null) { 
                    // First time in the loop. Just set lastChild
                    lastChild = child; 
                    continue; 
                }
 
                bool mergedOk = false;
                // try to merge lastChild and child
                if (false == skipRest && lastChild.OpType == CellTreeOpType.Leaf &&
                    child.OpType == CellTreeOpType.Leaf) { 
                    // Both are cell queries. Can try to merge them
                    // We do not add lastChild since it could merge 
                    // further. It will be added in a later loop or outside the loop 
                    mergedOk = TryMergeCellQueries(rootNode.OpType, canBooleansOverlap, ref lastChild, child);
                } 

                if (false == mergedOk) {
                    // No merge occurred. Simply add the previous child as it
                    // is (Note lastChild will be added in the next loop or if 
                    // the loop finishes, outside the loop
                    newNode.Add(lastChild); 
                    lastChild = child; 
                    if (false == isAssociativeOp) {
                        // LOJ is not associative: 
                        // (P loj PA) loj PO != P loj (PA loj PO). The RHS does not have
                        // Persons who have orders but no addresses
                        skipRest = true;
                    } 
                }
            } 
 
            newNode.Add(lastChild);
            CellTreeNode result = newNode.AssociativeFlatten(); 
            return result;
        }
        #endregion
 
        #region Private Methods
        // effects: Restructure tree so that it is better positioned for merges 
        private CellTreeNode RestructureTreeForMerges(CellTreeNode rootNode) { 
            List children = rootNode.Children;
            if (CellTreeNode.IsAssociativeOp(rootNode.OpType) == false || children.Count <= 1) { 
                return rootNode;
            }

            // If this node's operator is associative and each child's 
            // operator is also associative, check if there is a common set
            // of leaf nodes across all grandchildren 
 
            Set commonGrandChildren = GetCommonGrandChildren(children);
            if (commonGrandChildren == null) { 
                return rootNode;
            }

            CellTreeOpType commonChildOpType = children[0].OpType; 

            //  We do have the structure that we are looking for 
            // (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) becomes 
            // common op2 (gc2 op1 gc3 op1 gc4)
            // e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S) 
            // becomes A IJ B IJ ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S))

            // From each child in children, get the nodes other than commonGrandChildren - these are gc2, gc3, ...
            // Each gc2 must be connected by op2 as before, i.e., ABC + ACD = A(BC + CD) 

            // All children must be OpCellTreeNodes! 
            List newChildren = new List(children.Count); 
            foreach (OpCellTreeNode child in children) {
                // Remove all children in child that belong to commonGrandChildren 
                // All grandChildren must be leaf nodes at this point
                List newGrandChildren = new List(child.Children.Count);
                foreach (LeafCellTreeNode grandChild in child.Children) {
                    if (commonGrandChildren.Contains(grandChild) == false) { 
                        newGrandChildren.Add(grandChild);
                    } 
                } 
                // In the above example, child.OpType is IJ
                Debug.Assert(child.OpType == commonChildOpType); 
                OpCellTreeNode newChild = new OpCellTreeNode(m_normalizer, child.OpType,
                                                             Helpers.AsSuperTypeList(newGrandChildren));
                newChildren.Add(newChild);
            } 
            // Connect gc2 op1 gc3 op1 gc4 - op1 is UNION in this
            // ((X IJ Y) UNION (Y IJ Z) UNION (R IJ S)) 
            // rootNode.Type is UNION 
            CellTreeNode remainingNodes = new OpCellTreeNode(m_normalizer, rootNode.OpType,
                                                             Helpers.AsSuperTypeList(newChildren)); 
            // Take the common grandchildren and connect via commonChildType
            // i.e., A IJ B
            CellTreeNode commonNodes = new OpCellTreeNode(m_normalizer, commonChildOpType,
                                                            Helpers.AsSuperTypeList(commonGrandChildren)); 

            // Connect both by commonChildType 
            CellTreeNode result = new OpCellTreeNode(m_normalizer, commonChildOpType, 
                                                     new CellTreeNode[] { commonNodes, remainingNodes });
 
            result = result.AssociativeFlatten();
            return result;
        }
 
        // effects: Given a set of nodes, determines if all nodes are the exact same associative opType AND
        // there are leaf children that are common across the children "nodes". If there are any, 
        // returns them. Else return null 
        private static Set GetCommonGrandChildren(List nodes) {
            Set commonLeaves = null; 

            // We could make this general and apply recursively but we don't for now

            // Look for a tree of the form: (common op2 gc2) op1 (common op2 gc3) op1 (common op2 gc4) 
            // e.g., (A IJ B IJ X IJ Y) UNION (A IJ B IJ Y IJ Z) UNION (A IJ B IJ R IJ S)
            // Where op1 and op2 are associative and common, gc2 etc are leaf nodes 
            CellTreeOpType commonChildOpType = CellTreeOpType.Leaf; 

            foreach (CellTreeNode node in nodes) { 
                OpCellTreeNode opNode = node as OpCellTreeNode;
                if (opNode == null) {
                    return null;
                } 
                Debug.Assert(opNode.OpType != CellTreeOpType.Leaf, "Leaf type for op cell node?");
                // Now check for whether the op is associative and the same as the previous one 
                if (commonChildOpType == CellTreeOpType.Leaf) { 
                    commonChildOpType = opNode.OpType;
                } else if (CellTreeNode.IsAssociativeOp(opNode.OpType) == false || commonChildOpType != opNode.OpType) { 
                    return null;
                }

                // Make sure all the children are leaf children 
                Set nodeChildrenSet = new Set(LeafCellTreeNode.EqualityComparer);
                foreach (CellTreeNode grandChild in opNode.Children) { 
                    LeafCellTreeNode leafGrandChild = grandChild as LeafCellTreeNode; 
                    if (leafGrandChild == null) {
                        return null; 
                    }
                    nodeChildrenSet.Add(leafGrandChild);
                }
 
                if (commonLeaves == null) {
                    commonLeaves = nodeChildrenSet; 
                } else { 
                    commonLeaves.Intersect(nodeChildrenSet);
                } 
            }

            if (commonLeaves.Count == 0) {
                // No restructuring possible 
                return null;
            } 
            return commonLeaves; 
        }
        // effects: Given a list of node, produces a new list in which all 
        // leaf nodes of the same extent are adjacent to each other. Non-leaf
        // nodes are also adjacent to each other. CHANGE_[....]_IMPROVE: Merge with GroupByRightExtent
        private static List GroupLeafChildrenByExtent(List nodes) {
            // Keep track of leaf cells for each extent 
            KeyToListMap extentMap =
                new KeyToListMap(EqualityComparer.Default); 
 
            List newNodes = new List();
            foreach (CellTreeNode node in nodes) { 
                LeafCellTreeNode leafNode = node as LeafCellTreeNode;
                // All non-leaf nodes are added to the result now
                // leaf nodes are added outside the loop
                if (leafNode != null) { 
                    extentMap.Add(leafNode.RightCellQuery.Extent, leafNode);
                } else { 
                    newNodes.Add(node); 
                }
            } 
            // Go through the map and add the leaf children
            newNodes.AddRange(extentMap.AllValues);
            return newNodes;
        } 

        // effects: A restrictive version of GroupLeafChildrenByExtent -- 
        // only for LASJ and LOJ nodes (works for LOJ only when A LOJ B LOJ C 
        // s.t., B and C are subsets of A -- in our case that is how LOJs are constructed
        private static List GroupNonAssociativeLeafChildren(List nodes) { 
            // Keep track of leaf cells for each extent ignoring the 0th child
            KeyToListMap extentMap =
                new KeyToListMap(EqualityComparer.Default);
 
            List newNodes = new List();
            List nonLeafNodes = new List(); 
            // Add the 0th child 
            newNodes.Add(nodes[0]);
            for (int i = 1; i < nodes.Count; i++) { 
                CellTreeNode node = nodes[i];
                LeafCellTreeNode leafNode = node as LeafCellTreeNode;
                // All non-leaf nodes are added to the result now
                // leaf nodes are added outside the loop 
                if (leafNode != null) {
                    extentMap.Add(leafNode.RightCellQuery.Extent, leafNode); 
                } else { 
                    nonLeafNodes.Add(node);
                } 
            }
            // Go through the map and add the leaf children
            // If a group of nodes exists for the 0th node's extent -- place
            // that group first 
            LeafCellTreeNode firstNode = nodes[0] as LeafCellTreeNode;
            if (firstNode != null) { 
                EntitySetBase firstExtent = firstNode.RightCellQuery.Extent; 
                if (extentMap.ContainsKey(firstExtent)) {
                    newNodes.AddRange(extentMap.ListForKey(firstExtent)); 
                    // Remove this set from the map
                    extentMap.RemoveKey(firstExtent);
                }
            } 
            newNodes.AddRange(extentMap.AllValues);
            newNodes.AddRange(nonLeafNodes); 
            return newNodes; 
        }
 
        // requires: node1 and node2 are two children of the same parent
        // connected by opType
        // effects: Given two cell tree nodes, node1 and node2, runs the
        // TM/SP rule on them to merge them (if they belong to the same 
        // extent). Returns true if the merge succeeds
        private bool TryMergeCellQueries(CellTreeOpType opType, bool canBooleansOverlap, ref CellTreeNode node1, 
                                         CellTreeNode node2) { 

            LeafCellTreeNode leaf1 = node1 as LeafCellTreeNode; 
            LeafCellTreeNode leaf2 = node2 as LeafCellTreeNode;

            Debug.Assert(leaf1 != null, "Merge only possible on leaf nodes (1)");
            Debug.Assert(leaf2 != null, "Merge only possible on leaf nodes (2)"); 

            CellQuery node1Query = leaf1.RightCellQuery; 
            CellQuery node2Query = leaf2.RightCellQuery; 

            // Try to merge them using the TM/SP rule for opType 
            CellQuery mergedCellQuery;
            // Since we are always simplifying the cell queries of the right
            // side, we need to get the rightdomainmap
            if (false == node1Query.TryMerge(node2Query, opType, canBooleansOverlap, m_normalizer.MemberMaps.RightDomainMap, out mergedCellQuery)) { 
                return false;
            } 
 
            // Create a temporary node and add the two children
            // so that we can get the merged selectiondomains and attributes 
            // Note that temp.SelectionDomain below determines the domain
            // based on the opType, e.g., for IJ, it intersects the
            // multiconstants of all the children
            OpCellTreeNode temp = new OpCellTreeNode(m_normalizer, opType); 
            temp.Add(node1);
            temp.Add(node2); 
            // Note: We are losing the original cell number information here and the line number information 
            // But we will not raise any
 
            // We do not create CellExpressions with LOJ, FOJ - canBooleansOverlap is true for validation
            CellTreeOpType inputOpType = opType;
            if (canBooleansOverlap == false && (opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ)) {
                inputOpType = CellTreeOpType.IJ; 
            }
 
            LeftCellWrapper wrapper = new LeftCellWrapper(leaf1.LeftCellWrapper.SchemaContext, temp.Attributes, 
                                                          temp.LeftFragmentQuery,
                                                          mergedCellQuery, m_normalizer.MemberMaps, 
                                                          leaf1.LeftCellWrapper.Cells.Concat(leaf2.LeftCellWrapper.Cells));
            node1 = new LeafCellTreeNode(m_normalizer, wrapper, temp.RightFragmentQuery);
            return true;
        } 

        #endregion 
 
		#region String methods
		internal override void ToCompactString(StringBuilder builder) { 
			m_normalizer.MemberMaps.ProjectedSlotMap.ToCompactString(builder);
 		}
		#endregion
 
 	}
} 

// 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