APIdia Launch Partner
Top Description Fields Constructors Methods
com.badlogic.gdx.utils

public Class Select

extends Object
Class Inheritance
Imports
java.util.Comparator
This class is for selecting a ranked element (kth ordered statistic) from an unordered list in faster time than sorting the whole array. Typical applications include finding the nearest enemy unit(s), and other operations which are likely to run as often as every x frames. Certain values of k will result in a partial sorting of the Array.

The lowest ranking element starts at 1, not 0. 1 = first, 2 = second, 3 = third, etc. calling with a value of zero will result in a GdxRuntimeException

This class uses very minimal extra memory, as it makes no copies of the array. The underlying algorithms used are a naive single-pass for k=min and k=max, and Hoare's quickselect for values in between.

Author
Jon Renner

Field Summary

Modifier and TypeField and Description
private static Select
instance

private QuickSelect<T>
quickSelect

Constructor Summary

AccessConstructor and Description
public
Select()

Method Summary

Modifier and TypeMethod and Description
private <T> int
fastMax(T[] items, Comparator<T> comp, int size)

Faster than quickselect for n = max

private <T> int
fastMin(T[] items, Comparator<T> comp, int size)

Faster than quickselect for n = min

public static Select
instance()

Provided for convenience

public <T> T
select(T[] items, Comparator<T> comp, int kthLowest, int size)

public <T> int
selectIndex(T[] items, Comparator<T> comp, int kthLowest, int size)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

instanceback to summary
private static Select instance
quickSelectback to summary
private QuickSelect<T> quickSelect

Constructor Detail

Selectback to summary
public Select()

Method Detail

fastMaxback to summary
private <T> int fastMax(T[] items, Comparator<T> comp, int size)

Faster than quickselect for n = max

fastMinback to summary
private <T> int fastMin(T[] items, Comparator<T> comp, int size)

Faster than quickselect for n = min

instanceback to summary
public static Select instance()

Provided for convenience

selectback to summary
public <T> T select(T[] items, Comparator<T> comp, int kthLowest, int size)
selectIndexback to summary
public <T> int selectIndex(T[] items, Comparator<T> comp, int kthLowest, int size)