1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.numbers.arrays;
19
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collections;
23 import java.util.Comparator;
24 import java.util.List;
25
26 /**
27 * Sort an array and perform the same reordering of entries on other arrays.
28 * For example, if
29 * <ul>
30 * <li>{@code x = [3, 1, 2]}</li>
31 * <li>{@code y = [1, 2, 3]}</li>
32 * <li>{@code z = [0, 5, 7]}</li>
33 * </ul>
34 * then {@code Sort.ASCENDING.apply(x, y, z)} will update those arrays:
35 * <ul>
36 * <li>{@code x = [1, 2, 3]}</li>
37 * <li>{@code y = [2, 3, 1]}</li>
38 * <li>{@code z = [5, 7, 0]}</li>
39 * </ul>
40 */
41 public enum SortInPlace {
42 /** Sort in ascending order. */
43 ASCENDING((o1, o2) -> Double.compare(o1.key(), o2.key())),
44 /** Sort in descending order. */
45 DESCENDING((o1, o2) -> Double.compare(o2.key(), o1.key()));
46
47 /** Comparator. */
48 private final Comparator<PairDoubleInteger> comparator;
49
50 /**
51 * @param comparator Comparator.
52 */
53 SortInPlace(Comparator<PairDoubleInteger> comparator) {
54 this.comparator = comparator;
55 }
56
57 /**
58 * Sorts in place.
59 *
60 * @param x Array to be sorted and used as a pattern for permutation of
61 * the other arrays.
62 * @param yList Set of arrays whose permutations of entries will follow
63 * those performed on {@code x}.
64 * @throws IllegalArgumentException if not all arrays have the same size.
65 */
66 public void apply(double[] x,
67 double[]... yList) {
68 final int yListLen = yList.length;
69 final int len = x.length;
70
71 for (int j = 0; j < yListLen; j++) {
72 final double[] y = yList[j];
73 if (y.length != len) {
74 throw new IllegalArgumentException("Size mismatch: " +
75 y.length + " != " + len);
76 }
77 }
78
79 // Associate each abscissa "x[i]" with its index "i".
80 final List<PairDoubleInteger> list = new ArrayList<>(len);
81 for (int i = 0; i < len; i++) {
82 list.add(new PairDoubleInteger(x[i], i));
83 }
84
85 // Sort.
86 Collections.sort(list, comparator);
87
88 // Modify the original array so that its elements are in the prescribed order.
89 // Retrieve indices of original locations.
90 final int[] indices = new int[len];
91 for (int i = 0; i < len; i++) {
92 final PairDoubleInteger e = list.get(i);
93 x[i] = e.key();
94 indices[i] = e.value();
95 }
96
97 // In every associated array, move the elements to their new location.
98 for (int j = 0; j < yListLen; j++) {
99 // 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 }