package jsat.utils;
import java.io.Serializable;
import java.util.*;
/**
* 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
* {@link #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.
*
* @author Edward Raff
*/
public class IndexTable implements Serializable
{
private static final long serialVersionUID = -1917765351445664286L;
static private final Comparator defaultComp = (Comparator) (Object o1, Object o2) ->
{
Comparable co1 = (Comparable) o1;
Comparable co2 = (Comparable) o2;
return co1.compareTo(co2);
};
/**
* Obtains the reverse order comparator
* @param the data type
* @param cmp the original comparator
* @return the reverse order comparator
*/
public static Comparator getReverse(final Comparator cmp)
{
return (T o1, T o2) -> -cmp.compare(o1, o2);
}
/**
* We use an array of Integer objects instead of integers because we need
* the arrays.sort function that accepts comparators.
*/
private IntList index;
/**
* The size of the previously sorted array or list
*/
private int prevSize;
/**
* Creates a new index table of a specified size that is in linear order.
* @param size the size of the index table to create
*/
public IndexTable(int size)
{
index = new IntList(size);
ListUtils.addRange(index, 0, size, 1);
}
/**
* Creates a new index table based on the given array. The array will not be altered.
* @param array the array to create an index table for.
*/
public IndexTable(double[] array)
{
this(DoubleList.unmodifiableView(array, array.length));
}
/**
* Creates a new index table based on the given array. The array will not be altered.
* @param array the array to create an index table for
*/
public > IndexTable(T[] array)
{
index = new IntList(array.length);
ListUtils.addRange(index, 0, array.length, 1);
Collections.sort(index, new IndexViewCompG(array));
}
/**
* Creates a new index table based on the given list. The list will not be altered.
* @param list the list to create an index table for
*/
public > IndexTable(List list)
{
this(list, defaultComp);
}
/**
* Creates a new index table based on the given list and comparator. The
* list will not be altered.
*
* @param list the list of points to obtain a sorted IndexTable for
* @param comparator the comparator to determined the sorted order
*/
public IndexTable(List list, Comparator comparator)
{
index = new IntList(list.size());
ListUtils.addRange(index, 0, list.size(), 1);
sort(list, comparator);
}
/**
* 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.
*/
public void reset()
{
for(int i = 0; i < index.size(); i++)
index.set(i, i);
}
/**
* Reverse the current index order
*/
public void reverse()
{
Collections.reverse(index);
}
/**
* Adjusts this index table to contain the sorted index order for the given
* array
* @param array the input to get sorted order of
*/
public void sort(double[] array)
{
sort(DoubleList.unmodifiableView(array, array.length));
}
/**
* Adjusts this index table to contain the reverse sorted index order for
* the given array
* @param array the input to get sorted order of
*/
public void sortR(double[] array)
{
sortR(DoubleList.unmodifiableView(array, array.length));
}
/**
* Adjust this index table to contain the sorted index order for the given
* list
* @param the data type
* @param list the list of objects
*/
public > void sort(List list)
{
sort(list, defaultComp);
}
/**
* Adjusts this index table to contain the reverse sorted index order for
* the given list
* @param the data type
* @param list the list of objects
*/
public > void sortR(List list)
{
sort(list, getReverse(defaultComp));
}
/**
* Sets up the index table based on the given list of the same size and
* comparator.
*
* @param the type in use
* @param list the list of points to obtain a sorted IndexTable for
* @param cmp the comparator to determined the sorted order
*/
public void sort(List list, Comparator cmp)
{
if(index.size() < list.size())
for(int i = index.size(); i < list.size(); i++ )
index.add(i);
if(list.size() == index.size())
Collections.sort(index, new IndexViewCompList(list, cmp));
else
{
Collections.sort(index);//so [0, list.size) is at the front
Collections.sort(index.subList(0, list.size()), new IndexViewCompList(list, cmp));
}
prevSize = list.size();
}
private class IndexViewCompG> implements Comparator
{
T[] base;
public IndexViewCompG(T[] base)
{
this.base = base;
}
@Override
public int compare(Integer t, Integer t1)
{
return base[t].compareTo(base[t1]);
}
}
private class IndexViewCompList implements Comparator
{
final List base;
final Comparator comparator;
public IndexViewCompList(List base, Comparator comparator)
{
this.base = base;
this.comparator = comparator;
}
@Override
public int compare(Integer t, Integer t1)
{
return comparator.compare(base.get(t), base.get(t1));
}
}
/**
* Swaps the given indices in the index table.
* @param i the second index to swap
* @param j the first index to swap
*/
public void swap(int i, int j)
{
Collections.swap(index, i, j);
}
/**
* 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.{@link #length() length}(); i++)
* System.out.println(vals[indexTable.get(i)]);
*
* @param i the index of the i'th sorted value
* @return the index in the original list that would be in the i'th position
*/
public int index(int i)
{
if(i >= prevSize || i < 0)
throw new IndexOutOfBoundsException("The size of the previously sorted array/list is " + prevSize + " so index " + i + " is not valid");
return index.get(i);
}
/**
* The length of the previous array that was sorted
* @return the length of the original array
*/
public int length()
{
return prevSize;
}
/**
* Applies this index table to the specified target, putting {@code target}
* into the same ordering as this IndexTable.
*
* @throws RuntimeException if the length of the target array is not the same as the index table
*/
public void apply(double[] target)
{
//use DoubleList view b/d we are only using set ops, so we wont run into an issue of re-allocating the array
apply(DoubleList.view(target, target.length), new DoubleList(target.length));
}
/**
* Applies this index table to the specified target, putting {@code target}
* into the same ordering as this IndexTable.
*
* @throws RuntimeException if the length of the target List is not the same as the index table
*/
public void apply(List target)
{
apply(target, new ArrayList(target.size()));
}
/**
* Applies this index table to the specified target, putting {@code target}
* into the same ordering as this IndexTable. It will use the provided
* {@code tmp} space to store the original values in target in the same
* ordering. It will be modified, and may be expanded using the {@link
* List#add(java.lang.Object) add} method if it does not contain sufficient
* space. Extra size in the tmp list will be ignored. After this method is
* called, {@code tmp} will contain the same ordering that was in
* {@code target}
*
* This method is provided as a means to reducing memory use when multiple
* lists need to be sorted.
*
* @param target the list to sort, that should be the same size as the
* previously sorted list.
* @param tmp the temp list that may be of any size
*/
public void apply(List target, List tmp)
{
if (target.size() != length())
throw new RuntimeException("target array does not have the same length as the index table");
//fill tmp with the original ordering or target, adding when needed
for (int i = 0; i < target.size(); i++)
if (i >= tmp.size())
tmp.add(target.get(i));
else
tmp.set(i, target.get(i));
//place back into target from tmp to get sorted order
for(int i = 0; i < target.size(); i++)
target.set(i, tmp.get(index(i)));
}
}
Ads help maintain this website.