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  /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>


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


63  /// <returns>The linear linkage encoding in LLE format (with forwardlinks).</returns>


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


65  if (!Validate(lle))


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


67  return new LinearLinkage(lle);


68  }


69 


70  /// <summary>


71  /// Create a new LinearLinkage object by parsing a LLEb representation


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


73  /// </summary>


74  /// <remarks>


75  /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.


76  /// </remarks>


77  /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLEb array.</exception>


78  /// <param name="lleb">The LLEb representation (LLE with backlinks)</param>


79  /// <returns>The linear linkage encoding in LLE format (with forwardlinks).</returns>


80  public static LinearLinkage FromBackLinks(int[] lleb) {


81  var result = new LinearLinkage(lleb.Length);


82  for (var i = lleb.Length  1; i > 0; i) {


83  if (lleb[i] == i) {


84  if (result[i] == 0) result[i] = i;


85  continue;


86  }


87  result[lleb[i]] = i;


88  if (result[i] == 0) result[i] = i;


89  }


90  if (!Validate(result.array))


91  throw new ArgumentException("Array is malformed and does not represent a valid LLEb encoding (with backlinks).", "lleb");


92  return result;


93  }


94 


95  /// <summary>


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


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


98  /// </summary>


99  /// <remarks>


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


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


102  /// </remarks>


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


104  /// <returns>The linear linkage encoding in LLE format (with forwardlinks).</returns>


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


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


107  result.SetEndLinks(llee);


108  return result;


109  }


110 


111  /// <summary>


112  /// Create a new LinearLinkage object by translating


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


114  /// </summary>


115  /// <remarks>


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


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


118  /// </remarks>


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


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


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


122  var result = new LinearLinkage(length);


123  result.SetGroups(grouping);


124  return result;


125  }


126 


127  public override IDeepCloneable Clone(Cloner cloner) {


128  return new LinearLinkage(this, cloner);


129  }


130 


131  /// <summary>


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


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


134  /// </summary>


135  /// <remarks>


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


137  /// array.


138  /// </remarks>


139  /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>


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


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


142  var len = array.Length;


143  var used = new bool[len];


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


145  if (used[i]) continue;


146  var curr = i;


147  var next = array[curr];


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


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


150  used[curr] = true;


151  curr = next;


152  next = array[next];


153  group.Add(curr);


154  }


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


156  used[curr] = true;


157  yield return group;


158  }


159  }


160 


161  /// <summary>


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


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


164  /// </summary>


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


166  /// </param>


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


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


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


170  foreach (var n in GetGroupForward(index))


171  yield return n;


172  // the element index has already been yielded


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


174  yield return n;


175  }


176 


177  /// <summary>


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


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


180  /// belong to the same group.


181  /// </summary>


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


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


184  /// </param>


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


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


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


188  yield return index;


189  var next = array[index];


190  if (next == index) yield break;


191  int prev;


192  do {


193  yield return next;


194  prev = next;


195  next = array[next];


196  } while (next != prev);


197  }


198 


199  /// <summary>


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


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


202  /// belong to the same group.


203  /// </summary>


204  /// <remarks>


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


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


207  /// </remarks>


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


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


210  /// </param>


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


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


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


214  yield return index;


215  var next = array[index];


216  // return preceding elements in group


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


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


219  next = prev;


220  yield return next;


221  }


222  }


223 


224  /// <summary>


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


226  /// array representation.


227  /// </summary>


228  /// <remarks>


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


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


231  /// </remarks>


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


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


234  /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted


235  /// to a valid LLE representation. For instance, because elements are too big or too small,


236  /// or they're contained in multiple groups, or there are elements not assigned to any group.


237  /// </exception>


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


239  var len = array.Length;


240  var used = new bool[len];


241  foreach (var group in grouping) {


242  var prev = 1;


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


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


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


246  prev = g;


247  if (used[prev]) {


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


249  }


250  used[prev] = true;


251  }


252  array[prev] = prev;


253  }


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


255  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))));


256  }


257 


258  /// <summary>


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


260  /// </summary>


261  /// <remarks>


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


263  /// the array.


264  /// </remarks>


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


266  public bool Validate() {


267  return Validate(array);


268  }


269 


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


271  var len = array.Length;


272  var used = new bool[len];


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


274  if (used[i]) continue;


275  var curr = i;


276  var next = array[curr];


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


278  used[curr] = true;


279  curr = next;


280  next = array[next];


281  }


282  if (curr!=next) return false;


283  used[curr] = true;


284  }


285  return true;


286  }


287 


288  /// <summary>


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


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


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


292  /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.


293  /// This results in the following tree structure for group 7:


294  /// 7


295  /// / \


296  /// 5 6


297  /// / \ 


298  /// 0 1 2


299  /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.


300  /// Representing a tree with one branch: 0 > 1 > 2 > 5 > 6 > 7.


301  /// </summary>


302  /// <remarks>


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


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


305  /// as well as another copy of the underlying array.


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


307  ///


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


309  /// </remarks>


310  public void LinearizeTreeStructures() {


311  // Step 1: Convert the array into LLEe


312  ToEndLinksInplace(array);


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


314  SetEndLinks(array);


315  }


316 


317  /// <summary>


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


319  /// </summary>


320  /// <remarks>


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


322  /// ending item of a group.


323  /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become


324  /// 4, 4, 4, 7, 4, 7, 7, 7 in LLEe.


325  ///


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


327  /// </remarks>


328  /// <exception cref="ArgumentException">In case, this object does not


329  /// represent a valid LLE encoding.


330  /// </exception>


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


332  public int[] ToEndLinks() {


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


334  ToEndLinksInplace(result);


335  return result;


336  }


337 


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


339  var length = array.Length;


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


341  var next = array[i];


342  if (next > i) {


343  array[i] = array[next];


344  } else if (next < i) {


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


346  }


347  }


348  }


349 


350  /// <summary>


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


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


353  /// </summary>


354  /// <remarks>


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


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


357  /// </remarks>


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


359  /// <exception cref="ArgumentException">


360  /// If <paramref name="llee"/> does not contain a valid LLEe representation or


361  /// has a different length to the given instance.


362  /// </exception>


363  public void SetEndLinks(int[] llee) {


364  var length = array.Length;


365  if (length != llee.Length) {


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


367  }


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


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


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


371  var end = llee[i];


372  if (end == i) {


373  array[i] = end;


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


375  array[i] = lookup[end];


376  lookup[end] = i;


377  } else {


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


379  }


380  }


381  }


382 


383  /// <summary>


384  /// Creates a copy of the underlying array and turns it into LLEb.


385  /// </summary>


386  /// <remarks>


387  /// LLEb is a special format where each element points to the


388  /// predecessor instead of the successor.


389  /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7


390  /// would become 0, 0, 1, 3, 2, 3, 5, 6 in LLEb.


391  ///


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


393  /// </remarks>


394  /// <returns>An integer array in LLEb representation</returns>


395  public int[] ToBackLinks() {


396  var result = new int[array.Length];


397  var zeroLink = array[0];


398  for (var i = 0; i < array.Length; i++) {


399  if (array[i] == i) {


400  if (result[i] == 0 && i != zeroLink) result[i] = i;


401  continue;


402  }


403  result[array[i]] = i;


404  if (result[i] == 0 && i != zeroLink) result[i] = i;


405  }


406  return result;


407  }


408  }


409  }

