Arrays
: methods for binary searches
and sorts of arrays of the primitive type int with a comparator
provided by the caller (the comparator is an instance of
IntComparator
in this case).
The sort functions use the TimSort algorithm, essentially the same one used in openJDK. In this case, due to GPL issues, the Android version was used as a starting point as that version uses the Apache License (version 2.0). The licensing information is in the source code for the additional TimSort files. The TimSort classes themselves are not public classes. The reason for the code replication is that TimSort itself uses Java generics, which work with objects but not primitive types. To sort primitive types with the TimSort algorithm it was necessary to replicate the code, one class for each primitive type. The changes to the Android implementation were minor - essentially removing the use of generics and substituting a different comparator.
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic int
binarySearch
(byte[] a, byte key, ByteComparator c) Binary search of a sorted byte array.static int
binarySearch
(byte[] a, byte key, ByteComparator c, boolean keyflag) Binary search of a sorted byte array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(byte[] a, int fromIndex, int toIndex, byte key, ByteComparator c) Binary search of a range in a sorted byte array.static int
binarySearch
(byte[] a, int fromIndex, int toIndex, byte key, ByteComparator c, boolean keyflag) Binary search of a range in a sorted byte array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(char[] a, char key, CharComparator c) Binary search of a sorted char array.static int
binarySearch
(char[] a, char key, CharComparator c, boolean keyflag) Binary search of a sorted char array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(char[] a, int fromIndex, int toIndex, char key, CharComparator c) Binary search of a range in a sorted char array.static int
binarySearch
(char[] a, int fromIndex, int toIndex, char key, CharComparator c, boolean keyflag) Binary search of a range in a sorted char array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(double[] a, double key, DoubleComparator c) Binary search of a sorted double array.static int
binarySearch
(double[] a, double key, DoubleComparator c, boolean keyflag) Binary search of a sorted double array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(double[] a, int fromIndex, int toIndex, double key, DoubleComparator c) Binary search of a range in a sorted double array.static int
binarySearch
(double[] a, int fromIndex, int toIndex, double key, DoubleComparator c, boolean keyflag) Binary search of a range in a sorted double array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(float[] a, float key, FloatComparator c) Binary search of a sorted float array.static int
binarySearch
(float[] a, float key, FloatComparator c, boolean keyflag) Binary search of a sorted float array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(float[] a, int fromIndex, int toIndex, float key, FloatComparator c) Binary search of a range in a sorted float array.static int
binarySearch
(float[] a, int fromIndex, int toIndex, float key, FloatComparator c, boolean keyflag) Binary search of a range in a sorted float array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(int[] a, int fromIndex, int toIndex, int key, IntComparator c) Binary search of a range in a sorted int array.static int
binarySearch
(int[] a, int fromIndex, int toIndex, int key, IntComparator c, boolean keyflag) Binary search of a range in a sorted int array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(int[] a, int key, IntComparator c) Binary search of a sorted int array.static int
binarySearch
(int[] a, int key, IntComparator c, boolean keyflag) Binary search of a sorted int array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(long[] a, int fromIndex, int toIndex, long key, LongComparator c) Binary search of a range in a sorted long array.static int
binarySearch
(long[] a, int fromIndex, int toIndex, long key, LongComparator c, boolean keyflag) Binary search of a range in a sorted long array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(long[] a, long key, LongComparator c) Binary search of a sorted long array.static int
binarySearch
(long[] a, long key, LongComparator c, boolean keyflag) Binary search of a sorted long array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(short[] a, int fromIndex, int toIndex, short key, ShortComparator c) Binary search of a range in a sorted short array.static int
binarySearch
(short[] a, int fromIndex, int toIndex, short key, ShortComparator c, boolean keyflag) Binary search of a range in a sorted short array, choosing the minimum or maximum index whose array value matches a key.static int
binarySearch
(short[] a, short key, ShortComparator c) Binary search of a sorted short array.static int
binarySearch
(short[] a, short key, ShortComparator c, boolean keyflag) Binary search of a sorted short array, choosing the minimum or maximum index whose array value matches a key.static void
sort
(byte[] a, int fromIndex, int toIndex, ByteComparator c) Sort a range of an array whose components are the primitive type byte.static void
sort
(byte[] a, ByteComparator c) Sort an array whose components are the primitive type byte.static void
sort
(char[] a, int fromIndex, int toIndex, CharComparator c) Sort a range of an array whose components are the primitive type char.static void
sort
(char[] a, CharComparator c) Sort an array whose components are the primitive type char.static void
sort
(double[] a, int fromIndex, int toIndex, DoubleComparator c) Sort a range of an array whose components are the primitive type double.static void
sort
(double[] a, DoubleComparator c) Sort an array whose components are the primitive type double.static void
sort
(float[] a, int fromIndex, int toIndex, FloatComparator c) Sort a range of an array whose components are the primitive type float.static void
sort
(float[] a, FloatComparator c) Sort an array whose components are the primitive type float.static void
sort
(int[] a, int fromIndex, int toIndex, IntComparator c) Sort a range of an array whose components are the primitive type int.static void
sort
(int[] a, IntComparator c) Sort an array whose components are the primitive type int.static void
sort
(long[] a, int fromIndex, int toIndex, LongComparator c) Sort a range of an array whose components are the primitive type long.static void
sort
(long[] a, LongComparator c) Sort an array whose components are the primitive type long.static void
sort
(short[] a, int fromIndex, int toIndex, ShortComparator c) Sort a range of an array whose components are the primitive type short.static void
sort
(short[] a, ShortComparator c) Sort an array whose components are the primitive type short.
-
Constructor Details
-
PrimArrays
public PrimArrays()
-
-
Method Details
-
binarySearch
Binary search of a sorted int array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted int array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted int array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(int[] a, int fromIndex, int toIndex, int key, IntComparator c, boolean keyflag) Binary search of a range in a sorted int array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type int.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type int. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted byte array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted byte array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted byte array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key, ByteComparator c, boolean keyflag) Binary search of a range in a sorted byte array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type byte.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type byte. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted char array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted char array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted char array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(char[] a, int fromIndex, int toIndex, char key, CharComparator c, boolean keyflag) Binary search of a range in a sorted char array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type char.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type char. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted short array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted short array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted short array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(short[] a, int fromIndex, int toIndex, short key, ShortComparator c, boolean keyflag) Binary search of a range in a sorted short array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type short.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type short. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted long array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted long array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted long array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(long[] a, int fromIndex, int toIndex, long key, LongComparator c, boolean keyflag) Binary search of a range in a sorted long array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type long.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type long. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted float array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a range in a sorted float array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted float array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(float[] a, int fromIndex, int toIndex, float key, FloatComparator c, boolean keyflag) Binary search of a range in a sorted float array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type float.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type float. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-
binarySearch
Binary search of a sorted double array.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(double[] a, int fromIndex, int toIndex, double key, DoubleComparator c) Binary search of a range in a sorted double array. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the array- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
Binary search of a sorted double array, choosing the minimum or maximum index whose array value matches a key.Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortkey
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
binarySearch
public static int binarySearch(double[] a, int fromIndex, int toIndex, double key, DoubleComparator c, boolean keyflag) Binary search of a range in a sorted double array, choosing the minimum or maximum index whose array value matches a key. The range of indices included in the search is [fromIndex, toIndex).Note: The key is always the second argument passed to the comparator's compare method.
- Parameters:
a
- the array to sortfromIndex
- the lowest index for the search (inclusive)toIndex
- the highest index for the search (exclusive)key
- the key to search forc
- the comparator used to sort the arraykeyflag
- true if the maximum index matching a key is requested; false if the minimum index matching a key is requested- Returns:
- an index into the array whose value matches the key; otherwise (-(insertion_point) - 1)
-
sort
Sort an array whose components are the primitive type double.- Parameters:
a
- the array to sortc
- the comparator used to determine the order of elements in the sorted array
-
sort
Sort a range of an array whose components are the primitive type double. The elements sorted will be those whose indices are in the interval [fromIndex, toIndex).- Parameters:
a
- the array to sortfromIndex
- the lowest index for the sort (inclusive)toIndex
- the highest index for the sort (exclusive)c
- the comparator used to determine the order of elements in the sorted array
-