/*
 * Bernoulli Compiler
 * Copyright (c) Cornell University
 * Department of Computer Science
 * 
 * Kamen Yotov (kamen@yotov.org)
 * 
 * $Source: C:/CVS/kyotov/kyotov/Research/BC/Core/Grammars/First.cs,v $
 * $Revision: 1.5 $
 * $Date: 2002/10/22 19:50:41 $
 */

using System;
using System.Collections;

using XTensions.Collections;

namespace BC.Core
{
	namespace Grammars
	{
		using Symbols;

		public class First
		{
			protected IDictionary d;
			protected Set[] f;
			protected int k;

			public First (int k, Grammar g)
			{
				this.k = k;

				d = g.NonTerminalDictionary;

				f = new Set[d.Count];

				foreach (NonTerminal n in g.NonTerminals)
				{
					int ni = Index(n);

					f[ni] = new Set();

					foreach (Alternative an in g[n])
					{
						bool good = true;

						Sequence r = an.Sequence.GetRange(0, Math.Min(an.Sequence.Count, k));

						foreach (Symbol s in r)
							good = good && !(s is NonTerminal);

						if (good)
							f[ni].Add(r);
					}
				}

				Set[] fn;
				bool done;

				do
				{
					done = true;

					fn = new Set[d.Count];

					foreach (NonTerminal n in g.NonTerminals)
					{
						int ni = Index(n);

						fn[ni] = (Set)f[ni].Clone();

						foreach (Alternative an in g[n])
							fn[ni] += Combine(an.Sequence, k);

						done = done && f[ni] == fn[ni];
					}

					f = fn;
				} while (!done);
			}

			public Set Evaluate (Sequence a)
			{
				Set r = new Set();

				foreach (object o in Combine(a, k))
					r.Add(o);

				return r;
			}

			protected int Index (NonTerminal n)
			{
				return (int)d[n];
			}

			protected Set Combine (Set s1, Set s2, int k)
			{
				Set r = new Set();

				if (Set.isNull(s1) || s1.Count == 0 || Set.isNull(s2) || s2.Count == 0)
					return r;

				foreach (Sequence l1 in s1)
					foreach (Sequence l2 in s2)
						r.Add((l1 + l2).GetRange(0, Math.Min(l1.Count + l2.Count, k)));

				return r;
			}

			protected Set Combine (Sequence a, int k)
			{
				Set r = new Set(new Sequence());

				foreach (Symbol s in a)
					if (s is NonTerminal)
						r = Combine(r, f[Index(s as NonTerminal)], k);
					else
						r = Combine(r, SingletonSet(s), k);

				return r;
			}

			protected Set SingletonSet (Symbol s)
			{
				Set r = new Set();

				Sequence l = new Sequence();

				if (!(s is Epsilon))
					l.Add(s);

				r.Add(l);

				return r;
			}
		}
	}
}