orbital.util
Class Setops

java.lang.Object
  orbital.util.Setops

public final class Setops
extends java.lang.Object

Contains utility methods for common set operations and more general collection operations.

The selection methods (select(Function, Collection, Predicate, Comparator, boolean)) encapsulate a generalization of queries over Collections. These queries are build just like data queries over tables with SQL. In a selection query, a Collection is filtered to obtain the desired subset of data which matches the criteria, with the order being induced by a Comparator.

With its highly flexible bulk-style data-processing operations, Functionals is a worthwhile and extremely powerful supplement to Setops.

Author:

André Platzer

See Also:

Utility, Selectors, Collections, Functionals, Structured Query Language (SQL)

Stereotype:

Utilities

Field Summary

static java.util.Iterator	EMPTY_ITERATOR An iterator over the empty collection.
static java.util.Iterator	EMPTY_LIST_ITERATOR A list iterator over the empty list.
static BinaryFunction	intersection intersection of two collections.
static Function	intersectionFold n-ary intersection of a list of collections.
static BinaryFunction	union union of two collections.
static Function	unionFold n-ary union of a list of collections.

Method Summary

static boolean	all(java.util.Collection a, java.util.Collection b, BinaryPredicate found) Checks whether all corresponding pairs of objects in two collection satisfy the specified predicate.
static boolean	all(java.util.Collection coll, Predicate found) Checks whether all objects in a collection satisfy the specified predicate.
static boolean	all(java.util.Iterator i, java.util.Iterator j, BinaryPredicate found)
static boolean	all(java.util.Iterator i, Predicate found)
static java.lang.Object	any(java.util.Collection coll) Get any object of a collection.
static java.lang.Object	argmax(java.util.Iterator choices, Function f) Get the maximum argument.
static java.lang.Object	argmin(java.util.Iterator choices, Function f) Get the minimum argument.
static java.util.List	asList(java.util.Iterator it) Returns a list filled with the elements in the iterator.
static java.util.Map	asMap(java.lang.Object[][] entries) Converts an array of key and values to a map.
static java.util.Set	asSet(java.util.Iterator it) Returns a set filled with the elements in the iterator.
static java.util.Collection	complement(java.util.Collection universal, java.util.Collection a) Returns the complement of a collection in a universal set.
static java.util.Set	complement(java.util.Set universal, java.util.Set a)
static java.util.SortedSet	complement(java.util.SortedSet universal, java.util.SortedSet a)
static void	copy(java.util.ListIterator dest, java.util.Iterator src) Copies all of the elements from one list-iterator into another.
static int	count(java.util.Collection coll, Predicate cond) Counts the number of objects in a collection that satisfy the specified predicate.
static int	count(java.util.Iterator i, Predicate cond)
static Function	createSelection(Function what, Predicate where, java.util.Comparator orderBy, boolean asc) Creates a sophisticated selection filter.
static Function	createSelection(Predicate where)
static java.util.Collection	cross(java.util.Collection a, java.util.Collection b) Returns the cross product (or cartesian product) of two collections. a × b = {(x,y) ¦ x∈a ∧ y∈b}
static java.util.Iterator	cross(java.util.Iterator a, java.util.Iterator b)
static java.util.Collection	cross(java.util.List a) Returns the n-ary cross product (or cartesian product) of n collections. ×i=1,...,n ai = ∏i=1,...,n ai = {(xi)i=1,...,n ¦ ∀i=1,...,n xi∈ai}
static java.util.Collection	difference(java.util.Collection a, java.util.Collection b) Returns the difference of one collection to another.
static java.util.Set	difference(java.util.Set a, java.util.Set b)
static java.util.SortedSet	difference(java.util.SortedSet a, java.util.SortedSet b)
static java.lang.Object	epsilon(java.util.Collection coll, Predicate found) Return any element of a collection that satisfies the specified predicate.
static java.lang.Object	find(java.util.Collection coll, Predicate found) Return the first object in a collection that satisfies the specified predicate.
static java.lang.Object	find(java.util.Iterator i, Predicate found)
static boolean	hasDuplicates(java.util.Iterator i) Check whether the given iterator produces duplicate entries.
static void	insert(java.util.List l, java.lang.Object object) insert object into l such that l is still sorted.
static java.util.Collection	intersection(java.util.Collection a, java.util.Collection b) Returns the intersection of two collections.
static java.util.Set	intersection(java.util.Set a, java.util.Set b)
static java.util.SortedSet	intersection(java.util.SortedSet a, java.util.SortedSet b)
static java.util.List	merge(java.util.Iterator x, java.util.Iterator y, java.util.Comparator comp) Merge two iterator-views according to the order induced by a comparator.
static java.util.List	merge(java.util.List x, java.util.List y, java.util.Comparator comp) Merge two collections according to the order induced by a comparator.
static java.util.Collection	newCollectionLike(java.util.Collection c) Get a new instance of an empty collection of the same type as the one specified.
static java.util.Set	powerset(java.util.Set s) Returns the powerset of a set, i.e.
static java.util.Collection	select(Function what, java.util.Collection from)
static java.util.Collection	select(Function what, java.util.Collection from, java.util.Collection wherePredicates)
static java.util.Collection	select(Function what, java.util.Collection from, Predicate where)
static java.util.Collection	select(Function what, java.util.Collection from, Predicate where, java.util.Comparator orderBy, boolean asc) Select filter operation.
static boolean	some(java.util.Collection a, java.util.Collection b, BinaryPredicate found)
static boolean	some(java.util.Collection coll, Predicate found) Checks whether some objects (at least one) in a collection satisfy the specified predicate.
static boolean	some(java.util.Iterator i, java.util.Iterator j, BinaryPredicate found)
static boolean	some(java.util.Iterator i, Predicate found)
static java.util.Collection	symmetricDifference(java.util.Collection a, java.util.Collection b) Returns the symmetric difference of two collections. a Δ b := (a∖b) ∪ (b∖a)
static java.util.Set	symmetricDifference(java.util.Set a, java.util.Set b)
static java.util.SortedSet	symmetricDifference(java.util.SortedSet a, java.util.SortedSet b)
static java.util.Collection	union(java.util.Collection a, java.util.Collection b) Returns the union of two collections.
static java.util.Iterator	union(java.util.Iterator a, java.util.Iterator b)
static java.util.Set	union(java.util.Set a, java.util.Set b)
static java.util.SortedSet	union(java.util.SortedSet a, java.util.SortedSet b)
static java.util.Collection	unmodifiableCollectionLike(java.util.Collection c) Returns an unmodifiable view of the same type as the collection specified.
static java.util.Iterator	unmodifiableIterator(java.util.Iterator i) Returns an unmodifiable view of the specified iterator.
static java.util.ListIterator	unmodifiableListIterator(java.util.ListIterator i)

