org.eclipse.xtext.util.formallang

Class NfaUtil

java.lang.Object

org.eclipse.xtext.util.formallang.NfaUtil

public class NfaUtil
extends java.lang.Object

Author:

Moritz Eysholdt - Initial contribution and API

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	NfaUtil.BacktrackHandler<S,RESULT>
protected static class	NfaUtil.BacktrackingItem<RESULT,S>
protected static class	NfaUtil.GetToken<E,T>
static class	NfaUtil.MappedComparator<S,COMPARABLE extends java.lang.Comparable<COMPARABLE>>
static class	NfaUtil.NFAFactory<S>
static class	NfaUtil.NFAImpl<S>

Constructor Summary

Constructors

Constructor and Description
NfaUtil()

Method Summary

Methods

Modifier and Type	Method and Description
<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,P extends Nfa<DSTSTATE>> P	create(Nfa<SRCSTATE> source, NfaFactory<P,DSTSTATE,SRCSTATE> factory)
protected <SRCSTATE,DSTSTATE,P extends Nfa<DSTSTATE>> DSTSTATE	create(Nfa<SRCSTATE> source, P result, SRCSTATE src, NfaFactory<P,DSTSTATE,SRCSTATE> factory, java.util.Map<SRCSTATE,DSTSTATE> src2dst)
<E,T> Nfa<E>	create(Production<E,T> production, FollowerFunction<E> ff, E start, E stop)
<S,E,T,P extends Nfa<S>> P	create(Production<E,T> production, FollowerFunction<E> ff, NfaFactory<P,S,? super T> factory)
<S,E,T1,T2,P extends Nfa<S>> P	create(Production<E,T1> production, FollowerFunction<E> ff, com.google.common.base.Function<E,T2> tokenFunc, NfaFactory<P,S,? super T2> factory, T2 start, T2 stop)
protected <S,E,T1,T2,P extends Nfa<S>> void	create(Production<E,T1> production, P nfa, S state, java.lang.Iterable<E> followerElements, FollowerFunction<E> followerFunc, com.google.common.base.Function<E,T2> tokenFunc, NfaFactory<P,S,? super T2> factory, java.util.Map<E,S> ele2state)
<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> boolean	equalsIgnoreOrder(Nfa<S> nfa1, Nfa<S> nfa2)
<S> boolean	equalsIgnoreOrder(Nfa<S> nfa1, Nfa<S> nfa2, com.google.common.base.Function<S,? super java.lang.Object> keyFunc)
<S> boolean	equalsIgnoreOrder(Nfa<S> nfa1, Nfa<S> nfa2, S s1, S s2, com.google.common.base.Function<S,? super java.lang.Object> keyFunc, java.util.Set<S> visited)
<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> void	removeOrphans(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

backtrack

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

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)

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)

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)

collectedInverseMap

protected <S> void collectedInverseMap(Nfa<S> nfa,
                           S state,
                           java.util.Map<S,java.util.List<S>> inverseMap,
                           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)

create

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

create

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

create

public <E,T> Nfa<E> create(Production<E,T> production,
                  FollowerFunction<E> ff,
                  E start,
                  E stop)

create

public <S,E,T,P extends Nfa<S>> P create(Production<E,T> production,
                                FollowerFunction<E> ff,
                                NfaFactory<P,S,? super T> factory)

create

public <S,E,T1,T2,P extends Nfa<S>> P create(Production<E,T1> production,
                                    FollowerFunction<E> ff,
                                    com.google.common.base.Function<E,T2> tokenFunc,
                                    NfaFactory<P,S,? super T2> factory,
                                    T2 start,
                                    T2 stop)

create

protected <S,E,T1,T2,P extends Nfa<S>> void create(Production<E,T1> production,
                                       P nfa,
                                       S state,
                                       java.lang.Iterable<E> followerElements,
                                       FollowerFunction<E> followerFunc,
                                       com.google.common.base.Function<E,T2> tokenFunc,
                                       NfaFactory<P,S,? super T2> factory,
                                       java.util.Map<E,S> ele2state)

distanceFromStateMap

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

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)

equalsIgnoreOrder

public <S> boolean equalsIgnoreOrder(Nfa<S> nfa1,
                            Nfa<S> nfa2)

equalsIgnoreOrder

public <S> boolean equalsIgnoreOrder(Nfa<S> nfa1,
                            Nfa<S> nfa2,
                            com.google.common.base.Function<S,? super java.lang.Object> keyFunc)

equalsIgnoreOrder

public <S> boolean equalsIgnoreOrder(Nfa<S> nfa1,
                            Nfa<S> nfa2,
                            S s1,
                            S s2,
                            com.google.common.base.Function<S,? super java.lang.Object> keyFunc,
                            java.util.Set<S> visited)

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)

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)

findFirst

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

inverse

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

removeOrphans

public <S> void removeOrphans(Nfa<S> nfa)

sort

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

sort

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

sort

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