001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.numbers.arrays;
019
020import java.util.ArrayList;
021import java.util.Arrays;
022import java.util.Collections;
023import java.util.Comparator;
024import java.util.List;
025
026/**
027 * Sort an array and perform the same reordering of entries on other arrays.
028 * For example, if
029 * <ul>
030 *  <li>{@code x = [3, 1, 2]}</li>
031 *  <li>{@code y = [1, 2, 3]}</li>
032 *  <li>{@code z = [0, 5, 7]}</li>
033 * </ul>
034 * then {@code Sort.ASCENDING.apply(x, y, z)} will update those arrays:
035 * <ul>
036 *  <li>{@code x = [1, 2, 3]}</li>
037 *  <li>{@code y = [2, 3, 1]}</li>
038 *  <li>{@code z = [5, 7, 0]}</li>
039 * </ul>
040 */
041public enum SortInPlace {
042    /** Sort in ascending order. */
043    ASCENDING((o1, o2) -> Double.compare(o1.key(), o2.key())),
044    /** Sort in descending order. */
045    DESCENDING((o1, o2) -> Double.compare(o2.key(), o1.key()));
046
047    /** Comparator. */
048    private final Comparator<PairDoubleInteger> comparator;
049
050    /**
051     * @param comparator Comparator.
052     */
053    SortInPlace(Comparator<PairDoubleInteger> comparator) {
054        this.comparator = comparator;
055    }
056
057    /**
058     * Sorts in place.
059     *
060     * @param x Array to be sorted and used as a pattern for permutation of
061     * the other arrays.
062     * @param yList Set of arrays whose permutations of entries will follow
063     * those performed on {@code x}.
064     * @throws IllegalArgumentException if not all arrays have the same size.
065     */
066    public void apply(double[] x,
067                      double[]... yList) {
068        final int yListLen = yList.length;
069        final int len = x.length;
070
071        for (int j = 0; j < yListLen; j++) {
072            final double[] y = yList[j];
073            if (y.length != len) {
074                throw new IllegalArgumentException("Size mismatch: " +
075                                                   y.length + " != " + len);
076            }
077        }
078
079        // Associate each abscissa "x[i]" with its index "i".
080        final List<PairDoubleInteger> list = new ArrayList<>(len);
081        for (int i = 0; i < len; i++) {
082            list.add(new PairDoubleInteger(x[i], i));
083        }
084
085        // Sort.
086        Collections.sort(list, comparator);
087
088        // Modify the original array so that its elements are in the prescribed order.
089        // Retrieve indices of original locations.
090        final int[] indices = new int[len];
091        for (int i = 0; i < len; i++) {
092            final PairDoubleInteger e = list.get(i);
093            x[i] = e.key();
094            indices[i] = e.value();
095        }
096
097        // In every associated array, move the elements to their new location.
098        for (int j = 0; j < yListLen; j++) {
099            // Input array will be modified in place.
100            final double[] yInPlace = yList[j];
101            final double[] yOrig = Arrays.copyOf(yInPlace, len);
102
103            for (int i = 0; i < len; i++) {
104                yInPlace[i] = yOrig[indices[i]];
105            }
106        }
107    }
108
109    /**
110     * Helper data structure holding a (double, integer) pair.
111     */
112    private static class PairDoubleInteger {
113        /** Key. */
114        private final double key;
115        /** Value. */
116        private final int value;
117
118        /**
119         * @param key Key.
120         * @param value Value.
121         */
122        PairDoubleInteger(double key,
123                          int value) {
124            this.key = key;
125            this.value = value;
126        }
127
128        /** @return the key. */
129        double key() {
130            return key;
131        }
132
133        /** @return the value. */
134        int value() {
135            return value;
136        }
137    }
138}