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.11 2005/12/01 08:03:38 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) Adds a relation from key to each element of the set values.
java.lang.Object	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, revert, size, 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

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.

Specified by:

addAll 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 java.lang.Object 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>