Class UnificationTable

java.lang.Object
  |
  +--UnificationTable

public class UnificationTable

extends java.lang.Object

UnificationTable.java A unification table is required to keep track of which Variables have been matched against each other; otherwise transitivity might be lost through a series of pairwise comparisons, i.e ?z matches ?x, ?x matches Apple, what does ?z match now? store ?z/?x/Apple in table Every variable has two identities: a set of variables and possibly one constant to which it is bound (stored in "ht"); and a substitution set that lists possible additional bindings under consideration by the unification process (stored in "subs"). Created: Fri Apr 16 16:04:19 1999

Field Summary

(package private) static boolean	DEBUG
(package private) static java.lang.String	em
private java.util.Hashtable	ht
(package private) static java.lang.String	loc
private java.util.Hashtable	subs

Constructor Summary

UnificationTable()

Method Summary

void	add(Variable key, java.lang.Object value) Always adds key to vector of values so that when two sets of values are merged, we know both sources.
private void	addSubstitutions(Variable v1, java.lang.Object o2) Polymorphic, to the extent that java is.
private void	addSubstitutions(Variable var1, Variable var2)
void	clear()
void	clearSubstitutions()
java.lang.Object	clone()
boolean	findSamePredicateSubstitutions(Predicate p1, Predicate p2) Attempt to find a substitution that can unify the three fields of the predicates.
SetVector	get(Variable key) Returns the binding of a variable if it exists, otherwise binds it to empty SetVector.
private java.lang.Object	getConstant(Variable key) Returns the constant binding of a variable if it exists, otherwise returns null.
Predicate	getConstantPredicate(Predicate p) Return a predicate with all variables replaced by constants if they exist, otherwise return null.
private boolean	getNewSubstitutions(java.lang.Object o1, java.lang.Object o2) If a variable can be unified with an object or variable within the context of previous substitutions, then true is returned (can't just change the UT.ht because rest of predicate might not unify, or might want to try other combos.) Returns NULL if no valid substitution exists.
private boolean	getNewSubstitutions(java.lang.Object o2, Variable var1)
private boolean	getNewSubstitutions(Variable var1, java.lang.Object o2)
private boolean	getNewSubstitutions(Variable var1, Variable var2)
Predicate	getPredicateWithMoreConstants(Predicate p) Return a predicate with as many variables as possible replaced by constants; if at least one variable is replaced, return a new predicate; else return null.
private java.lang.Object	getSubsConstant(Variable v1)
private SetVector	getVariableSubstitutions(Variable v) If there are already substitutions in the subs table, get them.
private boolean	isBound(Variable key) Returns true if Variable is bound to a non-empty set.
private boolean	isBoundTo(Variable key, java.lang.Object value)
static void	main(java.lang.String[] args)
void	makeSubstitutions()
Predicate	subGetPredicateWithMoreConstants(Predicate p)
java.lang.String	toString()
private SetVector	unionSubstitutions(Variable v1, Variable v2)

Methods inherited from class java.lang.Object

, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, wait, wait, wait

Field Detail

ht

private java.util.Hashtable ht

subs

private java.util.Hashtable subs

DEBUG

static boolean DEBUG

em

static java.lang.String em

loc

static java.lang.String loc

Constructor Detail

UnificationTable

public UnificationTable()

Method Detail

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

add

public void add(Variable key,
                java.lang.Object value)

Always adds key to vector of values so that when two sets of values are merged, we know both sources.

get

public SetVector get(Variable key)

Returns the binding of a variable if it exists, otherwise binds it to empty SetVector.

getConstant

private java.lang.Object getConstant(Variable key)

Returns the constant binding of a variable if it exists, otherwise returns null.

getConstantPredicate

public Predicate getConstantPredicate(Predicate p)

Return a predicate with all variables replaced by constants if they exist, otherwise return null.

getPredicateWithMoreConstants

public Predicate getPredicateWithMoreConstants(Predicate p)

Return a predicate with as many variables as possible replaced by constants; if at least one variable is replaced, return a new predicate; else return null.

subGetPredicateWithMoreConstants

public Predicate subGetPredicateWithMoreConstants(Predicate p)

isBound

private boolean isBound(Variable key)

Returns true if Variable is bound to a non-empty set. True does not imply that the variable is bound to a constant; it may only be bound to other variables.

isBoundTo

private boolean isBoundTo(Variable key,
                          java.lang.Object value)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

addSubstitutions

private void addSubstitutions(Variable v1,
                              java.lang.Object o2)

Polymorphic, to the extent that java is.

addSubstitutions

private void addSubstitutions(Variable var1,
                              Variable var2)

getSubsConstant

private java.lang.Object getSubsConstant(Variable v1)

unionSubstitutions

private SetVector unionSubstitutions(Variable v1,
                                     Variable v2)

getVariableSubstitutions

private SetVector getVariableSubstitutions(Variable v)

If there are already substitutions in the subs table, get them. Otherwise, get the value from UT.ht, add the variable name, and return.

getNewSubstitutions

private boolean getNewSubstitutions(java.lang.Object o1,
                                    java.lang.Object o2)

If a variable can be unified with an object or variable within the context of previous substitutions, then true is returned (can't just change the UT.ht because rest of predicate might not unify, or might want to try other combos.) Returns NULL if no valid substitution exists. Polymorphic.

getNewSubstitutions

private boolean getNewSubstitutions(java.lang.Object o2,
                                    Variable var1)

getNewSubstitutions

private boolean getNewSubstitutions(Variable var1,
                                    java.lang.Object o2)

getNewSubstitutions

private boolean getNewSubstitutions(Variable var1,
                                    Variable var2)

clearSubstitutions

public void clearSubstitutions()

clear

public void clear()

makeSubstitutions

public void makeSubstitutions()

findSamePredicateSubstitutions

public boolean findSamePredicateSubstitutions(Predicate p1,
                                              Predicate p2)

Attempt to find a substitution that can unify the three fields of the predicates. If found, return true. The substitutions are stored in the UnificationTable so that a sequence of substitutions can be attempted, taking into account each earlier result.

main

public static void main(java.lang.String[] args)