com.jme3.util

Class ListSort<T>

java.lang.Object

com.jme3.util.ListSort<T>

public class ListSort<T>
extends java.lang.Object

Fast, stable sort used to sort geometries It's adapted from Tim Peters's work on list sorting for Python. More details here http://svn.python.org/projects/python/trunk/Objects/listsort.txt here is the C code from which this class is based http://svn.python.org/projects/python/trunk/Objects/listobject.c This class was also greatly inspired from java 7 TimSort by Josh Blosh with the difference that the temporary necessary memory space are allocated as the geometry list grows and reused all along the application execution. Usage : ListSort has to be instantiated and kept with the geometry list ( or w/e it may have to sort) Then the allocate method has to be called to allocate necessary tmp space needed for the sort. This should be called once for optimal performance, but can be called several times if the length of the list changes Disclaimer : I was intrigued by the use of val >>> 1 in java 7 Timsort class instead of val / 2 (integer division). Micro benching revealed that val >>> 1 is twice faster than val / 2 in java 6 and has similar perf in java 7. The following code uses val >>> 1 when ever a value needs to be divided by 2 and rounded to its floor

Constructor Summary

Constructors

Constructor and Description
ListSort() Creates a ListSort

Method Summary

Modifier and Type	Method and Description
void	allocateStack(int len) Allocate temp variables for the given length This method should be called at least once, but only if the length of the list to sort changed before sorting
int	getLength() return the useful length of the array being sorted
void	innerMergeHigh(java.util.Comparator<T> comp, T[] tempArray, T[] arr, int idxA) Attempt to unroll "goto" style original implementation.
void	innerMergeLow(java.util.Comparator<T> comp, T[] arr, T[] tempArray) Attempt to unroll "goto" style original implementation.
static void	main(java.lang.String[] argv) test case
void	sort(T[] array, java.util.Comparator<T> comparator) Sort the given array given the comparator

Methods inherited from class java.lang.Object

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

Constructor Detail

ListSort

public ListSort()

Creates a ListSort

Method Detail

allocateStack

public final void allocateStack(int len)

Allocate temp variables for the given length This method should be called at least once, but only if the length of the list to sort changed before sorting

Parameters:

len -

sort

public void sort(T[] array,
                 java.util.Comparator<T> comparator)

Sort the given array given the comparator

Parameters:

array - the array to sort

comparator - the comparator to compare elements of the array

innerMergeLow

public void innerMergeLow(java.util.Comparator<T> comp,
                          T[] arr,
                          T[] tempArray)

Attempt to unroll "goto" style original implementation. this method uses and change temp attributes of the class

Parameters:

comp - comparator

arr - the array

tempArray - the temp array

innerMergeHigh

public void innerMergeHigh(java.util.Comparator<T> comp,
                           T[] tempArray,
                           T[] arr,
                           int idxA)

Attempt to unroll "goto" style original implementation. this method uses and change temp attributes of the class

Parameters:

comp - comparator

arr - the array

tempArray - the temp array

idxA - the index of the first element of run A

getLength

public int getLength()

return the useful length of the array being sorted

Returns:

the length pass to the last allocateStack method

main

public static void main(java.lang.String[] argv)

test case