org.eclipse.xtext.util.formallang
Class NfaUtil

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

public class NfaUtil
extends java.lang.Object

Author:
Moritz Eysholdt - Initial contribution and API

Nested Class Summary
static interface NfaUtil.BacktrackHandler<S,RESULT>
           
protected static class NfaUtil.BacktrackingItem<RESULT,S>
           
static class NfaUtil.MappedComparator<S,COMPARABLE extends java.lang.Comparable<COMPARABLE>>
           
static class NfaUtil.NFAImpl<S>
           
 
Constructor Summary
NfaUtil()
           
 
Method Summary
<S,RESULT> java.util.List<RESULT>
backtrack(Nfa<S> nfa, RESULT initial, NfaUtil.BacktrackHandler<S,RESULT> handler)
           
<S,ITERABLE extends java.lang.Iterable<? extends S>>
boolean
canReach(Nfa<S> nfa, S state, com.google.common.base.Predicate<S> matcher)
           
<S,ITERABLE extends java.lang.Iterable<? extends S>>
boolean
canReachFinalState(Nfa<S> nfa, S state)
           
<S> java.util.Set<S>
collect(Nfa<S> nfa)
           
protected
<S> void
collect(Nfa<S> nfa, S state, java.util.Set<S> visited)
           
protected
<S> void
collectDistancesForm(Nfa<S> nfa, S from, int distance, java.util.Map<S,java.lang.Integer> distances, com.google.common.base.Predicate<S> matches)
           
protected
<S> void
collectedInverseMap(Nfa<S> nfa, S state, java.util.Map<S,java.util.List<S>> inverseMap, java.util.Set<S> visited)
           
protected
<S> void
collectFollowers(Nfa<S> nfa, S owner, java.util.Set<S> result, java.util.Set<S> visited, com.google.common.base.Predicate<S> filter)
           
<SRCSTATE,DSTSTATE>
Nfa<DSTSTATE>
create(Nfa<SRCSTATE> source, NfaFactory<DSTSTATE,SRCSTATE> factory)
           
protected
<SRCSTATE,DSTSTATE>
DSTSTATE
create(Nfa<SRCSTATE> source, SRCSTATE src, NfaFactory<DSTSTATE,SRCSTATE> factory, java.util.Map<SRCSTATE,DSTSTATE> src2dst)
           
<S> java.util.Map<S,java.lang.Integer>
distanceFromStateMap(Nfa<S> nfa, com.google.common.base.Predicate<S> matches)
           
<S> java.util.Map<S,java.lang.Integer>
distanceToFinalStateMap(Nfa<S> nfa)
           
<S> java.util.Map<S,java.lang.Integer>
distanceToStateMap(Nfa<S> nfa, com.google.common.base.Predicate<S> matches)
           
<S> Nfa<S>
filter(Nfa<S> nfa, com.google.common.base.Predicate<S> filter)
           
<S> java.util.Set<S>
filterFollowers(Nfa<S> nfa, java.lang.Iterable<S> followers, com.google.common.base.Predicate<S> filter)
           
<S,ITERABLE extends java.lang.Iterable<? extends S>>
S
find(Nfa<S> nfa, java.lang.Iterable<S> starts, com.google.common.base.Predicate<S> matcher)
           
<S> S
find(Nfa<S> nfa, com.google.common.base.Predicate<S> matcher)
           
protected
<S,ITERABLE extends java.lang.Iterable<? extends S>>
S
find(Nfa<S> nfa, S state, com.google.common.base.Predicate<S> matcher, java.util.Set<S> visited)
           
<S> java.util.Set<S>
findFirst(Nfa<S> nfa, java.lang.Iterable<S> starts, com.google.common.base.Predicate<S> match)
           
<S> Nfa<S>
inverse(Nfa<S> nfa)
           
<S extends java.lang.Comparable<S>>
Nfa<S>
sort(Nfa<S> nfa)
           
<S> Nfa<S>
sort(Nfa<S> nfa, java.util.Comparator<S> comparator)
           
<S,COMP extends java.lang.Comparable<COMP>>
Nfa<S>
sort(Nfa<S> nfa, java.util.Map<S,COMP> comparator)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

