jal.doubles
Class Modification

java.lang.Object
  jal.doubles.Modification

public final class Modification

extends Object

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.

Author:

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

See Also:

Inspection, Sorting, Numeric

Method Summary

static void	copy(double[] source, double[] destination, int first, int last, int to) Copy elements from one location to another.
static void	fill(double[] array, int first, int last, double x) Assigns a value to every element in a range.
static void	generate(double[] array, int first, int last, Generator f) Assigns values, produced by a function object that takes no arguments, to each element of a range.
static int	partition(double[] array, int first, int last, Predicate p) Rearranges elements in a range such that all elements that satisfy a condition are placed before all elements that do not satisfy it.
static void	random_shuffle(double[] array, int first, int last) Shuffles elements in a range, with uniform distribution.
static void	random_shuffle(double[] array, int first, int last, Random RNG) Shuffles elements in a range, with uniform distribution.
static int	remove_copy_if(double[] source, double[] destination, int first, int last, int to, Predicate p) Copies all of the elements in a range except for those that satisfy a given condition.
static int	remove_copy(double[] source, double[] destination, int first, int last, int to, double value) Copies all of the elements in a range except for those that are equal to a given value.
static int	remove_if(double[] array, int first, int last, double x) Remove all elements from a range that are equal to a given value.
static int	remove_if(double[] array, int first, int last, Predicate p) Remove all elements from a range that satisfy a specified condition.
static void	replace_copy_if(double[] source, double[] destination, int first, int last, int to, Predicate p, double new_value) Performs copying and substitution on a range of elements.
static void	replace_copy(double[] source, double[] destination, int first, int last, int to, double old_value, double new_value) Performs copying and substitution on a range of elements.
static void	replace_if(double[] array, int first, int last, Predicate p, double new_value) Performs in-place substitution on a range of elements.
static void	replace(double[] array, int first, int last, double old_value, double new_value) Performs in-place substitution on a range of elements.
static void	reverse_copy(double[] source, double[] destination, int first, int last, int to) Creates a copy of an input range consisting of that range in reverse order; equivalent to copy followed by reverse, but faster.
static void	reverse_copy(double[] array, int first, int last, int to)
static void	reverse(double[] array, int first, int last) Reverses a sequence of elements.
static void	rotate_copy(double[] source, double[] destination, int first, int middle, int last, int to) Creates a copy of an input range consisting of a rotation of that range.
static void	rotate(double[] array, int first, int middle, int last) Rotate a range in place: array[middle] is put in array[first], array[middle+1] is put in array[first+1], etc.
static int	stable_partition(double[] array, int first, int last, Predicate p) Rearranges elements in a range such that all elements that satisfy a condition are placed before all elements that do not satisfy it.
static int	stable_remove_if(double[] array, int first, int last, Predicate p) Remove all elements from a range that satisfy a specified condition.
static int	stable_remove(double[] array, int first, int last, double x) Remove all elements from a range that are equal to a given value.
static void	swap_ranges(double[] array1, double[] array2, int first1, int last1, int first2) Performs a pairwise swap of two ranges.
static void	transform(double[] source1, double[] source2, double[] destination, int first1, int last1, int first2, int to, BinaryOperator f) Performs a binary operation on elements of two ranges, assigning the result to elements of another range.
static void	transform(double[] source, double[] destination, int first, int last, int to, UnaryOperator f) Performs an operation on every element of a range and assigns the result to elements in another range.
static int	unique_copy(double[] source, double[] destination, int first, int last, int to) 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.
static int	unique_copy(double[] source, double[] destination, int first, int last, int to, BinaryPredicate p) 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.
static int	unique(double[] array, int first, int last) Eliminates all but the first element of every consecutive group of equal elements.
static int	unique(double[] array, int first, int last, BinaryPredicate p) Eliminates all but the first element of every consecutive group of equivalent elements, where equivalence is determined by a supplied predicate.

