Package com.jme3.util

Class ListSort<T>

java.lang.Object
com.jme3.util.ListSort<T>
public class ListSort<T> extends 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 on which this class is based: http://svn.python.org/projects/python/trunk/Objects/listobject.c This class was also greatly inspired by the Java7 TimSort by Josh Blosh, with the difference that temporary memory is allocated as the geometry list grows and reused throughout the execution of the application. 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 the Java7 Timsort in place of val / 2 (integer division). Micro benching revealed that val >>> 1 is twice as fast as val / 2 in Java6 and has similar perf in Java7. The following code uses val >>> 1 whenever a value needs to be divided by 2 and rounded to its floor.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ListSort()
    Creates a ListSort

  • Method Summary

    Modifier and Type
    Method
    Description
    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
    int
    getLength()
    return the useful length of the array being sorted
    void
    innerMergeHigh(Comparator<T> comp, T[] tempArray, T[] arr, int idxA)
    Attempt to unroll "goto" style original implementation.
    void
    innerMergeLow(Comparator<T> comp, T[] arr, T[] tempArray)
    Attempt to unroll "goto" style original implementation.
    static void
    main(String[] argv)
    test case
    void
    sort(T[] array, 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 Details

    • ListSort

      public ListSort()
      Creates a ListSort

  • Method Details

    • 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 - the size of the array to sort

    • sort

      public void sort(T[] array, 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(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(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(String[] argv)
      test case
      Parameters:
      argv - ignored