1 //---------------------------------------------------------------------
2 // <copyright file="Util.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
8 //---------------------------------------------------------------------
12 using System.Collections;
13 using System.Collections.Generic;
15 using System.Globalization;
16 using System.Diagnostics;
18 namespace System.Data.Common.Utils {
20 // Miscellaneous helper routines
21 internal static class Helpers {
24 // effects: Trace args according to the CLR format string with a new line
25 internal static void FormatTraceLine(string format, params object[] args) {
26 Trace.WriteLine(String.Format(CultureInfo.InvariantCulture, format, args));
29 // effects: Trace the string with a new line
30 internal static void StringTrace(string arg) {
34 // effects: Trace the string without adding a new line
35 internal static void StringTraceLine(string arg) {
41 // effects: compares two sets using the given comparer - removes
42 // duplicates if they exist
43 internal static bool IsSetEqual<Type>(IEnumerable<Type> list1, IEnumerable<Type> list2, IEqualityComparer<Type> comparer)
45 Set<Type> set1 = new Set<Type>(list1, comparer);
46 Set<Type> set2 = new Set<Type>(list2, comparer);
48 return set1.SetEquals(set2);
51 // effects: Given a stream of values of type "SubType", returns a
52 // stream of values of type "SuperType" where SuperType is a
53 // superclass/supertype of SubType
54 internal static IEnumerable<SuperType> AsSuperTypeList<SubType, SuperType>(IEnumerable<SubType> values)
55 where SubType : SuperType {
56 foreach (SubType value in values) {
62 /// Returns a new array with the first element equal to <paramref name="arg"/> and the remaining
63 /// elements taken from <paramref name="args"/>.
65 /// <typeparam name="TElement">The element type of the arrays</typeparam>
66 /// <param name="args">An array that provides the successive elements of the new array</param>
67 /// <param name="arg">An instance the provides the first element of the new array</param>
68 /// <returns>A new array containing the specified argument as the first element and the specified successive elements</returns>
69 internal static TElement[] Prepend<TElement>(TElement[] args, TElement arg)
71 Debug.Assert(args != null, "Ensure 'args' is non-null before calling Prepend");
73 TElement[] retVal = new TElement[args.Length + 1];
75 for (int idx = 0; idx < args.Length; idx++)
77 retVal[idx + 1] = args[idx];
84 /// Builds a balanced binary tree with the specified nodes as leaves.
85 /// Note that the current elements of <paramref name="nodes"/> MAY be overwritten
86 /// as the leaves are combined to produce the tree.
88 /// <typeparam name="TNode">The type of each node in the tree</typeparam>
89 /// <param name="nodes">The leaf nodes to combine into an balanced binary tree</param>
90 /// <param name="combinator">A function that produces a new node that is the combination of the two specified argument nodes</param>
91 /// <returns>The single node that is the root of the balanced binary tree</returns>
92 internal static TNode BuildBalancedTreeInPlace<TNode>(IList<TNode> nodes, Func<TNode, TNode, TNode> combinator)
94 EntityUtil.CheckArgumentNull(nodes, "nodes");
95 EntityUtil.CheckArgumentNull(combinator, "combinator");
97 Debug.Assert(nodes.Count > 0, "At least one node is required");
99 // If only one node is present, return the single node.
100 if (nodes.Count == 1)
105 // For the two-node case, simply combine the two nodes and return the result.
106 if (nodes.Count == 2)
108 return combinator(nodes[0], nodes[1]);
112 // Build the balanced tree in a bottom-up fashion.
113 // On each iteration, an even number of nodes are paired off using the
114 // combinator function, reducing the total number of available leaf nodes
115 // by half each time. If the number of nodes in an iteration is not even,
116 // the 'last' node in the set is omitted, then combined with the last pair
118 // Nodes are collected from left to right with newly combined nodes overwriting
119 // nodes from the previous iteration that have already been consumed (as can
120 // be seen by 'writePos' lagging 'readPos' in the main statement of the loop below).
121 // When a single available leaf node remains, this node is the root of the
122 // balanced binary tree and can be returned to the caller.
124 int nodesToPair = nodes.Count;
125 while (nodesToPair != 1)
127 bool combineModulo = ((nodesToPair & 0x1) == 1);
134 for (int readPos = 0; readPos < nodesToPair; readPos += 2)
136 nodes[writePos++] = combinator(nodes[readPos], nodes[readPos + 1]);
141 int updatePos = writePos - 1;
142 nodes[updatePos] = combinator(nodes[updatePos], nodes[nodesToPair]);
152 /// Uses a stack to non-recursively traverse a given tree structure and retrieve the leaf nodes.
154 /// <typeparam name="TNode">The type of each node in the tree structure</typeparam>
155 /// <param name="root">The node that represents the root of the tree</param>
156 /// <param name="isLeaf">A function that determines whether or not a given node should be considered a leaf node</param>
157 /// <param name="getImmediateSubNodes">A function that traverses the tree by retrieving the <b>immediate</b> descendants of a (non-leaf) node.</param>
158 /// <returns>An enumerable containing the leaf nodes (as determined by <paramref name="isLeaf"/>) retrieved by traversing the tree from <paramref name="root"/> using <paramref name="getImmediateSubNodes"/>.</returns>
159 internal static IEnumerable<TNode> GetLeafNodes<TNode>(TNode root, Func<TNode, bool> isLeaf, Func<TNode, IEnumerable<TNode>> getImmediateSubNodes)
161 EntityUtil.CheckArgumentNull(isLeaf, "isLeaf");
162 EntityUtil.CheckArgumentNull(getImmediateSubNodes, "getImmediateSubNodes");
164 Stack<TNode> nodes = new Stack<TNode>();
167 while (nodes.Count > 0)
169 TNode current = nodes.Pop();
172 yield return current;
176 List<TNode> childNodes = new List<TNode>(getImmediateSubNodes(current));
177 for (int idx = childNodes.Count - 1; idx > -1; idx--)
179 nodes.Push(childNodes[idx]);