jal.longs
Class Inspection

java.lang.Object
  jal.longs.Inspection

public final class Inspection

extends Object

A class that encapsulates non-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:

Modification, Sorting, Numeric

Method Summary

static int	adjacent_find(long[] array, int first, int last) Finds the first adjacent pair of equal elements in a range.
static int	adjacent_find(long[] array, int first, int last, BinaryPredicate p) Finds the first adjacent pair of elements in a range that satisfy some condition.
static int	count_if_not(long[] array, int first, int last, Predicate p) Counts the number of elements in a range that do not satisfy a condition.
static int	count_if(long[] array, int first, int last, Predicate p) Counts the number of elements in a range that satisfy a condition.
static boolean	equal(long[] array1, long[] array2, int first1, int last1, int first2) Tests whether two ranges are pairwise equal.
static boolean	equal(long[] array1, long[] array2, int first1, int last1, int first2, BinaryPredicate p) Tests whether two ranges satisfiy a condition pairwise.
static int	find_if_not(long[] array, int first, int last, Predicate p) Finds the first element in a range that does not satisfy some condition.
static int	find_if(long[] array, int first, int last, Predicate p) Finds the first element in a range that satisfies a condition.
static int	find_not(long[] array, int first, int last, long x) Finds the first element in a range that is not equal to a specified value.
static int	find(long[] array, int first, int last, long x) Finds the first element in a range that is equal to a specified value.
static void	for_each(long[] array, int first, int last, VoidFunction f) Applies a function to every element of a range.
static int	mismatch(long[] array1, long[] array2, int first1, int last1, int first2) Finds the first location at which two ranges differ.
static int	mismatch(long[] array1, long[] array2, int first1, int last1, int first2, BinaryPredicate p) Finds the first location at which two ranges fail to satisfy a condition.
static int	search(long[] array1, long[] array2, int first1, int last1, int first2, int last2) Searches, within one range, for a sequence of elements equal to the elements in a second range.
static int	search(long[] array1, long[] array2, int first1, int last1, int first2, int last2, BinaryPredicate p) Searches, within one range, for a sequence of elements that match the elements in a second range.

Methods inherited from class java.lang.Object

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

Method Detail

for_each

public static void for_each(long[] array,
                            int first,
                            int last,
                            VoidFunction f)

Applies a function to every element of a range.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

f - Function to be applied.

adjacent_find

public static int adjacent_find(long[] array,
                                int first,
                                int last)

Finds the first adjacent pair of equal elements in a range.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

Returns:

The first iterator i in the range [first, last-1) such that array[i] == array[i+1]. Returns last if no such iterator exists.

adjacent_find

public static int adjacent_find(long[] array,
                                int first,
                                int last,
                                BinaryPredicate p)

Finds the first adjacent pair of elements in a range that satisfy some condition.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

p - Condition that must be satisfied.

Returns:

The first iterator i in the range [first, last-1) such that p.apply(array[i], array[i+1]) is true. Returns last if no such iterator exists.

find

public static int find(long[] array,
                       int first,
                       int last,
                       long x)

Finds the first element in a range that is equal to a specified value.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Value to be searched for.

Returns:

Index of first element E such that E == x, or last if no such element exists.

find_not

public static int find_not(long[] array,
                           int first,
                           int last,
                           long x)

Finds the first element in a range that is not equal to a specified value.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

x - Value to be searched for.

Returns:

Index of first element E such that E != x, or last if no such element exists.

find_if

public static int find_if(long[] array,
                          int first,
                          int last,
                          Predicate p)

Finds the first element in a range that satisfies a condition.

Parameters:

array - Array containing the range.

first - Beginning of the range.

last - One past the end of the range.

p - Condition to search for.

Returns:

Index of first element E such that E == x, or last if no such element exists.

find_if_not

public static int find_if_not(long[] array,
                              int first,
                              int last,
                              Predicate p)

Finds the first element in a range that does not satisfy some condition.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

