edu.illinois.cs.cogcomp.lbj.coref.ir.solutions
Class ChainSolution<T>

java.lang.Object
  edu.illinois.cs.cogcomp.lbj.coref.ir.solutions.ChainSolution<T>

Type Parameters:

T - The type of element in the partition.

All Implemented Interfaces:

Solution, java.io.Serializable

public class ChainSolution<T>
extends java.lang.Object
implements Solution, java.io.Serializable

Represents a partition(a set of non-overlapping subsets called chains) and edges linking some items in the partition, along with edge labels. Provides functionality for linking chains and recording information about the links. In all cases defensive copying is done to inputs and unmodifiable views are returned. However, the underlying elements (of type T) are never copied. NOTE WELL: Depends on T objects being hashable (only an issue if two objects might be identical but independently created.)

Author:

Eric Bengtson

See Also:

Serialized Form

Field Summary

private java.util.Map<T,T>	m_antecedents
private java.util.List<java.util.Set<T>>	m_chains
private java.util.Map<Pair<T,T>,java.util.List<java.lang.String>>	m_edgeLabels
private java.util.List<Pair<T,T>>	m_edges
private java.util.Map<T,java.util.Set<T>>	m_mapToChains
private java.util.Map<T,java.util.Set<T>>	m_referrers
private static long	serialVersionUID

Constructor Summary

ChainSolution()
Constructs an empty solution.

ChainSolution(ChainSolution<T> otherSol)
Copy constructor.

ChainSolution(java.util.Collection<java.util.Collection<T>> chains)
Constructs a ChainSolution from a collection of chains (collections).

Method Summary

void	add(ChainSolution<T> otherSol) Adds all the chains from otherSol to this, including the edge labels.
void	addChain(java.util.Collection<T> chain) Adds a chain.
boolean	areTogether(T a, T b) Determines whether two elements are in the same chain (subset).
boolean	contains(T item) Determines whether the partition contains the specified item in any of its subsets.
boolean	equals(java.lang.Object o) Two ChainSolutions are equal if their subsets are equal.
java.util.Set<T>	getAllMembers() Gets an unmodifiable view all elements of the partition.
java.util.Set<T>	getChainContaining(java.util.Set<T> subset) Gets the chain that is a superset of the specified set.
java.util.Set<T>	getChainOf(T item) Gets the chain containing the specified item, or null if the item is not present.
java.util.List<java.util.Set<T>>	getChains() Gets an unmodifiable view of the chains of this partition.
java.util.Set<T>	getContainerFor(T item) Gets the chain containing the specified item, or null if the item is not present.
java.util.List<java.lang.String>	getEdgeLabelsFor(Pair<T,T> p) Gets the edges for a pair of objects.
java.util.List<Pair<T,T>>	getEdges() Gets the edges.
java.util.List<java.util.Set<T>>	getSubsets() Gets an unmodifiable view of the subsets of this partition.
int	hashCode() Generate hash code based on the collection of chains.
void	link(java.util.Set<T> chainA, T b, java.util.List<java.lang.String> labels) Links an object to a chain, applying labels.
void	link(java.util.Set<T> chainA, T b, java.lang.String label) Links an object to a chain, applying a label.
void	linkChains(java.util.Set<T> chainA, java.util.Set<T> chainB) Links the chains.
void	linkChains(java.util.Set<T> chainA, java.util.Set<T> chainB, java.util.List<java.lang.String> labels) Links the chains, applying labels.
void	linkChains(java.util.Set<T> chainA, java.util.Set<T> chainB, java.lang.String label) Links the chains, applying label.
private void	mergeChains(java.util.Set<T> c1, java.util.Set<T> c2, int n1, int n2) Utility function for merging chains.
void	recordDistinctness(T o1, T o2) Records the existence of two objects.
void	recordEquivalence(java.util.Set<T> chainA, java.util.Set<T> chainB) Records equivalence by recording the equivalence of all pairs of items in the chains.
void	recordEquivalence(T o1, T o2) Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present.
void	recordEquivalence(T o1, T o2, java.util.List<java.lang.String> labels) Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present.
void	recordEquivalence(T o1, T o2, java.lang.String label) Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present.
void	recordExistence(T c) Ensures that c is contained in some chain; if it is not yet, it is added to its own new chain.
protected void	setup() Initialize the member collections to empty.
java.lang.String	toDiffString(ChainSolution<T> other, java.lang.String fAbsentMark, java.lang.String fPresentMark) Gets a string showing the difference between this and another ChainSolution.
java.lang.String	toString() Represents this partition as a string.
protected void	updateMapToChains(T obj, java.util.Set<T> chain)

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

