Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.eclipse.xtext.util.formallang
Class PdaUtil

java.lang.Object
  extended by org.eclipse.xtext.util.formallang.PdaUtil

public class PdaUtil
extends java.lang.Object

Author:
Moritz Eysholdt - Initial contribution and API

Nested Class Summary
static class PdaUtil.CyclicStackItem<T>
           
static class PdaUtil.CyclicStackTraverser<S,P>
           
static class PdaUtil.HashStack<T>
           
protected static class PdaUtil.Identity<T>
           
protected static class PdaUtil.IsPop<S,P>
           
protected  class PdaUtil.StackItem<T>
           
protected  class PdaUtil.TraceItem<S,P>
           
protected static class PdaUtil.TraversalItem<S,R>
           
 
Field Summary
protected  NfaUtil nfaUtil
           
 long UNREACHABLE
           
 
Constructor Summary
PdaUtil()
           
 
Method Summary
<S,P> boolean
canReach(Pda<S,P> pda, S state, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
protected
<S,P,T,D extends Pda<S,P>>
S
clone(S state, Pda<S,P> src, D target, com.google.common.base.Function<S,T> tokens, PdaFactory<D,S,P,T> fact, PdaUtil.Identity<S> identity)
           
<S,P,E,T,D extends Pda<S,P>>
D
create(Cfg<E,T> cfg, FollowerFunction<E> ff, PdaFactory<D,S,P,? super E> fact)
           
protected
<S,P,E,T1,T2,D extends Pda<S,P>>
void
create(Cfg<E,T1> cfg, D pda, S state, E ele, java.lang.Iterable<E> followerElements, boolean canEnter, FollowerFunction<E> ff, com.google.common.base.Function<E,T2> tokens, PdaFactory<D,S,P,? super T2> fact, java.util.Map<E,S> states, java.util.Map<E,S> stops, com.google.common.collect.Multimap<E,E> callers)
           
<S,P,E,T1,T2,D extends Pda<S,P>>
D
create(Cfg<E,T1> cfg, FollowerFunction<E> ff, com.google.common.base.Function<E,T2> element2token, PdaFactory<D,S,P,? super T2> fact)
           
protected
<T> PdaUtil.StackItem<T>
createStack(java.util.Iterator<T> stack)
           
<S,P> long
distanceTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
<S,P,T,D extends Pda<S,P>>
D
expand(Pda<S,P> pda, com.google.common.base.Function<S,Pda<S,P>> expand, com.google.common.base.Function<S,T> tokens, PdaFactory<D,S,P,T> fact)
           
<S,P,R,D extends Pda<S,P>>
D
filterEdges(Pda<S,P> pda, Traverser<? super Pda<S,P>,S,R> traverser, PdaFactory<D,S,P,S> factory)
           
<S,P,D extends Pda<S,P>>
D
filterOrphans(Pda<S,P> pda, PdaFactory<D,S,P,S> factory)
           
<S,P> Nfa<S>
filterUnambiguousPaths(Pda<S,P> pda)
           
protected
<S,P> void
filterUnambiguousPaths(Pda<S,P> pda, S state, java.util.Map<S,java.lang.Integer> dist, java.util.Map<S,java.util.List<S>> followers)
           
protected
<S,R,P> PdaUtil.TraversalItem<S,R>
newItem(Pda<S,P> pda, NfaUtil.MappedComparator<S,java.lang.Integer> comp, java.util.Map<S,java.lang.Integer> distances, S next, R item)
           
<S,P> java.util.List<S>
shortestPathTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
<S,P> java.util.List<S>
shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches)
           
<S,P> java.util.List<S>
shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
<S,P> java.util.List<S>
shortestPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, S match)
           
