source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common/3.3/ExtensionMethods.cs @ 7759

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Core;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common {
  public static class ExtensionMethods {

    #region Choosing from a sequence
    /// <summary>
    /// Chooses one elements from a sequence under equal chances for each element.
    /// </summary>
    /// <remarks>
    /// Runtime complexity is O(1) for sequences that are <see cref="IList{T}"/> and
    /// O(N) for all other.
    /// </remarks>
    /// <typeparam name="T">The type of the items to be selected.</typeparam>
    /// <param name="source">The sequence of elements.</param>
    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    /// <param name="count">The number of items to be selected.</param>
    /// <returns>A sequence of elements that have been chosen randomly.</returns>
    public static T ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random) {
      return source.ChooseUniformRandom(random, 1).First();
    }
    /// <summary>
    /// Chooses <paramref name="count"/> elements from a sequence with repetition under equal chances for each element.
    /// </summary>
    /// <remarks>
    /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
    /// O(N * count) for all other.
    /// 
    /// The method is online.
    /// </remarks>
    /// <typeparam name="T">The type of the items to be selected.</typeparam>
    /// <param name="source">The sequence of elements.</param>
    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    /// <param name="count">The number of items to be selected.</param>
    /// <returns>A sequence of elements that have been chosen randomly.</returns>
    public static IEnumerable<T> ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random, int count) {
      if (source == null) throw new ArgumentNullException("source", "sequence is null");
      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");

      var listSource = source as IList<T>;
      if (listSource != null)
        while (count > 0) {
          yield return listSource[random.Next(listSource.Count)];
          count--;
        }

      while (count > 0) {
        var enumerator = source.GetEnumerator();
        enumerator.MoveNext();
        T selectedItem = enumerator.Current;
        int counter = 1;
        while (enumerator.MoveNext()) {
          counter++;
          if (counter * random.NextDouble() < 1.0)
            selectedItem = enumerator.Current;
        }
        yield return selectedItem;
        count--;
      }
    }
    /// <summary>
    /// Chooses <paramref name="count"/> elements from a sequence without repetition under equal chances for each element.
    /// </summary>
    /// <remarks>
    /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
    /// O(N * count) for all other.
    /// 
    /// The method is online, but the source enumerable is transformed into an array.
    /// </remarks>
    /// <typeparam name="T">The type of the items to be selected.</typeparam>
    /// <param name="source">The sequence of elements.</param>
    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    /// <param name="count">The number of items to be selected.</param>
    /// <returns>A sequence of elements that have been chosen randomly.</returns>
    public static IEnumerable<T> ChooseUniformRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count) {
      return source.Shuffle(random).Take(count);
    }

    /// <summary>
    /// Chooses items out of a sequence with repetition. The chance that an item is selected is proportional or inverse-proportional
    /// to the value obtained from <paramref name="valueSelector"/>.
    /// </summary>
    /// <remarks>
    /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be &gt; 0,
    /// otherwise an InvalidOperationException is thrown.
    /// 
    /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>
    /// is only applied once for each item.
    /// </remarks>
    /// <typeparam name="T">The type of the items to be selected.</typeparam>
    /// <param name="source">The sequence of elements.</param>
    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    /// <param name="count">The number of items to be selected.</param>
    /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>
    /// <param name="windowing">Whether to scale the proportional values or not.</param>
    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
    /// <returns>A sequence of selected items. The sequence might contain the same item more than once.</returns>
    public static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {
      return source.ChooseProportionalRandom(random, valueSelector, windowing, maximization).Take(count);
    }
    /// <summary>
    /// Same as <seealso cref="ChooseProportionalRandom<T>"/>, but selects each item exactly once.
    /// </summary>
    /// <remarks>
    /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be &gt; 0,
    /// otherwise an InvalidOperationException is thrown.
    /// 
    /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>
    /// is only applied once for each item.
    /// </remarks>
    /// <typeparam name="T">The type of the items to be selected.</typeparam>
    /// <param name="source">The sequence of elements.</param>
    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
    /// <param name="count">The number of items to be selected.</param>
    /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>
    /// <param name="windowing">Whether to scale the proportional values or not.</param>
    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
    /// <returns>A sequence of selected items.</returns>
    public static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {
      return source.ChooseProportionalRandomWithoutRepetition(random, valueSelector, windowing, maximization).Take(count);
    }
    #region Proportional Helpers
    private static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {
      if (source == null) throw new ArgumentNullException("source", "sequence is null");
      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");

      var sourceArray = source.ToArray();
      var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);
      double total = valueArray.Sum();

      while (true) {
        int index = 0;
        double ball = valueArray[index], sum = random.NextDouble() * total;
        while (ball < sum)
          ball += valueArray[++index];
        yield return sourceArray[index];
      }
    }
    private static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {
      if (source == null) throw new ArgumentNullException("source", "sequence is null");
      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");

      var sourceArray = source.ToArray();
      var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);
      double total = valueArray.Sum();

      HashSet<int> chosenIndices = new HashSet<int>();
      while (chosenIndices.Count < sourceArray.Length) {
        int index = 0;
        double ball = valueArray[index], sum = random.NextDouble() * total;
        while (ball < sum) {
          index++;
          if (!chosenIndices.Contains(index))
            ball += valueArray[++index];
        }
        yield return sourceArray[index];
        chosenIndices.Add(index);
        total -= valueArray[index];
      }
    }
    private static double[] PrepareProportional<T>(IList<T> sourceArray, Func<T, double> valueSelector, bool windowing, bool maximization) {
      double maxValue = double.MinValue, minValue = double.MaxValue;
      double[] valueArray = new double[sourceArray.Count];

      for (int i = 0; i < sourceArray.Count; i++) {
        valueArray[i] = valueSelector(sourceArray[i]);
        if (valueArray[i] > maxValue) maxValue = valueArray[i];
        if (valueArray[i] < minValue) minValue = valueArray[i];
      }
      if (minValue == maxValue) {  // all values are equal
        for (int i = 0; i < sourceArray.Count; i++) {
          valueArray[i] = 1.0;
        }
      } else {
        if (windowing) {
          if (maximization) ProportionalScale(valueArray, minValue);
          else InverseProportionalScale(valueArray, maxValue);
        } else {
          if (minValue < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with values < 0.");
          if (!maximization) InverseProportionalScale(valueArray, 2 * maxValue);
        }
      }
      return valueArray;
    }
    private static void ProportionalScale(double[] values, double minValue) {
      for (int i = 0; i < values.Length; i++) {
        values[i] = values[i] - minValue;
      }
    }
    private static void InverseProportionalScale(double[] values, double maxValue) {
      for (int i = 0; i < values.Length; i++) {
        values[i] = maxValue - values[i];
      }
    }
    #endregion

    /// <summary>
    /// Selects the first element in the sequence that is maximal with respect to the given key.
    /// </summary>
    /// <remarks>
    /// Runtime complexity of the operation is O(N).
    /// </remarks>
    /// <typeparam name="T">The type of the elements.</typeparam>
    /// <typeparam name="TComparable">The selected key (needs to be an IComparable).</typeparam>
    /// <param name="source">The enumeration in which the maximum item should be found.</param>
    /// <param name="keySelector">The function that selects the key.</param>
    /// <returns>The element in the enumeration where the selected key is the maximum.</returns>
    public static T ChooseMax<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
      if (source == null) throw new ArgumentNullException("source", "sequence is null");
      IEnumerator<T> enumerator = source.GetEnumerator();
      if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");
      T result = enumerator.Current;
      TComparable max = keySelector(result);
      while (enumerator.MoveNext()) {
        T item = enumerator.Current;
        TComparable comparison = keySelector(item);
        if (comparison.CompareTo(max) > 0) {
          result = item;
          max = comparison;
        }
      }
      return result;
    }

    /// <summary>
    /// Selects the first element in the sequence where the selected key is the minimum.
    /// </summary>
    /// <remarks>
    /// Runtime complexity of the operation is O(N).
    /// </remarks>
    /// <typeparam name="T">The type of the elements.</typeparam>
    /// <typeparam name="TComparable">The selected key (needs to be an IComparable).</typeparam>
    /// <param name="source">The enumeration in which the minimum item should be found.</param>
    /// <param name="keySelector">The function that selects the key.</param>
    /// <returns>The element in the enumeration where the selected key is the minimum.</returns>
    public static T ChooseMin<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
      if (source == null) throw new ArgumentNullException("source", "sequence is null");
      IEnumerator<T> enumerator = source.GetEnumerator();
      if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");
      T result = enumerator.Current;
      TComparable min = keySelector(result);
      while (enumerator.MoveNext()) {
        T item = enumerator.Current;
        TComparable comparison = keySelector(item);
        if (comparison.CompareTo(min) < 0) {
          result = item;
          min = comparison;
        }
      }
      return result;
    }
    #endregion

    #region Shuffling
    /// <summary>
    /// Shuffles an enumerable and returns a new enumerable according to the Fisher-Yates shuffle.
    /// </summary>
    /// <remarks>
    /// Note that this is an online shuffle, but the source enumerable is transformed into an array.
    /// 
    /// The implementation is described in http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
    /// </remarks>
    /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>
    /// <param name="source">The enumerable that contains the items.</param>
    /// <param name="random">The random number generator, its Next(n) method must deliver uniformly distributed random numbers in the range [0;n).</param>
    /// <returns>An enumerable with the elements shuffled.</returns>
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {
      T[] elements = source.ToArray();
      for (int i = elements.Length - 1; i > 0; i--) {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = random.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
      }
      yield return elements[0];
    }
    #endregion

    #region Graph walk
    /// <summary>
    /// Walks an operator graph in that it jumps from one operator to all its operator parameters and yields each operator it touches.
    /// Cycles are detected and not walked twice.
    /// </summary>
    /// <param name="initial">The operator where the walk starts (is also yielded).</param>
    /// <returns>An enumeration of all the operators that could be found.</returns>
    public static IEnumerable<IOperator> Walk(this IOperator initial) {
      var open = new Stack<IOperator>();
      var visited = new HashSet<IOperator>();
      open.Push(initial);

      while (open.Any()) {
        IOperator current = open.Pop();
        if (visited.Contains(current)) continue;
        visited.Add(current);

        foreach (var parameter in current.Parameters.OfType<IValueParameter>()) {
          if (typeof(IOperator).IsAssignableFrom(parameter.DataType)) {
            if (parameter.Value != null)
              open.Push((IOperator)parameter.Value);
          }
        }

        yield return current;
      }
    }
    #endregion

    #region Matrix operations
    public static double[,] Transpose(this double[,] matrix) {
      var result = new double[matrix.GetLength(1), matrix.GetLength(0)];
      for (int i = 0; i < matrix.GetLength(0); i++)
        for (int j = 0; j < matrix.GetLength(1); j++)
          result[j, i] = matrix[i, j];
      return result;
    }
    #endregion
  }
}