Package com.github.tommyettinger.ds

Class Select

java.lang.Object

com.github.tommyettinger.ds.Select

public final class Select
extends Object

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 RuntimeException

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.

Method Summary

Modifier and Type	Method	Description
static <T> T	select(Arrangeable.ArrangeableList<T> items, Comparator<T> comp, int kthLowest, int size)
static boolean	select(BooleanList items, BooleanComparator comp, int kthLowest, int size)
static byte	select(ByteList items, ByteComparator comp, int kthLowest, int size)
static char	select(CharList items, CharComparator comp, int kthLowest, int size)
static double	select(DoubleList items, DoubleComparator comp, int kthLowest, int size)
static float	select(FloatList items, FloatComparator comp, int kthLowest, int size)
static int	select(IntList items, IntComparator comp, int kthLowest, int size)
static long	select(LongList items, LongComparator comp, int kthLowest, int size)
static short	select(ShortList items, ShortComparator comp, int kthLowest, int size)
static <T> T	select(T[] items, Comparator<T> comp, int kthLowest, int size)
static <T> int	selectIndex(Arrangeable.ArrangeableList<T> items, Comparator<T> comp, int kthLowest, int size)
static int	selectIndex(BooleanList items, BooleanComparator comp, int kthLowest, int size)
static int	selectIndex(ByteList items, ByteComparator comp, int kthLowest, int size)
static int	selectIndex(CharList items, CharComparator comp, int kthLowest, int size)
static int	selectIndex(DoubleList items, DoubleComparator comp, int kthLowest, int size)
static int	selectIndex(FloatList items, FloatComparator comp, int kthLowest, int size)
static int	selectIndex(IntList items, IntComparator comp, int kthLowest, int size)
static int	selectIndex(LongList items, LongComparator comp, int kthLowest, int size)
static int	selectIndex(ShortList items, ShortComparator comp, int kthLowest, int size)
static <T> int	selectIndex(T[] items, Comparator<T> comp, int kthLowest, int size)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

select

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

selectIndex

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

select

public static <T> T select(Arrangeable.ArrangeableList<T> items,
 Comparator<T> comp,
 int kthLowest,
 int size)

selectIndex

public static <T> int selectIndex(Arrangeable.ArrangeableList<T> items,
 Comparator<T> comp,
 int kthLowest,
 int size)

select

public static int select(IntList items,
 IntComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(IntList items,
 IntComparator comp,
 int kthLowest,
 int size)

select

public static long select(LongList items,
 LongComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(LongList items,
 LongComparator comp,
 int kthLowest,
 int size)

select

public static float select(FloatList items,
 FloatComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(FloatList items,
 FloatComparator comp,
 int kthLowest,
 int size)

select

public static double select(DoubleList items,
 DoubleComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(DoubleList items,
 DoubleComparator comp,
 int kthLowest,
 int size)

select

public static short select(ShortList items,
 ShortComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(ShortList items,
 ShortComparator comp,
 int kthLowest,
 int size)

select

public static byte select(ByteList items,
 ByteComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(ByteList items,
 ByteComparator comp,
 int kthLowest,
 int size)

select

public static char select(CharList items,
 CharComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(CharList items,
 CharComparator comp,
 int kthLowest,
 int size)

select

public static boolean select(BooleanList items,
 BooleanComparator comp,
 int kthLowest,
 int size)

selectIndex

public static int selectIndex(BooleanList items,
 BooleanComparator comp,
 int kthLowest,
 int size)