/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.math4.legacy.genetics;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  
  import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
  import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException;
  import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  
  /**
   * Random Key chromosome is used for permutation representation. It is a vector
   * of a fixed length of real numbers in [0,1] interval. The index of the i-th
   * smallest value in the vector represents an i-th member of the permutation.
   * <p>
   * For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the
   * permutation of indices (3,0,1,2). If the original (unpermuted) sequence would
   * be (a,b,c,d), this would mean the sequence (d,a,b,c).
   * <p>
   * With this representation, common operators like n-point crossover can be
   * used, because any such chromosome represents a valid permutation.
   * <p>
   * Since the chromosome (and thus its arrayRepresentation) is immutable, the
   * array representation is sorted only once in the constructor.
   * <p>
   * For details, see:
   * <ul>
   *   <li>Bean, J.C.: Genetic algorithms and random keys for sequencing and
   *       optimization. ORSA Journal on Computing 6 (1994) 154-160</li>
   *   <li>Rothlauf, F.: Representations for Genetic and Evolutionary Algorithms.
   *       Volume 104 of Studies in Fuzziness and Soft Computing. Physica-Verlag,
   *       Heidelberg (2002)</li>
   * </ul>
   *
   * @param <T> type of the permuted objects
   * @since 2.0
   */
  public abstract class RandomKey<T> extends AbstractListChromosome<Double> implements PermutationChromosome<T> {
  
      /** Cache of sorted representation (unmodifiable). */
      private final List<Double> sortedRepresentation;
  
      /**
       * Base sequence [0,1,...,n-1], permuted according to the representation (unmodifiable).
       */
      private final List<Integer> baseSeqPermutation;
  
      /**
       * Constructor.
       *
       * @param representation list of [0,1] values representing the permutation
       * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
       */
      public RandomKey(final List<Double> representation) throws InvalidRepresentationException {
          super(representation);
          // store the sorted representation
          List<Double> sortedRepr = new ArrayList<> (getRepresentation());
          Collections.sort(sortedRepr);
          sortedRepresentation = Collections.unmodifiableList(sortedRepr);
          // store the permutation of [0,1,...,n-1] list for toString() and isSame() methods
          baseSeqPermutation = Collections.unmodifiableList(
              decodeGeneric(baseSequence(getLength()), getRepresentation(), sortedRepresentation)
          );
      }
  
      /**
       * Constructor.
       *
       * @param representation array of [0,1] values representing the permutation
       * @throws InvalidRepresentationException iff the <code>representation</code> can not represent a valid chromosome
       */
      public RandomKey(final Double[] representation) throws InvalidRepresentationException {
          this(Arrays.asList(representation));
      }
  
      /**
       * {@inheritDoc}
       */
      @Override
      public List<T> decode(final List<T> sequence) {
          return decodeGeneric(sequence, getRepresentation(), sortedRepresentation);
     }
 
     /**
      * Decodes a permutation represented by <code>representation</code> and
      * returns a (generic) list with the permuted values.
      *
      * @param <S> generic type of the sequence values
      * @param sequence the unpermuted sequence
      * @param representation representation of the permutation ([0,1] vector)
      * @param sortedRepr sorted <code>representation</code>
      * @return list with the sequence values permuted according to the representation
      * @throws DimensionMismatchException iff the length of the <code>sequence</code>,
      *   <code>representation</code> or <code>sortedRepr</code> lists are not equal
      */
     private static <S> List<S> decodeGeneric(final List<S> sequence, List<Double> representation,
                                              final List<Double> sortedRepr)
         throws DimensionMismatchException {
 
         int l = sequence.size();
 
         // the size of the three lists must be equal
         if (representation.size() != l) {
             throw new DimensionMismatchException(representation.size(), l);
         }
         if (sortedRepr.size() != l) {
             throw new DimensionMismatchException(sortedRepr.size(), l);
         }
 
         // do not modify the original representation
         List<Double> reprCopy = new ArrayList<> (representation);
 
         // now find the indices in the original repr and use them for permuting
         List<S> res = new ArrayList<> (l);
         for (int i=0; i<l; i++) {
             int index = reprCopy.indexOf(sortedRepr.get(i));
             res.add(sequence.get(index));
             reprCopy.set(index, null);
         }
         return res;
     }
 
     /**
      * Returns <code>true</code> iff <code>another</code> is a RandomKey and
      * encodes the same permutation.
      *
      * @param another chromosome to compare
      * @return true iff chromosomes encode the same permutation
      */
     @Override
     protected boolean isSame(final Chromosome another) {
         // type check
         if (! (another instanceof RandomKey<?>)) {
             return false;
         }
         RandomKey<?> anotherRk = (RandomKey<?>) another;
         // size check
         if (getLength() != anotherRk.getLength()) {
             return false;
         }
 
         // two different representations can still encode the same permutation
         // the ordering is what counts
         List<Integer> thisPerm = this.baseSeqPermutation;
         List<Integer> anotherPerm = anotherRk.baseSeqPermutation;
 
         for (int i=0; i<getLength(); i++) {
             if (!thisPerm.get(i).equals(anotherPerm.get(i))) {
                 return false;
             }
         }
         // the permutations are the same
         return true;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     protected void checkValidity(final List<Double> chromosomeRepresentation)
         throws InvalidRepresentationException {
 
         for (double val : chromosomeRepresentation) {
             if (val < 0 || val > 1) {
                 throw new InvalidRepresentationException(LocalizedFormats.OUT_OF_RANGE_SIMPLE,
                                                          val, 0, 1);
             }
         }
     }
 
 
     /**
      * Generates a representation corresponding to a random permutation of
      * length l which can be passed to the RandomKey constructor.
      *
      * @param l length of the permutation
      * @return representation of a random permutation
      */
     public static final List<Double> randomPermutation(final int l) {
         List<Double> repr = new ArrayList<>(l);
         for (int i=0; i<l; i++) {
             repr.add(GeneticAlgorithm.getRandomGenerator().nextDouble());
         }
         return repr;
     }
 
     /**
      * Generates a representation corresponding to an identity permutation of
      * length l which can be passed to the RandomKey constructor.
      *
      * @param l length of the permutation
      * @return representation of an identity permutation
      */
     public static final List<Double> identityPermutation(final int l) {
         List<Double> repr = new ArrayList<>(l);
         for (int i=0; i<l; i++) {
             repr.add((double)i/l);
         }
         return repr;
     }
 
     /**
      * Generates a representation of a permutation corresponding to the
      * <code>data</code> sorted by <code>comparator</code>. The
      * <code>data</code> is not modified during the process.
      *
      * This is useful if you want to inject some permutations to the initial
      * population.
      *
      * @param <S> type of the data
      * @param data list of data determining the order
      * @param comparator how the data will be compared
      * @return list representation of the permutation corresponding to the parameters
      */
     public static <S> List<Double> comparatorPermutation(final List<S> data,
                                                          final Comparator<S> comparator) {
         List<S> sortedData = new ArrayList<>(data);
         Collections.sort(sortedData, comparator);
 
         return inducedPermutation(data, sortedData);
     }
 
     /**
      * Generates a representation of a permutation corresponding to a
      * permutation which yields <code>permutedData</code> when applied to
      * <code>originalData</code>.
      *
      * This method can be viewed as an inverse to {@link #decode(List)}.
      *
      * @param <S> type of the data
      * @param originalData the original, unpermuted data
      * @param permutedData the data, somehow permuted
      * @return representation of a permutation corresponding to the permutation
      *   {@code originalData -> permutedData}
      * @throws DimensionMismatchException iff the length of <code>originalData</code>
      *   and <code>permutedData</code> lists are not equal
      * @throws MathIllegalArgumentException iff the <code>permutedData</code> and
      *   <code>originalData</code> lists contain different data
      */
     public static <S> List<Double> inducedPermutation(final List<S> originalData,
                                                       final List<S> permutedData)
         throws DimensionMismatchException, MathIllegalArgumentException {
 
         if (originalData.size() != permutedData.size()) {
             throw new DimensionMismatchException(permutedData.size(), originalData.size());
         }
         int l = originalData.size();
 
         List<S> origDataCopy = new ArrayList<> (originalData);
 
         Double[] res = new Double[l];
         for (int i=0; i<l; i++) {
             int index = origDataCopy.indexOf(permutedData.get(i));
             if (index == -1) {
                 throw new MathIllegalArgumentException(LocalizedFormats.DIFFERENT_ORIG_AND_PERMUTED_DATA);
             }
             res[index] = (double) i / l;
             origDataCopy.set(index, null);
         }
         return Arrays.asList(res);
     }
 
     /** {@inheritDoc} */
     @Override
     public String toString() {
         return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
     }
 
     /**
      * Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
      *
      * @param l length of list to generate
      * @return list of integers from 0 to l-1
      */
     private static List<Integer> baseSequence(final int l) {
         List<Integer> baseSequence = new ArrayList<> (l);
         for (int i=0; i<l; i++) {
             baseSequence.add(i);
         }
         return baseSequence;
     }
 }