package de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel;

/*
 This file is part of ELKI:
 Environment for Developing KDD-Applications Supported by Index-Structures

 Copyright (C) 2013
 Ludwig-Maximilians-Universität München
 Lehr- und Forschungseinheit für Datenbanksysteme
 ELKI Development Team

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program 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 Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.logging.Level;

import de.lmu.ifi.dbs.elki.data.FeatureVector;
import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance;
import de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFunction;
import de.lmu.ifi.dbs.elki.logging.LoggingUtil;
import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix;

/**
 * Provides a class for storing the kernel matrix and several extraction methods
 * for convenience.
 * 
 * @author Simon Paradies
 * 
 * @apiviz.uses de.lmu.ifi.dbs.elki.distance.similarityfunction.PrimitiveSimilarityFunction
 */
public class KernelMatrix {
  /**
   * The kernel matrix
   */
  Matrix kernel;
  
  /**
   * Wraps the matrixArray in a KernelMatrix
   * 
   * @param matrixArray two dimensional double array
   */
  public KernelMatrix(final double[][] matrixArray) {
    kernel = new Matrix(matrixArray);
  }

  /**
   * Provides a new kernel matrix.
   * 
   * @param kernelFunction the kernel function used to compute the kernel matrix
   * @param database the database for which the kernel matrix is computed
   * 
   * @deprecated ID mapping is not reliable!
   */
  @Deprecated
  public <O extends FeatureVector<?>> KernelMatrix(final PrimitiveSimilarityFunction<? super O, DoubleDistance> kernelFunction, final Relation<? extends O> database) {
    this(kernelFunction, database, DBIDUtil.ensureArray(database.getDBIDs()));
  }

  /**
   * Provides a new kernel matrix.
   * 
   * @param kernelFunction the kernel function used to compute the kernel matrix
   * @param database the database that holds the objects
   * @param ids the IDs of those objects for which the kernel matrix is computed
   */
  public <O extends FeatureVector<?>> KernelMatrix(final PrimitiveSimilarityFunction<? super O, DoubleDistance> kernelFunction, final Relation<? extends O> database, final ArrayDBIDs ids) {
    LoggingUtil.logExpensive(Level.FINER, "Computing kernel matrix");
    kernel = new Matrix(ids.size(), ids.size());
    double value;
    for(int idx = 0; idx < ids.size(); idx++) {
      for(int idy = idx; idy < ids.size(); idy++) {
        value = kernelFunction.similarity(database.get(ids.get(idx)), database.get(ids.get(idy))).doubleValue();
        kernel.set(idx, idy, value);
        kernel.set(idy, idx, value);
      }
    }
  }

  /**
   * Makes a new kernel matrix from matrix (with data copying).
   * 
   * @param matrix a matrix
   */
  public KernelMatrix(final Matrix matrix) {
    kernel = matrix.copy();
  }

  /**
   * Returns the kernel distance between the two specified objects.
   * 
   * @param o1 first ObjectID
   * @param o2 second ObjectID
   * @return the distance between the two objects
   */
  // FIXME: really use objectids!
  public double getDistance(final int o1, final int o2) {
    return Math.sqrt(getSquaredDistance(o1, o2));
  }

  /**
   * Get the kernel matrix.
   * 
   * @return kernel
   */
  public Matrix getKernel() {
    return kernel;
  }

  /**
   * Returns the kernel value of object o1 and object o2
   * 
   * @param o1 ID of first object
   * @param o2 ID of second object
   * @return the kernel value of object o1 and object o2
   */
  public double getSimilarity(final int o1, final int o2) {
    return kernel.get(o1 - 1, o2 - 1); // correct index shifts.
  }

  /**
   * Returns the squared kernel distance between the two specified objects.
   * 
   * @param o1 first ObjectID
   * @param o2 second ObjectID
   * @return the distance between the two objects
   */
  public double getSquaredDistance(final int o1, final int o2) {
    return getSimilarity(o1, o1) + getSimilarity(o2, o2) - 2 * getSimilarity(o1, o2);
  }

  /**
   * Returns the ith kernel matrix column for all objects in ids
   * 
   * @param i the column which should be returned
   * @param ids the objects
   * @return the ith kernel matrix column for all objects in ids
   */
  public Matrix getSubColumn(final int i, final List<Integer> ids) {
    final int[] ID = new int[1];
    ID[0] = i - 1; // correct index shift
    final int[] IDs = new int[ids.size()];
    for(int x = 0; x < IDs.length; x++) {
      IDs[x] = ids.get(x) - 1; // correct index shift
    }
    return kernel.getMatrix(IDs, ID);
  }

  /**
   * Returns a sub kernel matrix for all objects in ids
   * 
   * @param ids the objects
   * @return a sub kernel matrix for all objects in ids.
   */
  public Matrix getSubMatrix(final Collection<Integer> ids) {
    final int[] IDs = new int[ids.size()];
    int i = 0;
    for(Iterator<Integer> it = ids.iterator(); it.hasNext(); i++) {
      IDs[i] = it.next() - 1; // correct index shift
    }
    return kernel.getMatrix(IDs, IDs);
  }

  /**
   * Centers the matrix in feature space according to Smola et. Schoelkopf,
   * Learning with Kernels p. 431 Alters the input matrix. If you still need the
   * original matrix, use
   * <code>centeredMatrix = centerKernelMatrix(uncenteredMatrix.copy()) {</code>
   * 
   * @param matrix the matrix to be centered
   * @return centered matrix (for convenience)
   */
  public static Matrix centerMatrix(final Matrix matrix) {
    final Matrix normalizingMatrix = new Matrix(matrix.getRowDimensionality(), matrix.getColumnDimensionality(), 1.0 / matrix.getColumnDimensionality());
    return matrix.minusEquals(normalizingMatrix.times(matrix)).minusEquals(matrix.times(normalizingMatrix)).plusEquals(normalizingMatrix.times(matrix).times(normalizingMatrix));
  }

  @Override
  public String toString() {
    return super.toString();
  }

  /**
   * Centers the Kernel Matrix in Feature Space according to Smola et.
   * Schoelkopf, Learning with Kernels p. 431 Alters the input matrix. If you
   * still need the original matrix, use
   * <code>centeredMatrix = centerKernelMatrix(uncenteredMatrix.copy()) {</code>
   * 
   * @param kernelMatrix the kernel matrix to be centered
   * @return centered kernelMatrix (for convenience)
   */
  public static Matrix centerKernelMatrix(final KernelMatrix kernelMatrix) {
    return centerMatrix(kernelMatrix.getKernel());
  }
}