Module xl.impl

Package de.grogra.xl.impl.base

Class Graph

java.lang.Object

de.grogra.xl.impl.base.Graph

All Implemented Interfaces:

Graph, Cloneable

Direct Known Subclasses:

GraphImpl, RGGGraph

public abstract class Graph
extends Object
implements Graph, Cloneable

This class is an abstract base class for implementations of XL's runtime model for graph-like structures. Graph represents a single graph on which XL's query statements may operate.

The package documentation contains more information about the structure of the graph that is implied by this base class.

The current derivation mode for rule applications acting on this graph is set by setDerivationMode(int) and may be truly parallel (PARALLEL_MODE), parallel and non-deterministic (PARALLEL_NON_DETERMINISTIC_MODE, one application is chosen out of several applications which delete the same node), sequential (SEQUENTIAL_MODE, only the first rule application per derivation step is used), or sequential and non-deterministic (SEQUENTIAL_NON_DETERMINISTIC_MODE, only one rule application per derivation step is used).

Author:

Ole Kniemeyer

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	Graph.QState
protected static class	Graph.ThreadData

Field Summary

Fields

Modifier and Type	Field	Description
static final int	EXCLUDE_DELETED_FLAG	Bit mask for getDerivationMode() which indicates that nodes which were already deleted by previous rule applications of the current derivation step shall be excluded from further matches of the same step.
static final int	INTERPRETIVE_FLAG	Bit mask for getDerivationMode() which indicates that rules have to be applied as interpretive rules.
static final int	MODE_MASK	Mask for getDerivationMode() to obtain the mode part (one of PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE).
static final int	PARALLEL_MODE	Bit mask for getDerivationMode() indicating a true parallel derivation mode.
static final int	PARALLEL_NON_DETERMINISTIC_MODE	Bit mask for getDerivationMode() indicating a parallel non-deterministic derivation mode.
static final int	SEQUENTIAL_MODE	Bit mask for getDerivationMode() indicating a sequential derivation mode.
static final int	SEQUENTIAL_NON_DETERMINISTIC_MODE	Bit mask for getDerivationMode() indicating a sequential derivation mode.

Constructor Summary

Constructors

Constructor	Description
Graph(RuntimeModel model)

Method Summary

Modifier and Type	Method	Description
void	allowNoninjectiveMatchesByDefault(boolean value)
void	allowNoninjectiveMatchesForNextQuery(boolean value)	Deprecated.
boolean	areComparableScales(Object nodeA, Object nodeB)
protected abstract void	beginModifications()
boolean	canEnumerateNodes(Type type)	Can nodes of the specified type be enumerated?
protected abstract void	commitModifications()
Pattern.Matcher	createMatcher(Pattern pred, XBitSet providedConstants, IntList neededConstantsOut)
Graph.QState	createQueryState()	Creates a query state to be used for queries which use this graph.
protected abstract GraphQueue	createQueue(QueueCollection qc, QueueDescriptor descr)
protected Graph.ThreadData	createThreadData()
long	derive()
void	enumerateEdges(Object node, EdgeDirection dir, Type edgeType, QueryState qs, int toIndex, int patternIndex, Serializable pattern, int matchIndex, MatchConsumer consumer, int arg)
void	enumerateSpaces(Object node, EdgeDirection dir, Type edgeType, QueryState qs, int toIndex, int patternIndex, Serializable pattern, int matchIndex, MatchConsumer consumer, int arg)	Searches the graph (with reference to the type graph) for matching multiscale patterns
int	getDerivationMode()	Returns the current derivation mode.
int	getMinimumEncoarseDepthDiff(Object coarseNode, Object fineNode)	Returns the length of the shortest encoarsement path from fineNode to coarseNode
RuntimeModel	getModel()	Returns this graph's run-time model.
protected Object	getPredecessor(Object node)
QueueCollection	getQueues()
int	getScaleValue(HashMap<Object,Integer> sortedTypeGraph, Object node)
protected Graph.ThreadData	getThreadData()
Object	getTypeNode(Type t)
Object	getTypeNode(Object node)	Get node in type graph representing the type of the input node
boolean	isInTypeGraph(Object node)	Check if a node is in the type graph
boolean	isSameScale(Object nodeA, Object nodeB)	Checks if 2 nodes are in the same scale in the type graph.
void	setDerivationMode(int mode)	Sets the current derivation mode.
HashMap<Object,Integer>	sortedTypeGraph()	Returns the ordered scale values of the nodes in the type graph

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.grogra.xl.query.Graph

