jal.floats
Class Sorting

java.lang.Object
  jal.floats.Sorting

public final class Sorting

extends Object

A class that encapsulates sorting and related algorithms on one and two arrays. All methods are static and all variables are static and final, so this class has no constructors.

Most methods operate on a range of elements. A range is described by the index of its first element and an index that is one past its last element. So, for example, [n, n+1) is a range that contains one element, [n, n) is a range that contains zero elements, and [n, n-1) is not a valid range.

Many methods require a comparison function, an object of class BinaryPredicate. If comp is a comparison function, then comp.apply(a,b) should return true if a is less than b, and false if a is greater than or equal to b. In particular, comp must satisfy the requirement that, for any element a, comp.apply(a,a) is false.

Note that an inequality operator defines an equivalence relation: two elements a and b are equivalent if and only if the relations comp.apply(a,b) and comp.apply(b,a) are both false. Unless explicitly stated otherwise, the algorithms in this class always use this equivalence relation rather than the == operator or Object.equals().

Copyright © 1996 Silicon Graphics, Inc.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Silicon Graphics makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.

Author:

Matthew Austern (austern@mti.sgi.com), Alexander Stepanov (stepanov@mti.sgi.com)

See Also:

Inspection, Modification, Numeric

Method Summary

static boolean	binary_search(float[] array, int first, int last, float x) Performs a binary search on an already-sorted range: determines whether the range contains an element equivalent to a certain value.
static boolean	binary_search(float[] array, int first, int last, float x, BinaryPredicate comp) Performs a binary search on an already-sorted range: determines whether the range contains an element equivalent to a certain value.
static Range	equal_range(float[] array, int first, int last, float x) Performs a binary search on an already-sorted range: Finds the largest subrange in the supplied range such that an element can be inserted at any point in that subrange without violating the existing ordering.
static Range	equal_range(float[] array, int first, int last, float x, BinaryPredicate comp) Performs a binary search on an already-sorted range: Finds the largest subrange in the supplied range such that an element can be inserted at any point in that subrange without violating the existing ordering.
static boolean	includes(float[] array1, float[] array2, int first1, int last1, int first2, int last2) Tests whether the first range is a superset of the second; both ranges must be sorted.
static boolean	includes(float[] array1, float[] array2, int first1, int last1, int first2, int last2, BinaryPredicate comp) Tests whether the first range is a superset of the second; both ranges must be sorted.
static void	inplace_merge(float[] array, int first, int middle, int last) Transforms two consecutive sorted ranges into a single sorted range.
static void	inplace_merge(float[] array, int first, int middle, int last, BinaryPredicate comp) Transforms two consecutive sorted ranges into a single sorted range.
static void	insertion_sort(float[] array, int first, int last) Sort a range of elements by arithmetic comparison.
static void	insertion_sort(float[] array, int first, int last, BinaryPredicate comp) Sort a range of elements by a user-supplied comparison function.
static boolean	lexicographical_compare(float[] array1, float[] array2, int first1, int last1, int first2, int last2) Performs a lexicographical (element-by-element) comparison of two ranges.
static boolean	lexicographical_compare(float[] array1, float[] array2, int first1, int last1, int first2, int last2, BinaryPredicate comp) Performs a lexicographical (element-by-element) comparison of two ranges.
static int	lower_bound(float[] array, int first, int last, float x) Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering.
static int	lower_bound(float[] array, int first, int last, float x, BinaryPredicate comp) Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering.
static void	make_heap(float[] array, int first, int last) Turns the range [first, last) into a heap.
static void	make_heap(float[] array, int first, int last, BinaryPredicate comp) Turns the range [first, last) into a heap.
static int	max_element(float[] array, int first, int last) Finds the largest element in a range.
static int	max_element(float[] array, int first, int last, BinaryPredicate comp) Finds the largest element in a range.
static int	merge(float[] source1, float[] source2, float[] dest, int first1, int last1, int first2, int last2, int to) Merges two sorted ranges into a third range, which will be sorted.
static int	merge(float[] source1, float[] source2, float[] dest, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp) Merges two sorted ranges into a third range, which will be sorted.
static int	min_element(float[] array, int first, int last) Finds the smallest element in a range.
static int	min_element(float[] array, int first, int last, BinaryPredicate comp) Finds the smallest element in a range.
static boolean	next_permutation(float[] array, int first, int last) Transforms a range of elements into the next permutation of those elements, where the next permutation is defined by a lexicographical ordering of the set of all permutations.
static boolean	next_permutation(float[] array, int first, int last, BinaryPredicate comp) Transforms a range of elements into the next permutation of those elements, where the next permutation is defined by a lexicographical ordering of the set of all permutations.
static void	nth_element(float[] array, int first, int nth, int last) Partitions a range of elements into two subranges [first, nth) and [nth, last).
static void	nth_element(float[] array, int first, int nth, int last, BinaryPredicate comp) Partitions a range of elements into two subranges [first, nth) and [nth, last).
static int	partial_sort_copy(float[] source, float[] destination, int first, int last, int result_first, int result_last) Copies the first N sorted elements from one range into another, where N is the length of the smaller of the two ranges.
static int	partial_sort_copy(float[] source, float[] destination, int first, int last, int result_first, int result_last, BinaryPredicate comp) Copies the first N sorted elements from one range into another, where N is the length of the smaller of the two ranges.
static void	partial_sort(float[] array, int first, int middle, int last) Partially sorts a range by arithmetic comparison: places the first middle-first elements in the range [first, middle).
static void	partial_sort(float[] array, int first, int middle, int last, BinaryPredicate comp) Partially sorts a range by a user-supplied comparison function: places the first middle-first elements in the range [first, middle).
static void	pop_heap(float[] array, int first, int last) Removes the largest element from a heap.
static void	pop_heap(float[] array, int first, int last, BinaryPredicate comp) Removes the largest element from a heap.
static boolean	prev_permutation(float[] array, int first, int last) Transforms a range of elements into the previous permutation of those elements, where the previous permutation is defined by a lexicographical ordering of the set of all permutations.
static boolean	prev_permutation(float[] array, int first, int last, BinaryPredicate comp) Transforms a range of elements into the previous permutation of those elements, where the previous permutation is defined by a lexicographical ordering of the set of all permutations.
static void	push_heap(float[] array, int first, int last) Adds an element to a heap.
static void	push_heap(float[] array, int first, int last, BinaryPredicate comp) Adds an element to a heap.
static int	set_difference(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to) Constructs the set difference of two already-sorted ranges.
static int	set_difference(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp) Constructs the set difference of two already-sorted ranges.
static int	set_intersection(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to) Constructs an intersection of two already-sorted ranges.
static int	set_intersection(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp) Constructs an intersection of two already-sorted ranges.
static int	set_symmetric_difference(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to) Constructs the set symmetric difference of two already-sorted ranges.
static int	set_symmetric_difference(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp) Constructs the set symmetric difference of two already-sorted ranges.
static int	set_union(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to) Constructs a union of two already-sorted ranges.
static int	set_union(float[] source1, float[] source2, float[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp) Constructs a union of two already-sorted ranges.
static void	sort_heap(float[] array, int first, int last) Turns a heap into a sorted range; this operation is O(N log N).
static void	sort_heap(float[] array, int first, int last, BinaryPredicate comp) Turns a heap into a sorted range; this operation is O(N log N).
static void	sort(float[] array, int first, int last) Sort a range of elements by arithmetic comparison.
static void	sort(float[] array, int first, int last, BinaryPredicate comp) Sort a range of elements by a user-supplied comparison function.
static void	stable_sort(float[] array, int first, int last) Sort a range of elements by arithmetic comparison.
static void	stable_sort(float[] array, int first, int last, BinaryPredicate comp) Sort a range of elements by a user-supplied comparison function.
static int	upper_bound(float[] array, int first, int last, float x) Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering.
static int	upper_bound(float[] array, int first, int last, float x, BinaryPredicate comp) Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering.

Methods inherited from class java.lang.Object

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

Method Detail

sort

public static void sort(float[] array,
                        int first,
                        int last)

Sort a range of elements by arithmetic comparison. Uses the quicksort algorithm. Average performance goes as N log N; worst-case performance is quadratic, but this case is extremely rare.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

See Also:

stable_sort(float[], int, int), insertion_sort(float[], int, int), partial_sort(float[], int, int, int)

sort

public static void sort(float[] array,
                        int first,
                        int last,
                        BinaryPredicate comp)

Sort a range of elements by a user-supplied comparison function. Uses the quicksort algorithm. Average performance goes as N log N; worst-case performance is quadratic, but this case is extremely rare.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

See Also:

stable_sort(float[], int, int), insertion_sort(float[], int, int), partial_sort(float[], int, int, int)

insertion_sort

public static void insertion_sort(float[] array,
                                  int first,
                                  int last)

Sort a range of elements by arithmetic comparison. Uses the insertion sort algorithm. This is a quadratic algorithm, but it is useful for sorting small numbers of elements.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

See Also:

sort(float[], int, int)

insertion_sort

public static void insertion_sort(float[] array,
                                  int first,
                                  int last,
                                  BinaryPredicate comp)

Sort a range of elements by a user-supplied comparison function. Uses the insertion sort algorithm. This is a quadratic algorithm, but it is useful for sorting small numbers of elements.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

See Also:

sort(float[], int, int)

stable_sort

public static void stable_sort(float[] array,
                               int first,
                               int last)

Sort a range of elements by arithmetic comparison. The sort is stable---that is, the relative order of equal elements is unchanged. Worst case performance is N (log N)^2.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

See Also:

sort(float[], int, int)

stable_sort

public static void stable_sort(float[] array,
                               int first,
                               int last,
                               BinaryPredicate comp)

Sort a range of elements by a user-supplied comparison function. The sort is stable---that is, the relative order of equal elements is unchanged. Worst case performance is N (log N)^2.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

See Also:

sort(float[], int, int)

partial_sort

public static void partial_sort(float[] array,
                                int first,
                                int middle,
                                int last)

Partially sorts a range by arithmetic comparison: places the first middle-first elements in the range [first, middle). These elements are sorted, the rest are not. It is not guaranteed that the relative ordering of unsorted elements is preserved.

Parameters:

array - Array containing the range.

first - Beginning of the range.

middle - Element such that the range [first, middle) will be sorted.

last - One past the end of the range.

See Also:

partial_sort_copy(float[], float[], int, int, int, int), sort(float[], int, int)

partial_sort

public static void partial_sort(float[] array,
                                int first,
                                int middle,
                                int last,
                                BinaryPredicate comp)

Partially sorts a range by a user-supplied comparison function: places the first middle-first elements in the range [first, middle). These elements are sorted, the rest are not. It is not guaranteed that the relative ordering of unsorted elements is preserved.

Parameters:

array - Array containing the range.

first - Beginning of the range.

middle - Element such that the range [first, middle) will be sorted.

last - One past the end of the range.

comp - Comparison function.

See Also:

partial_sort_copy(float[], float[], int, int, int, int), sort(float[], int, int)

partial_sort_copy

public static int partial_sort_copy(float[] source,
                                    float[] destination,
                                    int first,
                                    int last,
                                    int result_first,
                                    int result_last)

Copies the first N sorted elements from one range into another, where N is the length of the smaller of the two ranges. Sort order is by arithmetic comparison. Existing elements in the output range will be overwritten.

Parameters:

source - Array containing the input range.

destination - Array containing the output range.

first - Beginning of the input range.

last - One past the end of the input range.

result_first - Beginning of the output range.

result_last - One past the end of the output range.

Returns:

result_first + N, where N = min(last-first, result_last-result_first).

See Also:

partial_sort(float[], int, int, int)

partial_sort_copy

public static int partial_sort_copy(float[] source,
                                    float[] destination,
                                    int first,
                                    int last,
                                    int result_first,
                                    int result_last,
                                    BinaryPredicate comp)

Copies the first N sorted elements from one range into another, where N is the length of the smaller of the two ranges. Sort order is by a user-supplied comparison function. Existing elements in the output range will be overwritten.

Parameters:

source - Array containing the input range.

destination - Array containing the output range.

first - Beginning of the input range.

last - One past the end of the input range.

result_first - Beginning of the output range.

result_last - One past the end of the output range.

comp - Comparison function.

Returns:

result_first + N, where N = min(last-first, result_last-result_first).

See Also:

partial_sort(float[], int, int, int)

nth_element

public static void nth_element(float[] array,
                               int first,
                               int nth,
                               int last)

Partitions a range of elements into two subranges [first, nth) and [nth, last). These satisfy the properties that no element in the first range is greater than any element in the second, and that the element in the position nth is the same as the one that would be in that position if the entire range [first, last) had been sorted. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

nth - Location of the partition point.

last - One past the end of the range.

nth_element

public static void nth_element(float[] array,
                               int first,
                               int nth,
                               int last,
                               BinaryPredicate comp)

Partitions a range of elements into two subranges [first, nth) and [nth, last). These satisfy the properties that no element in the first range is greater than any element in the second, and that the element in the position nth is the same as the one that would be in that position if the entire range [first, last) had been sorted. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

nth - Location of the partition point.

last - One past the end of the range.

comp - Comparison function.

lower_bound

public static int lower_bound(float[] array,
                              int first,
                              int last,
                              float x)

Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

Returns:

The largest index i such that, for every j in the range [first, i), array[j] < x.

See Also:

upper_bound(float[], int, int, float), equal_range(float[], int, int, float), binary_search(float[], int, int, float)

lower_bound

public static int lower_bound(float[] array,
                              int first,
                              int last,
                              float x,
                              BinaryPredicate comp)

Performs a binary search on an already-sorted range: finds the first position where an element can be inserted without violating the ordering. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function.

Returns:

The largest index i such that, for every j in the range [first, i), comp.apply(array[j], x) is true.

See Also:

upper_bound(float[], int, int, float), equal_range(float[], int, int, float), binary_search(float[], int, int, float)

upper_bound

public static int upper_bound(float[] array,
                              int first,
                              int last,
                              float x)

Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

x - Element to be searched for

Returns:

The largest index i such that, for every j in the range [first, i), !(x < array[j]).

See Also:

lower_bound(float[], int, int, float), equal_range(float[], int, int, float), binary_search(float[], int, int, float)

upper_bound

public static int upper_bound(float[] array,
                              int first,
                              int last,
                              float x,
                              BinaryPredicate comp)

Performs a binary search on an already-sorted range: finds the last position where an element can be inserted without violating the ordering. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function.

Returns:

The largest index i such that, for every j in the range [first, i), comp.apply(x, array[j]) is false.

See Also:

lower_bound(float[], int, int, float), equal_range(float[], int, int, float), binary_search(float[], int, int, float)

equal_range

public static Range equal_range(float[] array,
                                int first,
                                int last,
                                float x)

Performs a binary search on an already-sorted range: Finds the largest subrange in the supplied range such that an element can be inserted at any point in that subrange without violating the existing ordering. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

Returns:

An object Rof class R such that, for any index i in the range [R.first, R.last), the conditions array[i] < x and x < array[i] are both false. Note that it is possible for the return value to be an empty range.

See Also:

lower_bound(float[], int, int, float), upper_bound(float[], int, int, float), binary_search(float[], int, int, float)

equal_range

public static Range equal_range(float[] array,
                                int first,
                                int last,
                                float x,
                                BinaryPredicate comp)

Performs a binary search on an already-sorted range: Finds the largest subrange in the supplied range such that an element can be inserted at any point in that subrange without violating the existing ordering. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function

Returns:

An object Rof class R such that, for any index i in the range [R.first, R.last), the conditions comp.apply(array[i], x) and comp.apply(x, array[i]) are both false. Note that it is possible for the return value to be an empty range.

See Also:

lower_bound(float[], int, int, float), upper_bound(float[], int, int, float), binary_search(float[], int, int, float)

binary_search

public static boolean binary_search(float[] array,
                                    int first,
                                    int last,
                                    float x)

Performs a binary search on an already-sorted range: determines whether the range contains an element equivalent to a certain value. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

Returns:

true if and only if the range contains an element E such that value < E and E < value are both false.

See Also:

lower_bound(float[], int, int, float), upper_bound(float[], int, int, float), equal_range(float[], int, int, float)

binary_search

public static boolean binary_search(float[] array,
                                    int first,
                                    int last,
                                    float x,
                                    BinaryPredicate comp)

Performs a binary search on an already-sorted range: determines whether the range contains an element equivalent to a certain value. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Element to be searched for.

comp - Comparison function.

Returns:

true if and only if the range contains an element E such that value < E and E < value are both false.

See Also:

lower_bound(float[], int, int, float), upper_bound(float[], int, int, float), equal_range(float[], int, int, float)

merge

public static int merge(float[] source1,
                        float[] source2,
                        float[] dest,
                        int first1,
                        int last1,
                        int first2,
                        int last2,
                        int to)

Merges two sorted ranges into a third range, which will be sorted. Elements in the first input range will precede equal elements in the second. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by arithmetic comparison. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

dest - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

See Also:

inplace_merge(float[], int, int, int)

merge

public static int merge(float[] source1,
                        float[] source2,
                        float[] dest,
                        int first1,
                        int last1,
                        int first2,
                        int last2,
                        int to,
                        BinaryPredicate comp)

Merges two sorted ranges into a third range, which will be sorted. Elements in the first input range will precede equal elements in the second. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by a user-supplied comparison function. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

dest - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

comp - Comparison function

Returns:

One past the end of the output range, that is, to + (last1-first1) + (last2-first2).

See Also:

inplace_merge(float[], int, int, int)

inplace_merge

public static void inplace_merge(float[] array,
                                 int first,
                                 int middle,
                                 int last)

Transforms two consecutive sorted ranges into a single sorted range. The initial ranges are [first, middle) and [middle, last), and the resulting range is [first, last). Elements in the first input range will precede equal elements in the second. Sorting is by arithmetic comparison.

Parameters:

array - Array containing the ranges.

first - Beginning of the first range.

middle - One past the end of the first range, and beginning of the second.

last - One past the end of the second range.

See Also:

merge(float[], float[], float[], int, int, int, int, int)

inplace_merge

public static void inplace_merge(float[] array,
                                 int first,
                                 int middle,
                                 int last,
                                 BinaryPredicate comp)

Transforms two consecutive sorted ranges into a single sorted range. The initial ranges are [first, middle) and [middle, last), and the resulting range is [first, last). Elements in the first input range will precede equal elements in the second. Sorting is by a user-supplied comparison function.

Parameters:

array - Array containing the ranges.

first - Beginning of the first range.

middle - One past the end of the first range, and beginning of the second.

last - One past the end of the second range.

comp - Comparison function.

See Also:

merge(float[], float[], float[], int, int, int, int, int)

includes

public static boolean includes(float[] array1,
                               float[] array2,
                               int first1,
                               int last1,
                               int first2,
                               int last2)

Tests whether the first range is a superset of the second; both ranges must be sorted. Sorting is by arithmetic comparison.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the second range.

first1 - Beginning of the first range.

last1 - One past the end of the first range.

first2 - Beginning of the second range.

last2 - One past the end of the second range.

Returns:

true if and only if, for every element in the range [first2,last2), the range [first1,last1) contains an equivalent element.

See Also:

set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

includes

public static boolean includes(float[] array1,
                               float[] array2,
                               int first1,
                               int last1,
                               int first2,
                               int last2,
                               BinaryPredicate comp)

Tests whether the first range is a superset of the second; both ranges must be sorted. Sorting is by a user-supplied comparison function.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the second range.

first1 - Beginning of the first range.

last1 - One past the end of the first range.

first2 - Beginning of the second range.

last2 - One past the end of the second range.

comp - Comparison function.

Returns:

true if and only if, for every element in the range [first2,last2), the range [first1,last1) contains an equivalent element.

See Also:

set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_union

public static int set_union(float[] source1,
                            float[] source2,
                            float[] destination,
                            int first1,
                            int last1,
                            int first2,
                            int last2,
                            int to)

Constructs a union of two already-sorted ranges. That is, the output range will be a sorted range containing every element from either of the two input ranges. If an element in the second range is equivalent to one in the first, the one in the first range is copied. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by arithmetic comparison. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_union

public static int set_union(float[] source1,
                            float[] source2,
                            float[] destination,
                            int first1,
                            int last1,
                            int first2,
                            int last2,
                            int to,
                            BinaryPredicate comp)

Constructs a union of two already-sorted ranges. That is, the output range will be a sorted range containing every element from either of the two input ranges. If an element in the second range is equivalent to one in the first, the one in the first range is copied. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by a user-provided comparison function. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

comp - Comparison function

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_intersection

public static int set_intersection(float[] source1,
                                   float[] source2,
                                   float[] destination,
                                   int first1,
                                   int last1,
                                   int first2,
                                   int last2,
                                   int to)

Constructs an intersection of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element exists in the second range. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by arithmetic comparison. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_intersection

public static int set_intersection(float[] source1,
                                   float[] source2,
                                   float[] destination,
                                   int first1,
                                   int last1,
                                   int first2,
                                   int last2,
                                   int to,
                                   BinaryPredicate comp)

Constructs an intersection of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element exists in the second range. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by a user-provided comparison function. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

comp - Comparison function

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_difference

public static int set_difference(float[] source1,
                                 float[] source2,
                                 float[] destination,
                                 int first1,
                                 int last1,
                                 int first2,
                                 int last2,
                                 int to)

Constructs the set difference of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element does not exist in the second range. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by arithmetic comparison. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_difference

public static int set_difference(float[] source1,
                                 float[] source2,
                                 float[] destination,
                                 int first1,
                                 int last1,
                                 int first2,
                                 int last2,
                                 int to,
                                 BinaryPredicate comp)

Constructs the set difference of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element does not exist in the second range. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by a user-supplied comparison function. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

comp - Comparison function.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_symmetric_difference(float[], float[], float[], int, int, int, int, int)

set_symmetric_difference

public static int set_symmetric_difference(float[] source1,
                                           float[] source2,
                                           float[] destination,
                                           int first1,
                                           int last1,
                                           int first2,
                                           int last2,
                                           int to)

Constructs the set symmetric difference of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element does not exist in the second range, and every element in the second such that an equivalent element does not exist in the first. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by arithmetic comparison. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int)

