

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object jal.longs.Sorting
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, n1)
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.
Inspection
,
Modification
,
Numeric
Method Summary  
static boolean 
binary_search(long[] array,
int first,
int last,
long x)
Performs a binary search on an alreadysorted range: determines whether the range contains an element equivalent to a certain value. 
static boolean 
binary_search(long[] array,
int first,
int last,
long x,
BinaryPredicate comp)
Performs a binary search on an alreadysorted range: determines whether the range contains an element equivalent to a certain value. 
static Range 
equal_range(long[] array,
int first,
int last,
long x)
Performs a binary search on an alreadysorted 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(long[] array,
int first,
int last,
long x,
BinaryPredicate comp)
Performs a binary search on an alreadysorted 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(long[] array1,
long[] 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(long[] array1,
long[] 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(long[] array,
int first,
int middle,
int last)
Transforms two consecutive sorted ranges into a single sorted range. 
static void 
inplace_merge(long[] array,
int first,
int middle,
int last,
BinaryPredicate comp)
Transforms two consecutive sorted ranges into a single sorted range. 
static void 
insertion_sort(long[] array,
int first,
int last)
Sort a range of elements by arithmetic comparison. 
static void 
insertion_sort(long[] array,
int first,
int last,
BinaryPredicate comp)
Sort a range of elements by a usersupplied comparison function. 
static boolean 
lexicographical_compare(long[] array1,
long[] array2,
int first1,
int last1,
int first2,
int last2)
Performs a lexicographical (elementbyelement) comparison of two ranges. 
static boolean 
lexicographical_compare(long[] array1,
long[] array2,
int first1,
int last1,
int first2,
int last2,
BinaryPredicate comp)
Performs a lexicographical (elementbyelement) comparison of two ranges. 
static int 
lower_bound(long[] array,
int first,
int last,
long x)
Performs a binary search on an alreadysorted range: finds the first position where an element can be inserted without violating the ordering. 
static int 
lower_bound(long[] array,
int first,
int last,
long x,
BinaryPredicate comp)
Performs a binary search on an alreadysorted range: finds the first position where an element can be inserted without violating the ordering. 
static void 
make_heap(long[] array,
int first,
int last)
Turns the range [first, last) into a heap. 
static void 
make_heap(long[] array,
int first,
int last,
BinaryPredicate comp)
Turns the range [first, last) into a heap. 
static int 
max_element(long[] array,
int first,
int last)
Finds the largest element in a range. 
static int 
max_element(long[] array,
int first,
int last,
BinaryPredicate comp)
Finds the largest element in a range. 
static int 
merge(long[] source1,
long[] source2,
long[] 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(long[] source1,
long[] source2,
long[] 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(long[] array,
int first,
int last)
Finds the smallest element in a range. 
static int 
min_element(long[] array,
int first,
int last,
BinaryPredicate comp)
Finds the smallest element in a range. 
static boolean 
next_permutation(long[] 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(long[] 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(long[] array,
int first,
int nth,
int last)
Partitions a range of elements into two subranges [first, nth) and [nth, last) . 
static void 
nth_element(long[] 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(long[] source,
long[] 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(long[] source,
long[] 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(long[] array,
int first,
int middle,
int last)
Partially sorts a range by arithmetic comparison: places the first middlefirst elements in the range
[first, middle) . 
static void 
partial_sort(long[] array,
int first,
int middle,
int last,
BinaryPredicate comp)
Partially sorts a range by a usersupplied comparison function: places the first middlefirst elements in the range
[first, middle) . 
static void 
pop_heap(long[] array,
int first,
int last)
Removes the largest element from a heap. 
static void 
pop_heap(long[] array,
int first,
int last,
BinaryPredicate comp)
Removes the largest element from a heap. 
static boolean 
prev_permutation(long[] 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(long[] 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(long[] array,
int first,
int last)
Adds an element to a heap. 
static void 
push_heap(long[] array,
int first,
int last,
BinaryPredicate comp)
Adds an element to a heap. 
static int 
set_difference(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to)
Constructs the set difference of two alreadysorted ranges. 
static int 
set_difference(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to,
BinaryPredicate comp)
Constructs the set difference of two alreadysorted ranges. 
static int 
set_intersection(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to)
Constructs an intersection of two alreadysorted ranges. 
static int 
set_intersection(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to,
BinaryPredicate comp)
Constructs an intersection of two alreadysorted ranges. 
static int 
set_symmetric_difference(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to)
Constructs the set symmetric difference of two alreadysorted ranges. 
static int 
set_symmetric_difference(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to,
BinaryPredicate comp)
Constructs the set symmetric difference of two alreadysorted ranges. 
static int 
set_union(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to)
Constructs a union of two alreadysorted ranges. 
static int 
set_union(long[] source1,
long[] source2,
long[] destination,
int first1,
int last1,
int first2,
int last2,
int to,
BinaryPredicate comp)
Constructs a union of two alreadysorted ranges. 
static void 
sort_heap(long[] array,
int first,
int last)
Turns a heap into a sorted range; this operation is O(N log N) . 
static void 
sort_heap(long[] array,
int first,
int last,
BinaryPredicate comp)
Turns a heap into a sorted range; this operation is O(N log N) . 
static void 
sort(long[] array,
int first,
int last)
Sort a range of elements by arithmetic comparison. 
static void 
sort(long[] array,
int first,
int last,
BinaryPredicate comp)
Sort a range of elements by a usersupplied comparison function. 
static void 
stable_sort(long[] array,
int first,
int last)
Sort a range of elements by arithmetic comparison. 
static void 
stable_sort(long[] array,
int first,
int last,
BinaryPredicate comp)
Sort a range of elements by a usersupplied comparison function. 
static int 
upper_bound(long[] array,
int first,
int last,
long x)
Performs a binary search on an alreadysorted range: finds the last position where an element can be inserted without violating the ordering. 
static int 
upper_bound(long[] array,
int first,
int last,
long x,
BinaryPredicate comp)
Performs a binary search on an alreadysorted 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 
public static void sort(long[] array, int first, int last)
N log N
; worstcase performance
is quadratic, but this case is extremely rare.
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.stable_sort(long[], int, int)
,
insertion_sort(long[], int, int)
,
partial_sort(long[], int, int, int)
public static void sort(long[] array, int first, int last, BinaryPredicate comp)
N log N
; worstcase performance
is quadratic, but this case is extremely rare.
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.comp
 Comparison function.stable_sort(long[], int, int)
,
insertion_sort(long[], int, int)
,
partial_sort(long[], int, int, int)
public static void insertion_sort(long[] array, int first, int last)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.sort(long[], int, int)
public static void insertion_sort(long[] array, int first, int last, BinaryPredicate comp)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.comp
 Comparison function.sort(long[], int, int)
public static void stable_sort(long[] array, int first, int last)
N (log N)^2
.
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.sort(long[], int, int)
public static void stable_sort(long[] array, int first, int last, BinaryPredicate comp)
N (log N)^2
.
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.comp
 Comparison function.sort(long[], int, int)
public static void partial_sort(long[] array, int first, int middle, int last)
middlefirst
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.
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.partial_sort_copy(long[], long[], int, int, int, int)
,
sort(long[], int, int)
public static void partial_sort(long[] array, int first, int middle, int last, BinaryPredicate comp)
middlefirst
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.
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.partial_sort_copy(long[], long[], int, int, int, int)
,
sort(long[], int, int)
public static int partial_sort_copy(long[] source, long[] destination, int first, int last, int result_first, int result_last)
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.
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.
result_first + N
, where
N = min(lastfirst, result_lastresult_first)
.partial_sort(long[], int, int, int)
public static int partial_sort_copy(long[] source, long[] destination, int first, int last, int result_first, int result_last, BinaryPredicate comp)
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 usersupplied comparison function.
Existing elements in the output range will be overwritten.
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.
result_first + N
, where
N = min(lastfirst, result_lastresult_first)
.partial_sort(long[], int, int, int)
public static void nth_element(long[] array, int first, int nth, int last)
[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.
array
 Array containing the range.first
 Beginning of the range.nth
 Location of the partition point.last
 One past the end of the range.public static void nth_element(long[] array, int first, int nth, int last, BinaryPredicate comp)
[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 usersupplied comparison function.
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.public static int lower_bound(long[] array, int first, int last, long x)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.x
 Element to be searched for.
[first, i)
,
array[j] < x
.upper_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static int lower_bound(long[] array, int first, int last, long x, BinaryPredicate comp)
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.
[first, i)
,
comp.apply(array[j], x)
is
true
.upper_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static int upper_bound(long[] array, int first, int last, long x)
array
 Array containing the rangefirst
 Beginning of the rangelast
 One past the end of the rangex
 Element to be searched for
[first, i)
,
!(x < array[j])
.lower_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static int upper_bound(long[] array, int first, int last, long x, BinaryPredicate comp)
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.
[first, i)
,
comp.apply(x, array[j])
is
false
.lower_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static Range equal_range(long[] array, int first, int last, long x)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.x
 Element to be searched for.
R
of 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.lower_bound(long[], int, int, long)
,
upper_bound(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static Range equal_range(long[] array, int first, int last, long x, BinaryPredicate comp)
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
R
of 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.lower_bound(long[], int, int, long)
,
upper_bound(long[], int, int, long)
,
binary_search(long[], int, int, long)
public static boolean binary_search(long[] array, int first, int last, long x)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.x
 Element to be searched for.
true
if and only if the range contains
an element E
such that
value < E
and
E < value
are both
false
.lower_bound(long[], int, int, long)
,
upper_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
public static boolean binary_search(long[] array, int first, int last, long x, BinaryPredicate comp)
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.
true
if and only if the range contains
an element E
such that
value < E
and
E < value
are both
false
.lower_bound(long[], int, int, long)
,
upper_bound(long[], int, int, long)
,
equal_range(long[], int, int, long)
public static int merge(long[] source1, long[] source2, long[] dest, int first1, int last1, int first2, int last2, int to)
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.inplace_merge(long[], int, int, int)
public static int merge(long[] source1, long[] source2, long[] dest, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp)
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
to + (last1first1) + (last2first2)
.inplace_merge(long[], int, int, int)
public static void inplace_merge(long[] array, int first, int middle, int last)
[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.
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.merge(long[], long[], long[], int, int, int, int, int)
public static void inplace_merge(long[] array, int first, int middle, int last, BinaryPredicate comp)
[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 usersupplied comparison function.
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.merge(long[], long[], long[], int, int, int, int, int)
public static boolean includes(long[] array1, long[] array2, int first1, int last1, int first2, int last2)
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.
true
if and only if, for every element in
the range [first2,last2)
, the range
[first1,last1)
contains an equivalent
element.set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static boolean includes(long[] array1, long[] array2, int first1, int last1, int first2, int last2, BinaryPredicate comp)
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.
true
if and only if, for every element in
the range [first2,last2)
, the range
[first1,last1)
contains an equivalent
element.set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_union(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to)
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.
includes(long[], long[], int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_union(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp)
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
includes(long[], long[], int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_intersection(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to)
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.
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_intersection(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp)
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
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_difference(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to)
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.
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_difference(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp)
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.
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_symmetric_difference(long[], long[], long[], int, int, int, int, int)
public static int set_symmetric_difference(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to)
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.
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
public static int set_symmetric_difference(long[] source1, long[] source2, long[] destination, int first1, int last1, int first2, int last2, int to, BinaryPredicate comp)
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.
includes(long[], long[], int, int, int, int)
,
set_union(long[], long[], long[], int, int, int, int, int)
,
set_intersection(long[], long[], long[], int, int, int, int, int)
,
set_difference(long[], long[], long[], int, int, int, int, int)
public static void push_heap(long[] array, int first, int last)
[first, last1)
must be a valid heap, and the element to be added must be in
array[last1]
.
The heap is ordered by arithmetic comparison.
array
 Array containing the heap.first
 Beginning of the heap.last
 Index such that [first, last1)
is a
valid heap and such that array[last1]
contains the element to be added to the heap.make_heap(long[], int, int)
public static void push_heap(long[] array, int first, int last, BinaryPredicate comp)
[first, last1)
must be a valid heap, and the element to be added must be in
array[last1]
.
The heap is ordered by a usersupplied comparison function.
array
 Array containing the heap.first
 Beginning of the heap.last
 Index such that [first, last1)
is a
valid heap and such that array[last1]
contains the element to be added to the heap.comp
 Comparison function.make_heap(long[], int, int)
public static void pop_heap(long[] array, int first, int last)
[first, last)
is a valid heap, then remove
array[first]
(the largest element) from the heap,
rearrange elements such that [first, last1)
is
a valid heap, and place the removed element in array[last]
.
The heap is ordered by arithmetic comparison.
array
 Array containing the heap.first
 Beginning of the heap.last
 One past the end of the heap.make_heap(long[], int, int)
public static void pop_heap(long[] array, int first, int last, BinaryPredicate comp)
[first, last)
is a valid heap, then remove
array[first]
(the largest element) from the heap,
rearrange elements such that [first, last1)
is
a valid heap, and place the removed element in array[last]
.
The heap is ordered by a userdefined comparison function.
array
 Array containing the heap.first
 Beginning of the heap.last
 One past the end of the heap.comp
 Comparison function.make_heap(long[], int, int)
public static void make_heap(long[] array, int first, int last)
[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.
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.push_heap(long[], int, int)
,
pop_heap(long[], int, int)
,
sort_heap(long[], int, int)
public static void make_heap(long[] array, int first, int last, BinaryPredicate comp)
[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 userdefined comparison function.
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.push_heap(long[], int, int)
,
pop_heap(long[], int, int)
,
sort_heap(long[], int, int)
public static void sort_heap(long[] array, int first, int last)
O(N log N)
. Note that make_heap
followed by sort_heap
is the heap sort algorithm.
Ordering is by arithmetic comparison.
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.make_heap(long[], int, int)
public static void sort_heap(long[] array, int first, int last, BinaryPredicate comp)
O(N log N)
. Note that make_heap
followed by sort_heap
is the heap sort algorithm.
Ordering is by a usersupplied comparision function.
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.make_heap(long[], int, int)
public static int max_element(long[] array, int first, int last)
array
 Array containing the range.first
 Beginning of the range.last
 End of the range.
i
such that every element
in the range is less than or equivalent to
array[i]
. Returns last
if the range is empty.min_element(long[], int, int)
public static int max_element(long[] array, int first, int last, BinaryPredicate comp)
array
 Array containing the range.first
 Beginning of the range.last
 End of the range.comp
 Comparison function.
i
such that every element
in the range is less than or equivalent to
array[i]
. Returns last
if the range is empty.min_element(long[], int, int)
public static int min_element(long[] array, int first, int last)
array
 Array containing the rangefirst
 Beginning of the rangelast
 End of the range
i
such that every element
in the range is greater than or equivalent to
array[i]
. Returns last
if the range is empty.max_element(long[], int, int)
public static int min_element(long[] array, int first, int last, BinaryPredicate comp)
array
 Array containing the rangefirst
 Beginning of the rangelast
 End of the rangecomp
 Comparison function.
i
such that every element
in the range is greater than or equivalent to
array[i]
. Returns last
if the range is empty.max_element(long[], int, int)
public static boolean lexicographical_compare(long[] array1, long[] array2, int first1, int last1, int first2, int last2)
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.
true
if the sequence of elements in the
range [first1, last1)
is lexicographically
less than that in [first1, last1)
,
otherwise false
.public static boolean lexicographical_compare(long[] array1, long[] array2, int first1, int last1, int first2, int last2, BinaryPredicate comp)
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.
true
if the sequence of elements in the
range [first1, last1)
is lexicographically
less than that in [first1, last1)
,
otherwise false
.public static boolean next_permutation(long[] array, int first, int last)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.
true
if a next permutation exists,
false
if the range is already the largest
permutation.lexicographical_compare(long[], long[], int, int, int, int)
,
prev_permutation(long[], int, int)
public static boolean next_permutation(long[] array, int first, int last, BinaryPredicate comp)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.comp
 Comparison function
true
if a next permutation exists,
false
if the range is already the largest
permutation.lexicographical_compare(long[], long[], int, int, int, int)
,
prev_permutation(long[], int, int)
public static boolean prev_permutation(long[] array, int first, int last)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.
true
if a previous permutation exists,
false
if the range is already the smallest
permutation.lexicographical_compare(long[], long[], int, int, int, int)
,
next_permutation(long[], int, int)
public static boolean prev_permutation(long[] array, int first, int last, BinaryPredicate comp)
array
 Array containing the range.first
 Beginning of the range.last
 One past the end of the range.comp
 Comparison function
true
if a previous permutation exists,
false
if the range is already the smallest
permutation.lexicographical_compare(long[], long[], int, int, int, int)
,
next_permutation(long[], int, int)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 