m_chains

private java.util.List<java.util.Set<T>> m_chains

m_mapToChains

private java.util.Map<T,java.util.Set<T>> m_mapToChains

m_edges

private java.util.List<Pair<T,T>> m_edges

m_antecedents

private java.util.Map<T,T> m_antecedents

m_referrers

private java.util.Map<T,java.util.Set<T>> m_referrers

m_edgeLabels

private java.util.Map<Pair<T,T>,java.util.List<java.lang.String>> m_edgeLabels

Constructor Detail

ChainSolution

public ChainSolution()

Constructs an empty solution.

ChainSolution

public ChainSolution(ChainSolution<T> otherSol)

Copy constructor. Creates a new solution having the same edges as otherSol.

ChainSolution

public ChainSolution(java.util.Collection<java.util.Collection<T>> chains)

Constructs a ChainSolution from a collection of chains (collections). Chains are effectively copied (so subsequent changes to any chains in chains will not affect this).

Parameters:

chains - A collection of chains.

Method Detail

setup

protected void setup()

Initialize the member collections to empty.

add

public void add(ChainSolution<T> otherSol)

Adds all the chains from otherSol to this, including the edge labels. Edges are copied defensively. Any existing edges in this that are also in otherSol will be overwritten in this.

Parameters:

otherSol - Another solution.

addChain

public void addChain(java.util.Collection<T> chain)

Adds a chain. Simply records the equivalence of the elements in the chain. Chain is effectively copied (so subsequent changes to chain will not affect this).

Parameters:

chain - The chain to add.

areTogether

public boolean areTogether(T a,
                           T b)

Determines whether two elements are in the same chain (subset). Both elements should be contained in this partition.

Parameters:

a - An element.

b - Another element.

Returns:

Whether the elements are in the same chain (subset).

contains

public boolean contains(T item)

Determines whether the partition contains the specified item in any of its subsets.

Parameters:

item - An item.

Returns:

Whether the partition contains the specified item

getAllMembers

public java.util.Set<T> getAllMembers()

Gets an unmodifiable view all elements of the partition.

Returns:

An unmodifiable view of the set of all elements of the partition.

getChains

public java.util.List<java.util.Set<T>> getChains()

Gets an unmodifiable view of the chains of this partition.

Returns:

An unmodifiable list of chains, each an unmodifiable set.

getSubsets

public java.util.List<java.util.Set<T>> getSubsets()

Gets an unmodifiable view of the subsets of this partition.

Returns:

An unmodifiable list of the subsets, each an unmodifiable set.

getChainOf

public java.util.Set<T> getChainOf(T item)

Gets the chain containing the specified item, or null if the item is not present. Gets an unmodifiable view of the desired chain.

Returns:

The subset (chain) containing the specified item or null if the item is not present in the partition.

getContainerFor

public java.util.Set<T> getContainerFor(T item)

Gets the chain containing the specified item, or null if the item is not present. Gets an unmodifiable view of the desired chain.

Returns:

The subset (chain) containing the specified item or null if the item is not present in the partition.

getChainContaining

public java.util.Set<T> getChainContaining(java.util.Set<T> subset)

Gets the chain that is a superset of the specified set.

Returns:

An unmodifiable view of the chain containing or equal to subset, or null if no chain is found.

getEdges

public java.util.List<Pair<T,T>> getEdges()

Gets the edges.

Returns:

An unmodifiable view of the list of edges, as Pairs.

getEdgeLabelsFor

public java.util.List<java.lang.String> getEdgeLabelsFor(Pair<T,T> p)

Gets the edges for a pair of objects.

Returns:

An unmodifiable view of the (possibly empty) list of labels.

updateMapToChains

protected void updateMapToChains(T obj,
                                 java.util.Set<T> chain)

recordEquivalence

public void recordEquivalence(T o1,
                              T o2,
                              java.lang.String label)

Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present. Also, a label is added to the edge between the objects.

Parameters:

o1 - The first object.

o2 - The second object.

label - The label to append to the edge between o1 and o2.

recordEquivalence

public void recordEquivalence(T o1,
                              T o2,
                              java.util.List<java.lang.String> labels)

Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present. labels are applied to the edge between the objects, replacing any existing labels. Labels are copied defensively.

Parameters:

o1 - The first object.

o2 - The second object.

labels - The labels to apply to the edge between o1 and o2. Any existing labels are replaced.

recordEquivalence

