blog
Class ObjGenGraph

java.lang.Object
  common.AbstractDGraph
      blog.ObjGenGraph

All Implemented Interfaces:

DGraph

public class ObjGenGraph
extends AbstractDGraph

An object generation graph contains nodes that represent sets of objects with certain generation histories. A node in an object generation graph is like a formula with a free variable: given a particular world and a particular assignment of values to other variables, we can say whether any given object satisfies the node. An object o satisfies a node v given a world w and a variable assignment a if:

• v is a POPNode for a POP (tau, g1, ..., gk) and o satisfies a POP application (tau, (g1, o1), ..., (gk, ok)) such that o1, ..., ok satisfy the parents of v given (w, a);
• v is an OrNode and o satisfies one of the parents of v given (w, a) (we ensure that the parents of an OrNode are satisfied by disjoint sets);
• v is a TermNode for a term t and o is the denotation of t given (w, a);
• v is an IntegerNode with lower bounds s1, ..., sj and upper bounds t1, ..., tk, and o is an integer (or timestep) that is >= the denotations of s1, ..., sj and <= the denotations of t1, ..., tk given (w, a);
• v is a GuaranteedNode for type tau and o is a guaranteed object of type tau.

The arguments to the ObjGenGraph constructor describe a certain set of objects. The ObjGenGraph contains a distinguished target node that is satisfied by all the described objects (and possibly some other objects that exist). The iterator method returns an iterator over the objects that satisfy the target node. This set may be infinite, but we can still iterate over it. TODO: Fix case where term in TermNode evaluates to Model.NULL.

Nested Class Summary

static class	ObjGenGraph.GuaranteedNode
static class	ObjGenGraph.IntegerNode
static class	ObjGenGraph.Node
static class	ObjGenGraph.OrNode
static class	ObjGenGraph.POPNode Node satisfied by the set of objects that satisfy a given potential object pattern (POP).
static class	ObjGenGraph.TermNode Node satisfied only by the denotation of the given term.
static class	ObjGenGraph.TimestepNode

Field Summary

Fields inherited from interface common.DGraph

EMPTY_GRAPH

Constructor Summary

ObjGenGraph(Type type)
Creates an object generation graph where the target node is satisfied by all objects of the given type.

ObjGenGraph(Type type, LogicalVar subjectVar, java.util.List constraints)
Creates an object generation graph where the set of free variables consists of just the subject variable.

ObjGenGraph(Type type, LogicalVar subjectVar, java.util.List constraints, java.util.Set freeVars)
Creates an object generation graph where the target node is satisfied by all objects of the given type that satisfy all the given constraints when bound to subjectVar.

Method Summary

boolean	dependsOnIdOrder(EvalContext context) Returns true if the iteration order for objects that satisfy the target node is affected by the iteration order for object identifiers in the given context.
java.util.Set	getChildren(java.lang.Object v) Returns an unmodifiable set consisting of the given object's children, or null if the object is not in the graph.
java.util.Set	getParents(java.lang.Object v) Returns an unmodifiable set consisting of the given object's parents, or null if the object is not in the graph.
boolean	isExact() Returns true if this ObjGenGraph exactly represents the set specified in its constructor: that is, all the objects returned by elementSet satisfy the constraints passed to the constructor.
ObjectIterator	iterator(EvalContext context) Returns an iterator over the set of objects that satisfy the target node in the given context.
ObjectIterator	iterator(EvalContext context, java.util.Set externallyDistinguished, boolean returnPOPApps) Returns an iterator over the set of objects that satisfy the target node in the given context.
java.util.Set	nodes() Returns an unmodifiable set consisting of the nodes in this graph.

Methods inherited from class common.AbstractDGraph

addEdge, addNode, getAncestors, getDescendants, getRoots, print, removeEdge, removeNode, setParents

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ObjGenGraph

public ObjGenGraph(Type type)

Creates an object generation graph where the target node is satisfied by all objects of the given type.

ObjGenGraph

public ObjGenGraph(Type type,
                   LogicalVar subjectVar,
                   java.util.List constraints,
                   java.util.Set freeVars)

Creates an object generation graph where the target node is satisfied by all objects of the given type that satisfy all the given constraints when bound to subjectVar.

Parameters:

constraints - List of Formula objects. Only literals are processed.

freeVars - Set of LogicalVar objects representing variables that should not be used in the graph because they will not be assigned values when the graph is used.

ObjGenGraph

public ObjGenGraph(Type type,
                   LogicalVar subjectVar,
                   java.util.List constraints)

Creates an object generation graph where the set of free variables consists of just the subject variable.

Method Detail

isExact

public boolean isExact()

Returns true if this ObjGenGraph exactly represents the set specified in its constructor: that is, all the objects returned by elementSet satisfy the constraints passed to the constructor.

iterator

public ObjectIterator iterator(EvalContext context)

Returns an iterator over the set of objects that satisfy the target node in the given context.

iterator

public ObjectIterator iterator(EvalContext context,
                               java.util.Set externallyDistinguished,
                               boolean returnPOPApps)

Returns an iterator over the set of objects that satisfy the target node in the given context. If returnPOPApps is true, returns NumberVars to represent entire sets of POP application satisfiers, rather than returning the satifiers themselves.

dependsOnIdOrder

public boolean dependsOnIdOrder(EvalContext context)

Returns true if the iteration order for objects that satisfy the target node is affected by the iteration order for object identifiers in the given context. This is true if any ancestor of the target node is a POPNode for a type that is represented with object identifiers in the given context.

nodes

public java.util.Set nodes()

Description copied from interface: DGraph

Returns an unmodifiable set consisting of the nodes in this graph.

getParents

public java.util.Set getParents(java.lang.Object v)

Description copied from interface: DGraph

Returns an unmodifiable set consisting of the given object's parents, or null if the object is not in the graph.

getChildren

public java.util.Set getChildren(java.lang.Object v)

Description copied from interface: DGraph

Returns an unmodifiable set consisting of the given object's children, or null if the object is not in the graph.