package edu.vt.marian.search;

import java.io.*;
import java.util.*;

import edu.vt.marian.common.*;


/**
    A Searcher that implements the maximizing union operation over WtdObjSets.
    @author	Robert France
    <p> JDK Version  : 1.1.5
	@see	WtdObjSet
	@see	Sequencer
	@see	InsertionOrderWtdObjTable
*/


public class MaxUnionSearcher implements WtdObjSet
{
	protected Debug debug;

	/**
	 * The Maximizing Union Searcher combines a collection of weighted object sets
	 *  by taking the greatest weight in any set for any common elements.  The
	 *  collection of sets is maintained
	 *  by some form of Sequencer, which is initialized before the Searcher is
	 *  constructed.
	 */
	private Sequencer seq;

	/**
	 * The linking sets in Sequencer are merged through this Table.
	 */
	private InsertionOrderWtdObjTable tbl;


	/**
    		A WtdObjSetEnumeration for a MaxUnionSearcher.

    		@author	Robert France
    		<p> JDK Version  : 1.1.5
			@see	WtdObjSetEnumeration
			@see	MaxUnionSearcher
 	*/

	public class MaxUnionSearcherWtdObjSetEnum implements WtdObjSetEnumeration
	{
		protected Enumeration tblEnum;

		/**
	 	* Keep one element cached (if any available).  This simplifies everything
	 	*  (especially sampleToWt()).
	 	*/
		protected WtdObj top;

		/**
	 	* How many elements have we seen already (used to implement *NumRemaining()).
	 	*/
		protected int numSeen;


		public MaxUnionSearcherWtdObjSetEnum()
		{
			tblEnum = tbl.elements();
			try {
				advance();	// Get a first top element (if any available).
			} catch (NoSuchElementException e)
		    	{
				top = null;
		    	}
			numSeen = 0;
		}


		public synchronized boolean hasMoreElements()
		{
			advance();
			return( tblEnum.hasMoreElements() );
		}


		public synchronized Object nextElement()
		{
			Object t = top;
			advance();
			return( t );
		}


		private void advance() throws NoSuchElementException
		{
			try
			{
				while ( ! tblEnum.hasMoreElements() )
				{
					tbl.insert( (WtdObj) seq.nextElement() );
				}
				top = (WtdObj) tblEnum.nextElement();
				numSeen++;
			} catch (NoSuchElementException e)
		    	{
				top = null;
				throw e;
		    	}
		}


		/**
			Skip forward a certain number of elements.
			@param	k	How many elements to skip.
			@exception	NoSuchElementException
		*/      
		public synchronized void skip(int k)
		{
			int i;
			for (i=0; i<k; i++)
			{
				advance();
			}
		}


		/**
			Copy a certain number of elements into a bag.
			@param	num	How many elements to copy.
			@param	sampleBag	The WtdObjBag to add elements to.
			@return	OK	There were Num elements left, and they all were copied well.
			<BR>	anything else	Problems.
			@exception	NoSuchElementException
		*/      
  		public synchronized int sample(int num, WtdObjBag sampleBag)
		{
			int i;
			int Err;
			for (i=0; i<num; i++)
			{
				advance();
				if ( (Err = sampleBag.add( top )) != ReturnCodes.OK)
					return(Err);
			}
			return( ReturnCodes.OK );
		}


		/**
			Copy into a bag all the members of this set with weights >= some weight.
			@param	minWt	The lowest weight to copy.
			@param	sampleBag	The WtdObjBag to add elements to.
			@return	OK	There were Num elements left, and they all were copied well.
			<BR>	anything else	Problems.
			@exception	NoSuchElementException
		*/      
  		public synchronized int sampleToWt(Weight minWt, WtdObjBag sampleBag)
		{
			int compareVal;
			int Err;
			while ( ( (compareVal = minWt.compare(top.getWeight())) == Weight.LOWER) ||
				(compareVal == Weight.EQUAL) )
			{
				advance();
				if ( (Err = sampleBag.add( top )) != ReturnCodes.OK)
					return(Err);
			}
			return( ReturnCodes.OK );
		}


		/**
			Return exact number of elements remaining in the parent set.
			@return	The exact number of elements still to be enumerated.
		*/      
		public synchronized int exactNumRemaining()
		{
			try
			{
				while ( true )
				{
					tbl.insert((WtdObj) seq.nextElement());
				}
			}
			finally
			{
				return( tbl.size() - numSeen );
			}
		}



		/**
			Return approximate number of elements left.
			@return	The approximate number of elements still to be enumerated.
		*/      
		public int approxNumRemaining()
		{
			return( tbl.size() + seq.expectedNumElts() - numSeen );
		}


		/**
			Return maximum number of elements left.
			@return	The maximum number of elements still to be enumerated.
		*/      
		public int maxNumRemaining()
		{
			return( tbl.size() + seq.maxNumElts() - numSeen );
		}
	}	// end MaxUnionWtdObjSet.Enum


	public MaxUnionSearcher(Sequencer sequencer, Debug d)
	{
		seq = sequencer;
		debug = d;

		tbl = new InsertionOrderWtdObjTable(seq.expectedNumElts(), d);
	}


	/**
		Create an Enumeration for this set.
	*/
	public WtdObjSetEnumeration elements()
	{
		return( new MaxUnionSearcherWtdObjSetEnum() );
	}


	/**
		Is this set empty?
		@return	true / false
	*/
	public boolean isEmpty()
	{
		return( (tbl.size() == 0) && (seq.hasMoreElements() == false) );
	}


	/**
		Is a given ID an element of this set?	
		@param	id	The (ID of the) element to be tested.
		@return	null -- the element is not in the set.
		<BR>	any valid Weight -- the element is in the set with that Weight.
	<P>
	<B>DEVEL***:</B>  If we had Sequencer.isElt(), we might be able to do this
		more efficiently.
	*/
	public Weight isElt(FullID id)
	{
		try
		{
			while ( true )
			{
				tbl.insert((WtdObj) seq.nextElement());
			}
		} catch (NoSuchElementException e) {}
		WtdObj foundObj;
		if ( (foundObj = (WtdObj) tbl.get(id)) == null)
		{
			return( Weight.bottomWt );
		}
		else
		{
			return( foundObj.getWeight() );
		}
	}


	/**
		Return the exact number of elements in this set (may be costly).
	*/
	public int exactSize()
	{
		try
		{
			while ( true )
			{
				tbl.insert((WtdObj) seq.nextElement());
			}
		} catch (NoSuchElementException e) {}
		return( tbl.size() );
	}

	/**
		Return the approximate number of elements in this set (can be cheap
			and dirty).
	*/
	public int approxSize()
	{
		return( tbl.size() + seq.expectedNumElts() );
	}

	/**
		Return the maximum number of elements in this set (can be cheap
			and dirty).
	*/
	public int maxSize()
	{
		return( tbl.size() + seq.maxNumElts() );
	}


	/**
		Return a human-readable string for this entire set (may be large).
	 */
	public String toString()
	{
		return( new String( "{" + tbl.toString() + " + " + seq.toString() + "}") );
	}	

	/**
		Return a short human-readable string that quickly describes this set.
	 */
	public String profile()
	{
		// return( new String( "{" + tbl.profile() + " + " + seq.profile() + "}") );
		return( new String( "{" + seq.profile() + "}") );
	}
};