public void recordEquivalence(java.util.Set<T> chainA,
                              java.util.Set<T> chainB)

Records equivalence by recording the equivalence of all pairs of items in the chains. This is needed in case elements in the input chains are in distinct chains in this ChainSolution. Note that this means the implementation is quadratic in the number of members. Effectively copies all links; subsequent modifications of chainA or chainB will not affect this partition.

Parameters:

chainA - One set of objects.

chainB - Another set of objects.

linkChains

public void linkChains(java.util.Set<T> chainA,
                       java.util.Set<T> chainB)

Links the chains. An arbitrary pair of elements, one from each chain, is linked. Both chains must already exist in full in the partition. Subsequent modification of chainA or chainB will not affect this partition.

Parameters:

chainA - A chain.

chainB - Another chain.

linkChains

public void linkChains(java.util.Set<T> chainA,
                       java.util.Set<T> chainB,
                       java.lang.String label)

Links the chains, applying label. An arbitrary pair of elements, one from each chain, is linked. Both chains must already exist in full in the partition. Subsequent modification of chainA or chainB will not affect this partition. Label is copied defensively and overwrites any existing labels between the linked mentions.

Parameters:

chainA - A chain.

chainB - Another chain.

linkChains

public void linkChains(java.util.Set<T> chainA,
                       java.util.Set<T> chainB,
                       java.util.List<java.lang.String> labels)

Links the chains, applying labels. An arbitrary pair of elements from the chains are linked. Both chains must already exist in full in the partition. Subsequent modification of chainA or chainB will not affect this partition. Labels are copied defensively and overwrite any existing labels between the linked mentions.

Parameters:

chainA - A chain.

chainB - Another chain.

labels - Labels.

link

public void link(java.util.Set<T> chainA,
                 T b,
                 java.lang.String label)

Links an object to a chain, applying a label. Makes a link between one element of chainA and b. chainA must already exist in full in the partition. Subsequent modifications of chainA will not affect this partition. Label is copied defensively and overwrites any existing labels between the linked mentions.

Parameters:

chainA - A chain.

b - An object.

label - A label.

link

public void link(java.util.Set<T> chainA,
                 T b,
                 java.util.List<java.lang.String> labels)

Links an object to a chain, applying labels. Makes a link between one element of chainA and b. chainA must already exist in full in the partition. Subsequent modifications of chainA will not affect this partition. Labels are copied defensively and overwrite any existing labels between the linked mentions.

Parameters:

chainA - A chain.

b - An object.

labels - The labels.

mergeChains

private void mergeChains(java.util.Set<T> c1,
                         java.util.Set<T> c2,
                         int n1,
                         int n2)

Utility function for merging chains.

Parameters:

c1 - One chain.

c2 - Another chain.

n1 - The first chain's index in m_chains.

n2 - The second chain's index in m_chains.

recordEquivalence

public void recordEquivalence(T o1,
                              T o2)

Records the equivalence of two objects, adding them to the same subset of the partition if not yet present, or linking the subsets containing them if present.

Parameters:

o1 - An object.

o2 - Another object.

recordDistinctness

public void recordDistinctness(T o1,
                               T o2)

Records the existence of two objects. If either is not yet part of a subset, it will be added to its own subset. Otherwise, nothing will be done. Note that this method does not guarantee that the objects will be in separate subsets after it is called.

Parameters:

o1 - An object.

o2 - Another object.

recordExistence

public void recordExistence(T c)

Ensures that c is contained in some chain; if it is not yet, it is added to its own new chain.

toString

public java.lang.String toString()

Represents this partition as a string.

Overrides:

toString in class java.lang.Object

toDiffString

public java.lang.String toDiffString(ChainSolution<T> other,
                                     java.lang.String fAbsentMark,
                                     java.lang.String fPresentMark)

Gets a string showing the difference between this and another ChainSolution. Chains are aligned by a single arbitrary member from each solution.

Parameters:

other - Another ChainSolution, typically a reference key.

fAbsentMark - denotes things in other, but not found in this.

fPresentMark - denotes things in this but missing in other.

Returns:

A string describing this, indicating where it differs from other.

equals

public boolean equals(java.lang.Object o)

Two ChainSolutions are equal if their subsets are equal.

Overrides:

equals in class java.lang.Object

Parameters:

o - Another object.

Returns:

Whether the specified object is equal to this.

hashCode

public int hashCode()

Generate hash code based on the collection of chains.

Overrides:

hashCode in class java.lang.Object

Returns:

The hash code for this.