set_symmetric_difference

public static int set_symmetric_difference(float[] source1,
                                           float[] source2,
                                           float[] destination,
                                           int first1,
                                           int last1,
                                           int first2,
                                           int last2,
                                           int to,
                                           BinaryPredicate comp)

Constructs the set symmetric difference of two already-sorted ranges. That is, the output range will be a sorted range containing every element from the first range such that an equivelent element does not exist in the second range, and every element in the second such that an equivalent element does not exist in the first. There must be enough space in the destination array, and existing elements will be overwritten. Sorting is by a user-supplied comparison function. Note: the destination range is not permitted to overlap either of the two input ranges.

Parameters:

source1 - Array containing the first input range.

source2 - Array containing the second input range.

destination - Array containing the output range.

first1 - Beginning of the first input range.

last1 - One past the end of the first input range.

first2 - Beginning of the second input range.

last2 - One past the end of the second input range.

to - Beginning of the output range.

comp - Comparison function.

Returns:

One past the end of the output range.

See Also:

includes(float[], float[], int, int, int, int), set_union(float[], float[], float[], int, int, int, int, int), set_intersection(float[], float[], float[], int, int, int, int, int), set_difference(float[], float[], float[], int, int, int, int, int)

push_heap

public static void push_heap(float[] array,
                             int first,
                             int last)