NfaUtil

public NfaUtil()
Method Detail

create

protected <SRCSTATE,DSTSTATE> DSTSTATE create(Nfa<SRCSTATE> source,
                                              SRCSTATE src,
                                              NfaFactory<DSTSTATE,SRCSTATE> factory,
                                              java.util.Map<SRCSTATE,DSTSTATE> src2dst)

create

public <SRCSTATE,DSTSTATE> Nfa<DSTSTATE> create(Nfa<SRCSTATE> source,
                                                NfaFactory<DSTSTATE,SRCSTATE> factory)

inverse

public <S> Nfa<S> inverse(Nfa<S> nfa)

collectedInverseMap

protected <S> void collectedInverseMap(Nfa<S> nfa,
                                       S state,
                                       java.util.Map<S,java.util.List<S>> inverseMap,
                                       java.util.Set<S> visited)

distanceToFinalStateMap

public <S> java.util.Map<S,java.lang.Integer> distanceToFinalStateMap(Nfa<S> nfa)

distanceToStateMap

public <S> java.util.Map<S,java.lang.Integer> distanceToStateMap(Nfa<S> nfa,
                                                                 com.google.common.base.Predicate<S> matches)

distanceFromStateMap

public <S> java.util.Map<S,java.lang.Integer> distanceFromStateMap(Nfa<S> nfa,
                                                                   com.google.common.base.Predicate<S> matches)

collectDistancesForm

protected <S> void collectDistancesForm(Nfa<S> nfa,
                                        S from,
                                        int distance,
                                        java.util.Map<S,java.lang.Integer> distances,
                                        com.google.common.base.Predicate<S> matches)

backtrack

public <S,RESULT> java.util.List<RESULT> backtrack(Nfa<S> nfa,
                                                   RESULT initial,
                                                   NfaUtil.BacktrackHandler<S,RESULT> handler)

sort

public <S extends java.lang.Comparable<S>> Nfa<S> sort(Nfa<S> nfa)

sort

public <S,COMP extends java.lang.Comparable<COMP>> Nfa<S> sort(Nfa<S> nfa,
                                                               java.util.Map<S,COMP> comparator)

sort

public <S> Nfa<S> sort(Nfa<S> nfa,
                       java.util.Comparator<S> comparator)

collect

public <S> java.util.Set<S> collect(Nfa<S> nfa)

collect

protected <S> void collect(Nfa<S> nfa,
                           S state,
                           java.util.Set<S> visited)

collectFollowers

protected <S> void collectFollowers(Nfa<S> nfa,
                                    S owner,
                                    java.util.Set<S> result,
                                    java.util.Set<S> visited,
                                    com.google.common.base.Predicate<S> filter)

filter

public <S> Nfa<S> filter(Nfa<S> nfa,
                         com.google.common.base.Predicate<S> filter)

filterFollowers

public <S> java.util.Set<S> filterFollowers(Nfa<S> nfa,
                                            java.lang.Iterable<S> followers,
                                            com.google.common.base.Predicate<S> filter)

find

public <S,ITERABLE extends java.lang.Iterable<? extends S>> S find(Nfa<S> nfa,
                                                                   java.lang.Iterable<S> starts,
                                                                   com.google.common.base.Predicate<S> matcher)

canReach

public <S,ITERABLE extends java.lang.Iterable<? extends S>> boolean canReach(Nfa<S> nfa,
                                                                             S state,
                                                                             com.google.common.base.Predicate<S> matcher)

canReachFinalState

public <S,ITERABLE extends java.lang.Iterable<? extends S>> boolean canReachFinalState(Nfa<S> nfa,
                                                                                       S state)

findFirst

public <S> java.util.Set<S> findFirst(Nfa<S> nfa,
                                      java.lang.Iterable<S> starts,
                                      com.google.common.base.Predicate<S> match)

find

public <S> S find(Nfa<S> nfa,
                  com.google.common.base.Predicate<S> matcher)

find

protected <S,ITERABLE extends java.lang.Iterable<? extends S>> S find(Nfa<S> nfa,
                                                                      S state,
                                                                      com.google.common.base.Predicate<S> matcher,
                                                                      java.util.Set<S> visited)