package java_cup;

import java.util.Hashtable;
import java.util.Enumeration;

/** This class represents a set of LALR items.  For purposes of building
 *  these sets, items are considered unique only if they have unique cores
 *  (i.e., ignoring differences in their lookahead sets).<p>
 *
 *  This class provides fairly conventional set oriented operations (union,
 *  sub/super-set tests, etc.), as well as an LALR "closure" operation (see 
 *  compute_closure()).
 *
 * @see     java_cup.lalr_item
 * @see     java_cup.lalr_state
 * @version last updated: 3/6/96
 * @author  Scott Hudson
 */

public class lalr_item_set {

	/*-----------------------------------------------------------*/
	/*--- Constructor(s) ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Constructor for an empty set. */
	public lalr_item_set() {
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Constructor for cloning from another set. 
	 * @param other indicates set we should copy from.
	 */
	public lalr_item_set(lalr_item_set other)
			throws internal_error
	{
		not_null(other);
		_all = (Hashtable) other._all.clone();
	}

	/*-----------------------------------------------------------*/
	/*--- (Access to) Instance Variables ------------------------*/
	/*-----------------------------------------------------------*/

	/** A hash table to implement the set.  We store the items using themselves
	 *  as keys. 
	 */
	protected Hashtable _all = new Hashtable(11);

	/** Access to all elements of the set. */
	public Enumeration all() {
		return _all.elements();
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Cached hashcode for this set. */
	protected Integer hashcode_cache = null;

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Size of the set */
	public int size() {
		return _all.size();
	}

	/*-----------------------------------------------------------*/
	/*--- Set Operation Methods ---------------------------------*/
	/*-----------------------------------------------------------*/

	/** Does the set contain a particular item? 
	 * @param itm the item in question.
	 */
	public boolean contains(lalr_item itm) {
		return _all.containsKey(itm);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Return the item in the set matching a particular item (or null if not 
	 *  found) 
	 *  @param itm the item we are looking for.
	 */
	public lalr_item find(lalr_item itm) {
		return (lalr_item) _all.get(itm);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Is this set an (improper) subset of another? 
	 * @param other the other set in question.
	 */
	public boolean is_subset_of(lalr_item_set other) throws internal_error
	{
		not_null(other);

		/* walk down our set and make sure every element is in the other */
		for (Enumeration e = all(); e.hasMoreElements();)
			if (!other.contains((lalr_item) e.nextElement()))
				return false;

		/* they were all there */
		return true;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Is this set an (improper) superset of another? 
	 * @param other the other set in question.
	 */
	public boolean is_superset_of(lalr_item_set other) throws internal_error
	{
		not_null(other);
		return other.is_subset_of(this);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Add a singleton item, merging lookahead sets if the item is already 
	 *  part of the set.  returns the element of the set that was added or 
	 *  merged into.
	 * @param itm the item being added.
	 */
	public lalr_item add(lalr_item itm) throws internal_error
	{
		lalr_item other;

		not_null(itm);

		/* see if an item with a matching core is already there */
		other = (lalr_item) _all.get(itm);

		/* if so, merge this lookahead into the original and leave it */
		if (other != null)
		{
			other.lookahead().add(itm.lookahead());
			return other;
		}
		/* otherwise we just go in the set */
		else
		{
			/* invalidate cached hashcode */
			hashcode_cache = null;

			_all.put(itm, itm);
			return itm;
		}
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Remove a single item if it is in the set. 
	 * @param itm the item to remove.
	 */
	public void remove(lalr_item itm) throws internal_error
	{
		not_null(itm);

		/* invalidate cached hashcode */
		hashcode_cache = null;

		/* remove it from hash table implementing set */
		_all.remove(itm);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Add a complete set, merging lookaheads where items are already in 
	 *  the set 
	 * @param other the set to be added.
	 */
	public void add(lalr_item_set other) throws internal_error
	{
		not_null(other);

		/* walk down the other set and do the adds individually */
		for (Enumeration e = other.all(); e.hasMoreElements();)
			add((lalr_item) e.nextElement());
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Remove (set subtract) a complete set. 
	 * @param other the set to remove.
	 */
	public void remove(lalr_item_set other) throws internal_error
	{
		not_null(other);

		/* walk down the other set and do the removes individually */
		for (Enumeration e = other.all(); e.hasMoreElements();)
			remove((lalr_item) e.nextElement());
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Remove and return one item from the set (done in hash order). */
	public lalr_item get_one() throws internal_error
	{
		Enumeration the_set;
		lalr_item result;

		the_set = all();
		if (the_set.hasMoreElements())
		{
			result = (lalr_item) the_set.nextElement();
			remove(result);
			return result;
		}
		else
			return null;
	}

	/*-----------------------------------------------------------*/
	/*--- General Methods ---------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Helper function for null test.  Throws an interal_error exception if its
	 *  parameter is null.
	 *  @param obj the object we are testing.
	 */
	protected void not_null(Object obj) throws internal_error
	{
		if (obj == null)
			throw new internal_error("Null object used in set operation");
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Compute the closure of the set using the LALR closure rules.  Basically
	 *  for every item of the form: <pre>
	 *    [L ::= a *N alpha, l] 
	 *  </pre>
	 *  (where N is a a non terminal and alpha is a string of symbols) make 
	 *  sure there are also items of the form:  <pre>
	 *    [N ::= *beta, first(alpha l)] 
	 *  </pre>
	 *  corresponding to each production of N.  Items with identical cores but 
	 *  differing lookahead sets are merged by creating a new item with the same 
	 *  core and the union of the lookahead sets (the LA in LALR stands for 
	 *  "lookahead merged" and this is where the merger is).  This routine 
	 *  assumes that nullability and first sets have been computed for all 
	 *  productions before it is called.
	 */
	public void compute_closure()
			throws internal_error
	{
		lalr_item_set consider;
		lalr_item itm, new_itm, add_itm;
		non_terminal nt;
		terminal_set new_lookaheads;
		Enumeration p;
		production prod;
		boolean need_prop;

		/* invalidate cached hashcode */
		hashcode_cache = null;

		/* each current element needs to be considered */
		consider = new lalr_item_set(this);

		/* repeat this until there is nothing else to consider */
		while (consider.size() > 0)
		{
			/* get one item to consider */
			itm = consider.get_one();

			/* do we have a dot before a non terminal */
			nt = itm.dot_before_nt();
			if (nt != null)
			{
				/* create the lookahead set based on first after dot */
				new_lookaheads = itm.calc_lookahead(itm.lookahead());

				/* are we going to need to propagate our lookahead to new item */
				need_prop = itm.lookahead_visible();

				/* create items for each production of that non term */
				for (p = nt.productions(); p.hasMoreElements();)
				{
					prod = (production) p.nextElement();

					/* create new item with dot at start and that lookahead */
					new_itm = new lalr_item(prod,
							new terminal_set(new_lookaheads));

					/* add/merge item into the set */
					add_itm = add(new_itm);
					/* if propagation is needed link to that item */
					if (need_prop)
						itm.add_propagate(add_itm);

					/* was this was a new item*/
					if (add_itm == new_itm)
					{
						/* that may need further closure, consider it also */
						consider.add(new_itm);
					}
				}
			}
		}
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Equality comparison. */
	public boolean equals(lalr_item_set other)
	{
		if (other == null || other.size() != size())
			return false;

		/* once we know they are the same size, then improper subset does test */
		try {
			return is_subset_of(other);
		} catch (internal_error e) {
			/* can't throw error from here (because superclass doesn't) so crash */
			e.crash();
			return false;
		}

	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Generic equality comparison. */
	public boolean equals(Object other)
	{
		if (!(other instanceof lalr_item_set))
			return false;
		else
			return equals((lalr_item_set) other);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Return hash code. */
	public int hashCode()
	{
		int result = 0;
		Enumeration e;
		int cnt;

		/* only compute a new one if we don't have it cached */
		if (hashcode_cache == null)
		{
			/* hash together codes from at most first 5 elements */
			//   CSA fix! we'd *like* to hash just a few elements, but
			//   that means equal sets will have inequal hashcodes, which
			//   we're not allowed (by contract) to do.  So hash them all.
			for (e = all(), cnt = 0; e.hasMoreElements() /*&& cnt<5*/; cnt++)
				result ^= ((lalr_item) e.nextElement()).hashCode();

			hashcode_cache = new Integer(result);
		}

		return hashcode_cache.intValue();
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Convert to string. */
	public String toString()
	{
		StringBuffer result = new StringBuffer();

		result.append("{\n");
		for (Enumeration e = all(); e.hasMoreElements();)
		{
			result.append("  " + (lalr_item) e.nextElement() + "\n");
		}
		result.append("}");

		return result.toString();
	}
	/*-----------------------------------------------------------*/
}
