org.zedlib
Class HashRel

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractSet
          java.util.HashSet
              org.zedlib.HashSet
                  org.zedlib.HashRel

All Implemented Interfaces:

Cloneable, Collection, Relation, Serializable, Set, Set

Direct Known Subclasses:

HashFun

public class HashRel

extends HashSet

implements Relation

A relation is a set of relationships between two objects. Each (x,y) is termed a binary relation (or maplet) relating some x of set X to some y of set Y, contained within the relation X ↔ Y.

Note that this is not equivalent to a java.util.Map which enforces a unique set of keys (properly called a function). In other words, a relation allows x of X to appear multiple times so long as each x relates to a different y of Y.

If X and Y are sets, then X ↔ Y is the set of binary relations between X and Y. Each such relation is a subset of X x Y. A 'maplet' from x to y is another way of expressing the ordered pair (x, y).

For example, the following are valid binary relations (maplets, ordered pairs) within a Relation R:

(tom, mary)
(fred, jane)
(tom, jane)

Author:

Brad Long

See Also:

Serialized Form

Constructor Summary

HashRel()

HashRel(Collection c)
Constructs a relation containing all elements in the supplied collection of maplets.

HashRel(Collection x, Collection y)
Constructs a relation between two collections.

HashRel(Map m)
Constructs a relation from a given java.util.Map.

HashRel(Relation r)
Constructs a relation from the given relation R.

Method Summary

boolean	add(Maplet m) Adds a maplet to this relation.
boolean	add(Object o) Overrides add in Set to ensure only maplets are added.
boolean	add(Object x, Object y) Adds a pair of objects to this relation as a maplet.
boolean	addAll(Collection c) Adds all entries in a java.util.Collection to this relation.
boolean	addAll(Map m) Adds all entries in a java.util.Map to this relation.
protected void	buildRelation(Collection x, Collection y)
Relation	composition(Relation r) Returns the relational composition of this relation and another given relation, thus if (x,y) exists in this relation Q and (y,z) exists in R then (x,z) appears in the composed relation.
Set	domain() Returns a set containing the unique objects in X of the relation X ↔ Y.
Relation	domainAntiRestriction(Set s) Returns a relation being those maplets in this relation whose x in (x,y) do not appear in the given set.
Relation	domainRestriction(Set s) Returns a relation being only those maplets in this relation whose x in (x,y) appear in the given set.
protected Set	getInstance()
protected Set	getInstance(Set s)
Set	image(Set s) Returns a set containing the range of a domain restriction on this relation, that is, returns a set of all y of Y for which x of X is related in X ↔ Y.
Relation	inverse() Returns the relational inverse of this relation, thus each maplet (x,y) is inverted to (y,x).
boolean	isFunction()
boolean	isInjection()
boolean	isReflexive()
Relation	override(Relation r) Returns a relation being this relation overridden with a given relation.
Set	range() Returns a set containing the unique objects in Y of the relation X ↔ Y.
Relation	rangeAntiRestriction(Set t) Returns a relation containing those maplets in this relation whose y in (x,y) do not appear in the given set.
Relation	rangeRestriction(Set t) Returns a relation containing only those maplets of this relation whose y in (x,y) appear in the given set.
String	toString()
Relation	transitiveClosure() Returns the transitive closure of this relation.

Methods inherited from class org.zedlib.HashSet

cartesianProduct, difference, difference, identity, intersection, intersection, isProperSubsetOf, isSubsetOf, isSupersetOf, union, union

Methods inherited from class java.util.HashSet

clear, clone, contains, isEmpty, iterator, remove, size

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

containsAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.zedlib.Set

cartesianProduct, difference, identity, intersection, isSubsetOf, isSupersetOf, union

Methods inherited from interface java.util.Set

clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Constructor Detail

HashRel

public HashRel()

HashRel

public HashRel(Collection x,
               Collection y)

Constructs a relation between two collections. Each maplet is created by traversing the iterators of each collection and associating each x of X with y of Y.

Parameters:

x - any collection

y - any collection

Throws:

IllegalArgumentException - if the collections are not the same size

HashRel

public HashRel(Map m)

Constructs a relation from a given java.util.Map.

HashRel

public HashRel(Collection c)

Constructs a relation containing all elements in the supplied collection of maplets.

Throws:

ClassCastException - if the collection does not contain maplets

HashRel

public HashRel(Relation r)

Constructs a relation from the given relation R.

Method Detail

buildRelation

protected void buildRelation(Collection x,
                             Collection y)

getInstance

protected Set getInstance()

Overrides:

getInstance in class HashSet

getInstance

protected Set getInstance(Set s)

Overrides:

getInstance in class HashSet

domain

public Set domain()

Returns a set containing the unique objects in X of the relation X ↔ Y.

If R is a binary relation between X and Y, then the domain of R is the set of all members of X which are related to at least one member of Y by R.

Specified by:

domain in interface Relation

Returns:

the set of unique objects contained within X

range

public Set range()

Returns a set containing the unique objects in Y of the relation X ↔ Y.

If R is a binary relation between X and Y, then the range of R is the set of all members of Y to which at least one member of X is related by R.

Specified by:

range in interface Relation

add

public boolean add(Object o)

Overrides add in Set to ensure only maplets are added.

Specified by:

add in interface Set

Returns:

true if the object was added to this relation

Throws:

ClassCastException - if the object is not a Maplet

add

public boolean add(Maplet m)

Adds a maplet to this relation.

Specified by:

add in interface Relation

Parameters:

m - any maplet

Returns:

true if the given maplet was added to this relation

See Also:

Set.add(Object o)

add