Adds an element to a heap. The range [first, last-1) must be a valid heap, and the element to be added must be in array[last-1]. The heap is ordered by arithmetic comparison.

Parameters:

array - Array containing the heap.

first - Beginning of the heap.

last - Index such that [first, last-1) is a valid heap and such that array[last-1] contains the element to be added to the heap.

See Also:

make_heap(float[], int, int)

push_heap

public static void push_heap(float[] array,
                             int first,
                             int last,
                             BinaryPredicate comp)

Adds an element to a heap. The range [first, last-1) must be a valid heap, and the element to be added must be in array[last-1]. The heap is ordered by a user-supplied comparison function.

Parameters:

array - Array containing the heap.

first - Beginning of the heap.

last - Index such that [first, last-1) is a valid heap and such that array[last-1] contains the element to be added to the heap.

comp - Comparison function.

See Also:

make_heap(float[], int, int)

pop_heap

public static void pop_heap(float[] array,
                            int first,
                            int last)

Removes the largest element from a heap. If the range [first, last) is a valid heap, then remove array[first] (the largest element) from the heap, rearrange elements such that [first, last-1) is a valid heap, and place the removed element in array[last]. The heap is ordered by arithmetic comparison.

Parameters:

array - Array containing the heap.

first - Beginning of the heap.