<S,P> java.util.List<S>
shortestPathTo(Pda<S,P> pda, S start, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
<S,P> java.util.List<S>
shortestPathToFinalState(Pda<S,P> pda, java.util.Iterator<P> stack)
           
<S,P> java.util.List<S>
shortestStackpruningPathTo(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
<S,P> java.util.List<S>
shortestStackpruningPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches)
           
<S,P> java.util.List<S>
shortestStackpruningPathTo(Pda<S,P> pda, java.util.Iterator<P> stack, S matches)
           
<S,P> java.util.List<S>
shortestStackpruningPathTo(Pda<S,P> pda, S start, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
protected
<S,P> PdaUtil.TraceItem<S,P>
trace(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
protected
<S,P> PdaUtil.TraceItem<S,P>
traceToWithPruningStack(Pda<S,P> pda, java.lang.Iterable<S> starts, java.util.Iterator<P> stack, com.google.common.base.Predicate<S> matches, com.google.common.base.Predicate<S> canPass)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nfaUtil

@Inject
protected NfaUtil nfaUtil

UNREACHABLE

public final long UNREACHABLE
See Also:
Constant Field Values
Constructor Detail

PdaUtil

public PdaUtil()
Method Detail

canReach

public <S,P> boolean canReach(Pda<S,P> pda,
                              S state,
                              java.util.Iterator<P> stack,
                              com.google.common.base.Predicate<S> matches,
                              com.google.common.base.Predicate<S> canPass)

expand

public <S,P,T,D extends Pda<S,P>> D expand(Pda<S,P> pda,
                                           com.google.common.base.Function<S,Pda<S,P>> expand,
                                           com.google.common.base.Function<S,T> tokens,
                                           PdaFactory<D,S,P,T> fact)

clone

protected <S,P,T,D extends Pda<S,P>> S clone(S state,
                                             Pda<S,P> src,
                                             D target,
                                             com.google.common.base.Function<S,T> tokens,
                                             PdaFactory<D,S,P,T> fact,
                                             PdaUtil.Identity<S> identity)

create

public <S,P,E,T,D extends Pda<S,P>> D create(Cfg<E,T> cfg,
                                             FollowerFunction<E> ff,
                                             PdaFactory<D,S,P,? super E> fact)

create

protected <S,P,E,T1,T2,D extends Pda<S,P>> void create(Cfg<E,T1> cfg,
                                                       D pda,
                                                       S state,
                                                       E ele,
                                                       java.lang.Iterable<E> followerElements,
                                                       boolean canEnter,
                                                       FollowerFunction<E> ff,
                                                       com.google.common.base.Function<E,T2> tokens,
                                                       PdaFactory<D,S,P,? super T2> fact,
                                                       java.util.Map<E,S> states,
                                                       java.util.Map<E,S> stops,
                                                       com.google.common.collect.Multimap<E,E> callers)

create

public <S,P,E,T1,T2,D extends Pda<S,P>> D create(Cfg<E,T1> cfg,
                                                 FollowerFunction<E> ff,
                                                 com.google.common.base.Function<E,T2> element2token,
                                                 PdaFactory<D,S,P,? super T2> fact)

createStack

protected <T> PdaUtil.StackItem<T> createStack(java.util.Iterator<T> stack)

distanceTo

public <S,P> long distanceTo(Pda<S,P> pda,
                             java.lang.Iterable<S> starts,
                             java.util.Iterator<P> stack,
                             com.google.common.base.Predicate<S> matches,
                             com.google.common.base.Predicate<S> canPass)

filterEdges

public <S,P,R,D extends Pda<S,P>> D filterEdges(Pda<S,P> pda,
                                                Traverser<? super Pda<S,P>,S,R> traverser,
                                                PdaFactory<D,S,P,S> factory)

filterUnambiguousPaths

public <S,P> Nfa<S> filterUnambiguousPaths(Pda<S,P> pda)

filterUnambiguousPaths

protected <S,P> void filterUnambiguousPaths(Pda<S,P> pda,
                                            S state,
                                            java.util.Map<S,java.lang.Integer> dist,
                                            java.util.Map<S,java.util.List<S>> followers)

newItem

protected <S,R,P> PdaUtil.TraversalItem<S,R> newItem(Pda<S,P> pda,
                                                     NfaUtil.MappedComparator<S,java.lang.Integer> comp,
                                                     java.util.Map<S,java.lang.Integer> distances,
                                                     S next,
                                                     R item)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.lang.Iterable<S> starts,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              java.util.Iterator<P> stack,
                                              S match)

shortestPathTo

public <S,P> java.util.List<S> shortestPathTo(Pda<S,P> pda,
                                              S start,
                                              java.util.Iterator<P> stack,
                                              com.google.common.base.Predicate<S> matches,
                                              com.google.common.base.Predicate<S> canPass)

shortestPathToFinalState

public <S,P> java.util.List<S> shortestPathToFinalState(Pda<S,P> pda,
                                                        java.util.Iterator<P> stack)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.lang.Iterable<S> starts,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches,
                                                          com.google.common.base.Predicate<S> canPass)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          java.util.Iterator<P> stack,
                                                          S matches)

shortestStackpruningPathTo

public <S,P> java.util.List<S> shortestStackpruningPathTo(Pda<S,P> pda,
                                                          S start,
                                                          java.util.Iterator<P> stack,
                                                          com.google.common.base.Predicate<S> matches,
                                                          com.google.common.base.Predicate<S> canPass)

trace

protected <S,P> PdaUtil.TraceItem<S,P> trace(Pda<S,P> pda,
                                             java.lang.Iterable<S> starts,
                                             java.util.Iterator<P> stack,
                                             com.google.common.base.Predicate<S> matches,
                                             com.google.common.base.Predicate<S> canPass)

traceToWithPruningStack

protected <S,P> PdaUtil.TraceItem<S,P> traceToWithPruningStack(Pda<S,P> pda,
                                                               java.lang.Iterable<S> starts,
                                                               java.util.Iterator<P> stack,
                                                               com.google.common.base.Predicate<S> matches,
                                                               com.google.common.base.Predicate<S> canPass)

filterOrphans

public <S,P,D extends Pda<S,P>> D filterOrphans(Pda<S,P> pda,
                                                PdaFactory<D,S,P,S> factory)
Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD