|
|
using System.Collections.Generic;
|
|
|
using System.Linq;
|
|
|
|
|
|
namespace Implab.Automaton.RegularExpressions {
|
|
|
public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
|
|
|
|
|
|
readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
|
|
|
readonly IAlphabet<TInput> m_alphabet;
|
|
|
|
|
|
public RegularDFA(IAlphabet<TInput> alphabet) {
|
|
|
Safe.ArgumentNotNull(alphabet, "aplhabet");
|
|
|
|
|
|
m_alphabet = alphabet;
|
|
|
}
|
|
|
|
|
|
|
|
|
public IAlphabet<TInput> InputAlphabet {
|
|
|
get {
|
|
|
return m_alphabet;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public void MarkFinalState(int s, TTag[] tags) {
|
|
|
MarkFinalState(s);
|
|
|
SetStateTag(s, tags);
|
|
|
}
|
|
|
|
|
|
public void SetStateTag(int s, TTag[] tags) {
|
|
|
Safe.ArgumentNotNull(tags, "tags");
|
|
|
m_tags[s] = tags;
|
|
|
}
|
|
|
|
|
|
public TTag[] GetStateTag(int s) {
|
|
|
TTag[] tags;
|
|
|
return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
|
|
|
}
|
|
|
|
|
|
public TTag[][] CreateTagTable() {
|
|
|
var table = new TTag[StateCount][];
|
|
|
|
|
|
foreach (var pair in m_tags)
|
|
|
table[pair.Key] = pair.Value;
|
|
|
|
|
|
return table;
|
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
|
/// Optimize the specified alphabet.
|
|
|
/// </summary>
|
|
|
/// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
|
|
|
public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
|
|
|
Safe.ArgumentNotNull(alphabet, "alphabet");
|
|
|
|
|
|
var dfa = new RegularDFA<TInput, TTag>(alphabet);
|
|
|
|
|
|
var alphaMap = new Dictionary<int,int>();
|
|
|
var stateMap = new Dictionary<int,int>();
|
|
|
|
|
|
Optimize(dfa, alphaMap, stateMap);
|
|
|
|
|
|
// mark tags in the new DFA
|
|
|
foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
|
|
|
dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
|
|
|
|
|
|
// make the alphabet for the new DFA
|
|
|
// skip all unclassified symbols
|
|
|
foreach (var pair in alphaMap.Where(x => x.Value != 0))
|
|
|
alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
|
|
|
return dfa;
|
|
|
}
|
|
|
|
|
|
protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
|
|
|
var arrayComparer = new CustomEqualityComparer<TTag[]>(
|
|
|
(x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
|
|
|
x => x.Sum(it => x.GetHashCode())
|
|
|
);
|
|
|
return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
|
|
|
}
|
|
|
|
|
|
public override string ToString() {
|
|
|
var states = new MapAlphabet<string>(false, null);
|
|
|
|
|
|
for (int i = 0; i < StateCount; i++)
|
|
|
states.DefineSymbol(string.Format("s{0}", i), i);
|
|
|
|
|
|
return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize);
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