public boolean add(Object x,
                   Object y)

Adds a pair of objects to this relation as a maplet.

Specified by:

add in interface Relation

Parameters:

x - any object

y - any object

Returns:

true if the objects were added to this relation

addAll

public boolean addAll(Collection c)

Adds all entries in a java.util.Collection to this relation. Overrides addAll in Set to ensure only Maplets are added.

Specified by:

addAll in interface Set

Parameters:

c - any collection

Returns:

true if any objects of the collection were added to this relation

Throws:

ClassCastException - if any element is not a maplet

addAll

public boolean addAll(Map m)

Adds all entries in a java.util.Map to this relation.

Specified by:

addAll in interface Relation

Parameters:

m - any java.util.Map

Returns:

true if any objects of the map were added to this relation

See Also:

Set.addAll(Collection c)

domainRestriction

public Relation domainRestriction(Set s)

Returns a relation being only those maplets in this relation whose x in (x,y) appear in the given set.

The domain restriction R.domainRestriction(S) of this relation R to a set S, relates x to y if and only if R relates x to y and x is a member of S.

Specified by:

domainRestriction in interface Relation

Parameters:

s - the set of objects with which to restrict the domain of this relation

Returns:

a relation being this relation restricted to elemnets in the domain contained in s

domainAntiRestriction

public Relation domainAntiRestriction(Set s)

Returns a relation being those maplets in this relation whose x in (x,y) do not appear in the given set.

This operation is the complemented counterpart of the domain restriction operation. An object x is related to an object y by the relation R.domainAntiRestrict(S) if and only if x is related to y by R and x is not a member of S.

Specified by:

domainAntiRestriction in interface Relation

Parameters:

s - the set of objects with which to anti-restrict this relation. By definition, these objects will not appear in the domain of the restricted relation.

Returns:

a relation containing all maplets in this relation that are not in s

rangeRestriction

public Relation rangeRestriction(Set t)

Returns a relation containing only those maplets of this relation whose y in (x,y) appear in the given set.

The range restriction R.rangeRestrict(T) of R to a set T relates x to y if and only if R relates x to y and y is a member of T.

Specified by:

rangeRestriction in interface Relation

Parameters:

t - the set of objects with which to restrict the range of this relation

Returns:

a relation consisting of this relation restricted to maplets with y in (x,y) in t

rangeAntiRestriction

public Relation rangeAntiRestriction(Set t)

Returns a relation containing those maplets in this relation whose y in (x,y) do not appear in the given set.

This operation is the complemented counterpart of the domain restriction operation. An object x is related to an object y by the relation R.rangeAntiRestrict(T) if and only if x is related to y by R and y is not a member of T.

Specified by:

rangeAntiRestriction in interface Relation

Parameters:

t - the set of objects with which to anti-restrict this relation. By definition, these objects will not appear in the range of the restricted relation.

Returns:

a relation containing maplets in this relation whose y in (x,y) do not appear in t

inverse

public Relation inverse()

Returns the relational inverse of this relation, thus each maplet (x,y) is inverted to (y,x).

An object y is related to an object x by the relational inverse R∼ of R if and only if x is related to y by R.

Specified by:

inverse in interface Relation

Returns:

a relation being the inverse of this relation

composition

public Relation composition(Relation r)

Returns the relational composition of this relation and another given relation, thus if (x,y) exists in this relation Q and (y,z) exists in R then (x,z) appears in the composed relation.

The composition Q.compose(R) of two relations Q: X ↔ Y and R: Y ↔ Z relates a member x of X to a member z of Z if and only if there is at least one element y of Y to which x is related by Q and which is itself related to z by R.

Specified by:

composition in interface Relation

Parameters:

r - the relation R with which to perform the composition

Returns:

a relation composed of this relation with r

override

public Relation override(Relation r)

Returns a relation being this relation overridden with a given relation. The relation Q.override(R) relates everything in the domain of R to the same objects as R does, and everything else in the domain of Q to the same objects as Q does.

Specified by:

override in interface Relation

Parameters:

r - the relation to override this relation

Returns:

a relation being the composition of this relation with r

transitiveClosure

public Relation transitiveClosure()

Returns the transitive closure of this relation.

If R is a relation from a set X to itself, R.transitiveClosure(), or R+, is the strongest or smallest relation containing R which is transitive.

Example:

if R = { (a,b), (b,c), (a,e), (c,d) }
then R+ = { (a,b), (b,c), (a,e), (c,d), (a,c), (a,d), (b,d) }

If a relation Relation.transitiveClosure(r).intersect(Relation.identity(r)) is not empty, then the transitive closure contains one or more cycles.

Specified by:

transitiveClosure in interface Relation

Returns:

a relation being the transitive closure of this relation

image

public Set image(Set s)

Returns a set containing the range of a domain restriction on this relation, that is, returns a set of all y of Y for which x of X is related in X ↔ Y. The relational image R.image(S) of a set S through a relation R is the set of all objects y to which R relates some member x of S.

The operation does not modify this relation.

Specified by:

image in interface Relation

Returns:

the range of a relation formed by restricting the domain of this relation to the given set

isFunction

public boolean isFunction()

Specified by:

isFunction in interface Relation

Returns:

true if elements in the domain of this relation are unique

isInjection

public boolean isInjection()

Specified by:

isInjection in interface Relation

Returns:

true if elements in the domain of this relation are unique and none of them map to the same object.

isReflexive

public boolean isReflexive()

Specified by:

isReflexive in interface Relation

Returns:

true if all elements in the domain of this relation are at least related to themselves in the range of this relation.

toString

public String toString()

Returns:

a String representation of this relation