source: branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/UniqueThresholdCalculator.cs @ 10009

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace HeuristicLab.Analysis {

  public static class UniqueThresholdCalculator {

    private sealed class IndexRange {

      public int Start, End, N;
      public readonly bool Merge;
      private readonly List<IndexRange> receivers, distributors;

      public IndexRange(int start, int end, int n, bool merge) {
        Start = start;
        End = end;
        N = n;
        Merge = merge;
        receivers = new List<IndexRange>();
        distributors = new List<IndexRange>();
      }

      public void AddReceiver(IndexRange receiver) {
        if (receiver != null) {
          receivers.Add(receiver);
          receiver.distributors.Add(this);
        }
      }

      public void Distribute() {
        int n = N - 1;
        Debug.Assert(n >= 0);
        switch (receivers.Count) {
          case 0: break; // No receivers indexes are lost :-(
          case 1: receivers[0].N += n; N = 1; break;
          case 2: receivers[0].N += n / 2; receivers[1].N += n - n / 2; N = 1; break;
          default: throw new InvalidOperationException("More than two receivers registered");
        }
        var followers = distributors.Where(d => d.Start > End).ToList();
        if (followers.Count > 0)
          End = followers.Min(g => g.Start);
        var predecessors = distributors.Where(d => d.End < Start).ToList();
        if (predecessors.Count > 0)
          Start = predecessors.Max(g => g.End);
      }

      public override string ToString() {
        return string.Format("[{0}-{1}, n={2}, {3}]", Start, End, N, Merge ? "Merge" : "Spread");
      }
    }

    public static IEnumerable<double> DetermineThresholds(IEnumerable<double> differences, int n) {
      var thresholds = differences.Select(d => Math.Abs(d)).ToList();
      thresholds.Sort();
      if (thresholds.Count <= n) {
        foreach (var t in thresholds)
          yield return t;
      } else {
        double min = thresholds[0];
        double max = thresholds[thresholds.Count-1];
        if (min == max) {
          yield return min;
        } else {
          yield return min;
          foreach (var t in DetermineInnerThresholds(thresholds, n-2))
            yield return t;
          yield return max;
        }
      }
    }

    private static IEnumerable<double> DetermineInnerThresholds(List<double> thresholds, int n) {
      n = Math.Min(thresholds.Count - 2, n);
      var indexes = Enumerable.Range(0, n + 2).Select(i => (int)Math.Round(1.0 * i * (thresholds.Count - 1) / (n + 1))).ToList();
      var ranges = CreateRanges(thresholds, indexes);
      RedistributeIndexes(ranges);
      TrimBoundaryRanges(ranges);
      if (ranges.Count == 1 && ranges[0].Start == 0 && ranges[0].End == thresholds.Count - 1 && ranges[0].N == n) {
        if (ranges[0].Merge)
          yield return thresholds[ranges[0].Start];
        else
          foreach (var i in indexes.Where(i => ranges[0].Start < i && i < ranges[0].End))
            yield return thresholds[i];
      } else {
        foreach (var range in ranges) {
          if (range.Merge)
            yield return thresholds[range.Start];
          else
            foreach (var t in DetermineInnerThresholds(thresholds.GetRange(range.Start, range.End - range.Start + 1), range.N))
              yield return t;
        }
      }
    }

    private static void TrimBoundaryRanges(List<IndexRange> ranges) {
      if (ranges.Count > 0)
        if (ranges[0].Merge)
          ranges.RemoveAt(0);
        else
          ranges[0].N--;
      if (ranges.Count > 0)
        if (ranges[ranges.Count - 1].Merge)
          ranges.RemoveAt(ranges.Count - 1);
        else
          ranges[ranges.Count - 1].N--;
    }

    private static void RedistributeIndexes(List<IndexRange> ranges) {
      IndexRange lastReceiver = null;
      List<IndexRange> lastDistributors = new List<IndexRange>();
      foreach (var range in ranges) {
        if (range.Merge) {
          range.AddReceiver(lastReceiver);
          lastDistributors.Add(range);
        } else {
          foreach (var d in lastDistributors)
            d.AddReceiver(range);
          lastDistributors = new List<IndexRange>();
          lastReceiver = range;
        }
      }
      foreach (var range in ranges) {
        range.Distribute();
      }
    }

    private static List<IndexRange> CreateRanges(List<double> thresholds, List<int> indexes) {
      var values = indexes.Select(i => new { i, v = thresholds[i] }).ToList();
      var mergedRanges = values.GroupBy(iv => iv.v)
        .Select(g => g.Count() == 1 ?
          new IndexRange(g.First().i, g.First().i, 1, false) :
          new IndexRange(g.Min(iv => iv.i), g.Max(iv => iv.i), g.Count(), true)).ToList();
      IndexRange lastSpreadRange = null;
      var ranges = new List<IndexRange>();
      foreach (var group in mergedRanges) {
        if (group.Merge) {
          if (lastSpreadRange != null) {
            ranges.Add(lastSpreadRange);
            lastSpreadRange = null;
          }
          ranges.Add(group);
        } else {
          if (lastSpreadRange != null) {
            lastSpreadRange.End = group.End;
            lastSpreadRange.N++;
          } else {
            lastSpreadRange = group;
          }
        }
      }
      if (lastSpreadRange != null)
        ranges.Add(lastSpreadRange);
      return ranges;
    }
  }
}