jsat.utils

Class IndexTable

java.lang.Object

jsat.utils.IndexTable

All Implemented Interfaces:

java.io.Serializable

public class IndexTable
extends java.lang.Object
implements java.io.Serializable

The index table provides a way of accessing the sorted view of an array or list, without ever sorting the elements of said list. Given an array of elements, the index table creates an array of index values, and sorts the indices based on the values they point to. The IndexTable can then be used to find the index of the i'th sorted element in the array.

The IndexTable can be sorted multiple times by calling the sort(java.util.List, java.util.Comparator) methods. This can be called on inputs of varying size, and the internal order will be expanded when necessary.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
IndexTable(double[] array) Creates a new index table based on the given array.
IndexTable(int size) Creates a new index table of a specified size that is in linear order.
IndexTable(java.util.List<T> list) Creates a new index table based on the given list.
IndexTable(java.util.List<T> list, java.util.Comparator<T> comparator) Creates a new index table based on the given list and comparator.
IndexTable(T[] array) Creates a new index table based on the given array.

Method Summary

Modifier and Type	Method and Description
void	apply(double[] target) Applies this index table to the specified target, putting target into the same ordering as this IndexTable.
void	apply(java.util.List target) Applies this index table to the specified target, putting target into the same ordering as this IndexTable.
void	apply(java.util.List target, java.util.List tmp) Applies this index table to the specified target, putting target into the same ordering as this IndexTable.
static <T> java.util.Comparator<T>	getReverse(java.util.Comparator<T> cmp) Obtains the reverse order comparator
int	index(int i) Given the index i into what would be the sorted array, the index in the unsorted original array is returned.
int	length() The length of the previous array that was sorted
void	reset() Resets the index table so that the returned indices are in linear order, meaning the original input would be returned in its original order instead of sorted order.
void	reverse() Reverse the current index order
void	sort(double[] array) Adjusts this index table to contain the sorted index order for the given array
<T extends java.lang.Comparable<T>> void	sort(java.util.List<T> list) Adjust this index table to contain the sorted index order for the given list
<T> void	sort(java.util.List<T> list, java.util.Comparator<T> cmp) Sets up the index table based on the given list of the same size and comparator.
void	sortR(double[] array) Adjusts this index table to contain the reverse sorted index order for the given array
<T extends java.lang.Comparable<T>> void	sortR(java.util.List<T> list) Adjusts this index table to contain the reverse sorted index order for the given list
void	swap(int i, int j) Swaps the given indices in the index table.

Methods inherited from class java.lang.Object

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

Constructor Detail

IndexTable

public IndexTable(int size)

Creates a new index table of a specified size that is in linear order.

Parameters:

size - the size of the index table to create

IndexTable

public IndexTable(double[] array)

Creates a new index table based on the given array. The array will not be altered.

Parameters:

array - the array to create an index table for.

IndexTable

public IndexTable(T[] array)

Creates a new index table based on the given array. The array will not be altered.

Parameters:

array - the array to create an index table for

IndexTable

public IndexTable(java.util.List<T> list)

Creates a new index table based on the given list. The list will not be altered.

Parameters:

list - the list to create an index table for

IndexTable

public IndexTable(java.util.List<T> list,
                  java.util.Comparator<T> comparator)

Creates a new index table based on the given list and comparator. The list will not be altered.

Parameters:

list - the list of points to obtain a sorted IndexTable for

comparator - the comparator to determined the sorted order

Method Detail

getReverse

public static <T> java.util.Comparator<T> getReverse(java.util.Comparator<T> cmp)

Obtains the reverse order comparator

Type Parameters:

T - the data type

Parameters:

cmp - the original comparator

Returns:

the reverse order comparator

reset

public void reset()

Resets the index table so that the returned indices are in linear order, meaning the original input would be returned in its original order instead of sorted order.

reverse

public void reverse()

Reverse the current index order

sort

public void sort(double[] array)

Adjusts this index table to contain the sorted index order for the given array

Parameters:

array - the input to get sorted order of

sortR

public void sortR(double[] array)

Adjusts this index table to contain the reverse sorted index order for the given array

Parameters:

array - the input to get sorted order of

sort

public <T extends java.lang.Comparable<T>> void sort(java.util.List<T> list)

Adjust this index table to contain the sorted index order for the given list

Type Parameters:

T - the data type

Parameters:

list - the list of objects

sortR

public <T extends java.lang.Comparable<T>> void sortR(java.util.List<T> list)

Adjusts this index table to contain the reverse sorted index order for the given list

Type Parameters:

T - the data type

Parameters:

list - the list of objects

sort

public <T> void sort(java.util.List<T> list,
                     java.util.Comparator<T> cmp)

Sets up the index table based on the given list of the same size and comparator.

Type Parameters:

T - the type in use

Parameters:

list - the list of points to obtain a sorted IndexTable for

cmp - the comparator to determined the sorted order

swap

public void swap(int i,
                 int j)

Swaps the given indices in the index table.

Parameters:

i - the second index to swap

j - the first index to swap

index

public int index(int i)

Given the index i into what would be the sorted array, the index in the unsorted original array is returned.
If the original array was a double array, double[] vals, then the sorted order can be printed with

 for(int i = 0; i < indexTable.length(); i++)
     System.out.println(vals[indexTable.get(i)]);
 

Parameters:

i - the index of the i'th sorted value

Returns:

the index in the original list that would be in the i'th position

length

public int length()

The length of the previous array that was sorted

Returns:

the length of the original array

apply

public void apply(double[] target)

Applies this index table to the specified target, putting target into the same ordering as this IndexTable.

Throws:

java.lang.RuntimeException - if the length of the target array is not the same as the index table

apply

public void apply(java.util.List target)

Applies this index table to the specified target, putting target into the same ordering as this IndexTable.

Throws:

java.lang.RuntimeException - if the length of the target List is not the same as the index table

apply

public void apply(java.util.List target,
                  java.util.List tmp)

Applies this index table to the specified target, putting target into the same ordering as this IndexTable. It will use the provided tmp space to store the original values in target in the same ordering. It will be modified, and may be expanded using the add method if it does not contain sufficient space. Extra size in the tmp list will be ignored. After this method is called, tmp will contain the same ordering that was in target

This method is provided as a means to reducing memory use when multiple lists need to be sorted.

Parameters:

target - the list to sort, that should be the same size as the previously sorted list.

tmp - the temp list that may be of any size