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

using System;
using System.Collections;

using XTensions.Collections;

namespace BC.Core
{
	using Grammars;
	using Grammars.Symbols;

	namespace Automatas
	{
		[Serializable]
		public class FA
		{
			protected static Epsilon E = new Epsilon();
			protected Node s;
			[NonSerialized]
			protected int c;

			public FA (Grammar g)
			{
				First f = new First(1, g);

				c = 0;
				s = BuildNFA(g.S, g, f, new Hashtable());

				s.Singleton.LA.Add(new Sequence(Grammar.EOF));

				Channel();
			}

			public FA (FA n)
			{
				Hashtable h = new Hashtable();

				c = 0;
				s = BuildDFA(Reachable(new Set(n.S), E), n, ref h);
			}

			public Node S
			{
				get
				{
					return s;
				}
			}

			protected Node BuildNFA (NonTerminal n, Grammar g, First f, IDictionary s)
			{
				Node t = (Node)s[n];

				if (t == null)
				{
					s.Add(n, t = new Node(new Item(n)));

					foreach (Alternative a in g[n])
					{
						Production p = new Production(n, a);

						Node tn = new Node(new Item(p, 0));

						t[E].Add(tn);

						for (int i = 0; i < a.Sequence.Count; i++)
						{
							Symbol d = tn.Singleton.P.RHS.Sequence[i];

							if (d is NonTerminal)
							{
								Node tnnn = BuildNFA(d as NonTerminal, g, f, s);

								tnnn.Singleton.LA += f.Evaluate(a.Sequence.Tail(i + 1));

								tn[E].Add(tnnn);
							}

							Node tnn = new Node(new Item(p, i + 1));

							tn[d].Add(tnn);

							tn = tnn;
						}
					}
				}

				return t;
			}

			protected void Channel ()
			{
				Set N = Nodes;

				bool done;

				do
				{
					done = true;

					foreach (Node nf in N)
						foreach (Symbol k in nf.Edges)
							foreach (Node nt in nf[k])
								if ((!nt.Singleton.IsStation || nf.Singleton.IsLastNonTerminal) && !(nf.Singleton.LA - nt.Singleton.LA).Empty)
								{
									nt.Singleton.LA += nf.Singleton.LA;

									done = false;
								}
				} while (!done);
			}

			protected Node BuildDFA (Set q, FA a, ref Hashtable h)
			{
				Node r = (Node)h[q];

				if (r == null)
				{
					h[q] = r = new Node();

					foreach (Node n in q)
					{
						r.Items += n.Items;
					
						foreach (Symbol ns in n.Edges)
							if (!(ns is Epsilon))
								r[ns] = new Set();
					}

					foreach (Symbol w in r.Edges)
						if (!(w is Epsilon))
							r[w].Add(BuildDFA(Reachable(q, w), a, ref h));
				}

				return r;
			}

			public Set Reachable (Set q, Symbol s)
			{
				return EReachable(SReachable(EReachable(q), s));
			}
				
			public Set SReachable (Set q, Symbol s)
			{
				Set r = new Set();

				foreach (Node n in q)
					if (n.HasEdge(s))
						r += n[s];

				return r;
			}

			protected Set EReachable (Set q)
			{
				Set v = new Set();
				Set r = (Set)q.Clone();

				foreach (Node n in q)
					EReachable(n, ref r, ref v);

				return r;
			}

			protected void EReachable (Node n, ref Set r, ref Set v)
			{
				if (!v.Contains(n))
				{
					v.Add(n);

					foreach (Node nn in n[E])
					{
						r.Add(nn);

						EReachable(nn, ref r, ref v);
					}
				}
			}

			/*
			public Set Reachable (Set q, Symbol s)
			{
				Set r = new Set();

				foreach (Node n in q)
				{
					foreach (Item i in n.Items)
						if (i.P.LHS.Name == "_struct_declaration_list")
						{
							int k = 0;

							break;
						}

					Set v = new Set();

					if (s is Epsilon)
						r.Add(n);

					Reachable(n, s, ref r, ref v);
				}

				return r;
			}

			protected void Reachable (Node n, Symbol s, ref Set r, ref Set v)
			{
				if (!v.Contains(n))
				{
					v.Add(n);

					foreach (Symbol ns in n.Edges)
						if (ns is Epsilon || Symbol.Match(ns, s))
							foreach (Node nn in n[ns])
								if (Symbol.Match(ns, s))
								{
									r.Add(nn);

									Reachable(nn, E, ref r, ref v);
								}
								else
									Reachable(nn, s, ref r, ref v);
				}
			}
			*/

			protected void Accumulate (Node n, ref Set s)
			{
				if (!s.Contains(n))
				{
					s.Add(n);

					foreach (Symbol t in n.Edges)
						foreach (Node nn in n[t])
							Accumulate(nn, ref s);
				}
			}

			public Set Nodes
			{
				get
				{
					Set s = new Set();

					Accumulate(S, ref s);

					return s;
				}
			}

			public void Dump ()
			{
				foreach (Node n in Nodes)
				{
					Console.WriteLine("--------------------\n{0}", n);

					/*
					foreach (Symbol a in n.Edges)
					{
						Console.WriteLine("\t{0:\"}:", a);

						foreach (Node t in n[a])
							Console.WriteLine("\t\t{0}", t.Singleton);
					}
					*/
				}
			}
		}
	}
}