com.sun.tools.xjc.reader.gbind
Class Element

java.lang.Object
  extended by com.sun.tools.xjc.reader.gbind.Expression
      extended by com.sun.tools.xjc.reader.gbind.Element
All Implemented Interfaces:
ElementSet, Iterable<Element>
Direct Known Subclasses:
GElement, SinkNode, SourceNode

public abstract class Element
extends Expression
implements ElementSet

Expression that represents an alphabet of a regular language.

Since this package is about a regular expression over element declarations, this represents an XML element declaration (hence the name.) Element needs to be interned, meaning one Element per one tag name.

Implements ElementSet to represent a self.


Field Summary
(package private)  Set<Element> backEdges
           
(package private)  Set<Element> foreEdges
          Once we build a graph from Expression, we represent an edge e1 -> e2 by e1.foreEdges.contains(e2) and e2.backEdges.contains(e1).
(package private)  Element prevPostOrder
          Previous element in the DFS post-order traveral of the element graph.
 
Fields inherited from class com.sun.tools.xjc.reader.gbind.Expression
EPSILON
 
Fields inherited from interface com.sun.tools.xjc.reader.gbind.ElementSet
EMPTY_SET
 
Constructor Summary
protected Element()
           
 
Method Summary
 void addNext(Element element)
          For each element in this set, adds an edge to the given element.
(package private)  Element assignDfsPostOrder(Element prev)
          Traverses the Element graph with DFS and set prevPostOrder.
(package private)  void buildDAG(ElementSet incoming)
          Builds up a DAG among Elements in this expression.
 void buildStronglyConnectedComponents(List<ConnectedComponent> ccs)
          Builds a set of strongly connected components and puts them all into the given set.
(package private)  boolean checkCutSet(ConnectedComponent cc, Set<Element> visited)
          Checks if the given ConnectedComponent forms a cut-set of a graph.
 boolean contains(ElementSet rhs)
          Doesn't have to be strict (it's OK for this method to return false when it's actually true) since this is used just for optimization.
 boolean hasSelfLoop()
           
(package private)  boolean isNullable()
          True of \epsilon \in L(exp)
(package private)  boolean isSink()
          True if this Element is SinkNode.
(package private)  boolean isSource()
          True if this Element is SourceNode.
 Iterator<Element> iterator()
          Deprecated. if you statically call this method, there's something wrong.
(package private)  ElementSet lastSet()
          Computes LAST(exp)
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

foreEdges

final Set<Element> foreEdges
Once we build a graph from Expression, we represent an edge e1 -> e2 by e1.foreEdges.contains(e2) and e2.backEdges.contains(e1).


backEdges

final Set<Element> backEdges

prevPostOrder

Element prevPostOrder
Previous element in the DFS post-order traveral of the element graph.

We use prevPostOrder==null as a check if the element is visted in DFS, so this chain terminates by a self-reference, not by having null. Set in assignDfsPostOrder(Element)

Constructor Detail

Element

protected Element()
Method Detail

lastSet

ElementSet lastSet()
Description copied from class: Expression
Computes LAST(exp)

Specified by:
lastSet in class Expression

isNullable

boolean isNullable()
Description copied from class: Expression
True of \epsilon \in L(exp)

Specified by:
isNullable in class Expression

isSource

boolean isSource()
True if this Element is SourceNode.


isSink

boolean isSink()
True if this Element is SinkNode.


buildDAG

void buildDAG(ElementSet incoming)
Description copied from class: Expression
Builds up a DAG among Elements in this expression.

Specified by:
buildDAG in class Expression

addNext

public void addNext(Element element)
Description copied from interface: ElementSet
For each element in this set, adds an edge to the given element.

Specified by:
addNext in interface ElementSet

contains

public boolean contains(ElementSet rhs)
Description copied from interface: ElementSet
Doesn't have to be strict (it's OK for this method to return false when it's actually true) since this is used just for optimization. (Erring on the other side is NG)

Specified by:
contains in interface ElementSet

iterator

public Iterator<Element> iterator()
Deprecated. if you statically call this method, there's something wrong.

Just to satisfy the ElementSet contract.

Specified by:
iterator in interface Iterable<Element>

assignDfsPostOrder

Element assignDfsPostOrder(Element prev)
Traverses the Element graph with DFS and set prevPostOrder. Should be first invoked on the source node of the graph.


buildStronglyConnectedComponents

public void buildStronglyConnectedComponents(List<ConnectedComponent> ccs)
Builds a set of strongly connected components and puts them all into the given set.


hasSelfLoop

public boolean hasSelfLoop()

checkCutSet

final boolean checkCutSet(ConnectedComponent cc,
                          Set<Element> visited)
Checks if the given ConnectedComponent forms a cut-set of a graph.

Parameters:
visited - Used to keep track of visited nodes.
Returns:
true if it is indeed a cut-set. false if not.