Methods inherited from class java.lang.Object

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

Field Detail

EMPTY_ITERATOR

public static final java.util.Iterator EMPTY_ITERATOR

An iterator over the empty collection.

EMPTY_LIST_ITERATOR

public static final java.util.Iterator EMPTY_LIST_ITERATOR

A list iterator over the empty list.

union

public static final BinaryFunction union

union of two collections.

unionFold

public static final Function unionFold

n-ary union of a list of collections. Returns the union of all collections contained in the argument list.

intersection

public static final BinaryFunction intersection

intersection of two collections.

intersectionFold

public static final Function intersectionFold

n-ary intersection of a list of collections. Returns the intersection of all collections contained in the argument list.

Method Detail

find

public static java.lang.Object find(java.util.Collection coll,
                                    Predicate found)

Return the first object in a collection that satisfies the specified predicate.

Returns:

the first object in a collection that satisfies the specified predicate, or null if no such object exists.

find

public static java.lang.Object find(java.util.Iterator i,
                                    Predicate found)

epsilon

public static java.lang.Object epsilon(java.util.Collection coll,
                                       Predicate found)

Return any element of a collection that satisfies the specified predicate. This method can be used to express don't care nondeterminisms in algorithms.

Returns:

any object in the collection that satisfies the specified predicate, or null if no such object exists.

See Also:

any(Collection)

count

public static int count(java.util.Collection coll,
                        Predicate cond)

Counts the number of objects in a collection that satisfy the specified predicate.

count

public static int count(java.util.Iterator i,
                        Predicate cond)

all

public static boolean all(java.util.Collection coll,
                          Predicate found)

