001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009package imagingbook.common.util;
010
011import java.util.stream.IntStream;
012
013/**
014 * <p>
015 * Determines the 'permutation' of a sequence of numbers and keeps it as an array ({@code perm}) of position indexes.
016 * These indexes indicate how the original input array may be re-ordered to become sorted (see
017 * {@link #getPermutation()}). Implemented only for arrays of type {@code int}, {@code float} and {@code double}.
018 * </p>
019 * <p>
020 * Usage example - get the second-smallest element of a {@code double} array:
021 * </p>
022 * <pre>
023 *      double[] a = ...        // some array
024 *      int k = PrimitiveSortMap.getNthSmallestIndex(a, 1);     // index of 2nd-smallest element
025 *      double x = a[k];
026 * </pre>
027 * <p>
028 * Alternatively, the 2nd-smallest <em>value</em> can be obtained directly by
029 * </p>
030 * <pre>
031 * double x = PrimitiveSortMap.getNthSmallestValue(a, 1);
032 * </pre>
033 *
034 * @author WB
035 * @version 2022/09/15
036 */
037public class PrimitiveSortMap {
038        
039        private final int[] perm;
040        
041        /**
042         * Constructor for {@code double[]}. The input array is not modified.
043         * @param a the input array
044         */
045        public PrimitiveSortMap(double[] a) {
046                this.perm = IntStream.range(0, a.length).boxed()
047                        .sorted((i, j) -> Double.compare(a[i], a[j]))
048                        .mapToInt(x->x.intValue()).toArray();
049        }
050        
051        /**
052         * Constructor for {@code float[]}. The input array is not modified.
053         * @param a the input array
054         */
055        public PrimitiveSortMap(float[] a) {
056                this.perm = IntStream.range(0, a.length).boxed()
057                        .sorted((i, j) -> Float.compare(a[i], a[j]))
058                        .mapToInt(x->x.intValue()).toArray();
059        }
060        
061        /**
062         * Constructor for {@code int[]}. The input array is not modified.
063         * @param a the input array
064         */
065        public PrimitiveSortMap(int[] a) {
066                this.perm = IntStream.range(0, a.length).boxed()
067                        .sorted((i, j) -> Integer.compare(a[i], a[j]))
068                        .mapToInt(x->x.intValue()).toArray();
069        }
070        
071        // --------------------------------------------------
072
073        /**
074         * Returns the permutation (position indexes) for the underlying number sequence as a {@code int} array. That is,
075         * the first value in the returned array is the index of the smallest element in {@code numbers}, the second element
076         * points to the second-smallest element, etc. For example, if the original number sequence (passed to the
077         * constructor) is
078         * <pre>
079         *     double[] a = {50.0, 20.0, 100.0, 120.0, 40.0, -10.0};
080         * </pre>
081         * then the index array produced by
082         * <pre>
083         *     int[] perm = new PrimitiveSortMap(a).getPermutation();
084         * </pre> contains
085         * {@code (5, 1, 4, 0, 2, 3)}. This means that
086         * <pre>
087         *     a[perm[i]] &le; a[perm[i+1]]
088         * </pre>
089         * and thus the sequence
090         * <pre>
091         *     {a[perm[0]], A[perm[1]],..., A[perm[N-1]]}
092         * </pre>
093         * is sorted.
094         *
095         * @return the sorting map (permutation)
096         */
097        public int[] getPermutation() {
098                return this.perm;
099        }
100
101        /**
102         * Returns the index of the n-th smallest element of the original number sequence (passed to the constructor),
103         * starting with {@code n = 0}, which returns the index of the smallest element.
104         *
105         * @param n the index
106         * @return the index of the n-th smallest element in the original number sequence
107         */
108        public int getIndex(int n) {
109                if (n < 0 || n >= perm.length) {
110                        throw new IllegalArgumentException("position index n out of range: " + n);
111                }
112                return perm[n];
113        }
114        
115        // --------------------------------------------------
116
117        /**
118         * Returns the nth smallest element of the specified array, starting with n = 0, which returns the smallest element
119         * of the array.
120         *
121         * @param numbers sequence of unsorted values
122         * @param n the index
123         * @return the n-th smallest element
124         */
125        public static double getNthSmallestValue(double[] numbers, int n) {
126                return numbers[getNthSmallestIndex(numbers, n)];
127        }
128
129        /**
130         * Returns the index of the nth smallest element of the specified array, starting with n = 0, which returns the
131         * smallest element of the array.
132         *
133         * @param numbers sequence of unsorted values
134         * @param n the index
135         * @return the index of the n-th smallest element
136         */
137        public static int getNthSmallestIndex(double[] numbers, int n) {
138                return new PrimitiveSortMap(numbers).getIndex(n);
139        }
140        
141        /**
142         * Returns the largest element of the specified array.
143         * 
144         * @param numbers sequence of unsorted values
145         * @return the largest element
146         */
147        public static double getLargestValue(double[] numbers) {
148                return numbers[getLargestIndex(numbers)];
149        }
150        
151        /**
152         * Returns the index of the largest element of the specified array.
153         * 
154         * @param numbers sequence of unsorted values
155         * @return the index of the largest element
156         */
157        public static int getLargestIndex(double[] numbers) {
158                return getNthSmallestIndex(numbers, numbers.length - 1);
159        }
160
161        /**
162         * Returns the nth smallest element of the specified array, starting with n = 0, which returns the smallest element
163         * of the array.
164         *
165         * @param numbers sequence of unsorted values
166         * @param n the index
167         * @return the n-th smallest element
168         */
169        public static float getNthSmallestValue(float[] numbers, int n) {
170                return numbers[getNthSmallestIndex(numbers, n)];
171        }
172
173        /**
174         * Returns the index of the nth smallest element of the specified array, starting with n = 0, which returns the
175         * smallest element of the array.
176         *
177         * @param numbers sequence of unsorted values
178         * @param n the index
179         * @return the index of the n-th smallest element
180         */
181        public static int getNthSmallestIndex(float[] numbers, int n) {
182                return new PrimitiveSortMap(numbers).getIndex(n);
183        }
184        
185        /**
186         * Returns the largest element of the specified array.
187         * 
188         * @param numbers sequence of unsorted values
189         * @return the largest element
190         */
191        public static float getLargestValue(float[] numbers) {
192                return numbers[getLargestIndex(numbers)];
193        }
194        
195        /**
196         * Returns the index of the largest element of the specified array.
197         * 
198         * @param numbers sequence of unsorted values
199         * @return the index of the largest element
200         */
201        public static int getLargestIndex(float[] numbers) {
202                return getNthSmallestIndex(numbers, numbers.length - 1);
203        }
204
205        /**
206         * Returns the nth smallest element of the specified {@code int[]}, starting with {@code n = 0}, which returns the
207         * smallest element of {@code numbers}.
208         *
209         * @param numbers sequence of unsorted values
210         * @param n the index
211         * @return the n-th smallest element of {@code numbers}
212         */
213        public static int getNthSmallestValue(int[] numbers, int n) {
214                return numbers[getNthSmallestIndex(numbers, n)];
215        }
216
217        /**
218         * Returns the index of the nth smallest element of the specified array, starting with n = 0, which returns the
219         * smallest element of the array.
220         *
221         * @param numbers sequence of unsorted values
222         * @param n the index
223         * @return the index of the n-th smallest element
224         */
225        public static int getNthSmallestIndex(int[] numbers, int n) {
226                return new PrimitiveSortMap(numbers).getIndex(n);
227        }
228        
229        /**
230         * Returns the largest element of the specified array.
231         * 
232         * @param numbers sequence of unsorted values
233         * @return the largest element
234         */
235        public static float getLargestValue(int[] numbers) {
236                return numbers[getLargestIndex(numbers)];
237        }
238        
239        /**
240         * Returns the index of the largest element of the specified array.
241         * 
242         * @param numbers sequence of unsorted values
243         * @return the index of the largest element
244         */
245        public static int getLargestIndex(int[] numbers) {
246                return getNthSmallestIndex(numbers, numbers.length - 1);
247        }
248        
249}