last - One past the end of the heap.

See Also:

make_heap(float[], int, int)

pop_heap

public static void pop_heap(float[] array,
                            int first,
                            int last,
                            BinaryPredicate comp)

Removes the largest element from a heap. If the range [first, last) is a valid heap, then remove array[first] (the largest element) from the heap, rearrange elements such that [first, last-1) is a valid heap, and place the removed element in array[last]. The heap is ordered by a user-defined comparison function.

Parameters:

array - Array containing the heap.

first - Beginning of the heap.

last - One past the end of the heap.

comp - Comparison function.

See Also:

make_heap(float[], int, int)

make_heap

public static void make_heap(float[] array,
                             int first,
                             int last)

Turns the range [first, last) into a heap. A heap has the properties that array[first] is the largest element, and that it is possible to add a new element, or to remove array[first], efficiently. The heap is ordered by arithmetic comparison.

Parameters:

array - Array containing the range that is to be made a heap.

first - Beginning of the range.

last - One past the end of the range.

See Also:

push_heap(float[], int, int), pop_heap(float[], int, int), sort_heap(float[], int, int)

make_heap

public static void make_heap(float[] array,
                             int first,
                             int last,
                             BinaryPredicate comp)

Turns the range [first, last) into a heap. A heap has the properties that array[first] is the largest element, and that it is possible to add a new element, or to remove array[first], efficiently. The heap is ordered by a user-defined comparison function.