canEnumerateEdges, createProducer, enumerateNodes, getRoot, getTypeRoot

Field Details

PARALLEL_MODE

public static final int PARALLEL_MODE

Bit mask for getDerivationMode() indicating a true parallel derivation mode. All rules are applied via every possible match in parallel. A single node may be deleted by several rule applications.

See Also:

• Constant Field Values

PARALLEL_NON_DETERMINISTIC_MODE

public static final int PARALLEL_NON_DETERMINISTIC_MODE

Bit mask for getDerivationMode() indicating a parallel non-deterministic derivation mode. It is ensured that a single node is deleted by at most one actual rule application. If several potential rule applications delete the same node, one actual application is chosen pseudo-randomly.

See Also:

• Constant Field Values

SEQUENTIAL_MODE

public static final int SEQUENTIAL_MODE

Bit mask for getDerivationMode() indicating a sequential derivation mode. Only one rule application is performed in a single step (as marked by derive()). If several applications are possible, only the first one is chosen.

See Also:

• Constant Field Values

SEQUENTIAL_NON_DETERMINISTIC_MODE

public static final int SEQUENTIAL_NON_DETERMINISTIC_MODE

Bit mask for getDerivationMode() indicating a sequential derivation mode. Only one rule application is performed in a single step (as marked by derive()). If several applications are possible, one is chosen pseudo-randomly.

See Also:

• Constant Field Values

MODE_MASK

public static final int MODE_MASK

Mask for getDerivationMode() to obtain the mode part (one of PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE).

See Also:

• Constant Field Values

INTERPRETIVE_FLAG

public static final int INTERPRETIVE_FLAG

Bit mask for getDerivationMode() which indicates that rules have to be applied as interpretive rules.

See Also:

• Constant Field Values

EXCLUDE_DELETED_FLAG

public static final int EXCLUDE_DELETED_FLAG

Bit mask for getDerivationMode() which indicates that nodes which were already deleted by previous rule applications of the current derivation step shall be excluded from further matches of the same step.

See Also:

• Constant Field Values

Constructor Details

Graph

public Graph(RuntimeModel model)

Method Details

getThreadData

protected Graph.ThreadData getThreadData()

createThreadData

protected Graph.ThreadData createThreadData()

getModel

public RuntimeModel getModel()

Description copied from interface: Graph

Returns this graph's run-time model.

Specified by:

getModel in interface Graph

Returns:

the run-time model

createQueue

protected abstract GraphQueue createQueue(QueueCollection qc,
 QueueDescriptor descr)

createQueryState

public Graph.QState createQueryState()

Description copied from interface: Graph

Creates a query state to be used for queries which use this graph. The returned query state has to be an instance of the type defined by CompiletimeModel.getQueryStateType() of the corresponding compile-time model.

Specified by:

createQueryState in interface Graph

Returns:

a new query state

allowNoninjectiveMatchesByDefault

public void allowNoninjectiveMatchesByDefault(boolean value)

allowNoninjectiveMatchesForNextQuery

@Deprecated
public void allowNoninjectiveMatchesForNextQuery(boolean value)

Deprecated.

getDerivationMode

public int getDerivationMode()

Returns the current derivation mode. This is a combination of one of the bit masks PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE with the flags INTERPRETIVE_FLAG and EXCLUDE_DELETED_FLAG.