Methods inherited from class java.lang.Object

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

Method Detail

copy

public static void copy(double[] source,
                        double[] destination,
                        int first,
                        int last,
                        int to)

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.

Parameters:

source - Array from which elements are copied

destination - Array to which elements are copied

first - Beginning of the range from which elements are copied

last - One past the end of the range

to - Beginning of the range to which elements will be copied.

Throws:

ArrayIndexOutOfBoundsException - If the input or output range is invalid.

swap_ranges

public static void swap_ranges(double[] array1,
                               double[] array2,
                               int first1,
                               int last1,
                               int first2)

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.

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.

transform

public static void transform(double[] source,
                             double[] destination,
                             int first,
                             int last,
                             int to,
                             UnaryOperator f)

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.

Parameters:

source - Array containing the elements to be operated on.

destination - Array in which results of the operation will be stored.

first - Beginning of the input range.

last - One past the end of the input range.

to - Beginning of the output range.

f - Operation to perform on elements of the input range.

transform

public static void transform(double[] source1,
                             double[] source2,
                             double[] destination,
                             int first1,
                             int last1,
                             int first2,
                             int to,
                             BinaryOperator f)

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.

Parameters:

source1 - Array containing first range of input elements.

source2 - Array containing second range of input elements.

destination - Array in which results of the operation will be stored.

first1 - Beginning of the first input range.

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

first2 - Beginning of the second input range.

to - Beginning of the output range.

f - Operation to perform on elements of the input range.

replace

public static void replace(double[] array,
                           int first,
                           int last,
                           double old_value,
                           double new_value)

Performs in-place substitution on a range of elements. All elements equal to old_value are replaced by new_value.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

old_value - Value that will be replaced.

new_value - Value that old_value will be replaced with.

replace_if

public static void replace_if(double[] array,
                              int first,
                              int last,
                              Predicate p,
                              double new_value)

Performs in-place substitution on a range of elements. Every element E for which p.apply(E) is true are replaced by new_value.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

p - Condition for replacement.

new_value - Value to be substituted for replaced elements.

replace_copy

public static void replace_copy(double[] source,
                                double[] destination,
                                int first,
                                int last,
                                int to,
                                double old_value,
                                double new_value)

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.

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.

to - Beginning of the output range.

old_value - Value to be replaced.

new_value - Value that old_value will be replaced with.

replace_copy_if

public static void replace_copy_if(double[] source,
                                   double[] destination,
                                   int first,
                                   int last,
                                   int to,
                                   Predicate p,
                                   double new_value)

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.

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.

to - Beginning of the output range.

p - Condition for replacement.

new_value - Value to be substituted for replaced elements.

fill

public static void fill(double[] array,
                        int first,
                        int last,
                        double x)

Assigns a value to every element in a range. The array must contain sufficient space, and existing elements will be overwritten.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

x - Value to be assigned to elements in the range

generate

public static void generate(double[] array,
                            int first,
                            int last,
                            Generator f)

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.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

f - Source of values to be assigned to elements in the range. f.apply() is evaluated exactly last-first times.

remove_if

public static int remove_if(double[] array,
                            int first,
                            int last,
                            double x)

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.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

x - Value to be removed.

Returns:

An index i such that all remaining elements are contained in the range [first, i).

remove_if

public static int remove_if(double[] array,
                            int first,
                            int last,
                            Predicate p)

Remove all elements from a range that satisfy a specified condition. It is not guaranteed that the relative order of remaining elements is unchanged.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

An index i such that all remaining elements are contained in the range [first, i).

stable_remove

public static int stable_remove(double[] array,
                                int first,
                                int last,
                                double x)

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.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Value to be removed.

Returns:

An index i such that all remaining elements are contained in the range [first, i).

stable_remove_if

public static int stable_remove_if(double[] array,
                                   int first,
                                   int last,
                                   Predicate p)

Remove all elements from a range that satisfy a specified condition. It is guaranteed that the relative order of remaining elements is unchanged.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

