common
Class AbstractMapWithPreimages

java.lang.Object
  java.util.AbstractMap
      common.AbstractMapWithPreimages

All Implemented Interfaces:

MapWithPreimages, java.util.Map

Direct Known Subclasses:

HashMapWithPreimages, MapWithPreimages.EmptyMapWithPreimages, MapWithPreimagesDiff

public abstract class AbstractMapWithPreimages
extends java.util.AbstractMap
implements MapWithPreimages

Abstract implementation of the MapWithPreimages interface. A concrete subclass only needs to implement a constructor that initializes the protected variables map and preimages. The implemented methods do not support null keys or null values.

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface common.MapWithPreimages

MapWithPreimages.EmptyMapWithPreimages

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

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

Field Summary

protected java.util.Map	map The map itself.
protected MultiMap	preimages MultiMap from values in map to the keys for which they serve as the value.

Fields inherited from interface common.MapWithPreimages

EMPTY_MAP_WITH_PREIMAGES

Constructor Summary

AbstractMapWithPreimages()

Method Summary

void	clear()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object v)
java.util.Set	entrySet()
java.lang.Object	get(java.lang.Object key)
java.util.Set	getPreimage(java.lang.Object value) 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.
boolean	isEmpty()
java.util.Set	keySet()
int	numCorefPairs() Returns the number of two-element sets of objects {k1, k2} such that isCorefPair(k1, k2) returns true.
java.lang.Object	put(java.lang.Object key, java.lang.Object newVal)
java.lang.Object	remove(java.lang.Object key)
int	size()
java.util.Collection	values()
java.util.Set	valueSet() Returns the set of values in the map.

Methods inherited from class java.util.AbstractMap

clone, equals, hashCode, putAll, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

equals, hashCode, putAll

Field Detail

map

protected java.util.Map map

The map itself.

preimages

protected MultiMap preimages

MultiMap from values in map to the keys for which they serve as the value.

Constructor Detail

AbstractMapWithPreimages

public AbstractMapWithPreimages()

Method Detail

size

public int size()

Specified by:

size in interface java.util.Map

Overrides:

size in class java.util.AbstractMap

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map

Overrides:

isEmpty in class java.util.AbstractMap

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map

Overrides:

containsKey in class java.util.AbstractMap

containsValue

public boolean containsValue(java.lang.Object v)

Specified by:

containsValue in interface java.util.Map

Overrides:

containsValue in class java.util.AbstractMap

get

public java.lang.Object get(java.lang.Object key)

Specified by:

get in interface java.util.Map

Overrides:

get in class java.util.AbstractMap

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object newVal)

Specified by:

put in interface java.util.Map

Overrides:

put in class java.util.AbstractMap

remove

public java.lang.Object remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map

Overrides:

remove in class java.util.AbstractMap

clear

public void clear()

Specified by:

clear in interface java.util.Map

Overrides:

clear in class java.util.AbstractMap

keySet

public java.util.Set keySet()

Specified by:

keySet in interface java.util.Map

Overrides:

keySet in class java.util.AbstractMap

values

public java.util.Collection values()

Specified by:

values in interface java.util.Map

Overrides:

values in class java.util.AbstractMap

entrySet

public java.util.Set entrySet()

Specified by:

entrySet in interface java.util.Map

Specified by:

entrySet in class java.util.AbstractMap

valueSet

public java.util.Set valueSet()

Description copied from interface: MapWithPreimages

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.

Specified by:

valueSet in interface MapWithPreimages

getPreimage

public java.util.Set getPreimage(java.lang.Object value)

Description copied from interface: MapWithPreimages

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

Specified by:

getPreimage in interface MapWithPreimages

Returns:

an unmodifiable Set of keys

getPreimages

public MultiMap getPreimages()

Description copied from interface: MapWithPreimages

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.

Specified by:

getPreimages in interface MapWithPreimages

isCorefPair

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

Description copied from interface: MapWithPreimages

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

Specified by:

isCorefPair in interface MapWithPreimages

numCorefPairs

public int numCorefPairs()

Description copied from interface: MapWithPreimages

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.

Specified by:

numCorefPairs in interface MapWithPreimages