1 | using System;
|
---|
2 | using System.Linq;
|
---|
3 | using System.Collections.Generic;
|
---|
4 | using System.Diagnostics;
|
---|
5 |
|
---|
6 | namespace HeuristicLab.Analysis {
|
---|
7 |
|
---|
8 | public static class UniqueThresholdCalculator {
|
---|
9 |
|
---|
10 | private sealed class IndexRange {
|
---|
11 |
|
---|
12 | public int Start, End, N;
|
---|
13 | public readonly bool Merge;
|
---|
14 | private readonly List<IndexRange> receivers, distributors;
|
---|
15 |
|
---|
16 | public IndexRange(int start, int end, int n, bool merge) {
|
---|
17 | Start = start;
|
---|
18 | End = end;
|
---|
19 | N = n;
|
---|
20 | Merge = merge;
|
---|
21 | receivers = new List<IndexRange>();
|
---|
22 | distributors = new List<IndexRange>();
|
---|
23 | }
|
---|
24 |
|
---|
25 | public void AddReceiver(IndexRange receiver) {
|
---|
26 | if (receiver != null) {
|
---|
27 | receivers.Add(receiver);
|
---|
28 | receiver.distributors.Add(this);
|
---|
29 | }
|
---|
30 | }
|
---|
31 |
|
---|
32 | public void Distribute() {
|
---|
33 | int n = N - 1;
|
---|
34 | Debug.Assert(n >= 0);
|
---|
35 | switch (receivers.Count) {
|
---|
36 | case 0: break; // No receivers indexes are lost :-(
|
---|
37 | case 1: receivers[0].N += n; N = 1; break;
|
---|
38 | case 2: receivers[0].N += n / 2; receivers[1].N += n - n / 2; N = 1; break;
|
---|
39 | default: throw new InvalidOperationException("More than two receivers registered");
|
---|
40 | }
|
---|
41 | var followers = distributors.Where(d => d.Start > End).ToList();
|
---|
42 | if (followers.Count > 0)
|
---|
43 | End = followers.Min(g => g.Start);
|
---|
44 | var predecessors = distributors.Where(d => d.End < Start).ToList();
|
---|
45 | if (predecessors.Count > 0)
|
---|
46 | Start = predecessors.Max(g => g.End);
|
---|
47 | }
|
---|
48 |
|
---|
49 | public override string ToString() {
|
---|
50 | return string.Format("[{0}-{1}, n={2}, {3}]", Start, End, N, Merge ? "Merge" : "Spread");
|
---|
51 | }
|
---|
52 | }
|
---|
53 |
|
---|
54 | public static IEnumerable<double> DetermineThresholds(IEnumerable<double> differences, int n) {
|
---|
55 | var thresholds = differences.Select(d => Math.Abs(d)).ToList();
|
---|
56 | thresholds.Sort();
|
---|
57 | if (thresholds.Count <= n) {
|
---|
58 | foreach (var t in thresholds)
|
---|
59 | yield return t;
|
---|
60 | } else {
|
---|
61 | double min = thresholds[0];
|
---|
62 | double max = thresholds[thresholds.Count-1];
|
---|
63 | if (min == max) {
|
---|
64 | yield return min;
|
---|
65 | } else {
|
---|
66 | yield return min;
|
---|
67 | foreach (var t in DetermineInnerThresholds(thresholds, n-2))
|
---|
68 | yield return t;
|
---|
69 | yield return max;
|
---|
70 | }
|
---|
71 | }
|
---|
72 | }
|
---|
73 |
|
---|
74 | private static IEnumerable<double> DetermineInnerThresholds(List<double> thresholds, int n) {
|
---|
75 | n = Math.Min(thresholds.Count - 2, n);
|
---|
76 | var indexes = Enumerable.Range(0, n + 2).Select(i => (int)Math.Round(1.0 * i * (thresholds.Count - 1) / (n + 1))).ToList();
|
---|
77 | var ranges = CreateRanges(thresholds, indexes);
|
---|
78 | RedistributeIndexes(ranges);
|
---|
79 | TrimBoundaryRanges(ranges);
|
---|
80 | if (ranges.Count == 1 && ranges[0].Start == 0 && ranges[0].End == thresholds.Count - 1 && ranges[0].N == n) {
|
---|
81 | if (ranges[0].Merge)
|
---|
82 | yield return thresholds[ranges[0].Start];
|
---|
83 | else
|
---|
84 | foreach (var i in indexes.Where(i => ranges[0].Start < i && i < ranges[0].End))
|
---|
85 | yield return thresholds[i];
|
---|
86 | } else {
|
---|
87 | foreach (var range in ranges) {
|
---|
88 | if (range.Merge)
|
---|
89 | yield return thresholds[range.Start];
|
---|
90 | else
|
---|
91 | foreach (var t in DetermineInnerThresholds(thresholds.GetRange(range.Start, range.End - range.Start + 1), range.N))
|
---|
92 | yield return t;
|
---|
93 | }
|
---|
94 | }
|
---|
95 | }
|
---|
96 |
|
---|
97 | private static void TrimBoundaryRanges(List<IndexRange> ranges) {
|
---|
98 | if (ranges.Count > 0)
|
---|
99 | if (ranges[0].Merge)
|
---|
100 | ranges.RemoveAt(0);
|
---|
101 | else
|
---|
102 | ranges[0].N--;
|
---|
103 | if (ranges.Count > 0)
|
---|
104 | if (ranges[ranges.Count - 1].Merge)
|
---|
105 | ranges.RemoveAt(ranges.Count - 1);
|
---|
106 | else
|
---|
107 | ranges[ranges.Count - 1].N--;
|
---|
108 | }
|
---|
109 |
|
---|
110 | private static void RedistributeIndexes(List<IndexRange> ranges) {
|
---|
111 | IndexRange lastReceiver = null;
|
---|
112 | List<IndexRange> lastDistributors = new List<IndexRange>();
|
---|
113 | foreach (var range in ranges) {
|
---|
114 | if (range.Merge) {
|
---|
115 | range.AddReceiver(lastReceiver);
|
---|
116 | lastDistributors.Add(range);
|
---|
117 | } else {
|
---|
118 | foreach (var d in lastDistributors)
|
---|
119 | d.AddReceiver(range);
|
---|
120 | lastDistributors = new List<IndexRange>();
|
---|
121 | lastReceiver = range;
|
---|
122 | }
|
---|
123 | }
|
---|
124 | foreach (var range in ranges) {
|
---|
125 | range.Distribute();
|
---|
126 | }
|
---|
127 | }
|
---|
128 |
|
---|
129 | private static List<IndexRange> CreateRanges(List<double> thresholds, List<int> indexes) {
|
---|
130 | var values = indexes.Select(i => new { i, v = thresholds[i] }).ToList();
|
---|
131 | var mergedRanges = values.GroupBy(iv => iv.v)
|
---|
132 | .Select(g => g.Count() == 1 ?
|
---|
133 | new IndexRange(g.First().i, g.First().i, 1, false) :
|
---|
134 | new IndexRange(g.Min(iv => iv.i), g.Max(iv => iv.i), g.Count(), true)).ToList();
|
---|
135 | IndexRange lastSpreadRange = null;
|
---|
136 | var ranges = new List<IndexRange>();
|
---|
137 | foreach (var group in mergedRanges) {
|
---|
138 | if (group.Merge) {
|
---|
139 | if (lastSpreadRange != null) {
|
---|
140 | ranges.Add(lastSpreadRange);
|
---|
141 | lastSpreadRange = null;
|
---|
142 | }
|
---|
143 | ranges.Add(group);
|
---|
144 | } else {
|
---|
145 | if (lastSpreadRange != null) {
|
---|
146 | lastSpreadRange.End = group.End;
|
---|
147 | lastSpreadRange.N++;
|
---|
148 | } else {
|
---|
149 | lastSpreadRange = group;
|
---|
150 | }
|
---|
151 | }
|
---|
152 | }
|
---|
153 | if (lastSpreadRange != null)
|
---|
154 | ranges.Add(lastSpreadRange);
|
---|
155 | return ranges;
|
---|
156 | }
|
---|
157 | }
|
---|
158 | }
|
---|