Checks whether all objects in a collection satisfy the specified predicate.

Returns:

true if all objects satisfy the predicate, false if one does not. Returns an optimized version of Functionals.map(and, Functionals.map(Functionals.asFunction(found), i)).

See Also:

Internal Iterator, Functionals

all

public static boolean all(java.util.Iterator i,
                          Predicate found)

all

public static boolean all(java.util.Collection a,
                          java.util.Collection b,
                          BinaryPredicate found)

Checks whether all corresponding pairs of objects in two collection satisfy the specified predicate.

Returns:

true if all objects satisfy the predicate, false if one does not. Returns an optimized version of Functionals.map(and, Functionals.map(Functionals.asFunction(found), i), j).

See Also:

Internal Iterator, Functionals

all

public static boolean all(java.util.Iterator i,
                          java.util.Iterator j,
                          BinaryPredicate found)

some

public static boolean some(java.util.Collection coll,
                           Predicate found)

Checks whether some objects (at least one) in a collection satisfy the specified predicate.

Returns:

true if at least one objects satisfies the predicate, false if none does. Returns an optimized version of return Functionals.map(or, Functionals.map(Functionals.asFunction(found), i)).

See Also:

Internal Iterator, Functionals

some

public static boolean some(java.util.Iterator i,
                           Predicate found)

some

public static boolean some(java.util.Collection a,
                           java.util.Collection b,
                           BinaryPredicate found)

some

public static boolean some(java.util.Iterator i,
                           java.util.Iterator j,
                           BinaryPredicate found)

argmin

public static final java.lang.Object argmin(java.util.Iterator choices,
                                            Function f)

Get the minimum argument.

Parameters:

choices - the available choices M.

f - the evaluation function f:M→R.

Returns:

argmin_a∈M f(a) with minimum f-value in choices.

Throws:

java.util.NoSuchElementException - if !choices.hasNext()

See Also:

Operations.inf, Collections.min(Collection,Comparator), Functionals.foldLeft(BinaryFunction, Object,Object[]), EvaluativeAlgorithm.EvaluationComparator

Preconditions:

choices.hasNext()

Postconditions:

RES = argmin_a'∈M f(a'), i.e. ∀a'∈M f(RES)≤f(a')

argmax

public static final java.lang.Object argmax(java.util.Iterator choices,
                                            Function f)

Get the maximum argument.

Parameters:

choices - the available choices M.

f - the evaluation function f:M→R.

Returns:

argmax_a∈M f(a) with maximum f-value in choices.

Throws:

java.util.NoSuchElementException - if !choices.hasNext()

See Also:

Operations.sup, Collections.max(Collection,Comparator), Functionals.foldLeft(BinaryFunction, Object, Object[]), EvaluativeAlgorithm.EvaluationComparator

Preconditions:

choices.hasNext()

Postconditions:

RES = argmax_a'∈M f(a'), i.e. ∀a'∈M f(RES)≥f(a')

union

public static java.util.Collection union(java.util.Collection a,
                                         java.util.Collection b)

Returns the union of two collections.

Returns:

a ∪ b.

Postconditions:

RES has same type as a

union

public static java.util.Set union(java.util.Set a,
                                  java.util.Set b)

union

public static java.util.SortedSet union(java.util.SortedSet a,
                                        java.util.SortedSet b)

union

public static java.util.Iterator union(java.util.Iterator a,
                                       java.util.Iterator b)

intersection

public static java.util.Collection intersection(java.util.Collection a,
                                                java.util.Collection b)

Returns the intersection of two collections.

Returns:

a ∩ b.

Postconditions:

RES has same type as a

intersection

public static java.util.Set intersection(java.util.Set a,
                                         java.util.Set b)

intersection

public static java.util.SortedSet intersection(java.util.SortedSet a,
                                               java.util.SortedSet b)

complement

public static java.util.Collection complement(java.util.Collection universal,
                                              java.util.Collection a)

Returns the complement of a collection in a universal set. Is the same as the difference universal ∖ a.

Returns:

a^∁, a collection of all elements that are in universal, but not in a.

Postconditions:

RES has same type as universal

complement

public static java.util.Set complement(java.util.Set universal,
                                       java.util.Set a)

complement