Index of first element E such that p.apply(E) is false, or last if no such element exists.

count_if

public static int count_if(long[] array,
                           int first,
                           int last,
                           Predicate p)

Counts the number of elements in a range that satisfy a condition.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

Number of elements E such that p.apply(E) is true.

count_if_not

public static int count_if_not(long[] array,
                               int first,
                               int last,
                               Predicate p)

Counts the number of elements in a range that do not satisfy a condition.

Parameters:

array - Array containing the range

first - Beginning of the range

last - One past the end of the range

p - Condition being tested

Returns:

Number of elements E such that p.apply(E) is false.

mismatch

public static int mismatch(long[] array1,
                           long[] array2,
                           int first1,
                           int last1,
                           int first2)

Finds the first location at which two ranges differ. Note: the two ranges are permitted to be in the same array and are permitted to overlap.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first range.

first1 - Beginning of the first range

last1 - One past the end of the first range

first2 - Beginning of the second range

Returns:

The first index i such that array1[i] != array2[first2 + (i-first1)], or last1 if no such index in the range [first1,last1) exists.

mismatch

public static int mismatch(long[] array1,
                           long[] array2,
                           int first1,
                           int last1,
                           int first2,
                           BinaryPredicate p)

Finds the first location at which two ranges fail to satisfy a condition. Note: the two ranges are permitted to be in the same array and are permitted to overlap.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first range.

first1 - Beginning of the first range

last1 - One past the end of the first range

first2 - Beginning of the second range

p - Condition to be tested

Returns:

The first index i such that p.apply(array1[i], array2[first2 + (i-first1)]) is false, or last1 if no such index in the range [first1,last1) exists.

equal

public static boolean equal(long[] array1,
                            long[] array2,
                            int first1,
                            int last1,
                            int first2)

Tests whether two ranges are pairwise equal. Note: the two ranges are permitted to be in the same array and are permitted to overlap.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first range.

first1 - Beginning of the first range

last1 - One past the end of the first range

first2 - Beginning of the second range

Returns:

true if, for every index i in the range [first1,last1), array1[i] == array2[first2 + (i-first1)], otherwise returns false.

equal

public static boolean equal(long[] array1,
                            long[] array2,
                            int first1,
                            int last1,
                            int first2,
                            BinaryPredicate p)

Tests whether two ranges satisfiy a condition pairwise. Note: the two ranges are permitted to be in the same array and are permitted to overlap.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first range.

first1 - Beginning of the first range.

last1 - One past the end of the first range.

first2 - Beginning of the second range.

p - Condition to be tested

Returns:

true if, for every index i in the range [first1,last1), p.apply(array1[i], array2[first2 + (i-first1)]) is true, otherwise returns false.

search

public static int search(long[] array1,
                         long[] array2,
                         int first1,
                         int last1,
                         int first2,
                         int last2)

Searches, within one range, for a sequence of elements equal to the elements in a second range. Note: the two ranges are permitted to be in the same array and are permitted to overlap. Note: the worst-case performance of this algorithm is quadratic.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first 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:

The first index in the range [first1, last1-len) such that for every non-negative i<len (where len = last2-first2), the condition array1[first1+n] == array2[first1+n] is satisfied, or last1 if no such index exists.

search

public static int search(long[] array1,
                         long[] array2,
                         int first1,
                         int last1,
                         int first2,
                         int last2,
                         BinaryPredicate p)

Searches, within one range, for a sequence of elements that match the elements in a second range. Matching is defined as satisfying a BinaryPredicate passed as an argument. Note: the two ranges are permitted to be in the same array and are permitted to overlap. Note: the worst-case performance of this algorithm is quadratic.

Parameters:

array1 - Array containing the first range.

array2 - Array containing the first 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.

p - Condition to be tested pairwise.

Returns:

The first index in the range [first1, last1-len) such that for every non-negative i<len (where len = last2-first2), the condition p.apply(array1[first1+n],array2[first1+n]) is satisfied, or last1 if no such index exists.