//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
// 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
{
  /**
   * This is the class of LR(0) items. An LR(0) item consists of a pair
   * <tt>(rule,mark)</tt> where <tt>mark</tt> is the index of the dot in
   * the RHS. Dot marks range from 1 to <tt>rule.Sequence.Length</tt>.
   *
   * @version     Last modified on Sat May 21 20:04:50 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 Item : ArrayListIndexed
    {
      /**
       * Constructs an Item with the specified reference rule, item
       * index, and mark position.
       */
      internal Item (Rule rule, int index, int mark)
	: base(grammar.Items,index)
        {
	  this.rule = rule;
	  this.mark = mark;
	}

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

      /** The rule referred to by this item. */
      private Rule rule;
      internal Rule @Rule
        {
	  get { return rule; }
	}

      /** The mark of the dot (= 1,...,length). */
      private int mark;

      /**
       * The FIRST set of the sequence that follows the symbol after the dot;
       * that is,  the value of FIRST(S) if this item is of the form A -> P.BS.
       */
      private SetOf suffixFirst;
      internal SetOf SuffixFirst
        {
	  get { return suffixFirst; }
	}

      /**
       * This is <tt>true</tt> iff this item is of the form A -> P.BS
       * and all the symbols in FIRST(S) derive the empty symbol.
       */
      private bool isNullable = true;
      internal bool IsNullable
        {
	  get { return isNullable; }
	}

      /**
       * This is <tt>true</tt> iff this item has a dot at the left end
       * of the RHS.
       */
      internal bool IsInitial
        {
	  get { return mark == 1; }
	}

      /**
       * This is <tt>true</tt> iff this item has a dot at the right end
       * of the RHS.
       */
      internal bool IsFinal
        {
	  get { return mark == rule.Sequence.Length; }
	}

      /**
       * This is <tt>true</tt> iff this item is empty production.
       */
      internal bool IsEmpty
        {
	  get { return IsInitial && IsFinal; }
	}

      /**
       * This is the grammar symbol that is immediately after the dot in
       * this item. If the dot is at the right end of the RHS, returns
       * the EMPTY symbol.
       */
      internal GrammarSymbol Marker
        {
	  get { return IsFinal ? Grammar.EMPTY : rule.Sequence[mark]; }
	}

      /**
       * This is true iff the marker is a nonterminal.
       */
      internal bool MarkerIsNonTerminal
        {
	  get { return Marker is NonTerminal; }
	}

      /**
       * This is the item obtained from this one by shifting the dot
       * over one position to the right. If the dot is at the end of the
       * rule's RHS, it is this item.
       */
      internal Item Shift
        {
	  get { return IsFinal ? this : grammar.GetItem(rule,mark+1); }
	}

      /**
       * This is the item obtained from this one by shifting the dot
       * over one position to the left. If the dot is at the beginning
       * of the rule's RHS, it is this item.
       */
      internal Item Unshift
        {
	  get { return IsInitial ? this : grammar.GetItem(rule,mark-1); }
	}

      /**
       * This is <tt>true</tt> iff this item is a kernel item (see
       * definition on page 223 of the Dragon Book).
       */
      internal bool IsKernel
        {
	  get { return IsInitial ? rule.Head.IsSTART : (mark > 1); }
	}

      /**
       * Computes the FIRST set of the suffix of this item past the
       * symbol after the dot; that is, the value of FIRST(S) if this
       * item is of the form A -> P.BS. See Dragon Book, page 189.
       */
      internal void ComputeSuffixFirst ()
        {
	  suffixFirst = new SetOf(grammar.Terminals);

	  for (int i=mark+1; i<rule.Sequence.Length; i++)
	    {
	      suffixFirst.Union(rule.Sequence[i].First);
	      isNullable &= rule.Sequence[i].IsNullable;
	      if (!isNullable)
		break;
	    }
	}

      /**
       * A table associating to a state S the set of states that lead to
       * S when following the sequence of symbols before this item's
       * dot.
       */
      private Hashtable predTable;

      /**
       * Returns the set of states in PRED(state,this) - if necessry by
       * initializing it to the empty set.
       */
      internal SetOf Pred (State state)
        {
	  if (predTable == null)
	    predTable = new Hashtable();

	  SetOf states = (SetOf)predTable[state];

	  if (states == null)
	    {
	      states = new SetOf(grammar.States);
	      predTable[state] = states;
	    }

	  return states;
	}

      /**
       * Update PRED(state,this) with from state, and returns
       * <tt>true</tt> iff this changes the previous set.
       */
      internal bool AddPred (State state, State from)
        {
	  SetOf preds = Pred(state);

	  if (preds[from])
	    return false;

	  preds.Add(from);
	  return true;
	}

      /**
       * Update PRED(state,this) with froms set of states, and returns
       * <tt>true</tt> iff this changes the previous set.
       */
      internal bool AddPred (State state, SetOf froms)
        {
	  SetOf preds = Pred(state);

	  if (froms <= preds)
	    return false;

	  preds.Union(froms);
	  return true;
	}

      /**
       * A table associating to each state in which this item occurs a
       * set of terminal symbols which are the lookahead symbols that
       * propagate to this item in that state.
       */
      private Hashtable lookaheadTable;

      /**
       * Initializes and returns this item's lookahead set in the given
       * state.
       */
      internal SetOf InitLookaheads (State state)
        {
	  if (lookaheadTable == null)
	    lookaheadTable = new Hashtable();

	  SetOf symbols = new SetOf(grammar.Terminals);
	  lookaheadTable[state] = symbols;
	  return symbols;
	}

      /**
       * Returns the set of lookahead symbols for this item in the given
       * state. NB: No check is made for null table or entry because, by
       * construction, it will always be used for a state for which this
       * is not the case.
       */
      internal SetOf GetLookaheads (State state)
        {
	  return (SetOf)lookaheadTable[state];
	}

      /**
       * Returns true iff the specified object denotes the same item.
       */
      public override bool Equals (object other)
        {
	  if (!(other is Item))
	    return false;

	  return index == ((Item)other).index;
	}

      /**
       * Returns a hash code for this Item.
       */
      public override int GetHashCode ()
        {
	  return index;
	}

      /**
       * Returns a string description for this item of the form
       * of a rule with a dot (.) indicating the mark position.
       */
      public override string ToString ()
        {
	  StringBuilder s = new StringBuilder();

	  s.Append("[")
	   .Append(rule.Index)
	   .Append("] ")
	   .Append(rule.Sequence[0])
	   .Append(" -->");
	  
	  for (int i=1; i<rule.Sequence.Length; i++)
	    s.Append(i == mark ? " . " : " ")
	     .Append(rule.Sequence[i]);

	  if (IsFinal)
	    s.Append(" .");

	  return s.ToString();
	}
  }
}