|
//---------------------------------------------------------------------
// <copyright file="Util.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Globalization;
using System.Diagnostics;
namespace System.Data.Common.Utils {
// Miscellaneous helper routines
internal static class Helpers {
#region Trace methods
// effects: Trace args according to the CLR format string with a new line
internal static void FormatTraceLine(string format, params object[] args) {
Trace.WriteLine(String.Format(CultureInfo.InvariantCulture, format, args));
}
// effects: Trace the string with a new line
internal static void StringTrace(string arg) {
Trace.Write(arg);
}
// effects: Trace the string without adding a new line
internal static void StringTraceLine(string arg) {
Trace.WriteLine(arg);
}
#endregion
#region Misc Helpers
// effects: compares two sets using the given comparer - removes
// duplicates if they exist
internal static bool IsSetEqual<Type>(IEnumerable<Type> list1, IEnumerable<Type> list2, IEqualityComparer<Type> comparer)
{
Set<Type> set1 = new Set<Type>(list1, comparer);
Set<Type> set2 = new Set<Type>(list2, comparer);
return set1.SetEquals(set2);
}
// effects: Given a stream of values of type "SubType", returns a
// stream of values of type "SuperType" where SuperType is a
// superclass/supertype of SubType
internal static IEnumerable<SuperType> AsSuperTypeList<SubType, SuperType>(IEnumerable<SubType> values)
where SubType : SuperType {
foreach (SubType value in values) {
yield return value;
}
}
/// <summary>
/// Returns a new array with the first element equal to <paramref name="arg"/> and the remaining
/// elements taken from <paramref name="args"/>.
/// </summary>
/// <typeparam name="TElement">The element type of the arrays</typeparam>
/// <param name="args">An array that provides the successive elements of the new array</param>
/// <param name="arg">An instance the provides the first element of the new array</param>
/// <returns>A new array containing the specified argument as the first element and the specified successive elements</returns>
internal static TElement[] Prepend<TElement>(TElement[] args, TElement arg)
{
Debug.Assert(args != null, "Ensure 'args' is non-null before calling Prepend");
TElement[] retVal = new TElement[args.Length + 1];
retVal[0] = arg;
for (int idx = 0; idx < args.Length; idx++)
{
retVal[idx + 1] = args[idx];
}
return retVal;
}
/// <summary>
/// Builds a balanced binary tree with the specified nodes as leaves.
/// Note that the current elements of <paramref name="nodes"/> MAY be overwritten
/// as the leaves are combined to produce the tree.
/// </summary>
/// <typeparam name="TNode">The type of each node in the tree</typeparam>
/// <param name="nodes">The leaf nodes to combine into an balanced binary tree</param>
/// <param name="combinator">A function that produces a new node that is the combination of the two specified argument nodes</param>
/// <returns>The single node that is the root of the balanced binary tree</returns>
internal static TNode BuildBalancedTreeInPlace<TNode>(IList<TNode> nodes, Func<TNode, TNode, TNode> combinator)
{
EntityUtil.CheckArgumentNull(nodes, "nodes");
EntityUtil.CheckArgumentNull(combinator, "combinator");
Debug.Assert(nodes.Count > 0, "At least one node is required");
// If only one node is present, return the single node.
if (nodes.Count == 1)
{
return nodes[0];
}
// For the two-node case, simply combine the two nodes and return the result.
if (nodes.Count == 2)
{
return combinator(nodes[0], nodes[1]);
}
//
// Build the balanced tree in a bottom-up fashion.
// On each iteration, an even number of nodes are paired off using the
// combinator function, reducing the total number of available leaf nodes
// by half each time. If the number of nodes in an iteration is not even,
// the 'last' node in the set is omitted, then combined with the last pair
// that is produced.
// Nodes are collected from left to right with newly combined nodes overwriting
// nodes from the previous iteration that have already been consumed (as can
// be seen by 'writePos' lagging 'readPos' in the main statement of the loop below).
// When a single available leaf node remains, this node is the root of the
// balanced binary tree and can be returned to the caller.
//
int nodesToPair = nodes.Count;
while (nodesToPair != 1)
{
bool combineModulo = ((nodesToPair & 0x1) == 1);
if (combineModulo)
{
nodesToPair--;
}
int writePos = 0;
for (int readPos = 0; readPos < nodesToPair; readPos += 2)
{
nodes[writePos++] = combinator(nodes[readPos], nodes[readPos + 1]);
}
if (combineModulo)
{
int updatePos = writePos - 1;
nodes[updatePos] = combinator(nodes[updatePos], nodes[nodesToPair]);
}
nodesToPair /= 2;
}
return nodes[0];
}
/// <summary>
/// Uses a stack to non-recursively traverse a given tree structure and retrieve the leaf nodes.
/// </summary>
/// <typeparam name="TNode">The type of each node in the tree structure</typeparam>
/// <param name="root">The node that represents the root of the tree</param>
/// <param name="isLeaf">A function that determines whether or not a given node should be considered a leaf node</param>
/// <param name="getImmediateSubNodes">A function that traverses the tree by retrieving the <b>immediate</b> descendants of a (non-leaf) node.</param>
/// <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>
internal static IEnumerable<TNode> GetLeafNodes<TNode>(TNode root, Func<TNode, bool> isLeaf, Func<TNode, IEnumerable<TNode>> getImmediateSubNodes)
{
EntityUtil.CheckArgumentNull(isLeaf, "isLeaf");
EntityUtil.CheckArgumentNull(getImmediateSubNodes, "getImmediateSubNodes");
Stack<TNode> nodes = new Stack<TNode>();
nodes.Push(root);
while (nodes.Count > 0)
{
TNode current = nodes.Pop();
if (isLeaf(current))
{
yield return current;
}
else
{
List<TNode> childNodes = new List<TNode>(getImmediateSubNodes(current));
for (int idx = childNodes.Count - 1; idx > -1; idx--)
{
nodes.Push(childNodes[idx]);
}
}
}
}
#endregion
}
}
|