//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
// PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

using System.Text;
using System.Collections;
using Ilog.Language.Util;

namespace Ilog.Language.Syntax
{
  /**
   * A state is really a set of rule items, also represented as a hash
   * table for efficient computation of the next state. The fields are:
   * <dl>
   * <dt><b>items:</b></dt>
   * <dd>the set of items comprising the state
   * </dd>
   * <dt><b>transitions:</b></dt>
   * <dd>a hash table associating the symbols after the dot in some item
   *     of this state (or the empty symbol, for any final item) to a
   *     <tt>StateTransition</tt>.
   * </dd>
   * </dl>
   *
   * @see	StateTransition
   * @version	Last modified on Fri Jun 10 02:24:39 2005 by hak
   * @author	<a href="mailto:hak@ilog.fr">Hassan A&iuml;t-Kaci</a>
   * @copyright	&copy; 2000 <a href="http://www.ilog.fr/">ILOG, S.A.</a>
   */
  internal class State : ArrayListIndexed
    {
      /**
       * Constructs a state with the grammar item of specified index as
       * seed item.
       */
      internal State (int index)
	: base(grammar.States)
        {
	  Add(grammar.GetItem(index));
	}

      /**
       * Constructs a state with the specified grammar item as seed
       * item.
       */
      internal State (Item item)
	: base(grammar.States)
        {
	  Add(item);
	}

      /**
       * Constructs a state with the specified set of grammar items as
       * seed items.
       */
      internal State (SetOf items)
	: base(grammar.States)
        {
	  Add(items);
	}

      /** The grammar this symbol belongs to. */
      private static Grammar grammar = Grammar.currentGrammar;

      /**
       * This state's set of items.
       */
      private SetOf items = new SetOf(grammar.Items);
      internal SetOf Items
        {
	  get { return items; }
	}

      /**
       * This state's set of kernel items.
       */
      private SetOf kernels = new SetOf(grammar.Items);
      internal SetOf Kernels
        {
	  get { return kernels; }
	}

      /**
       * This table records the state transition of a symbol that is an
       * item marker (which can be the empty symbol for final items).
       */
//       private Hashtable transitions = new Hashtable();
//       internal Hashtable Transitions
      private Table transitions = new Table();
      internal Table Transitions
        {
	  get { return transitions; }
	}

      /**
       * Returns the state transition associated with the specified
       * symbol.
       */
      private StateTransition GetTransition (GrammarSymbol symbol)
        {
	  return (StateTransition)transitions[symbol];
	}

      /**
       * Adds the specified item to this state.
       */
      private void Add (Item item)
        {
	  GrammarSymbol symbol = item.Marker;
	  StateTransition transition = GetTransition(symbol);
	  if (transition == null)
	    {
	      transition = new StateTransition(this,symbol,new SetOf(grammar.Items));
	      transitions[symbol] = transition;
	    }
	  transition.Items.Add(item.Index);
	  items.Add(item.Index);
	}

      /**
       * Adds the specified set of items to this state.
       */
      private void Add (SetOf items)
        {
	  foreach (Item item in items)
	    Add(item);
	}

      /**
       * Adds to this state all the necessary items that must be in its
       * LR(0) closure. An algorithm is described in the Dragon Book on page
       * 223. This is a better one, taken from the Park-Choe-Chang article.
       * It makes use of the pre-computed closure of the L-graph and thus
       * avoids repeatedly traversing the set of rules as done by the Dragon
       * Book's method. The formula is simply:
       * <pre>
       *        CLOSURE(s) = s U { C --> .W | A --> P.BS in s & B L* C }
       * </pre>
       */
      internal void Closure ()
        {
	  foreach (Item item in items)
	    {
	      GrammarSymbol marker = item.Marker;
	      if (marker is NonTerminal)
		foreach (NonTerminal n in ((NonTerminal)marker).LSet)
		  foreach (Rule rule in n.Rules)
		    Add(grammar.GetItem(rule,1));
	    }
        }


      /**
       * Compute the next state for all the entries in the transition table.
       */
      internal void ComputeNextStates ()
        {
	  foreach (StateTransition transition in transitions.Values)
	    transition.ComputeNextState();
	}

      /**
       * Extracts the kernel items from the set of items.
       */
      internal void ExtractKernels ()
        {
	  kernels = new SetOf(grammar.Items);
	  foreach (Item item in items)
	    if (item.IsKernel)
	      kernels.Add(item.Index);
	}

      /**
       * Compute the <tt>PRED</tt> relation for this state, and returns
       * <tt>true</tt> iff this made an actual change in
       * <tt>PRED(this,item)</tt> for some item.
       */
      internal bool ComputePreds ()
        {
	  bool change = false;
	  foreach (StateTransition transition in transitions.Values)
	    change |= transition.ComputePreds();
	  return change;
	}

      /**
       * Returns the next state for the given symbol, or <tt>null</tt>
       * if so such state exists.
       */
      internal State Next (GrammarSymbol symbol)
        {
	  return GetTransition(symbol).Next;
	}

      /**
       * A table associating nonterminals to their follow sets in this
       * state.
       */
      private Hashtable followTable;
      internal Hashtable FollowTable
        {
	  get { return followTable; }
	}

      /**
       * Returns the follow set for the given nonterminal in this state
       * if one has been computed; otherwise, returns the empty set.
       */
      internal SetOf Follow (NonTerminal n)
        {
	  Follow f;

	  if (followTable == null || (f=(Follow)followTable[n]) == null)
	    return new SetOf(grammar.Terminals);

	  return f.Follows;
	}

