#region License Information /* HeuristicLab * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text.RegularExpressions; namespace HeuristicLab.Grammars { public class Language : IEnumerable> { private class PartiallyProcessedSequence { private Sequence terminalSeq; private Sequence remainingSeq; private IGrammar grammar; private PartiallyProcessedSequence parent; private PartiallyProcessedSequence(PartiallyProcessedSequence parent) { this.parent = parent; this.terminalSeq = new Sequence(); } public PartiallyProcessedSequence(Sequence seq, IGrammar g) { this.terminalSeq = new Sequence(); this.remainingSeq = seq; this.grammar = g; } public bool ProcessToNextNonTerminal(out ISymbol ntSymbol) { var enumerator = remainingSeq.GetEnumerator(); int i = 0; while (enumerator.MoveNext() && grammar.IsTerminal(enumerator.Current)) { terminalSeq.Add(enumerator.Current); i++; } if (enumerator.Current == null) { ntSymbol = null; return false; } else { ntSymbol = enumerator.Current; remainingSeq = new Sequence(remainingSeq.Skip(i + 1)); return true; } } public PartiallyProcessedSequence CreateAlternativeSequence(Sequence seq) { var p = new PartiallyProcessedSequence(this); p.grammar = grammar; p.remainingSeq = new Sequence(seq.Concat(remainingSeq)); return p; } public Sequence GetSequence() { if (parent == null) return terminalSeq; else { return new Sequence(parent.GetSequence().Concat(terminalSeq)); } } } private class LanguageEnumerator : IEnumerator> { private IGrammar g; private IEnumerable currentSentence; private Queue queue = new Queue(); public LanguageEnumerator(IGrammar g) { this.g = g; Reset(); } public void Dispose() { // nothing to do } public bool MoveNext() { if (!queue.Any()) return false; // iterate until a sequence with only non-terminals is found do { var f = queue.Dequeue(); ISymbol ntSymbol = null; if (f.ProcessToNextNonTerminal(out ntSymbol) == true) { // find first non-terminal and create chains for each alternative foreach (var p in g.GetAlternatives(ntSymbol)) { var chain = f.CreateAlternativeSequence(p); queue.Enqueue(chain); } } else { // only terminals in the chain => return as sentence currentSentence = f.GetSequence().Select(symb => symb.Name); return true; } } while (true); } public void Reset() { queue.Clear(); foreach (var p in g.GetAlternatives(g.StartSymbol)) { queue.Enqueue(new PartiallyProcessedSequence(p, g)); } } public IEnumerable Current { get { return currentSentence; } } object IEnumerator.Current { get { return Current; } } } private readonly IGrammar grammar; public Language(IGrammar g) { this.grammar = g; } public IEnumerator> GetEnumerator() { return new LanguageEnumerator(grammar); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } }