1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


29 


30  namespace HeuristicLab.Encodings.LinearLinkageEncoding {


31  [Item("LinearLinkage", "Represents an LLE grouping of items.")]


32  [StorableClass]


33  public sealed class LinearLinkage : IntArray {


34 


35  [StorableConstructor]


36  private LinearLinkage(bool deserializing) : base(deserializing) { }


37  private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }


38  public LinearLinkage() { }


39 


40  private LinearLinkage(int length) : base(length) { }


41  private LinearLinkage(int[] elements) : base(elements) { }


42 


43  /// <summary>


44  /// Create a new LinearLinkage object where every element is in a seperate group.


45  /// </summary>


46  public static LinearLinkage SingleElementGroups(int length) {


47  var elements = new int[length];


48  for (var i = 0; i < length; i++) {


49  elements[i] = i;


50  }


51  return new LinearLinkage(elements);


52  }


53 


54  /// <summary>


55  /// Create a new LinearLinkage object from an int[] in LLE


56  /// </summary>


57  /// <remarks>


58  /// This operation checks if the argument is a well formed LLE


59  /// and throws an ArgumentException otherwise.


60  /// </remarks>


61  /// <param name="lle">The LLE representation</param>


62  public static LinearLinkage FromForwardLinks(int[] lle) {


63  if (!Validate(lle)) {


64  throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");


65  }


66  return new LinearLinkage(lle);


67  }


68 


69  /// <summary>


70  /// Create a new LinearLinkage object by parsing an LLEe representation


71  /// and modifing the underlying array so that it is in LLE representation.


72  /// </summary>


73  /// <remarks>


74  /// This operation runs in O(n) time, but requires additional memory


75  /// in form of a int[].


76  /// </remarks>


77  /// <param name="llee">The LLEe representation</param>


78  /// <returns>LinearLinkage</returns>


79  public static LinearLinkage FromEndLinks(int[] llee) {


80  var result = new LinearLinkage(llee.Length);


81  result.SetEndLinks(llee);


82  return result;


83  }


84 


85  /// <summary>


86  /// Create a new LinearLinkage object by translating


87  /// an enumeration of groups into the underlying array representation.


88  /// </summary>


89  /// <remarks>


90  /// Throws an ArgumentException when there is an element assigned to


91  /// multiple groups or elements that are not assigned to any group.


92  /// </remarks>


93  /// <param name="grouping">The grouping of the elements, each element must


94  /// be part of exactly one group.</param>


95  public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {


96  var result = new LinearLinkage(length);


97  result.SetGroups(grouping);


98  return result;


99  }


100 


101  public override IDeepCloneable Clone(Cloner cloner) {


102  return new LinearLinkage(this, cloner);


103  }


104 


105  /// <summary>


106  /// This method parses the encoded array and calculates the membership of


107  /// each element to the groups. It starts at the lowest element.


108  /// </summary>


109  /// <remarks>


110  /// Runtime complexity of this method is O(n) where n is the length of the


111  /// array.


112  /// </remarks>


113  /// <returns>An enumeration of all groups.</returns>


114  public IEnumerable<List<int>> GetGroups() {


115  var len = array.Length;


116  var used = new bool[len];


117  for (var i = 0; i < len; i++) {


118  if (used[i]) continue;


119  var curr = i;


120  var next = array[curr];


121  var group = new List<int> { curr };


122  while (next > curr && next < len && !used[next]) {


123  used[curr] = true;


124  curr = next;


125  next = array[next];


126  group.Add(curr);


127  }


128  if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");


129  used[curr] = true;


130  yield return group;


131  }


132  /*


133  var len = array.Length;


134  var used = new bool[len];


135  // iterate from lowest to highest index


136  for (var i = 0; i < len; i++) {


137  if (used[i]) continue;


138  var group = new List<int> { i };


139  used[i] = true;


140  var next = array[i];


141  if (next < i  next >= len) {


142  throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");


143  }


144  while (next != array[next]) {


145  if (next < 0  next >= len  used[next]) {


146  throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");


147  }


148  group.Add(next);


149  used[next] = true;


150  next = array[next];


151  }


152  yield return group;


153  }*/


154  }


155 


156  /// <summary>


157  /// This method parses the encoded array and gathers all elements


158  /// that belong to the same group as element <paramref name="index"/>.


159  /// </summary>


160  /// <param name="index">The element whose group should be returned.


161  /// </param>


162  /// <returns>The element at <paramref name="index"/> and all other


163  /// elements in the same group.</returns>


164  public IEnumerable<int> GetGroup(int index) {


165  foreach (var n in GetGroupForward(index))


166  yield return n;


167  // the element index has already been yielded


168  foreach (var n in GetGroupBackward(index).Skip(1))


169  yield return n;


170  }


171 


172  /// <summary>


173  /// This method parses the encoded array and gathers the element


174  /// <paramref name="index"/> as well as subsequent elements that


175  /// belong to the same group.


176  /// </summary>


177  /// <param name="index">The element from which subsequent (having a


178  /// larger number) elements in the group should be returned.


179  /// </param>


180  /// <returns>The element <paramref name="index"/> and all subsequent


181  /// elements in the same group.</returns>


182  public IEnumerable<int> GetGroupForward(int index) {


183  yield return index;


184  var next = array[index];


185  if (next == index) yield break;


186  int prev;


187  do {


188  yield return next;


189  prev = next;


190  next = array[next];


191  } while (next != prev);


192  }


193 


194  /// <summary>


195  /// This method parses the encoded array and gathers the element


196  /// given <paramref name="index"/> as well as preceeding elements that


197  /// belong to the same group.


198  /// </summary>


199  /// <remarks>


200  /// Warning, this code has performance O(index) as the array has to


201  /// be fully traversed backwards from the given index.


202  /// </remarks>


203  /// <param name="index">The element from which preceeding (having a


204  /// smaller number) elements in the group should be returned.


205  /// </param>


206  /// <returns>The element <paramref name="index"/> and all preceeding


207  /// elements in the same group.</returns>


208  public IEnumerable<int> GetGroupBackward(int index) {


209  yield return index;


210  var next = array[index];


211  // return preceding elements in group


212  for (var prev = index  1; prev >= 0; prev) {


213  if (array[prev] != next) continue;


214  next = prev;


215  yield return next;


216  }


217  }


218 


219  /// <summary>


220  /// This method translates an enumeration of groups into the underlying


221  /// array representation.


222  /// </summary>


223  /// <remarks>


224  /// Throws an ArgumentException when there is an element assigned to


225  /// multiple groups or elements that are not assigned to any group.


226  /// </remarks>


227  /// <param name="grouping">The grouping of the elements, each element must


228  /// be part of exactly one group.</param>


229  public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {


230  var len = array.Length;


231  var used = new bool[len];


232  foreach (var group in grouping) {


233  var prev = 1;


234  foreach (var g in group.OrderBy(x => x)) {


235  if (g < prev  g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len  1), "grouping");


236  if (prev >= 0) array[prev] = g;


237  prev = g;


238  if (used[prev]) {


239  throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");


240  }


241  used[prev] = true;


242  }


243  array[prev] = prev;


244  }


245  if (!used.All(x => x))


246  throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i))));