      /**
       * For the given symbol, this checks whether Follow(this,symbol)
       * already exists. If so, it returns it. If not, this creates a new
       * Follow object, records it as appropriate, and returns it.
       */
      internal Follow GetFollow (NonTerminal n)
        {
	  if (followTable == null)
	    followTable = new Hashtable();

	  Follow f = (Follow)followTable[n];

	  if (f == null)
	    {
	      f = new Follow(this,n);
	      followTable[n] = f;
	      f.Add();
	      grammar.FCount++;
	    }

	  return f;
	}

      //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

      /**
       * This records description of conflicts encountered in this state.
       */
      private ArrayList conflicts;
      internal ArrayList Conflicts
        {
	  get { return conflicts; }
	}

      /**
       * Adds the specified conflict description.
       */
      internal void AddConflict (string conflict)
        {
	  if (conflicts == null)
	    conflicts = new ArrayList(5);

	  conflicts.Add(conflict);
	}

      /**
       * Displays conflicts encountered in this state, if any.
       */
      internal void ShowConflicts ()
        {
	  if (conflicts == null)
	    return;

	  Grammar.Say("This state has conflicts:\n");
	  
	  foreach (string conflict in conflicts)
	    Grammar.Say(conflict);

	  Grammar.Say("-----------------------------");
	}

      //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

      /**
       * A list of sets of actions for dynamic operators.
       */
      private ArrayList dynamicActions = new ArrayList();
      internal ArrayList DynamicActions
        {
	  get { return dynamicActions; }
	}

      /**
       * A table recording the parsing automaton actions for this state.
       */
      private Map actionTable = new Map();
      internal Map ActionTable
        {
	  get { return actionTable; }
	  set { actionTable = value; }
	}

      /**
       * This is the index identifying this state's action table.
       */
      private int ac_index;
      internal int ActionTableIndex
        {
	  get { return ac_index; }
	  set { ac_index = value; }
	}

      /*
       * Returns the parsing action to perform upon reading the
       * specified token symbol when in this state.
       */
      internal Action GetAction (Terminal symbol)
        {
	  return (Action)actionTable[symbol];
	}

      /**
       * Sets the parsing action to perform in this state for the
       * specified token symbol.
       */
      internal void SetAction (Terminal symbol, Action action)
        {
	  actionTable[symbol] = action;
	}

      /**
       * A table recording the parsing automaton "goto" transitions from
       * this state.
       */
      private Map gotoTable = new Map();
      internal Map GotoTable
        {
	  get { return gotoTable; }
	  set { gotoTable = value; }
	}

      /**
       * This is the index identifying this state's goto table.
       */
      private int gt_index;
      internal int GotoTableIndex
        {
	  get { return gt_index; }
	  set { gt_index = value; }
	}

      /*
       * Returns the state to go to upon seeing the specified noterminal
       * symbol on the top of the stack when in this state.
       */
      internal State GetGoto (NonTerminal symbol)
        {
	  return (State)gotoTable[symbol];
	}

      /*
       * Sets the state to go to upon seeing the specified noterminal
       * symbol on the top of the stack when in this state to the
       * specified state.
       */
      internal void SetGoto (NonTerminal symbol, State next)
        {
	  gotoTable[symbol] = next;
	}

      /**
       * A help method returning a string representation of this state's
       * set of dynamic actions.
       */
      private string DynamicActionSet ()
        {
	  StringBuilder b = new StringBuilder("{");
	  int n = dynamicActions.Count;

	  for (int i=0; i<n; i++)
 	    b.Append(i+":"+Tools.Misc.ListToString((IList)dynamicActions[i]))
	     .Append(i == n-1 ? "" : ",");

	  return b.Append("}").ToString();
	}

      /**
       * Returns <tt>true</tt> iff the given <tt>object</tt> is also a
       * <tt>State</tt> and equal to this one.
       */
      public override bool Equals (object other)
        {
	  if (other is State)
	    return this.IsEqualTo((State)other);

	  return false;
	}

      /**
       * Returns <tt>true</tt> iff the given <tt>State</tt> is equal to
       * this one - <i>i.e.</i>, iff they have the same set of items.
       */
      internal bool IsEqualTo (State state)
        {
	  return items.IsEqualTo(state.items);
	}

      /**
       * Returns a hashcode for this State. It is that of the state's
       * set of items.
       */
      public override int GetHashCode ()
        {
	  return items.GetHashCode();
	}

      /**
       * Displays this state's internal properties on the grammar's
       * output.
       */
      internal void Show ()
        {
	  Grammar.NewLine();
	  Grammar.Say("=============================");
	  Grammar.Say("STATE NUMBER: "+index);
	  Grammar.Say("=============================");

	  ShowConflicts();

	  if (dynamicActions.Count != 0)
	    {
	      Grammar.Say("This state has dynamic actions:\n\t");
	      Grammar.Say(DynamicActionSet());
	      Grammar.Say("-----------------------------");
	    }

	  foreach (Item item in items)
	    {
	      Grammar.SaySome(item.ToString());
	      
	      if (item.IsKernel)
	      {
		Grammar.SaySome("\n\tPreceding states: "+item.Pred(this));
		if (item.MarkerIsNonTerminal)
		  Grammar.SaySome("\n\tFollow set: "+
				  GetFollow((NonTerminal)item.Marker).Follows);
	      }
	      
	      if (item.IsInitial)
		Grammar.SaySome("\n\tPreceding states: "+item.Pred(this));

	      if (item.IsFinal)
		Grammar.SaySome("\n\tLookahead set: "+item.GetLookaheads(this));
	      Grammar.NewLine();
	    }

	  Grammar.Say("-----------------------------");

	  foreach (StateTransition transition in transitions.Values)
	    if (!transition.Symbol.IsEmpty)
	      Grammar.Say("With " + transition.Symbol + ", go to state "
			  + transition.Next.Index);
        }
  }
}