net.sf.jga.util

Class Iterators

public class Iterators extends Object

Facade for the Algorithms adapted from STL, defined to work primarily with iterators. These algorithms are adapted from STL, with modifications to be consistent with typical java practice. For example, typical STL algorithms are defined with pairs of iterators defining a half-open range over some implied collection. It works in C++ because the STL iterators can be compared for equality. Java iterators are not guaranteed to be comparable to each other by contract, so the same signatures wouldn't work.

Typically, where an STL algorithm would take a pair of iterators, this facade will take a single iterator and where an STL algorithm would return an iterator, we'll return an iterator. In this facade, the iterator returned will frequently be specialized in some way: either a ListIterator or one of the iterators defined in jga.

It is best to assume that all of the methods in this class may (but are not guaranteed to) advance the iterator argument. Also, once an iterator has been passed to one of the methods of this class, it should not be used again. On the other hand, unless otherwise noted, it is safe to pass the iterator returned by one of the methods in this class back to the method that returned it, or to any of the other methods.

Copyright © 2003 David A. Hall

Author: David A. Hall

Method Summary
static <T> Taccumulate(Iterator<T> iterator, T initial, BinaryFunctor<T,T,T> bf)
Applies the binary functor to each element in the iterator, returning the final result.
static <T> longcount(Iterator<? extends T> iterator, T value)
Counts the number of occurrences of value in the iteration, using the equals() method of the value.
static <T> longcount(Iterator<? extends T> iterator, Equality<T> eq, T value)
Counts the number of occurrences of value in the iteration, using the given equality operator.
static <T> longcount(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Counts the items in the collection for which the given function returns TRUE.
static <T extends Comparable> booleanequal(Iterator<? extends T> iterator1, Iterator<? extends T> iterator2)
Returns true if the two iterations are equal, using the Comparable interface to compare elements in the iterations.
static <T> booleanequal(Iterator<? extends T> iterator1, Iterator<? extends T> iterator2, Comparator<T> comp)
Returns true if the two iterations are equal, using the given Comparator to compare elements in the iterations.
static <T> booleanequal(Iterator<? extends T> iter1, Iterator<? extends T> iter2, BinaryFunctor<T,T,Boolean> eq)
Returns true if the two iterations are equal, using the given BinaryFunctor to compare elements in the iterations.
static <T> FindIterator<T>find(Iterator<? extends T> iterator, T value)
Finds an arbitrary value in an iteration using the equals() method.
static <T> FindIterator<T>find(Iterator<? extends T> iterator, T value, Equality<T> eq)
Finds an arbitrary value in an iteration using the given Equality operator.
static <T> FindIterator<T>find(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Finds a value in a collection for which the given function returns TRUE.
static <T> LookAheadIterator<T>findAdjacent(Iterator<? extends T> iterator)
Finds adjacent pairs of equivalent values in an iteration using the equals() method.
static <T> LookAheadIterator<T>findAdjacent(Iterator<? extends T> iterator, BinaryFunctor<T,T,Boolean> bf)
Finds adjacent pairs of equivalent values in an iteration for which the given function returns TRUE.
static <T> FindIterator<T>findElement(Iterator<? extends T> iterator, Collection<? extends T> desired)
Finds any value from the given collection using the collection's contains() method.
static <T> FindIterator<T>findElement(Iterator<? extends T> iter, Collection<? extends T> coll, BinaryFunctor<T,T,Boolean> eq)
Finds any value from the given collection using the given functor to determine equivalence.
static <T> LookAheadIterator<T>findRepeated(Iterator<? extends T> iterator, int n, T value)
Finds arbitrary length runs of a given value in an iteration using the equals() method.
static <T> LookAheadIterator<T>findRepeated(Iterator<? extends T> iterator, int n, T value, Equality<T> eq)
Finds arbitrary length runs of a given value in an iteration using the given equality operator.
static <T> LookAheadIterator<T>findRepeated(Iterator<? extends T> iterator, int n, UnaryFunctor<T,Boolean> eq)
Finds arbitrary length runs of a given value in an iteration for which the given function returns TRUE.
static <T,R> UnaryFunctor<T,R>forEach(Iterator<? extends T> iterator, UnaryFunctor<T,R> fn)
Applies the given UnaryFunctor to every element in the iteration, and returns the Functor.
static <T extends Comparable> booleanlessThan(Iterator<? extends T> iter1, Iterator<? extends T> iter2)
Returns true if the first iterator is lexically less than the second, using the default comparison operation to compare the elements in each iterator.
static <T> booleanlessThan(Iterator<? extends T> iter1, Iterator<? extends T> iter2, Comparator<T> comp)
Returns true if the first iterator is lexically less than the second, using the given comparator to compare the elements in each iterator.
static <T> booleanlessThan(Iterator<? extends T> i1, Iterator<? extends T> i2, BinaryFunctor<T,T,Boolean> lt)
Returns true if the first iterator is lexically less than the second, using the given operator to compare the elements in each iterator.
static <T> LookAheadIterator<T>match(Iterator<? extends T> iterator, Collection<? extends T> pattern)
Finds the given pattern in the iteration using the equals method.
static <T> LookAheadIterator<T>match(Iterator<? extends T> iterator, Collection<? extends T> pattern, BinaryFunctor<T,T,Boolean> eq)
Finds the given pattern in the collection using the given functor to determine equivalence.
static <T extends Comparable> TmaximumValue(Iterator<? extends T> iterator)
Finds the maximum value in an iteration using the natural ordering of the iterator's elements.
static <T> TmaximumValue(Iterator<? extends T> iterator, Comparator<T> comp)
Finds the maximum value in an iteration using the given comparator.
static <T> TmaximumValue(Iterator<? extends T> iterator, BinaryFunctor<T,T,T> bf)
Finds the maximum value in an iteration using the given functor to compare elements.
static <T extends Comparable> TminimumValue(Iterator<? extends T> iterator)
Finds the minimum value in an iteration using the natural ordering of the iterator's elements.
static <T> TminimumValue(Iterator<? extends T> iterator, Comparator<T> comp)
Finds the minimum value in an iteration using the given comparator.
static <T> TminimumValue(Iterator<? extends T> iterator, BinaryFunctor<T,T,T> bf)
Finds the minimum value in an iteration using the given functor to compare elements.
static <T> LookAheadIterator<T>mismatch(Iterator<? extends T> iterator, Collection<? extends T> pattern)
Finds the point at which two collections differ, using NotEqualTo.
static <T> LookAheadIterator<T>mismatch(Iterator<? extends T> iterator, Collection<? extends T> pattern, BinaryFunctor<T,T,Boolean> neq)
Finds the point at which two collections differ, using the given functor
static <T> FilterIterator<T>removeAll(Iterator<? extends T> iterator, T value)
Filters an arbitrary value from an iteration using the equals() method.
static <T> FilterIterator<T>removeAll(Iterator<? extends T> iterator, T value, Equality<T> eq)
Filters an arbitrary value from an iteration using the given Equality operator.
static <T> FilterIterator<T>removeAll(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Filters values from an iteration for which the given function returns TRUE.
static <T> Iterator<T>replaceAll(Iterator<? extends T> iter, UnaryFunctor<T,Boolean> test, T value)
Tests each element in an iterator, replacing those for which the test is true with the replacement value.
static <T,R> TransformIterator<T,R>transform(Iterator<? extends T> iter, UnaryFunctor<T,R> uf)
Applies the UnaryFunctor to each element in the input, returning an iterator over the results.
static <T1,T2,R> Iterator<R>transform(Iterator<? extends T1> i1, Iterator<? extends T2> i2, BinaryFunctor<T1,T2,R> bf)
Applies the BinaryFunctor to corresponding elements of the two input iterators, and returns an iterator over the results.
static <T> UniqueIterator<T>unique(Iterator<? extends T> iterator)
Skips duplicate values in the given iteration.
static <T> UniqueIterator<T>unique(Iterator<? extends T> iterator, BinaryFunctor<T,T,Boolean> eq)
Skips duplicate values in the given iteration.

Method Detail

accumulate

public static <T> T accumulate(Iterator<T> iterator, T initial, BinaryFunctor<T,T,T> bf)
Applies the binary functor to each element in the iterator, returning the final result. Along with each element is passed the result of the previous call of the functor (or the initial value for the first call to the functor). The elements in the iteration are always passed in the 2nd postion.

Returns: the final result. If the iteration is empty, then the initial value is returned

count

public static <T> long count(Iterator<? extends T> iterator, T value)
Counts the number of occurrences of value in the iteration, using the equals() method of the value.

Returns: the number of instances found

count

public static <T> long count(Iterator<? extends T> iterator, Equality<T> eq, T value)
Counts the number of occurrences of value in the iteration, using the given equality operator.

Returns: the number of instances found

count

public static <T> long count(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Counts the items in the collection for which the given function returns TRUE.

Returns: the number of instances found

equal

public static <T extends Comparable> boolean equal(Iterator<? extends T> iterator1, Iterator<? extends T> iterator2)
Returns true if the two iterations are equal, using the Comparable interface to compare elements in the iterations.

Returns: true if the two iterations are equal

equal

public static <T> boolean equal(Iterator<? extends T> iterator1, Iterator<? extends T> iterator2, Comparator<T> comp)
Returns true if the two iterations are equal, using the given Comparator to compare elements in the iterations.

Returns: true if the two iterations are equal

equal

public static <T> boolean equal(Iterator<? extends T> iter1, Iterator<? extends T> iter2, BinaryFunctor<T,T,Boolean> eq)
Returns true if the two iterations are equal, using the given BinaryFunctor to compare elements in the iterations.

Returns: true if the two iterations are equal

find

public static <T> FindIterator<T> find(Iterator<? extends T> iterator, T value)
Finds an arbitrary value in an iteration using the equals() method.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the next instance of value in the iteration, using the equals() method of the value. If the value is not in the iteration, then the returned iterator's hasNext() will report false.

find

public static <T> FindIterator<T> find(Iterator<? extends T> iterator, T value, Equality<T> eq)
Finds an arbitrary value in an iteration using the given Equality operator.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the next instance of value in the iteration, using the given equality operator. If the value is not in the iteration, then the returned iterator's hasNext() will report false.

find

public static <T> FindIterator<T> find(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Finds a value in a collection for which the given function returns TRUE.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the next instance in the iteration for which the given function returns true. If the value is not in the iteration, then the returned iterator's hasNext() will report false.

findAdjacent

public static <T> LookAheadIterator<T> findAdjacent(Iterator<? extends T> iterator)
Finds adjacent pairs of equivalent values in an iteration using the equals() method.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first of a pair of adjacent values. If no pair of values exists in the iteration, then the returned iterator's hasNext() will report false.

findAdjacent

public static <T> LookAheadIterator<T> findAdjacent(Iterator<? extends T> iterator, BinaryFunctor<T,T,Boolean> bf)
Finds adjacent pairs of equivalent values in an iteration for which the given function returns TRUE.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first of a pair of adjacent values. If no pair of values exists in the iteration, then the returned iterator's hasNext() will report false.

findElement

public static <T> FindIterator<T> findElement(Iterator<? extends T> iterator, Collection<? extends T> desired)
Finds any value from the given collection using the collection's contains() method.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first instance of any value found in the second collection. If no such value is found in the iteration, then the returned iterator's hasNext() will report false.

findElement

public static <T> FindIterator<T> findElement(Iterator<? extends T> iter, Collection<? extends T> coll, BinaryFunctor<T,T,Boolean> eq)
Finds any value from the given collection using the given functor to determine equivalence. Each item in the iteration will be compared to every item in the second collection using the given functor, stopping when the iteration is exhausted or when any pair returns TRUE.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first instance of any value in the second collection, where equivelency is determined by the given functor. If no such value is found in the iteration, then the returned iterator's hasNext() will report false.

findRepeated

public static <T> LookAheadIterator<T> findRepeated(Iterator<? extends T> iterator, int n, T value)
Finds arbitrary length runs of a given value in an iteration using the equals() method. Runs of length zero are well-defined: every iteration begins with a run of length zero of all possible values.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first of n adjacent instances of value. If no run of values of the requested length exist in the iteration, then the returned iterator's hasNext() will report false.

findRepeated

public static <T> LookAheadIterator<T> findRepeated(Iterator<? extends T> iterator, int n, T value, Equality<T> eq)
Finds arbitrary length runs of a given value in an iteration using the given equality operator. Runs of length zero are well-defined: every iteration begins with a run of length zero of all possible values.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first of n adjacent instances of value. If no run of values of the requested length exist in the iteration, then the returned iterator's hasNext() will report false.

findRepeated

public static <T> LookAheadIterator<T> findRepeated(Iterator<? extends T> iterator, int n, UnaryFunctor<T,Boolean> eq)
Finds arbitrary length runs of a given value in an iteration for which the given function returns TRUE. Runs of length zero are well-defined: every iteration begins with a run of length zero of all possible values.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first of n adjacent instances of value. If no run of values of the requested length exist in the iteration, then the returned iterator's hasNext() will report false.

forEach

public static <T,R> UnaryFunctor<T,R> forEach(Iterator<? extends T> iterator, UnaryFunctor<T,R> fn)
Applies the given UnaryFunctor to every element in the iteration, and returns the Functor. This is useful when the Functor gathers information on each successive call.

Returns: the functor, after it has been called once for every element

lessThan

public static <T extends Comparable> boolean lessThan(Iterator<? extends T> iter1, Iterator<? extends T> iter2)
Returns true if the first iterator is lexically less than the second, using the default comparison operation to compare the elements in each iterator.

Returns: true if the first iteration is less than the second

lessThan

public static <T> boolean lessThan(Iterator<? extends T> iter1, Iterator<? extends T> iter2, Comparator<T> comp)
Returns true if the first iterator is lexically less than the second, using the given comparator to compare the elements in each iterator.

Returns: true if the first iteration is less than the second

lessThan

public static <T> boolean lessThan(Iterator<? extends T> i1, Iterator<? extends T> i2, BinaryFunctor<T,T,Boolean> lt)
Returns true if the first iterator is lexically less than the second, using the given operator to compare the elements in each iterator. The first is less than the second if it is not longer than the second and if the first corresponding element that is not equal is less.

Returns: true if the first iteration is less than the second

match

public static <T> LookAheadIterator<T> match(Iterator<? extends T> iterator, Collection<? extends T> pattern)
Finds the given pattern in the iteration using the equals method.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first element of a sequence that matches the entire contents of the collection. If no such match is found in the iteration, then the returned iterator's hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.

match

public static <T> LookAheadIterator<T> match(Iterator<? extends T> iterator, Collection<? extends T> pattern, BinaryFunctor<T,T,Boolean> eq)
Finds the given pattern in the collection using the given functor to determine equivalence.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first element of a sequence that matches the entire contents of the collection. If no such match is found in the iteration, then the returned iterator's hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.

maximumValue

public static <T extends Comparable> T maximumValue(Iterator<? extends T> iterator)
Finds the maximum value in an iteration using the natural ordering of the iterator's elements.

Returns: the maximum value found in the iteration

maximumValue

public static <T> T maximumValue(Iterator<? extends T> iterator, Comparator<T> comp)
Finds the maximum value in an iteration using the given comparator.

Returns: the maximum value found in the iteration

maximumValue

public static <T> T maximumValue(Iterator<? extends T> iterator, BinaryFunctor<T,T,T> bf)
Finds the maximum value in an iteration using the given functor to compare elements. The functor is presumed to return the lesser of its two arguments.

Returns: the maximum value found in the iteration

minimumValue

public static <T extends Comparable> T minimumValue(Iterator<? extends T> iterator)
Finds the minimum value in an iteration using the natural ordering of the iterator's elements.

Returns: the minimum value found in the iteration

minimumValue

public static <T> T minimumValue(Iterator<? extends T> iterator, Comparator<T> comp)
Finds the minimum value in an iteration using the given comparator.

Returns: the minimum value found in the iteration

minimumValue

public static <T> T minimumValue(Iterator<? extends T> iterator, BinaryFunctor<T,T,T> bf)
Finds the minimum value in an iteration using the given functor to compare elements. The functor is presumed to return the lesser of its two arguments.

Returns: the minimum value found in the iteration

mismatch

public static <T> LookAheadIterator<T> mismatch(Iterator<? extends T> iterator, Collection<? extends T> pattern)
Finds the point at which two collections differ, using NotEqualTo.

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first element in the iteration that does not equal the corresponding element in the pattern. If the pattern matches the iteration but is longer, than the returned iterator's hasNext() will report false. If the pattern is empty, then the iteration is not advanced.

mismatch

public static <T> LookAheadIterator<T> mismatch(Iterator<? extends T> iterator, Collection<? extends T> pattern, BinaryFunctor<T,T,Boolean> neq)
Finds the point at which two collections differ, using the given functor

Returns: an iterator based on the given iterator whose next() [if it hasNext()] will return the first element in the iteration for which the given function returns TRUE when given the element and the corresponding element in the pattern. If the pattern matches the iteration but is longer, than the returned iterator's hasNext() will report false. If the pattern is empty, then the iteration is not advanced.

removeAll

public static <T> FilterIterator<T> removeAll(Iterator<? extends T> iterator, T value)
Filters an arbitrary value from an iteration using the equals() method.

Returns: an iterator based on the given iterator that will return not include elements equal to the given value

removeAll

public static <T> FilterIterator<T> removeAll(Iterator<? extends T> iterator, T value, Equality<T> eq)
Filters an arbitrary value from an iteration using the given Equality operator.

Returns: an iterator based on the given iterator that will not include elements that are equal to the value using the given Equality

removeAll

public static <T> FilterIterator<T> removeAll(Iterator<? extends T> iterator, UnaryFunctor<T,Boolean> eq)
Filters values from an iteration for which the given function returns TRUE.

Returns: an iterator based on the given iterator that will not include elements that pass the given test.

replaceAll

public static <T> Iterator<T> replaceAll(Iterator<? extends T> iter, UnaryFunctor<T,Boolean> test, T value)
Tests each element in an iterator, replacing those for which the test is true with the replacement value.

transform

public static <T,R> TransformIterator<T,R> transform(Iterator<? extends T> iter, UnaryFunctor<T,R> uf)
Applies the UnaryFunctor to each element in the input, returning an iterator over the results.

Returns: an iterator based on the given iterator that will return the results obtained when passing each element of the input iteration to the given unary functor.

transform

public static <T1,T2,R> Iterator<R> transform(Iterator<? extends T1> i1, Iterator<? extends T2> i2, BinaryFunctor<T1,T2,R> bf)
Applies the BinaryFunctor to corresponding elements of the two input iterators, and returns an iterator over the results. The resulting iterator will have the same number of elements as the shorter of the two input iterations.

Returns: an iterator that will return the results obtained when passing each pair of corresponding elements of the input iterations to the given binary functor.

unique

public static <T> UniqueIterator<T> unique(Iterator<? extends T> iterator)
Skips duplicate values in the given iteration.

Returns: an iterator based on the given iterator that will not return the same element twice in succession

unique

public static <T> UniqueIterator<T> unique(Iterator<? extends T> iterator, BinaryFunctor<T,T,Boolean> eq)
Skips duplicate values in the given iteration.

Returns: an iterator based on the given iterator that will not return the same element twice in succession, using the given functor to compare elements