source: branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Language.cs @ 15675

#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 <http://www.gnu.org/licenses/>.
 */
#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<IEnumerable<string>> {
    private class PartiallyProcessedSequence {
      private List<ISymbol> terminalSeq;
      private Sequence remainingSeq;
      private IGrammar grammar;

      private PartiallyProcessedSequence parent;
      private PartiallyProcessedSequence(PartiallyProcessedSequence parent) {
        this.parent = parent;
        this.terminalSeq = new List<ISymbol>();
      }

      public PartiallyProcessedSequence(Sequence seq, IGrammar g) {
        this.terminalSeq = new List<ISymbol>();
        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).ToList());
          return true;
        }
      }
      public PartiallyProcessedSequence CreateAlternativeSequence(Sequence seq) {
        var p = new PartiallyProcessedSequence(this);
        p.grammar = grammar;
        p.remainingSeq = new Sequence(seq.Concat(remainingSeq).ToList());
        return p;
      }
      public IList<ISymbol> GetSequence() {
        if (parent == null) return terminalSeq;
        else {
          return new Sequence(parent.GetSequence().Concat(terminalSeq).ToList());
        }
      }
    }

    private class LanguageEnumerator : IEnumerator<IEnumerable<string>> {
      private IGrammar g;
      private IEnumerable<string> currentSentence;
      private Queue<PartiallyProcessedSequence> queue = new Queue<PartiallyProcessedSequence>();
      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<string> Current { get { return currentSentence; } }

      object IEnumerator.Current {
        get { return Current; }
      }
    }

    private readonly IGrammar grammar;

    public Language(IGrammar g) {
      this.grammar = g;
    }

    public IEnumerator<IEnumerable<string>> GetEnumerator() {
      return new LanguageEnumerator(grammar);
    }


    IEnumerator IEnumerable.GetEnumerator() {
      return GetEnumerator();
    }
  }
}