Parameters:

array - Array containing the range that is to be made a heap.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function.

See Also:

push_heap(float[], int, int), pop_heap(float[], int, int), sort_heap(float[], int, int)

sort_heap

public static void sort_heap(float[] array,
                             int first,
                             int last)

Turns a heap into a sorted range; this operation is O(N log N). Note that make_heap followed by sort_heap is the heap sort algorithm. Ordering is by arithmetic comparison.

Parameters:

array - Array containing the heap that is to be made a sorted range.

first - Beginning of the heap.

last - One past the end of the range.

See Also:

make_heap(float[], int, int)

sort_heap

public static void sort_heap(float[] array,
                             int first,
                             int last,
                             BinaryPredicate comp)

Turns a heap into a sorted range; this operation is O(N log N). Note that make_heap followed by sort_heap is the heap sort algorithm. Ordering is by a user-supplied comparision function.

Parameters:

array - Array containing the heap that is to be made a sorted range.

first - Beginning of the heap.

last - One past the end of the range.

comp - Comparison function.

See Also:

make_heap(float[], int, int)

max_element

public static int max_element(float[] array,
                              int first,
                              int last)

Finds the largest element in a range. Ordering is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - End of the range.

Returns:

The smallest index i such that every element in the range is less than or equivalent to array[i]. Returns last if the range is empty.

