jpaul.DataStructs
Class Relation<K,V>

java.lang.Object
  jpaul.DataStructs.Relation<K,V>

All Implemented Interfaces:

java.lang.Cloneable

Direct Known Subclasses:

MapSetRelation

public abstract class Relation<K,V>
extends java.lang.Object
implements java.lang.Cloneable

Relation is a binary relation, accepting one to many and many to one mappings.

It is similar to net.cscott.jutil.MultiMap. One difference: Relation does not implement the Map interface. I have always found this very confusing; e.g., MultiMap.get(v) returns an arbitrary value from the collection to which the multimap maps the value v.

Version:

$Id: Relation.java,v 1.13 2005/12/09 03:36:53 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

Nested Class Summary

static interface

Relation.EntryVisitor<Key,Value> Relation.EntryVisitor is a wrapper for a function that is called on a relation entry of the form <key,value>.

Constructor Summary

Relation()

Method Summary

protected abstract java.util.Set<V>	_getValues(K key) Method used by the internal implementation of the Relation or its subclasses.
abstract boolean	add(K key, V value) Adds the pair <key, value> to the relation.
abstract boolean	addAll(K key, java.util.Collection<V> values) Adds a relation from key to each element of the set values.
java.lang.Object	clone()
boolean	contains(K key, V value) Checks the existence of the relation <key,value>.
boolean	containsAll(K key, java.util.Collection<V> values) Checks the existence of the relation between key and every element from values.
abstract boolean	containsKey(K key) Checks the existence of the key key in this relation.
abstract boolean	equals(java.lang.Object o) Checks the equality of two relations
void	forAllEntries(Relation.EntryVisitor<K,V> visitor) Visits all the entries <key,value> of this relation and calls visitor.visit on each of them.
java.util.Set<V>	getValues(K key) Returns the image of key through this relation.
abstract boolean	isEmpty() Tests if this relation is empty or not.
abstract java.util.Set<K>	keys() Returns an IMMUTABLE view of all the keys appearing in this relation.
abstract boolean	remove(K key, V value) Removes the relation between key and value.
abstract boolean	removeAll(K key, java.util.Collection<V> values) Removes the relation between key and any element from values.
abstract boolean	removeKey(K key) Removes all the relations attached to key.
abstract boolean	removeKeys(Predicate<K> predicate) Removes all the keys that satisfy predicate.check().
abstract boolean	removeValues(Predicate<V> predicate) Removes all the values that satisfy predicate.check().
Relation<V,K>	revert(Relation<V,K> result) Revert this relation and store the result into the relation result.
int	size() Returns the number of <key,value> pairs in this relation.
java.lang.String	toString() Pretty-print function for debug.
abstract boolean	union(Relation<K,V> rel) Combines this relation with relation rel.
static <K,V> Relation<K,V>	unmodifiableRelation(Relation<K,V> rel)
abstract java.lang.Iterable<V>	values() Returns an IMMUTABLE view of all the values appearing in this relation.

Methods inherited from class java.lang.Object

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

Constructor Detail

Relation

public Relation()

Method Detail

add

public abstract boolean add(K key,
                            V value)

Adds the pair <key, value> to the relation. Returns true if the new relation is bigger.

addAll

public abstract boolean addAll(K key,
                               java.util.Collection<V> values)

Adds a relation from key to each element of the set values. values should not contain duplicated elements. Returns true if the new relation is bigger.

remove

public abstract boolean remove(K key,
                               V value)

Removes the relation between key and value.

Returns:

true iff the relation changed

removeAll

public abstract boolean removeAll(K key,
                                  java.util.Collection<V> values)

Removes the relation between key and any element from values.

Returns:

true iff the relation changed

removeKey

public abstract boolean removeKey(K key)

Removes all the relations attached to key.

Returns:

true iff the relation changed

removeKeys

public abstract boolean removeKeys(Predicate<K> predicate)

Removes all the keys that satisfy predicate.check().

Returns:

true iff the relation changed

removeValues

public abstract boolean removeValues(Predicate<V> predicate)

Removes all the values that satisfy predicate.check().

Returns:

true iff the relation changed

contains

public boolean contains(K key,
                        V value)

Checks the existence of the relation <key,value>.

containsAll

public boolean containsAll(K key,
                           java.util.Collection<V> values)

Checks the existence of the relation between key and every element from values.

containsKey

public abstract boolean containsKey(K key)

Checks the existence of the key key in this relation.

isEmpty

public abstract boolean isEmpty()

Tests if this relation is empty or not.

getValues

public final java.util.Set<V> getValues(K key)

Returns the image of key through this relation. The returned collection IS IMMUTABLE. Returns Collections.emptySet() if no value is attached to key.

_getValues

protected abstract java.util.Set<V> _getValues(K key)

Method used by the internal implementation of the Relation or its subclasses. Similar to the user-level getValues(K) but the returned set IS MUTABLE. Mutating this set affects the set of values that are associated with a given key; therefore, this method cannot be used by Relation clients directly.

keys

public abstract java.util.Set<K> keys()

Returns an IMMUTABLE view of all the keys appearing in this relation. If you want to delete a key, then use removeKey(K).

values

public abstract java.lang.Iterable<V> values()

Returns an IMMUTABLE view of all the values appearing in this relation. The view may contain the same value twice, if it is associated with two distinct keys.

union

public abstract boolean union(Relation<K,V> rel)

Combines this relation with relation rel. A null parameter is considered to be an empty relation.

Returns:

true iff this relation has changed.

equals

public abstract boolean equals(java.lang.Object o)

Checks the equality of two relations

Overrides:

equals in class java.lang.Object

forAllEntries

public void forAllEntries(Relation.EntryVisitor<K,V> visitor)

Visits all the entries <key,value> of this relation and calls visitor.visit on each of them. This traversal of the relation entries can be stopped at any point by throwing an InterruptTraversalException from the visitor; the exception is caught internally by the implementation of this method.

revert

public Relation<V,K> revert(Relation<V,K> result)

Revert this relation and store the result into the relation result. <a,b> appears in the reverse relation iff <b,a> appears in this relation. Returns the new relation (ie, result).

size

public int size()

Returns the number of <key,value> pairs in this relation. Linear in the size of the relation. This may be also implemented in O(1) by incrementally updating a size field, but that may complicate the code in the presence of subclassing, etc. Will think about it if it becomes a problem.

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Pretty-print function for debug. rel1.equals(rel2) <==> rel1.toString().equals(rel2.toString())

Overrides:

toString in class java.lang.Object

unmodifiableRelation

public static <K,V> Relation<K,V> unmodifiableRelation(Relation<K,V> rel)