net.sf.kdgcommons.collections

Class InplaceSort

java.lang.Object

net.sf.kdgcommons.collections.InplaceSort

public class InplaceSort
extends Object

A collection of static sort routines for random-access data structures that provide the following characteristics:

• O(NlogN) performance
• In-place operation; unlike the JDK's list/array sort, does not consume additional heap memory
• Allows a comparator for sorting primitive ints
• Supports sorting of arbitrary data structures (eg, records stored in an of-heap buffer)
• May not be stable (the current implementation is heapsort, which is not stable)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	InplaceSort.Accessor The sort uses an implementation of this interface to access an array-like structure.
static interface	InplaceSort.IntComparator Implementations of this class compare two primitive ints, returning the same values as java.util.Comparator.

Constructor Summary

Constructors

Constructor and Description
InplaceSort()

Method Summary

Modifier and Type	Method and Description
static void	sort(InplaceSort.Accessor acc) Sorts a collection encapsulated by the provided InplaceSort.Accessor.
static void	sort(int[] array, InplaceSort.IntComparator comparator) Sorts a primitive integer array using an external comparator.
static void	sort(int[] array, int fromIndex, int toIndex, InplaceSort.IntComparator comparator) Sorts a portion of a primitive integer array using an external comparator.
static <T extends Comparable<T>> void	sort(List<T> list) Sorts a list using natural ordering.
static <T> void	sort(List<T> list, Comparator<T> comparator) Sorts a list using the provided comparator.
static <T extends Comparable<T>> void	sort(List<T> list, int fromIndex, int toIndex) Sorts a portion of a list using natural ordering.
static <T> void	sort(List<T> list, int fromIndex, int toIndex, Comparator<T> comparator) Sorts a portion of a list using natural ordering.
static <T extends Comparable<T>> void	sort(T[] array) Sorts an object array using natural ordering.
static <T> void	sort(T[] array, Comparator<T> comparator) Sorts an object array using the provided comparator.
static <T extends Comparable<T>> void	sort(T[] array, int fromIndex, int toIndex) Sorts a portion of an object array using natural ordering.
static <T> void	sort(T[] array, int fromIndex, int toIndex, Comparator<T> comparator) Sorts a portion of an object array using the provided comparator.

Methods inherited from class java.lang.Object

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

Constructor Detail

InplaceSort

public InplaceSort()

Method Detail

sort

public static void sort(int[] array,
                        InplaceSort.IntComparator comparator)

Sorts a primitive integer array using an external comparator.

This functionality is not provided by the JDK.

Parameters:

array - The array to be sorted

comparator - Used to order array elements

sort

public static void sort(int[] array,
                        int fromIndex,
                        int toIndex,
                        InplaceSort.IntComparator comparator)

Sorts a portion of a primitive integer array using an external comparator.

This functionality is not provided by the JDK.

Parameters:

array - The array to be sorted

fromIndex - The minimum bound of the search (inclusive)

toIndex - The maximum bound of the search (exclusive, following similar usage in the JDK; to sort the end of the array, pass array.length)

comparator - Used to order array elements

sort

public static <T extends Comparable<T>> void sort(T[] array)

Sorts an object array using natural ordering.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Arrays.sort() (a cost of 4 or 8 bytes per element, depending on JVM).

Parameters:

array - The array to be sorted

sort

public static <T extends Comparable<T>> void sort(T[] array,
                                                  int fromIndex,
                                                  int toIndex)

Sorts a portion of an object array using natural ordering.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Arrays.sort() (a cost of 4 or 8 bytes per element, depending on JVM).

Parameters:

array - The array to be sorted

fromIndex - The minimum bound of the search (inclusive)

toIndex - The maximum bound of the search (exclusive, following similar usage in the JDK; to sort the end of the array, pass array.length)

sort

public static <T> void sort(T[] array,
                            Comparator<T> comparator)

Sorts an object array using the provided comparator.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Arrays.sort() (a cost of 4 or 8 bytes per element, depending on JVM).

Parameters:

array - The array to be sorted

comparator - Used to order array elements

sort

public static <T> void sort(T[] array,
                            int fromIndex,
                            int toIndex,
                            Comparator<T> comparator)

Sorts a portion of an object array using the provided comparator.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Arrays.sort() (a cost of 4 or 8 bytes per element, depending on JVM).

Parameters:

array - The array to be sorted

fromIndex - The minimum bound of the search (inclusive)

toIndex - The maximum bound of the search (exclusive, following similar usage in the JDK; to sort the end of the array, pass array.length)

comparator - Used to order array elements

sort

public static <T extends Comparable<T>> void sort(List<T> list)

Sorts a list using natural ordering. This method is only appropriate for random-access lists.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Collections.sort() (a cost of 8 or 16 bytes per element, depending on JVM).

Parameters:

list - The list to be sorted

sort

public static <T extends Comparable<T>> void sort(List<T> list,
                                                  int fromIndex,
                                                  int toIndex)

Sorts a portion of a list using natural ordering. This method is only appropriate for random-access lists.

This method does not have an equivalent in the JDK.

Parameters:

list - The list to be sorted

fromIndex - The minimum bound of the search (inclusive)

toIndex - The maximum bound of the search (exclusive, following similar usage in the JDK; to sort the end of the list, pass list.size())

sort

public static <T> void sort(List<T> list,
                            Comparator<T> comparator)

Sorts a list using the provided comparator. This method is only appropriate for random-access lists.

You would use this method in a constrained-memory situation, to avoid creating the working array used by the JDK's Collections.sort() (a cost of 8 or 16 bytes per element, depending on JVM).

Parameters:

list - The list to be sorted

comparator - Used to order list elements

sort

public static <T> void sort(List<T> list,
                            int fromIndex,
                            int toIndex,
                            Comparator<T> comparator)

Sorts a portion of a list using natural ordering. This method is only appropriate for random-access lists.

This method does not have an equivalent in the JDK.

Parameters:

list - The list to be sorted

fromIndex - The minimum bound of the search (inclusive)

toIndex - The maximum bound of the search (exclusive, following similar usage in the JDK; to sort the end of the list, pass list.size())

comparator - Used to order list elements

sort

public static void sort(InplaceSort.Accessor acc)

Sorts a collection encapsulated by the provided InplaceSort.Accessor. This is used to physically sort a collection that is not backed by an array (eg, a memory-mapped file).

Since the Accessor includes both range and comparator, this is the only variant of this method.