package jal.GENERIC; import jal.GENERIC.Generator; import jal.GENERIC.UnaryOperator; import jal.GENERIC.BinaryOperator; import jal.GENERIC.Predicate; import jal.GENERIC.BinaryPredicate; import java.util.Random; import java.lang.Math; /** * A class that encapsulates mutating sequence 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.
*
*
*
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.
*
*
* @see Inspection
* @see Sorting
* @see Numeric
* @author Matthew Austern (austern@mti.sgi.com)
* @author Alexander Stepanov (stepanov@mti.sgi.com)
*/
public final class Modification
{
/**
* Copy elements from one location to another. There must be
* enough space in the destination array, and existing elements
* will be overwritten. Note: the source and destination ranges are
* permitted to be in the same range and are permitted to overlap.
* @param source Array from which elements are copied
* @param destination Array to which elements are copied
* @param first Beginning of the range from which elements are copied
* @param last One past the end of the range
* @param to Beginning of the range to which elements will be
* copied.
* @exception ArrayIndexOutOfBoundsException If the input or
* output range is invalid.
*/
static public void copy(generic[] source, generic[] destination,
int first, int last, int to)
{
if (last > first)
System.arraycopy(source, first, destination, to, last - first);
}
/**
* Performs a pairwise swap of two ranges. That is: for every index
* i
in the range [first1,last1)
, swaps
* array1[i]
and array2[first2 + (i-first1)]
.
* Note: if the two ranges are in the same array, they are not
* permitted to overlap.
* @param array1 Array containing the first range.
* @param array2 Array containing the second range.
* @param first1 Beginning of the first range.
* @param last1 One past the end of the first range
* @param first2 Beginning of the second range.
*/
static public void swap_ranges(generic[] array1, generic[] array2,
int first1, int last1, int first2)
{
while (first1 < last1) {
generic tmp = array2[first2];
array2[first2] = array1[first1];
array1[first1] = tmp;
++first1;
++first2;
}
}
/**
* Performs an operation on every element of a range and assigns the result
* to elements in another range. That is: for every index i
* in the range [first,last)
, performs the operation
* destination[to + (i-first)] = f.apply(source[i])
.
* The destination array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the elements to be operated on.
* @param destination Array in which results of the operation will be
* stored.
* @param first Beginning of the input range.
* @param last One past the end of the input range.
* @param to Beginning of the output range.
* @param f Operation to perform on elements of the
* input range.
*/
public static void transform(generic[] source, generic[] destination,
int first, int last, int to,
UnaryOperator f)
{
while (first < last)
destination[to++] = f.apply(source[first++]);
}
/**
* Performs a binary operation on elements of two ranges, assigning the
* result to elements of another range. That is: for every index i
* in the range [first1,last1)
, performs the operation
* destination[to + (i-first1)] =
* f.apply(source1[i], source2[first2 + (i-first1)])
.
* The destination array must contain
* sufficient space, and existing elements will be overwritten.
* @param source1 Array containing first range of input elements.
* @param source2 Array containing second range of input elements.
* @param destination Array in which results of the operation will be
* stored.
* @param first1 Beginning of the first input range.
* @param last1 One past the end of the first input range.
* @param first2 Beginning of the second input range.
* @param to Beginning of the output range.
* @param f Operation to perform on elements of the
* input range.
*/
public static void transform(generic[] source1, generic[] source2,
generic[] destination,
int first1, int last1, int first2, int to,
BinaryOperator f)
{
while (first1 < last1)
destination[to++] = f.apply(source1[first1++], source2[first2++]);
}
/**
* Performs in-place substitution on a range of elements. All elements
* equal to old_value
are replaced by new_value
.
* @param array Array containing the range.
* @param first Beginning of the range.
* @param last One past the end of the range.
* @param old_value Value that will be replaced.
* @param new_value Value that old_value will be replaced with.
*/
public static void replace(generic[] array, int first, int last,
generic old_value, generic new_value)
{
while (first < last) {
if (array[first] == old_value)
array[first] = new_value;
++first;
}
}
/**
* Performs in-place substitution on a range of elements. Every element
* E
for which p.apply(E)
is true
* are replaced by new_value
.
* @param array Array containing the range.
* @param first Beginning of the range.
* @param last One past the end of the range.
* @param p Condition for replacement.
* @param new_value Value to be substituted for replaced elements.
*/
public static void replace_if(generic[] array, int first, int last,
Predicate p, generic new_value)
{
while (first < last) {
if (p.apply(array[first]))
array[first] = new_value;
++first;
}
}
/**
* Performs copying and substitution on a range of elements. The elements
* in the input range are copied to an output range, except that
* new_value
is substituted for any elements that are equal
* to old_value
.
* The destination array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range.
* @param last One past the end of the input range.
* @param to Beginning of the output range.
* @param old_value Value to be replaced.
* @param new_value Value that old_value will be replaced with.
*/
public static void replace_copy(generic[] source, generic[] destination,
int first, int last, int to,
generic old_value, generic new_value)
{
while (first < last) {
generic tmp = source[first++];
destination[to++] = (tmp == old_value) ? new_value : tmp;
}
}
/**
* Performs copying and substitution on a range of elements. The elements
* in the input range are copied to an output range, except that
* new_value
is substituted for any elements E
* that satisfy the condition p.apply(E)
.
* The destination array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range.
* @param last One past the end of the input range.
* @param to Beginning of the output range.
* @param p Condition for replacement.
* @param new_value Value to be substituted for replaced elements.
*/
public static void replace_copy_if(generic[] source, generic[] destination,
int first, int last, int to,
Predicate p, generic new_value)
{
while (first < last) {
generic tmp = source[first++];
destination[to++] = p.apply(tmp) ? new_value : tmp;
}
}
/**
* Assigns a value to every element in a range. The array must contain
* sufficient space, and existing elements will be overwritten.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param x Value to be assigned to elements in the range
*/
public static void fill(generic[] array, int first, int last,
generic x)
{
while(first < last)
array[first++] = x;
}
/**
* Assigns values, produced by a function object that takes no arguments,
* to each element of a range. The array must contain
* sufficient space, and existing elements will be overwritten.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param f Source of values to be assigned to elements in
* the range. f.apply()
is evaluated
* exactly last-first
times.
*/
public static void generate(generic[] array, int first, int last,
Generator f)
{
while(first < last)
array[first++] = f.apply();
}
/**
* Remove all elements from a range that are equal to a given value.
* It is not guaranteed that the relative order of remaining elements is
* unchanged.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param x Value to be removed.
* @return An index i
such that all remaining elements
* are contained in the range [first, i)
.
*/
public static int remove_if(generic[] array, int first, int last,
generic x)
{
int oldLast = last;
--first;
while (true) {
while (++first < last && array[first] != x);
while (first < --last && array[last] == x);
if (first >= last) {
return first;
}
array[first] = array[last];
}
}
/**
* Remove all elements from a range that satisfy a specified condition.
* It is not guaranteed that the relative order of remaining elements is
* unchanged.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param p Condition being tested
* @return An index i
such that all remaining elements
* are contained in the range [first, i)
.
*/
public static int remove_if(generic[] array, int first, int last,
Predicate p)
{
int oldLast = last;
--first;
while (true) {
while (++first < last && !p.apply(array[first]));
while (first < --last && p.apply(array[last]));
if (first >= last) {
return first;
}
array[first] = array[last];
}
}
/**
* Remove all elements from a range that are equal to a given value.
* It is guaranteed that the relative order of remaining elements is
* unchanged.
* @param array Array containing the range.
* @param first Beginning of the range.
* @param last One past the end of the range.
* @param x Value to be removed.
* @return An index i
such that all remaining elements
* are contained in the range [first, i)
.
*/
public static int stable_remove(generic[] array, int first, int last,
generic x)
{
first = Inspection.find(array, first, last, x);
int next = Inspection.find_not(array, first, last, x);
while (next < last) {
array[first++] = array[next];
next = Inspection.find_not(array, ++next, last, x);
}
return first;
}
/**
* Remove all elements from a range that satisfy a specified condition.
* It is guaranteed that the relative order of remaining elements is
* unchanged.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param p Condition being tested
* @return An index i
such that all remaining elements
* are contained in the range [first, i)
.
*/
public static int stable_remove_if(generic[] array, int first, int last,
Predicate p)
{
first = Inspection.find_if(array, first, last, p);
int next = Inspection.find_if_not(array, first, last, p);
while (next < last) {
array[first++] = array[next];
next = Inspection.find_if_not(array, ++next, last, p);
}
return first;
}
/**
* Copies all of the elements in a range except for those that are
* equal to a given value. It is guaranteed that the relative order of
* elements that are copied is the same as in the input range.
* The output array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range
* @param last One past the end of the input range
* @param to Beginning of the output range.
* @param value Value to be removed.
* @return An index i such that the resulting output range
* is [to, i)
.
*/
static public int remove_copy(generic[] source, generic[] destination,
int first, int last, int to,
generic value)
{
while (first < last) {
generic tmp = source[first++];
if (tmp != value)
destination[to++] = tmp;
}
return to;
}
/**
* Copies all of the elements in a range except for those that satisfy
* a given condition. It is guaranteed that the relative order of
* elements that are copied is the same as in the input range.
* The output array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range
* @param last One past the end of the input range
* @param to Beginning of the output range.
* @param p Condition for removal.
* @return An index i such that the resulting output range
* is [to, i)
.
*/
static public int remove_copy_if(generic[] source, generic[] destination,
int first, int last, int to,
Predicate p)
{
while (first < last) {
generic tmp = source[first++];
if (!p.apply(tmp))
destination[to++] = tmp;
}
return to;
}
/**
* Eliminates all but the first element of every consecutive group
* of equal elements. The relative order of remaining elements is
* guaranteed to be unchanged.
* @param array Array containing the range
* @param first Beginning of the input range
* @param last One past the end of the input range
* @return An index i such that the resulting output range
* is [first, i)
.
*/
public static int unique(generic[] array, int first, int last)
{
first = Inspection.adjacent_find(array, first, last);
return unique_copy(array, array, first, last, first);
}
/**
* Eliminates all but the first element of every consecutive group
* of equivalent elements, where equivalence is determined by a
* supplied predicate.
* The relative order of remaining elements is
* guaranteed to be unchanged.
* @param array Array containing the range
* @param first Beginning of the input range
* @param last One past the end of the input range
* @param p Predicate used to determine equivalence.
* @return An index i such that the resulting output range
* is [first, i)
.
*/
public static int unique(generic[] array, int first, int last,
BinaryPredicate p)
{
first = Inspection.adjacent_find(array, first, last, p);
return unique_copy(array, array, first, last, first, p);
}
/**
* Copies elements from an input range to an output range, except that
* only the first element is copied from every consecutive group of
* equal elements.
* The relative order of elements that are copied is
* guaranteed to be the same as in the input range.
* The output array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range.
* @param last One past the end of the input range.
* @param to Beginning of the output range.
* @return An index i such that the resulting output range
* is [to, i)
.
*/
public static int unique_copy(generic[] source, generic[] destination,
int first, int last, int to)
{
if (first >= last)
return to;
else
destination[to] = source[first];
while (++first < last) {
if (destination[to] != source[first])
destination[++to] = source[first];
}
return to + 1;
}
/**
* Copies elements from an input range to an output range, except that
* only the first element is copied from every consecutive group of
* equivalent elements; equivalence is determined by a
* supplied predicate.
* The relative order of elements that are copied is
* guaranteed to be the same as in the input range.
* The output array must contain
* sufficient space, and existing elements will be overwritten.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range.
* @param last One past the end of the input range.
* @param to Beginning of the output range.
* @param p Predicate used to determine equivalence.
* @return An index i such that the resulting output range
* is [to, i)
.
*/
public static int unique_copy(generic[] source, generic[] destination,
int first, int last, int to,
BinaryPredicate p)
{
if (first >= last)
return to;
else
destination[to] = source[first];
while (++first < last) {
if (!p.apply(destination[to], source[first]))
destination[++to] = source[first];
}
return to + 1;
}
/**
* Reverses a sequence of elements.
* @param array Array containing the sequence
* @param first Beginning of the range
* @param last One past the end of the range
* @exception ArrayIndexOutOfBoundsException If the range
* is invalid.
*/
static public void reverse(generic[] array, int first, int last)
{
while (first < --last) {
generic tmp = array[first];
array[first++] = array[last];
array[last] = tmp;
}
}
public static void reverse_copy(generic[] array, int first, int last, int to)
{
while (last > first)
array[to++] = array[--last];
}
/**
* Creates a copy of an input range consisting of that range in
* reverse order; equivalent to copy followed by reverse, but faster.
* There must be enough space in the array, and existing elements will
* be overwritten. Note: if source
and
* destination
are the same array, the input and output
* ranges are not permitted to overlap.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range
* @param last One past the end of the input range
* @param to First element of the output range
*/
public static void reverse_copy(generic[] source, generic[] destination,
int first, int last, int to)
{
while (last > first)
destination[to++] = source[--last];
}
/**
* Rotate a range in place: array[middle]
is put in
* array[first]
, array[middle+1]
is put in
* array[first+1]
, etc. Generally, the element in position
* i
is put into position
* (i + (last-middle)) % (last-first)
.
* @param array Array containing the range
* @param first Beginning of the range
* @param middle Index of the element that will be put in
* array[first]
* @param last One past the end of the range
*/
public static void rotate(generic[] array, int first, int middle,
int last)
{
if (middle != first && middle != last) {
reverse(array, first, middle);
reverse(array, middle, last);
reverse(array, first, last);
}
}
/**
* Creates a copy of an input range consisting of a rotation of that
* range. Specifically: for each i, first + i
is assigned to
* to + (i + (last-middle)) % (last-first)
.
* There must be enough space in the output array, and existing elements
* will be overwritten. Note: if source
and
* destination
are the same array, the input and output
* ranges are not permitted to overlap.
* @param source Array containing the input range.
* @param destination Array containing the output range.
* @param first Beginning of the input range
* @param middle Element that is mapped to to
.
* @param last One past the end of the input range
* @param to First element of the output range
*/
public static void rotate_copy(generic[] source, generic[] destination,
int first, int middle, int last, int to)
{
copy(source, destination, middle, last, to);
copy(source, destination, first, middle, to + (last - middle));
}
/**
* Shuffles elements in a range, with uniform distribution.
* @param array Array containing the range to be shuffled
* @param first Beginning of the range
* @param last One past the end of the range
* @param RNG Object of class java.util.Random
,
* used to supply random numbers.
*/
public static void random_shuffle(generic[] array, int first, int last,
Random RNG)
{
for (int i = first + 1; i < last; ++i) {
int randomPlace = Math.abs(RNG.nextInt()) %
((i - first) + 1);
generic tmp = array[randomPlace];
array[randomPlace] = array[i];
array[i] = tmp;
}
}
private static Random default_RNG = new Random();
/**
* Shuffles elements in a range, with uniform distribution.
* Uses a default random number generator.
* @param array Array containing the range to be shuffled
* @param first Beginning of the range
* @param last One past the end of the range
*/
public static void random_shuffle(generic[] array, int first, int last)
{
random_shuffle(array, first, last, default_RNG);
}
/**
* Rearranges elements in a range such that all elements that satisfy
* a condition are placed before all elements that do not satisfy it.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param p Condition being tested
* @return An index a
such that for all
* first <= i < a
,
* p.apply(array[i])
is true
* and such that for all
* a <= i < last
,
* p.apply(array[i])
is false
.
* @see Predicate
*/
public static int partition(generic[] array, int first, int last,
Predicate p)
{
--first;
while (true) {
while (++first < last && p.apply(array[first]));
while (first < --last && !p.apply(array[last]));
if (first >= last) return first;
generic tmp = array[first];
array[first] = array[last];
array[last] = tmp;
}
}
/**
* Rearranges elements in a range such that all elements that satisfy
* a condition are placed before all elements that do not satisfy it.
* It is guaranteed that the relative ordering within each group is
* unchanged.
* @param array Array containing the range
* @param first Beginning of the range
* @param last One past the end of the range
* @param p Condition being tested
* @return An index a
such that for all
* first <= i < a
,
* p.apply(array[i])
is true
* and such that for all
* a <= i < last
,
* p.apply(array[i])
is false
.
* @see Predicate
*/
public static int stable_partition(generic[] array, int first,
int last, Predicate p)
{
if (first + 1 < last) {
int middle = first + (last - first) / 2;
int firstCut = stable_partition(array, first, middle, p);
int secondCut = stable_partition(array, middle, last, p);
rotate(array, firstCut, middle, secondCut);
return firstCut + (secondCut - middle);
}
if (first >= last || !p.apply(array[first]))
return first;
else
return last;
}
/* We don't need a constructor. */
private Modification() {}
}