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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 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 : SolutionDictionary<PermutationWrapper, PermutationInformation> {
    [Storable]
    protected Dictionary<PermutationWrapper, List<PermutationInformation>> solutionDictionary;

    public Dictionary<PermutationWrapper, List<PermutationInformation>> SolutionDictionary {
      get { return solutionDictionary; }
    }

    [Storable]
    PermutationEqualityComparer peq;

    public PermutationSolutionDictionary() {
      solutionDictionary = new Dictionary<PermutationWrapper, List<PermutationInformation>>(new PermutationWrapperEqualityComparer());
      peq = new PermutationEqualityComparer();
    }

    [StorableConstructor]
    protected PermutationSolutionDictionary(bool deserializing) : base(deserializing) { }
    protected PermutationSolutionDictionary(PermutationSolutionDictionary original, Cloner cloner)
      : base(original, cloner) {
      this.solutionDictionary = new Dictionary<PermutationWrapper, List<PermutationInformation>>(original.solutionDictionary, new PermutationWrapperEqualityComparer());
      this.peq = new PermutationEqualityComparer();
    }

    public override int Size() {
      return solutionDictionary.Count;
    }

    public override void Add(PermutationWrapper key, PermutationInformation value) {
      if (solutionDictionary.Count == 0) {
        var lst = new List<PermutationInformation>();
        lst.Add(value);
        solutionDictionary.Add(key, lst);
        return;
      }

      if (ContainsKey(key)) {
        if (!solutionDictionary[key].Contains(value))
          solutionDictionary[key].Add(value);
      } else {
        InsertKeyValue(key, value);
      }
    }

    protected override void InsertKeyValue(PermutationWrapper key, PermutationInformation 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<PermutationInformation>();
      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 PermutationWrapper GetPermutationWrapperOfPermutation(Permutation permutation) {
      return solutionDictionary.Single(x => peq.GetHashCode(x.Key.GetPermutation()) == peq.GetHashCode(permutation)).Key;
    }

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

    public int NumberOfPartialSolutions() {
      return solutionDictionary.Where(x => x.Key.ElementType == ElementType.Diff).Count();
    }

    public int NumberOfCompleteSolutions() {
      return solutionDictionary.Where(x => x.Key.ElementType == ElementType.Complete).Count();
    }

    public List<PermutationWrapper> GetSolutionsFromGeneration(int generation) {
      return solutionDictionary.Where(x => x.Value.Where(y => y.Generation == generation).Count() != 0).Select(x => x.Key).ToList<PermutationWrapper>();
    }

    public override bool ContainsKey(PermutationWrapper key) {
      return solutionDictionary.ContainsKey(key);
    }
  }
}