An index i such that all remaining elements are contained in the range [first, i).

remove_copy

public static int remove_copy(double[] source,
                              double[] destination,
                              int first,
                              int last,
                              int to,
                              double value)

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.

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

to - Beginning of the output range.

value - Value to be removed.

Returns:

An index i such that the resulting output range is [to, i).

remove_copy_if

public static int remove_copy_if(double[] source,
                                 double[] destination,
                                 int first,
                                 int last,
                                 int to,
                                 Predicate p)

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.

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

to - Beginning of the output range.

p - Condition for removal.

Returns:

An index i such that the resulting output range is [to, i).

unique

public static int unique(double[] array,
                         int first,
                         int last)

Eliminates all but the first element of every consecutive group of equal elements. The relative order of remaining elements is guaranteed to be unchanged.

Parameters:

array - Array containing the range

first - Beginning of the input range

last - One past the end of the input range

Returns:

An index i such that the resulting output range is [first, i).

unique

public static int unique(double[] array,
                         int first,
                         int last,
                         BinaryPredicate p)

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.

Parameters:

array - Array containing the range

first - Beginning of the input range

last - One past the end of the input range

p - Predicate used to determine equivalence.

Returns:

An index i such that the resulting output range is [first, i).

unique_copy

public static int unique_copy(double[] source,
                              double[] destination,
                              int first,
                              int last,
                              int to)

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.

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.

to - Beginning of the output range.

Returns:

An index i such that the resulting output range is [to, i).

unique_copy

public static int unique_copy(double[] source,
                              double[] destination,
                              int first,
                              int last,
                              int to,
                              BinaryPredicate p)

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.

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.

to - Beginning of the output range.

p - Predicate used to determine equivalence.

Returns:

An index i such that the resulting output range is [to, i).

reverse

public static void reverse(double[] array,
                           int first,
                           int last)

Reverses a sequence of elements.

Parameters:

array - Array containing the sequence

first - Beginning of the range

last - One past the end of the range

Throws:

ArrayIndexOutOfBoundsException - If the range is invalid.

reverse_copy

public static void reverse_copy(double[] array,
                                int first,
                                int last,
                                int to)

reverse_copy

public static void reverse_copy(double[] source,
                                double[] destination,
                                int first,
                                int last,
                                int to)

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.

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

to - First element of the output range

rotate

public static void rotate(double[] array,
                          int first,
                          int middle,
                          int 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).

Parameters:

array - Array containing the range

first - Beginning of the range

middle - Index of the element that will be put in array[first]

last - One past the end of the range

rotate_copy

public static void rotate_copy(double[] source,
                               double[] destination,
                               int first,
                               int middle,
                               int last,
                               int to)

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.

Parameters:

source - Array containing the input range.

destination - Array containing the output range.

first - Beginning of the input range

middle - Element that is mapped to to.

last - One past the end of the input range

to - First element of the output range

random_shuffle

public static void random_shuffle(double[] array,
                                  int first,
                                  int last,
                                  Random RNG)

Shuffles elements in a range, with uniform distribution.

Parameters:

array - Array containing the range to be shuffled

first - Beginning of the range

last - One past the end of the range

RNG - Object of class java.util.Random, used to supply random numbers.

random_shuffle

public static void random_shuffle(double[] array,
                                  int first,
                                  int last)

Shuffles elements in a range, with uniform distribution. Uses a default random number generator.

Parameters:

array - Array containing the range to be shuffled

first - Beginning of the range

last - One past the end of the range

partition

public static int partition(double[] array,
                            int first,
                            int last,
                            Predicate p)

Rearranges elements in a range such that all elements that satisfy a condition are placed before all elements that do not satisfy it.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

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 Also:

Predicate

stable_partition

public static int stable_partition(double[] array,
                                   int first,
                                   int last,
                                   Predicate p)

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.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

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 Also:

Predicate