jpaul.DataStructs
Class Relation<K,V>

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

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable

Direct Known Subclasses:

MapSetRelation

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

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

Unless otherwise specified a relation is modifiable and thread-UNsafe. Similar to the Collection framework, we provide unmodifiable and thread-safe wrappers:

• Relation.unmodifiableRelation(Relation)
• Relation.synchronizedRelation(Relation)

Version:

$Id: Relation.java,v 1.25 2006/02/26 16:34:03 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

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) Puts key in relation to each element of the collection values.
abstract boolean	addAll2(K key, java.util.Collection<? extends V> values) Similar to addAll(K, java.util.Collection) except that the type of the collection values allows more flexibility.
abstract void	clear() Removes all mappings stored in this relation.
Relation<K,V>	clone()
boolean	contains(K key, V value) Checks the existence of the relation <key,value>.
boolean	containsAll(K key, java.util.Collection<? extends 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.
boolean	isFunction() Checks whether this relation maps each key to a single value.
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() Return a relation that is the reverse of this relation.
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.
static <K,V> Relation<K,V>	synchronizedRelation(Relation<K,V> rel) Returns a synchronized (thread-safe) relation wrapper backed by the given relation rel.
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) Returns an unmodifiable wrapper backed by the given relation 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)

Puts key in relation to each element of the collection values. Returns true if the relation becomes bigger.

addAll2

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

Similar to addAll(K, java.util.Collection) except that the type of the collection values allows more flexibility. Puts key in relation to each element from the collection values. Returns true if the relation becomes bigger.

Only for the very curious users: A legitimate question is "why two almost identical versions of addAll?" The answer has to do with speed optimizations and historic reasons. In program analysis, it is frequent to propagate large relations, with only the mappings for a few keys being changed. Consequently, jpaul offers special Copy-On-Write (COW) sets and other datastructures (see COWSetFactory). For the rest of this discussion, let's assume that key is not in relation with any value yet. The historically first version, addAll(K, java.util.Collection), allows the possible underlying set factory to "clone" the COW set values (if values is indeed a COW set). "Cloning" a COW datastructure is very fast, and consumes almost no memory at all, leading to enormous speedups (e.g., in Alex Salcianu's pointer analysis prototype). Unfortunately, cloning in the presence of wildcards would violate type safety: cloning a Set<? extends V> does not produce a Set<V>. Instead, the usual implementations of addAll2(K, java.util.Collection) work by creating a brand-new Set<V> and adding the new values to it, one-by-one. Retrospectively, the design could have been better, but we didn't want to do anything that would break the performances of the applications that already use jpaul.

clear

public abstract void clear()

Removes all mappings stored in this relation.

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<? extends 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()

Return a relation that is the reverse of this relation. The reverse relation contains a pair <a,b> iff this relation contains the pair <b,a>. Once created, the reverse relation is independent of this relation: mutation on one of them will not affect the other one. The reverse relation is represented as a hashset/hashmap-based MapSetRelation.

Warning: This default representation may be very inefficient for small relations. If speed is an issue, please use revert(Relation): it allows you to create the revert relation, using your favorite Relation implementation.

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.

isFunction

public boolean isFunction()

Checks whether this relation maps each key to a single value. Mathematically, checks whether this relation is a (partial) function.

clone

public Relation<K,V> 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)

Returns an unmodifiable wrapper backed by the given relation rel. This allows "read-only" access, although changes in the backing collection show up in this view. Attempts to modify the relation will fail with UnsupportedOperationException.

synchronizedRelation

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

Returns a synchronized (thread-safe) relation wrapper backed by the given relation rel. Each operation synchronizes on rel.

For operations that return a collection (e.g., keys(), values()), it is strongly recommended to synchronize the whole block that (1) invokes the collection-returning relation operation, and (2) uses that collection. This is similar to the recommended usage pattern for the JDK synchronized collections (e.g., Collections.synchronizedSet. Here is an example:

        Relation<K,V> syncRel = Relation.synchronizedRelation(someRel);
        ...
        synchronized(syncRel) {
          Iterator<K> it = syncRel.keys().iterator();
          while(it.hasNext()) {
            K key = it.next();
            ...
          }
        }
        

This pattern prevents non-deterministic, hard-to-reproduce behavior due to modifications from other threads on the relation you iterate over.