1 /******************************************************************************* 2 * Copyright 2011 See AUTHORS file. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 ******************************************************************************/ 16 17 package com.badlogic.gdx.utils; 18 19 import java.util.Comparator; 20 21 /** This class is for selecting a ranked element (kth ordered statistic) from an unordered list in faster time than sorting the 22 * whole array. Typical applications include finding the nearest enemy unit(s), and other operations which are likely to run as 23 * often as every x frames. Certain values of k will result in a partial sorting of the Array. 24 * <p> 25 * The lowest ranking element starts at 1, not 0. 1 = first, 2 = second, 3 = third, etc. calling with a value of zero will result 26 * in a {@link GdxRuntimeException} 27 * </p> 28 * <p> 29 * This class uses very minimal extra memory, as it makes no copies of the array. The underlying algorithms used are a naive 30 * single-pass for k=min and k=max, and Hoare's quickselect for values in between. 31 * </p> 32 * @author Jon Renner */ 33 public class Select { 34 private static Select instance; 35 private QuickSelect quickSelect; 36 37 /** Provided for convenience */ instance()38 public static Select instance () { 39 if (instance == null) instance = new Select(); 40 return instance; 41 } 42 select(T[] items, Comparator<T> comp, int kthLowest, int size)43 public <T> T select (T[] items, Comparator<T> comp, int kthLowest, int size) { 44 int idx = selectIndex(items, comp, kthLowest, size); 45 return items[idx]; 46 } 47 selectIndex(T[] items, Comparator<T> comp, int kthLowest, int size)48 public <T> int selectIndex (T[] items, Comparator<T> comp, int kthLowest, int size) { 49 if (size < 1) { 50 throw new GdxRuntimeException("cannot select from empty array (size < 1)"); 51 } else if (kthLowest > size) { 52 throw new GdxRuntimeException("Kth rank is larger than size. k: " + kthLowest + ", size: " + size); 53 } 54 int idx; 55 // naive partial selection sort almost certain to outperform quickselect where n is min or max 56 if (kthLowest == 1) { 57 // find min 58 idx = fastMin(items, comp, size); 59 } else if (kthLowest == size) { 60 // find max 61 idx = fastMax(items, comp, size); 62 } else { 63 // quickselect a better choice for cases of k between min and max 64 if (quickSelect == null) quickSelect = new QuickSelect(); 65 idx = quickSelect.select(items, comp, kthLowest, size); 66 } 67 return idx; 68 } 69 70 /** Faster than quickselect for n = min */ fastMin(T[] items, Comparator<T> comp, int size)71 private <T> int fastMin (T[] items, Comparator<T> comp, int size) { 72 int lowestIdx = 0; 73 for (int i = 1; i < size; i++) { 74 int comparison = comp.compare(items[i], items[lowestIdx]); 75 if (comparison < 0) { 76 lowestIdx = i; 77 } 78 } 79 return lowestIdx; 80 } 81 82 /** Faster than quickselect for n = max */ fastMax(T[] items, Comparator<T> comp, int size)83 private <T> int fastMax (T[] items, Comparator<T> comp, int size) { 84 int highestIdx = 0; 85 for (int i = 1; i < size; i++) { 86 int comparison = comp.compare(items[i], items[highestIdx]); 87 if (comparison > 0) { 88 highestIdx = i; 89 } 90 } 91 return highestIdx; 92 } 93 } 94