247  }


248 


249  /// <summary>


250  /// Performs a check whether the array represents a valid LLE encoding.


251  /// </summary>


252  /// <remarks>


253  /// The runtime complexity of this method is O(n) where n is the length of


254  /// the array.


255  /// </remarks>


256  /// <returns>True if the encoding is valid.</returns>


257  public bool Validate() {


258  return Validate(array);


259  }


260 


261  private static bool Validate(int[] array) {


262  var len = array.Length;


263  var used = new bool[len];


264  for (var i = 0; i < len; i++) {


265  if (used[i]) continue;


266  var curr = i;


267  var next = array[curr];


268  while (next > curr && next < len && !used[next]) {


269  used[curr] = true;


270  curr = next;


271  next = array[next];


272  }


273  if (curr!=next) return false;


274  used[curr] = true;


275  }


276  return true;


277  }


278 


279  /// <summary>


280  /// This method flattens tree structures that may be present in groups.


281  /// These tree structures may be created by e.g. merging two groups by


282  /// linking one end node to the end node of another.


283  /// Consider following 1based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.


284  /// This results in the following tree structure for group 8:


285  /// 8


286  /// / \


287  /// 6 7


288  /// / \ 


289  /// 1 2 3


290  /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.


291  /// Representing a tree with one branch: 1 > 2 > 3 > 6 > 7 > 8


292  /// </summary>


293  /// <remarks>


294  /// The method first converts the array to LLEe format and then


295  /// linearizes the links. This requires two passes of the whole array


296  /// as well as a dictionary to hold the smallest index of each group.


297  /// The runtime complexity is O(n).


298  ///


299  /// The method assumes that there are no back links present.


300  /// </remarks>


301  public void LinearizeTreeStructures() {


302  // Step 1: Convert the array into LLEe


303  ToEndLinksInplace(array);


304  // Step 2: For all groups linearize the links


305  SetEndLinks(array);


306  }


307 


308  /// <summary>


309  /// Creates a copy of the underlying array and turns it into LLEe.


310  /// </summary>


311  /// <remarks>


312  /// LLEe is a special format where each element points to the


313  /// ending item of a group.


314  /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become


315  /// 5, 5, 5, 8, 5, 8, 8, 8 in LLEe.


316  ///


317  /// This operation runs in O(n) time.


318  /// </remarks>


319  /// <returns>An integer array in LLEe representation</returns>


320  public int[] ToEndLinks() {


321  var result = (int[])array.Clone();


322  ToEndLinksInplace(result);


323  return result;


324  }


325 


326  private static void ToEndLinksInplace(int[] array) {


327  var length = array.Length;


328  for (var i = length  1; i >= 0; i) {


329  var next = array[i];


330  if (next > i) {


331  array[i] = array[next];


332  } else if (next < i) {


333  throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");


334  }


335  }


336  }


337 


338  /// <summary>


339  /// Parses an LLEe representation and modifies the underlying array


340  /// so that it is in LLE representation.


341  /// </summary>


342  /// <remarks>


343  /// This operation runs in O(n) time, but requires additional memory


344  /// in form of a int[].


345  /// </remarks>


346  /// <param name="llee">The LLEe representation</param>


347  public void SetEndLinks(int[] llee) {


348  var length = array.Length;


349  if (length != llee.Length) {


350  throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");


351  }


352  // If we are ok with mutating llee we can avoid this clone


353  var lookup = (int[])llee.Clone();


354  for (var i = length  1; i >= 0; i) {


355  var end = llee[i];


356  if (end == i) {


357  array[i] = end;


358  } else if (end > i && end < length) {


359  array[i] = lookup[end];


360  lookup[end] = i;


361  } else {


362  throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");


363  }


364  }


365  }


366  }


367  }