public static java.util.SortedSet complement(java.util.SortedSet universal,
                                             java.util.SortedSet a)

difference

public static final java.util.Collection difference(java.util.Collection a,
                                                    java.util.Collection b)

Returns the difference of one collection to another.

Returns:

a ∖ b = complement(a,b) = b^∁ relative to a.

Postconditions:

RES has same type as a

difference

public static final java.util.Set difference(java.util.Set a,
                                             java.util.Set b)

difference

public static final java.util.SortedSet difference(java.util.SortedSet a,
                                                   java.util.SortedSet b)

symmetricDifference

public static java.util.Collection symmetricDifference(java.util.Collection a,
                                                       java.util.Collection b)

Returns the symmetric difference of two collections.
a Δ b := (a∖b) ∪ (b∖a)

Returns:

a collection of all elements which are unique to either of the collections.

Postconditions:

RES has same type as a

symmetricDifference

public static java.util.Set symmetricDifference(java.util.Set a,
                                                java.util.Set b)

symmetricDifference

public static java.util.SortedSet symmetricDifference(java.util.SortedSet a,
                                                      java.util.SortedSet b)

cross

public static java.util.Collection cross(java.util.Collection a,
                                         java.util.Collection b)

Returns the cross product (or cartesian product) of two collections.
a × b = {(x,y) ¦ x∈a ∧ y∈b}

Returns:

a collection of all tupels in a × b as Pair objects.

See Also:

#outer(BinaryFunction, Collection, Collection)

cross

public static java.util.Iterator cross(java.util.Iterator a,
                                       java.util.Iterator b)

cross

public static java.util.Collection cross(java.util.List a)

Returns the n-ary cross product (or cartesian product) of n collections.
×_i=1,...,n a_i = ∏_i=1,...,n a_i = {(x_i)_i=1,...,n ¦ ∀i=1,...,n x_i∈a_i}

Implemented as an iterative unrolling of a recursion.

Parameters:

a - the list ⟨a₁,...,a_n⟩ of collections a_i to choose from.

Returns:

a collection of all n-tupels in ×_i=1,...,n a_i as List objects.

See Also:

#outer(BinaryFunction, Collection, Collection), "Axiom of Choice (for infinite case)"

powerset

public static java.util.Set powerset(java.util.Set s)

Returns the powerset of a set, i.e. the set of all subsets.
℘(S) := {E ⊆ S}

any

public static java.lang.Object any(java.util.Collection coll)

Get any object of a collection. This method can be used to express don't care nondeterminisms in algorithms. So if an alogrithm does not depend upon the exact order in which elements are returned, you can specifiy this by using:

 // expresses don't care nondeterminism
 Object o = Setops.any(someCollection);
 

See Also:

epsilon(Collection,Predicate)

asList

public static java.util.List asList(java.util.Iterator it)

Returns a list filled with the elements in the iterator.

This method works somewhat like java.util.Arrays.asList(Object[]) but is not backed by the iterator.

See Also:

Arrays.asList(Object[])

asSet

public static java.util.Set asSet(java.util.Iterator it)

Returns a set filled with the elements in the iterator.

Except for set notation, this method works somewhat like java.util.Arrays.asList(Object[]) but is not backed by the iterator.

See Also:

Arrays.asList(Object[])

newCollectionLike

public static java.util.Collection newCollectionLike(java.util.Collection c)

Get a new instance of an empty collection of the same type as the one specified.

If no such collection could be instantiated, a similar collection is used.

unmodifiableIterator

public static java.util.Iterator unmodifiableIterator(java.util.Iterator i)

Returns an unmodifiable view of the specified iterator.

Query operations on the returned iterator "read through" to the specified iterator, and attempts to modify the returned iterator result in an UnsupportedOperationException.

unmodifiableListIterator

public static java.util.ListIterator unmodifiableListIterator(java.util.ListIterator i)

unmodifiableCollectionLike

public static java.util.Collection unmodifiableCollectionLike(java.util.Collection c)

Returns an unmodifiable view of the same type as the collection specified.

See Also:

newCollectionLike(Collection), Collections.unmodifiableCollection(Collection), Collections.unmodifiableList(List), Collections.unmodifiableSet(Set), Collections.unmodifiableSortedSet(SortedSet)

copy

public static void copy(java.util.ListIterator dest,
                        java.util.Iterator src)

Copies all of the elements from one list-iterator into another. After the operation, the index of each copied element in the destination list-iterator will be identical to its index in the source list-iterator. The destination list-iterator must be at least as long as the source list-iterator. If it is longer, the remaining elements in the destination list-iterator are unaffected. This method runs in linear time.

Of course the list-iterators will be at different positions when this method finishes.

Parameters:

dest - The destination list-iterator.

src - The source list-iterator.

Throws:

java.lang.IndexOutOfBoundsException - if the destination list-iterator is too small to contain the entire source List.

java.lang.UnsupportedOperationException - if the destination list-iterator does not support the set operation.

See Also:

Collections.copy(List,List)

merge

public static java.util.List merge(java.util.List x,
                                   java.util.List y,
                                   java.util.Comparator comp)

Merge two collections according to the order induced by a comparator.

Preconditions:

isSorted(x) && isSorted(y)

Postconditions:

isSorted(RES) && RES = a ∪ b

merge

public static java.util.List merge(java.util.Iterator x,
                                   java.util.Iterator y,
                                   java.util.Comparator comp)

Merge two iterator-views according to the order induced by a comparator.

Preconditions:

isSorted(x) && isSorted(y)

Postconditions:

isSorted(RES) && RES = a ∪ b

insert

public static final void insert(java.util.List l,
                                java.lang.Object object)

insert object into l such that l is still sorted. Special case of merge.

Preconditions:

sorted(l)

Postconditions:

sorted(l) ∧ object∈l

asMap

public static final java.util.Map asMap(java.lang.Object[][] entries)

Converts an array of key and values to a map.

Parameters:

entries - Contains keys and their values. Stored as an array of length-2 arrays with entries[i][0] being the key String, and entries[i][1] being the value Object.

See Also:

Arrays.asList(Object[])

createSelection

public static final Function createSelection(Function what,
                                             Predicate where,
                                             java.util.Comparator orderBy,
                                             boolean asc)

Creates a sophisticated selection filter.

When applied upon a collection of objects the filter will perform an operation like ResultSet: SELECT whatFilter FROM ObjectCollection WHERE Predicate ORDER BY Comparator ASC|DESC.

This is a (minor) generalization of )

filter p	=	(|∅,f|)
Where
f a as	=	[a|as]	⇐ p(a)
f a as	=	as	⇐ ¬p(a)

Parameters:

what - states what data in the collection is requested. All if null. See Also Filters.

where - states what predicate is checked as condition for selecting data elements. No condition if null.

orderBy - states how to sort every two data elements. No sorting if null.

asc - whether to use ascending order, or descending. If false, orderBy comparator will be used reverse.

Returns:

a filter that selects the specified data from the source of data it is applied upon. It will apply on arguments of type Collection,Iterator.

See Also:

"FacadeFactory", Filters, Functionals.Catamorphism, orbital.logic.functor.Functionals#filter(Predicate,Iterator)

createSelection

public static final Function createSelection(Predicate where)

select

public static final java.util.Collection select(Function what,
                                                java.util.Collection from,
                                                Predicate where,
                                                java.util.Comparator orderBy,
                                                boolean asc)

Select filter operation.

ResultSet: SELECT whatFilter FROM ObjectCollection WHERE Predicate ORDER BY Comparator ASC|DESC.

Parameters:

what - states what data in the collection is requested. All if null. See Also Filters.

from - sets the source of data.

where - states what predicate is checked as condition for selecting data elements. None if null.

orderBy - states how to sort every two data elements. No sorting if null.

asc - whether to use ascending order, or descending. If false, orderBy comparator will be used reverse.

See Also:

Facade Pattern, Filters, createSelection(Function,Predicate,Comparator,boolean)

select

public static final java.util.Collection select(Function what,
                                                java.util.Collection from,
                                                Predicate where)

select

public static final java.util.Collection select(Function what,
                                                java.util.Collection from)

select

public static final java.util.Collection select(Function what,
                                                java.util.Collection from,
                                                java.util.Collection wherePredicates)

hasDuplicates

public static boolean hasDuplicates(java.util.Iterator i)

Check whether the given iterator produces duplicate entries.