See Also:

min_element(float[], int, int)

max_element

public static int max_element(float[] array,
                              int first,
                              int last,
                              BinaryPredicate comp)

Finds the largest element in a range. Ordering is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - End of the range.

comp - Comparison function.

Returns:

The smallest index i such that every element in the range is less than or equivalent to array[i]. Returns last if the range is empty.

See Also:

min_element(float[], int, int)

min_element

public static int min_element(float[] array,
                              int first,
                              int last)

Finds the smallest element in a range. Ordering is by arithmetic comparison.

Parameters:

array - Array containing the range

first - Beginning of the range

last - End of the range

Returns:

The smallest index i such that every element in the range is greater than or equivalent to array[i]. Returns last if the range is empty.

See Also:

max_element(float[], int, int)

min_element

public static int min_element(float[] array,
                              int first,
                              int last,
                              BinaryPredicate comp)

Finds the smallest element in a range. Ordering is by a user-supplied comparison function.

Parameters:

array - Array containing the range

first - Beginning of the range

last - End of the range

comp - Comparison function.

Returns:

The smallest index i such that every element in the range is greater than or equivalent to array[i]. Returns last if the range is empty.

See Also:

max_element(float[], int, int)

lexicographical_compare

public static boolean lexicographical_compare(float[] array1,
                                              float[] array2,
                                              int first1,
                                              int last1,
                                              int first2,
                                              int last2)

