jpaul.DataStructs
Class MapSetRelation<K,V>

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

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable

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

MapSetRelation is an implementation of the Relation interface based on a Map from keys to Sets of values.

Version:

$Id: MapSetRelation.java,v 1.18 2006/03/14 02:55:23 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class jpaul.DataStructs.Relation

Relation.EntryVisitor<Key,Value>

Constructor Summary

MapSetRelation()
Constructs a Relation represented using a LinkedHashMap from keys to LinkedHashSets of values.

MapSetRelation(MapFactory<K,java.util.Set<V>> mapFact, SetFactory<V> setFact)
Constructs a Relation represented by a Map from keys to Sets of values.

Method Summary

protected java.util.Set<V>	_getValues(K key) Method used by the internal implementation of the Relation or its subclasses.
boolean	add(K key, V value) Adds the pair <key, value> to the relation.
boolean	addAll(K key, java.util.Collection<V> values) Puts key in relation to each element of the collection values.
boolean	addAll2(K key, java.util.Collection<? extends V> values) Similar to Relation.addAll(K, java.util.Collection) except that the type of the collection values allows more flexibility.
void	clear() Removes all mappings stored in this relation.
MapSetRelation<K,V>	clone() Creates a new, independent relation (independent = the operations on the new relation won't affect the old one).
boolean	containsKey(K key) Checks the existence of the key key in this relation.
boolean	equals(java.lang.Object o) Checks the equality of two relations
int	hashCode() Complexity: linear in the number of (key,value) pairs from the relation.
boolean	isEmpty() Tests if this relation is empty or not.
java.util.Set<K>	keys() Returns an IMMUTABLE view of all the keys appearing in this relation.
boolean	remove(K key, V value) Removes the relation between key and value.
boolean	removeAll(K key, java.util.Collection<V> values) Removes the relation between key and any element from values.
boolean	removeKey(K key) Removes all the relations attached to key.
boolean	removeKeys(Predicate<K> predicate) Removes all the keys that satisfy predicate.check().
boolean	removeValues(Predicate<V> predicate) Removes all the values that satisfy predicate.check().
boolean	union(Relation<K,V> rel) Combines this relation with relation rel.
java.lang.Iterable<V>	values() Returns an IMMUTABLE view of all the values appearing in this relation.

Methods inherited from class jpaul.DataStructs.Relation

contains, containsAll, forAllEntries, getValues, isFunction, revert, revert, size, synchronizedRelation, toString, unmodifiableRelation

Methods inherited from class java.lang.Object

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

Constructor Detail

MapSetRelation

public MapSetRelation()

Constructs a Relation represented using a LinkedHashMap from keys to LinkedHashSets of values. Consumes a lot of memory but fast for large relation.

MapSetRelation

public MapSetRelation(MapFactory<K,java.util.Set<V>> mapFact,
                      SetFactory<V> setFact)

Constructs a Relation represented by a Map from keys to Sets of values. The map is created by mapFact and the sets by setFact.

See Also:

MapFacts, SetFacts

Method Detail

add

public boolean add(K key,
                   V value)

Description copied from class: Relation

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

Specified by:

add in class Relation<K,V>

addAll

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

Description copied from class: Relation

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

Specified by:

addAll in class Relation<K,V>

addAll2

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

Description copied from class: Relation

Similar to Relation.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, Relation.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 Relation.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.

Specified by:

addAll2 in class Relation<K,V>

clear

public void clear()

Description copied from class: Relation

Removes all mappings stored in this relation.

Specified by:

clear in class Relation<K,V>

remove

public boolean remove(K key,
                      V value)

Description copied from class: Relation

Removes the relation between key and value.

Specified by:

remove in class Relation<K,V>

Returns:

true iff the relation changed

removeAll

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

Description copied from class: Relation

Removes the relation between key and any element from values.

Specified by:

removeAll in class Relation<K,V>

Returns:

true iff the relation changed

removeKey

public boolean removeKey(K key)

Description copied from class: Relation

Removes all the relations attached to key.

Specified by:

removeKey in class Relation<K,V>

Returns:

true iff the relation changed

removeKeys

public boolean removeKeys(Predicate<K> predicate)

Description copied from class: Relation

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

Specified by:

removeKeys in class Relation<K,V>

Returns:

true iff the relation changed

removeValues

public boolean removeValues(Predicate<V> predicate)

Description copied from class: Relation

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

Specified by:

removeValues in class Relation<K,V>

Returns:

true iff the relation changed

containsKey

public boolean containsKey(K key)

Description copied from class: Relation

Checks the existence of the key key in this relation.

Specified by:

containsKey in class Relation<K,V>

isEmpty

public boolean isEmpty()

Description copied from class: Relation

Tests if this relation is empty or not.

Specified by:

isEmpty in class Relation<K,V>

_getValues

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

Description copied from class: Relation

Method used by the internal implementation of the Relation or its subclasses. Similar to the user-level Relation.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.

Specified by:

_getValues in class Relation<K,V>

keys

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

Description copied from class: Relation

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

Specified by:

keys in class Relation<K,V>

values

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

Description copied from class: Relation

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.

Specified by:

values in class Relation<K,V>

union

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

Description copied from class: Relation

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

Specified by:

union in class Relation<K,V>

Returns:

true iff this relation has changed.

hashCode

public int hashCode()

Complexity: linear in the number of (key,value) pairs from the relation. We could maintain the hashCode incrementally, keeping the amortized cost of all operations to O(1). However, that complicates the code significantly, and I'm not sure it's that useful: how many times does one use a set of relations? The Java collections do not compute their hashcode incrementally either.

Overrides:

hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Description copied from class: Relation

Checks the equality of two relations

Specified by:

equals in class Relation<K,V>

clone

public MapSetRelation<K,V> clone()

Creates a new, independent relation (independent = the operations on the new relation won't affect the old one).

Overrides:

clone in class Relation<K,V>