source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs @ 10833

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2014 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;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Matching {
  public class MaxCommonSequenceCalculator<T, TComp>
    where T : class
    where TComp : IEqualityComparer<T> {

    private TComp comparer;
    public TComp Comparer {
      get { return comparer; }
      set { comparer = value; }
    }

    private int[,] matrix;
    private List<T> sequence;

    public MaxCommonSequenceCalculator(TComp comparer) {
      this.comparer = comparer;
    }

    /// <summary>
    /// Calculate the maximal common subsequence between arrays a and b and return it.
    /// THIS DOES NOT WORK FOR TREES
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public IEnumerable<T> Calculate(T[] a, T[] b) {
      int m = a.Length;
      int n = b.Length;

      if (m == 0 || n == 0) return null;
      sequence = new List<T>();
      matrix = new int[m + 1, n + 1];

      for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
          if (comparer.Equals(a[i - 1], b[j - 1])) {
            matrix[i, j] = matrix[i - 1, j - 1] + 1;
          } else {
            matrix[i, j] = Math.Max(matrix[i - 1, j], matrix[i, j - 1]);
          }
        }
      }
      Recon(a, b, n, m); // build the common subsequence
      return sequence;
    }

    private void Recon(T[] a, T[] b, int i, int j) {
      while (i > 0 && j > 0) {
        if (comparer.Equals(a[i - 1], b[j - 1])) {
          Recon(a, b, i - 1, j - 1);
          sequence.Add(a[i - 1]);
        } else if (matrix[i - 1, j] > matrix[i, j - 1]) {
          i = i - 1;
          continue;
        } else {
          j = j - 1;
          continue;
        }
        break;
      }
    }
  }
}