mcs/class/referencesource/System.Core/System/Linq/Parallel/Enumerables/AggregationMinMaxHelpers.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
   7 //
   8 // AggregationMinMaxHelpers.cs
   9 //
  10 // <OWNER>Microsoft</OWNER>
  11 //
  12 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  13
  14 using System.Collections.Generic;
  15 using System.Linq.Parallel;
  16 using System.Diagnostics.Contracts;
  17
  18 namespace System.Linq
  19 {
  20     internal static class AggregationMinMaxHelpers<T>
  21     {
  22
  23         //-----------------------------------------------------------------------------------
  24         // Helper method to find the minimum or maximum element in the source.
  25         //
  26
  27         private static T Reduce(IEnumerable<T> source, int sign)
  28         {
  29             Contract.Assert(source != null);
  30             Contract.Assert(sign == -1 || sign == 1);
  31
  32             Func<Pair<bool, T>, T, Pair<bool, T>> intermediateReduce = MakeIntermediateReduceFunction(sign);
  33             Func<Pair<bool, T>, Pair<bool, T>, Pair<bool, T>> finalReduce = MakeFinalReduceFunction(sign);
  34             Func<Pair<bool, T>, T> resultSelector = MakeResultSelectorFunction();
  35
  36             AssociativeAggregationOperator<T, Pair<bool, T>, T> aggregation =
  37                 new AssociativeAggregationOperator<T, Pair<bool, T>, T>(source, new Pair<bool, T>(false, default(T)), null,
  38                                                                         true, intermediateReduce, finalReduce, resultSelector, default(T) != null, QueryAggregationOptions.AssociativeCommutative);
  39
  40             return aggregation.Aggregate();
  41         }
  42
  43         //-----------------------------------------------------------------------------------
  44         // Helper method to find the minimum element in the source.
  45         //
  46
  47         internal static T ReduceMin(IEnumerable<T> source)
  48         {
  49             return Reduce(source, -1);
  50         }
  51
  52         //-----------------------------------------------------------------------------------
  53         // Helper method to find the maximum element in the source.
  54         //
  55
  56         internal static T ReduceMax(IEnumerable<T> source)
  57         {
  58             return Reduce(source, 1);
  59         }
  60
  61         //-----------------------------------------------------------------------------------
  62         // These methods are used to generate delegates to perform the comparisons.
  63         //
  64
  65         private static Func<Pair<bool, T>, T, Pair<bool, T>> MakeIntermediateReduceFunction(int sign)
  66         {
  67             Comparer<T> comparer = Util.GetDefaultComparer<T>();
  68
  69             // Note that we capture the 'sign' argument and 'comparer' local, and therefore the C#
  70             // compiler will transform this into an instance-based delegate, incurring an extra (hidden)
  71             // object allocation.
  72             return delegate(Pair<bool, T> accumulator, T element)
  73                        {
  74                            // If this is the first element, or the sign of the result of comparing the element with
  75                            // the existing accumulated result is equal to the sign requested by the function factory,
  76                            // we will return a new pair that contains the current element as the best item.  We will
  77                            // ignore null elements (for reference and nullable types) in the input stream.
  78                            if ((default(T) != null || element != null) &&
  79                                (!accumulator.First || Util.Sign(comparer.Compare(element, accumulator.Second)) == sign))
  80                            {
  81                                return new Pair<bool, T>(true, element);
  82                            }
  83
  84                            // Otherwise, just return the current accumulator result.
  85                            return accumulator;
  86                        };
  87         }
  88
  89         private static Func<Pair<bool, T>, Pair<bool, T>, Pair<bool, T>> MakeFinalReduceFunction(int sign)
  90         {
  91             Comparer<T> comparer = Util.GetDefaultComparer<T>();
  92
  93             // Note that we capture the 'sign' argument and 'comparer' local, and therefore the C#
  94             // compiler will transform this into an instance-based delegate, incurring an extra (hidden)
  95             // object allocation.
  96             return delegate(Pair<bool, T> accumulator, Pair<bool, T> element)
  97                        {
  98                            // If the intermediate reduction is empty, we will ignore it. Otherwise, if this is the
  99                            // first element, or the sign of the result of comparing the element with the existing
 100                            // accumulated result is equal to the sign requested by the function factory, we will
 101                            // return a new pair that contains the current element as the best item.
 102                            if (element.First &&
 103                                (!accumulator.First || Util.Sign(comparer.Compare(element.Second, accumulator.Second)) == sign))
 104                            {
 105                                Contract.Assert(default(T) != null || element.Second != null, "nulls unexpected in final reduce");
 106                                return new Pair<bool, T>(true, element.Second);
 107                            }
 108
 109                            // Otherwise, just return the current accumulator result.
 110                            return accumulator;
 111                        };
 112         }
 113
 114         private static Func<Pair<bool, T>, T> MakeResultSelectorFunction()
 115         {
 116             // If we saw at least one element in the source stream, the right pair element will contain
 117             // the element we're looking for -- so we return that. In the case of non-nullable value
 118             // types, the aggregation API will have thrown an exception before calling us for
 119             // empty sequences.  Else, we will just return the element, which may be null for other types.
 120             return delegate(Pair<bool, T> accumulator)
 121                        {
 122                            Contract.Assert(accumulator.First || default(T) == null,
 123                                            "for non-null types we expect an exception to be thrown before getting here");
 124                            return accumulator.Second;
 125                        };
 126         }
 127     }
 128 }