Performs a lexicographical (element-by-element) comparison of two ranges. Ordering of individual elements is by arithmetic comparison.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the second range.

first1 - Beginning of the first range.

last1 - One past the end of the first range.

first2 - Beginning of the second range.

last2 - One past the end of the second range.

Returns:

true if the sequence of elements in the range [first1, last1) is lexicographically less than that in [first1, last1), otherwise false.

lexicographical_compare

public static boolean lexicographical_compare(float[] array1,
                                              float[] array2,
                                              int first1,
                                              int last1,
                                              int first2,
                                              int last2,
                                              BinaryPredicate comp)

Performs a lexicographical (element-by-element) comparison of two ranges. Ordering of individual elements is by a user-supplied comparison function.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the second range.

first1 - Beginning of the first range.

last1 - One past the end of the first range.

first2 - Beginning of the second range.

last2 - One past the end of the second range.

comp - Comparison function.

Returns:

true if the sequence of elements in the range [first1, last1) is lexicographically less than that in [first1, last1), otherwise false.

next_permutation

public static boolean next_permutation(float[] array,
                                       int first,
                                       int last)

Transforms a range of elements into the next permutation of those elements, where the next permutation is defined by a lexicographical ordering of the set of all permutations. If no such permutation exists, transforms the range into the smallest permutation. Ordering of individual elements is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

