source: branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/SolutionsCaching/PermutationSolutionDictionary.cs @ 9723

#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.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Analysis.AlgorithmBehavior.Analyzers {
  [Item("PermutationSolutionDictionary", "Stores permutations generated by an algorithm.")]
  [StorableClass]
  public class PermutationSolutionDictionary<TKey, TValue> : SolutionDictionary<TKey, TValue>
    where TKey : PermutationWrapper {

    public PermutationSolutionDictionary() {
      solutionDictionary = new Dictionary<TKey, List<TValue>>(new PermutationWrapperEqualityComparer());
    }

    [StorableConstructor]
    protected PermutationSolutionDictionary(bool deserializing) : base(deserializing) { }
    protected PermutationSolutionDictionary(PermutationSolutionDictionary<TKey, TValue> original, Cloner cloner)
      : base(original, cloner) {
    }

    protected override void InsertKeyValue(TKey key, TValue value) {
      int diffCnt;
      Permutation p = key.GetPermutation();
      Permutation ms = GetMostSimilarSolution(p, out diffCnt);

      if (diffCnt < ms.Length / 2) {
        key.StorePartialPermutation(ms, p);
      }

      var lst = new List<TValue>();
      lst.Add(value);
      solutionDictionary.Add(key, lst);
    }

    private Permutation GetMostSimilarSolution(Permutation permutation, out int diffCnt) {
      Permutation result = null; int min = int.MaxValue;
      foreach (PermutationWrapper p in solutionDictionary.Keys.Where(x => x.ElementType == ElementType.Complete)) {
        Permutation pr = p.GetPermutation();
        int diffs = CountDiffs(permutation, pr);
        if (diffs < min) {
          result = pr;
          min = diffs;
        }
      }
      diffCnt = min;
      return result;
    }

    private int CountDiffs(Permutation x, Permutation y) {
      int result = 0;
      // yes we ignore path encoding at the moment
      for (int i = 0; i < x.Length; i++) {
        if (x[i] != y[i]) result++;
      }
      return result;
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PermutationSolutionDictionary<TKey, TValue>(this, cloner);
    }
  }
}