de.grogra.xl.impl.base
Class Graph

java.lang.Object
  extended by de.grogra.xl.impl.base.Graph
All Implemented Interfaces:
Graph, java.lang.Cloneable
Direct Known Subclasses:
GraphImpl, RGGGraph

public abstract class Graph
extends java.lang.Object
implements Graph, java.lang.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
 class Graph.QState
           
protected static class Graph.ThreadData
           
 
Field Summary
static 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 int INTERPRETIVE_FLAG
          Bit mask for getDerivationMode() which indicates that rules have to be applied as interpretive rules.
static 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 int PARALLEL_MODE
          Bit mask for getDerivationMode() indicating a true parallel derivation mode.
static int PARALLEL_NON_DETERMINISTIC_MODE
          Bit mask for getDerivationMode() indicating a parallel non-deterministic derivation mode.
static int SEQUENTIAL_MODE
          Bit mask for getDerivationMode() indicating a sequential derivation mode.
static int SEQUENTIAL_NON_DETERMINISTIC_MODE
          Bit mask for getDerivationMode() indicating a sequential derivation mode.
 
Constructor Summary
Graph(RuntimeModel model)
           
 
Method Summary
 void allowNoninjectiveMatchesByDefault(boolean value)
           
 void allowNoninjectiveMatchesForNextQuery(boolean value)
          Deprecated. 
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(java.lang.Object node, EdgeDirection dir, Type edgeType, QueryState qs, int toIndex, int patternIndex, java.io.Serializable pattern, int matchIndex, MatchConsumer consumer, int arg)
           
 int getDerivationMode()
          Returns the current derivation mode.
 RuntimeModel getModel()
          Returns this graph's run-time model.
protected  java.lang.Object getPredecessor(java.lang.Object node)
           
 QueueCollection getQueues()
           
protected  Graph.ThreadData getThreadData()
           
 void setDerivationMode(int mode)
          Sets the current derivation mode.
 
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
 

Field Detail

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

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

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

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
Constructor Detail

Graph

public Graph(RuntimeModel model)
Method Detail

allowNoninjectiveMatchesByDefault

public void allowNoninjectiveMatchesByDefault(boolean value)

allowNoninjectiveMatchesForNextQuery

@Deprecated
public void allowNoninjectiveMatchesForNextQuery(boolean value)
Deprecated. 


beginModifications

protected abstract void beginModifications()

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

commitModifications

protected abstract void commitModifications()

createMatcher

public Pattern.Matcher createMatcher(Pattern pred,
                                     XBitSet providedConstants,
                                     IntList neededConstantsOut)
Specified by:
createMatcher in interface Graph

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

createQueue

protected abstract GraphQueue createQueue(QueueCollection qc,
                                          QueueDescriptor descr)

createThreadData

protected Graph.ThreadData createThreadData()

derive

public long derive()

enumerateEdges

public void enumerateEdges(java.lang.Object node,
                           EdgeDirection dir,
                           Type edgeType,
                           QueryState qs,
                           int toIndex,
                           int patternIndex,
                           java.io.Serializable pattern,
                           int matchIndex,
                           MatchConsumer consumer,
                           int arg)
Specified by:
enumerateEdges in interface Graph

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)

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

getPredecessor

protected java.lang.Object getPredecessor(java.lang.Object node)

getQueues

public QueueCollection getQueues()

getThreadData

protected Graph.ThreadData getThreadData()

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()