common
Interface MapWithPreimages

All Superinterfaces:

java.util.Map

All Known Implementing Classes:

AbstractMapWithPreimages, HashMapWithPreimages, MapWithPreimages.EmptyMapWithPreimages, MapWithPreimagesDiff

public interface MapWithPreimages
extends java.util.Map

An extension of the Map interface that provides efficient access to the pre-image of a value in the map. The pre-image of a value y is the set of keys that map to y.

Nested Class Summary

static class

MapWithPreimages.EmptyMapWithPreimages

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

static MapWithPreimages

EMPTY_MAP_WITH_PREIMAGES An empty MapWithPreimages.

Method Summary

java.util.Set	getPreimage(java.lang.Object v) Returns the set of keys that map to v.
MultiMap	getPreimages() Returns a MultiMap view of the inverse of this map.
boolean	isCorefPair(java.lang.Object k1, java.lang.Object k2) Returns true if k1 and k2 are coreferent, that is, they are both keys that map to the same value.
int	numCorefPairs() Returns the number of two-element sets of objects {k1, k2} such that isCorefPair(k1, k2) returns true.
java.util.Set	valueSet() Returns the set of values in the map.

Methods inherited from interface java.util.Map

clear, containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keySet, put, putAll, remove, size, values

Field Detail

EMPTY_MAP_WITH_PREIMAGES

static final MapWithPreimages EMPTY_MAP_WITH_PREIMAGES

An empty MapWithPreimages.

Method Detail

valueSet

java.util.Set valueSet()

Returns the set of values in the map. This method differs from the values method in the Map interface in that it returns a Set rather than a Collection.

getPreimage

java.util.Set getPreimage(java.lang.Object v)

Returns the set of keys that map to v. If no keys map to v, this is the empty set.

Returns:

an unmodifiable Set of keys

getPreimages

MultiMap getPreimages()

Returns a MultiMap view of the inverse of this map. The MultiMap is backed by this MapWithPreimages, so it will change as this MapWithPreimages changes. It should be treated as unmodifiable.

isCorefPair

boolean isCorefPair(java.lang.Object k1,
                    java.lang.Object k2)

Returns true if k1 and k2 are coreferent, that is, they are both keys that map to the same value.

numCorefPairs

int numCorefPairs()

Returns the number of two-element sets of objects {k1, k2} such that isCorefPair(k1, k2) returns true. This can be computed by summing, over all values v in the map, the number of two-element subsets of getPreimage(v). The number of two-element subsets of a set of size n is n-choose-2, or n * (n-1) / 2.

Note that this is different from computing the number of ordered pairs (k1, k2) such that isCorefPair(k1, k2) returns true; then we wouldn't divide by 2 in the formula above.