Returns:

current derivation mode

See Also:

• setDerivationMode(int)

setDerivationMode

public void setDerivationMode(int mode)

Sets the current derivation mode. mode is a combination of the bit masks PARALLEL_MODE, PARALLEL_NON_DETERMINISTIC_MODE, SEQUENTIAL_MODE, SEQUENTIAL_NON_DETERMINISTIC_MODE with the flags INTERPRETIVE_FLAG and EXCLUDE_DELETED_FLAG.

Parameters:

mode - desired derivation mode

See Also:

• getDerivationMode()

derive

public long derive()

beginModifications

protected abstract void beginModifications()

commitModifications

protected abstract void commitModifications()

getQueues

public QueueCollection getQueues()

canEnumerateNodes

public boolean canEnumerateNodes(Type type)

Description copied from interface: Graph

Can nodes of the specified type be enumerated? This method returns true iff this graph can enumerate nodes of the given type using the method Graph.enumerateNodes(de.grogra.reflect.Type, de.grogra.xl.query.QueryState, int, de.grogra.xl.query.MatchConsumer, int).

Specified by:

canEnumerateNodes in interface Graph

Parameters:

type - the type of nodes

Returns:

true iff nodes of type can be enumerated

enumerateEdges

public void enumerateEdges(Object node,
 EdgeDirection dir,
 Type edgeType,
 QueryState qs,
 int toIndex,
 int patternIndex,
 Serializable pattern,
 int matchIndex,
 MatchConsumer consumer,
 int arg)

Specified by:

enumerateEdges in interface Graph

getPredecessor

protected Object getPredecessor(Object node)

createMatcher

public Pattern.Matcher createMatcher(Pattern pred,
 XBitSet providedConstants,
 IntList neededConstantsOut)

Specified by:

createMatcher in interface Graph

enumerateSpaces

public void enumerateSpaces(Object node,
 EdgeDirection dir,
 Type edgeType,
 QueryState qs,
 int toIndex,
 int patternIndex,
 Serializable pattern,
 int matchIndex,
 MatchConsumer consumer,
 int arg)

Searches the graph (with reference to the type graph) for matching multiscale patterns

Specified by:

enumerateSpaces in interface Graph

Parameters:

node - node already bound before this spacing

dir - edge direction

edgeType - class type of edge, normally int

qs - QueryState instance

pattern - edge pattern, i.e. successor, branching, refinement, etc.

consumer - CompoundPattern instance for continuing match logic

isInTypeGraph

public boolean isInTypeGraph(Object node)

Check if a node is in the type graph

Parameters:

node -

Returns:

true if input node is part of the type graph, false otherwise

sortedTypeGraph

public HashMap<Object,Integer> sortedTypeGraph()

Description copied from interface: Graph

Returns the ordered scale values of the nodes in the type graph

Specified by:

sortedTypeGraph in interface Graph

Returns:

HashMap instance containing mappings from the type graph nodes to scale values

getScaleValue

public int getScaleValue(HashMap<Object,Integer> sortedTypeGraph,
 Object node)

getTypeNode

public Object getTypeNode(Type t)

getTypeNode

public Object getTypeNode(Object node)

Get node in type graph representing the type of the input node

Parameters:

node -

Returns:

node from type graph representing type of input node

areComparableScales

public boolean areComparableScales(Object nodeA,
 Object nodeB)

isSameScale

public boolean isSameScale(Object nodeA,
 Object nodeB)

Checks if 2 nodes are in the same scale in the type graph.

Parameters:

nodeA -

nodeB -

Returns:

getMinimumEncoarseDepthDiff

public int getMinimumEncoarseDepthDiff(Object coarseNode,
 Object fineNode)

Returns the length of the shortest encoarsement path from fineNode to coarseNode

Parameters:

coarseNode -

fineNode -

Returns:

length of path, 0 if coarseNode is not encoarsement of fineNode, -1 if error