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

#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.Collections.Generic;
using System.Linq;
using HeuristicLab.Core;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
  public static class ExtensionMethods {
    /// <summary>
    /// Selects an element from an enumerable randomly with equal probability for each element.
    /// </summary>
    /// <typeparam name="T">The type of the items that are to be selected.</typeparam>
    /// <param name="source">The enumerable that contains the items.</param>
    /// <param name="random">The random number generator, its NextDouble() method must return a value in the range [0;1).</param>
    /// <param name="selected">True if an element was selected, false otherwise (mainly because of an empty sequence).</param>
    /// <returns>The selected item.</returns>
    public static T SelectRandomOrDefault<T>(this IEnumerable<T> source, IRandom random, out bool selected) {
      int counter = 1;
      selected = false;
      T selectedItem = default(T);
      foreach (T item in source) {
        if (random.NextDouble() < 1.0 / counter) {
          selectedItem = item;
          selected = true;
        }
      }
      return selectedItem;
    }

    /// <summary>
    /// Shuffles an enumerable and returns an new enumerable according to the Fisher-Yates shuffle.
    /// </summary>
    /// <remarks>
    /// Source code taken from http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
    /// Note that this is an online shuffle, but the source enumerable is transformed into an array.
    /// </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(int) method must deliver uniformly distributed random numbers.</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();
      // Note i > 0 to avoid final pointless iteration
      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.
      }

      // there is one item remaining that was not returned - we return it now
      yield return elements[0];
    }

    /// <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;
      }
    }

  }
}