source: branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs @ 12285

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 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.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Encodings.LinearLinkageEncoding {
  [Item("LinearLinkage", "Represents an LLE-e grouping of items.")]
  [StorableClass]
  public sealed class LinearLinkage : IntArray {

    [StorableConstructor]
    private LinearLinkage(bool deserializing) : base(deserializing) { }
    private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
    public LinearLinkage() { }
    public LinearLinkage(int length) : base(length) { }
    public LinearLinkage(int[] elements) : base(elements) { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new LinearLinkage(this, cloner);
    }

    /// <summary>
    /// This method parses the encoded array and calculates the membership of each element to the groups.
    /// It starts at the lowest element.
    /// </summary>
    /// <remarks>
    /// Runtime complexity of this method is O(n) where n is the length of the array.
    /// </remarks>
    /// <returns>An enumeration of all groups.</returns>
    public IEnumerable<List<int>> GetGroups() {
      var len = array.Length;
      var dict = new Dictionary<int, List<int>>();
      for (var i = 0; i < len; i++) {
        var end = array[i];
        if (end < i || end >= len || array[end] != end)
          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding.");
        List<int> list;
        if (!dict.TryGetValue(end, out list))
          dict.Add(end, new List<int>() { i });
        else list.Add(i);
      }
      return dict.Values;
      /* This code implements group extraction from LLE forward encoding
       * var len = array.Length;
      var remaining = new HashSet<int>(Enumerable.Range(0, len));
      // iterate from lowest to highest index
      for (var i = 0; i < len; i++) {
        if (!remaining.Contains(i)) continue;
        var group = new List<int> { i };
        remaining.Remove(i);
        var next = array[i];
        if (next != i) {
          int prev;
          do {
            group.Add(next);
            if (!remaining.Remove(next))
              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
            prev = next;
            next = array[next];
          } while (next != prev);
        }
        yield return group;
      }*/
    }

    /// <summary>
    /// This method parses the encoded array and gathers all items that belong to the same group as element <paramref name="index"/>.
    /// </summary>
    /// <param name="index">The element whose group should be returned.</param>
    /// <returns>The element at <paramref name="index"/> and all other elements in the same group.</returns>
    public IEnumerable<int> GetGroup(int index) {
      yield return index;
      var gn = array[index];
      for (var i = index + 1; i <= gn; i++) {
        if (array[i] == gn) yield return i;
      }
      for (var i = index - 1; i >= 0; i++) {
        if (array[i] == gn) yield return i;
      }
      /* This code implements group extraction from LLE forward encoding
      // return current element
      yield return index;
      var next = array[index];
      if (next == index) yield break;
      int prev;
      // return succeeding elements in group
      do {
        yield return next;
        prev = next;
        next = array[next];
      } while (next != prev);
      next = array[index];
      // return preceding elements in group
      for (prev = index - 1; prev >= 0; prev--) {
        if (array[prev] != next) continue;
        next = prev;
        yield return next;
      }*/
    }

    /// <summary>
    /// This method parses the encoded array and gathers the item itself as well as subsequent items that belong to the same group as element <paramref name="index"/>.
    /// </summary>
    /// <param name="index">The element from which items in the group should be returned.</param>
    /// <returns>The element at <paramref name="index"/> and all subsequent elements in the same group.</returns>
    public IEnumerable<int> GetGroupForward(int index) {
      yield return index;
      var gn = array[index];
      for (var i = index + 1; i <= gn; i++) {
        if (array[i] == gn) yield return i;
      }
      /* This code implements group extraction from LLE forward encoding
      yield return index;
      var next = array[index];
      if (next == index) yield break;
      int prev;
      do {
        yield return next;
        prev = next;
        next = array[next];
      } while (next != prev);*/
    }

    /// <summary>
    /// This method translates an enumeration of groups into the underlying array representation.
    /// </summary>
    /// <remarks>
    /// Throws an ArgumentException when there is an element assigned to multiple groups or elements that
    /// are not assigned to any group.
    /// </remarks>
    /// <param name="grouping">The grouping of the elements, each element must be part of exactly one group.</param>
    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
      var len = array.Length;
      var remaining = new HashSet<int>(Enumerable.Range(0, len));
      foreach (var group in grouping) {
        var max = -1;
        foreach (var g in group.OrderByDescending(x => x)) {
          if (max < 0) max = g;
          array[g] = max;
          remaining.Remove(g);
        }
      }
      if (remaining.Count > 0)
        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
      /* This code implements group setting for LLE forward encoding
      var len = array.Length;
      var remaining = new HashSet<int>(Enumerable.Range(0, len));
      foreach (var group in grouping) {
        var prev = -1;
        foreach (var g in group.OrderBy(x => x)) {
          if (prev >= 0) array[prev] = g;
          prev = g;
          if (!remaining.Remove(prev))
            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
        }
        if (prev >= 0) array[prev] = prev;
      }
      if (remaining.Count > 0)
        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
       */
    }

    /// <summary>
    /// Performs a check whether the array represents a valid LLE-e encoding.
    /// </summary>
    /// <remarks>
    /// The runtime complexity of this method is O(n) where n is the length of the array.
    /// </remarks>
    /// <returns>True if the encoding is valid.</returns>
    public bool Validate() {
      var len = array.Length;
      for (var i = 0; i < len; i++) {
        var end = array[i];
        if (end < i || end >= len || array[end] != end)
          return false;
      }
      return true;
      /* This code implements group setting for LLE forward encoding
      var len = array.Length;
      var remaining = new HashSet<int>(Enumerable.Range(0, len));
      for (var i = 0; i < len; i++) {
        if (!remaining.Contains(i)) continue;
        remaining.Remove(i);
        var next = array[i];
        if (next == i) continue;
        int prev;
        do {
          if (!remaining.Remove(next)) return false;
          prev = next;
          next = array[next];
        } while (next != prev);
      }
      return remaining.Count == 0;*/
    }
  }
}