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