Returns:

true if a next permutation exists, false if the range is already the largest permutation.

See Also:

lexicographical_compare(float[], float[], int, int, int, int), prev_permutation(float[], int, int)

next_permutation

public static boolean next_permutation(float[] array,
                                       int first,
                                       int last,
                                       BinaryPredicate comp)

Transforms a range of elements into the next permutation of those elements, where the next permutation is defined by a lexicographical ordering of the set of all permutations. If no such permutation exists, transforms the range into the smallest permutation. Ordering of individual elements is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function

Returns:

true if a next permutation exists, false if the range is already the largest permutation.

See Also:

lexicographical_compare(float[], float[], int, int, int, int), prev_permutation(float[], int, int)

prev_permutation

public static boolean prev_permutation(float[] array,
                                       int first,
                                       int last)

Transforms a range of elements into the previous permutation of those elements, where the previous permutation is defined by a lexicographical ordering of the set of all permutations. If no such permutation exists, transforms the range into the largest permutation. Ordering of individual elements is by arithmetic comparison.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

Returns:

true if a previous permutation exists, false if the range is already the smallest permutation.

See Also:

lexicographical_compare(float[], float[], int, int, int, int), next_permutation(float[], int, int)

prev_permutation

public static boolean prev_permutation(float[] array,
                                       int first,
                                       int last,
                                       BinaryPredicate comp)

Transforms a range of elements into the previous permutation of those elements, where the previous permutation is defined by a lexicographical ordering of the set of all permutations. If no such permutation exists, transforms the range into the largest permutation. Ordering of individual elements is by a user-supplied comparison function.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

comp - Comparison function

Returns:

true if a previous permutation exists, false if the range is already the smallest permutation.

See Also:

lexicographical_compare(float[], float[], int, int, int, int), next_permutation(float[], int, int)