package edu.vt.marian.search;

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

import edu.vt.marian.common.*;

/**
 * Provides hash table functionality for (singly-linked) weighted
 * objects keyed on FullIDs, implicitly ordered on the order in which they
 * were inserted.  This class is essentially a wrapper around
 * WtdObjTable to impose the insertion order semantics.
 * <P>
 * This method implicitly relies upon the hashCode method to be
 * defined in the object that is going to be used as a key object.
 *
 * @author Paul Mather
 * @version 1.0
 * @see edu.vt.marian.search.WtdObjTable
 * @see edu.vt.marian.common.WtdObjSingleLink
 * @see java.util.Hashtable
 * @see edu.vt.marian.common.Debug
 */
public class InsertionOrderWtdObjTable extends WtdObjTable
{
    /**
     * FullID key of the WtdObj we last inserted into the list, for
     * maintaining insertion ordering
     */
    private FullID prevKeyInserted = null;

    /**
     * FullID key of first item inserted into table, for resetting
     * order for enumerations
     */
    private FullID first = null;

    /**
     * Create an empty hash table for (singly-linked) weighted objects
     */
    public InsertionOrderWtdObjTable(Debug debug)
    {
        super(debug);
    }

    /**
     * Create an empty hash table for (singly-linked) weighted objects
     * specifying initial capacity and load factor.
     * @param initialCapacity initial size of hash table
     * @param loadFactor      occupancy threshold before growth needed
     * @param debug debugging object
     */
    public InsertionOrderWtdObjTable(int initialCapacity, float loadFactor,
				     Debug debug)
    {
        super(initialCapacity, loadFactor, debug);
    }

    /**
     * Create an empty hash table for (singly-linked) weighted objects
     * specifying initial capacity, but with default load factor.
     * @param initialCapacity initial size of hash table
     * @param debug debugging object
     */
    public InsertionOrderWtdObjTable(int initialCapacity, Debug debug)
    {
        super(initialCapacity, debug);
    }

    /**
     * Add a weighted object to the table.  This not only adds the weighted
     * object, but also makes the previously inserted weighted object
     * point to this one, to effect a linked list of weighted objects
     * in insertion order.  Note: if the weighted object is already
     * in the table, it is not "overwritten" by this one, nor is this
     * one added to the end of the ordering (it is ignored).
     * @param wtdObj weighted object to be inserted
     * @return null if the weighted object was not already present,
     * otherwise return the Object that was already there.
     */
    public Object insert( WtdObj wtdObj )
    {
	Object returnValue = null;
	WtdObjSingleLink elt, prevInsertion;
	FullID wtdObjKey;

	// Check WtdObj is valid
	if (wtdObj.isValid())
	{
	    /*
	     * We insert a new WtdObj thus:
	     * 1) Check to see if this WtdObj has already been inserted
	     * 2) If not, make a new WtdObjSingleLink whose "next" "pointer"
	     * is null and whose contents is the WtdObj passed us.
	     * 3) Insert this into the table
	     * 4) Get the item previously inserted into the table
	     * prior to this one (key stored in prevKeyInserted)
	     * 5) Set its "next" "pointer" to be the FullID of the
	     * WtdObj used in (2)
	     * 6) Update the "previously inserted" FullID key to be
	     * that used in (2), also
	     */
	    // Get (copy of) FullID of weighted object
	    wtdObjKey = wtdObj.getID();
	    // Make sure this has already not been stored in the table
	    // before proceeding
	    if (!containsKey(wtdObjKey))
	    {
		// Make new WtdObjSingleLink comprising:
		// (#key#weight#)->(null)
		elt = new WtdObjSingleLink(wtdObj, debug);
		// Insert this new element into the table
		returnValue = put(wtdObjKey, elt);
		// Now get the item we inserted last time this method was invoked
		// (if applicable) and update its "next" pointer
		if (prevKeyInserted != null)
		{
		    prevInsertion = (WtdObjSingleLink) get(prevKeyInserted);
		    if (prevInsertion == null)
		    {
			// This should not happen!!
			debug.dumpTrace("InsertionOrderWtdObjTable.insertWtdObj: " +
					"Previously inserted object has vanished " +
					"from the table!!");
		    }
		    else
		    {
			// Set the "next" "pointer" to be that of our wtdObjKey
			prevInsertion.setNext( wtdObjKey );
		    }
		}
		else
		{
		    // This was the first object inserted, so make a copy
		    // of its key
		    first = new FullID( wtdObjKey, debug );
		}
		// Set previous insertion key to that of the new
		// item inserted this time around
		prevKeyInserted = wtdObjKey;
	    }
	}
	else
	{
	    // We weren't given a valid WtdObj so complain
	    debug.dumpTrace("InsertionOrderWtdObjTable.insertWtdObj: Invalid WtdObj passed");
	}

	return returnValue;
    }

    /**
     * Return the FullID key of the start of this ordering.
     * @return copy of FullID key of the start of this ordering.
     */
    public FullID getFirstKey()
    {
	if (this.first == null)
	    return null;
	else
	    return new FullID( this.first, this.debug );
    }

    /**
     * Clear hash table.  This basically just calls the superclass
     * clear() method, but also resets prevKeyInserted
     * to null to reflect initial table status.
     * @see java.util.Hashtable
     */
    public synchronized void clear()
    {
	super.clear();
	prevKeyInserted = null;
    }

    /**
     * Return an enumeration for this InsertionOrderWtdObjTable.
     * @return enumeration for this InsertionOrderWtdObjTable
     */
    public Enumeration elements()
    {
	/**
	 * Provides an implementation of WtdObjSetEnumeration for
	 * InsertionOrderWtdObjTable in that it will return an object which
	 * then can be used as an iterator over all elements in the
	 * WtdObjTable.  The iterator starts from the first item inserted
	 * into the table.
	 * <P>
	 * This method implicitly relies upon the hashCode method to be
	 * defined in the object that is going to be used as a key object.
	 *
	 * @author Paul Mather
	 * @version 0.9
	 * @see edu.vt.marian.search.InsertionOrderWtdObjTable
	 * @see edu.vt.marian.common.WtdObjSingleLink
	 * @see java.util.Hashtable
	 * @see edu.vt.marian.common.Debug
	 */

	class InsertionOrderWtdObjTableEnum implements Enumeration
	{
	    /**
	     * nextElement item for use in Enumerations
	     */
	    private WtdObjSingleLink enum = null;

	    /**
	     * Number of elements iterated over so far
	     */
	    private int numIteratedOver = 0;

	    /**
	     * Create an enumeration over an InsertionOrderWtdObjTable
	     * initialised to the first entry in the table
	     */
	    public InsertionOrderWtdObjTableEnum()
	    {
		FullID first;
		
		// Set the starting point of our enumeration to the first item
		// of the InsertionOrderWtdObjTable
//  		first = InsertionOrderWtdObjTable.this.getFirstKey();
		first = getFirstKey();
		if (first != null)
		{
		    enum = (WtdObjSingleLink) get(first);
		    if (enum == null)
			// This should not happen!!
			debug.dumpTrace("InsertionOrderWtdObjTableEnum: " +
					"Previously inserted element has " +
					"vanished from the table!!");
		}
		else
		    // Nothing has been inserted yet
		    enum = null;
		// Reset count of number of elements returned so far
		numIteratedOver = 0;
	    }

	    /**
	     * Return true if this table enumeration has more
	     * elements, else return false.
	     * @return boolean denoting whether there are elements
	     * remaining in this table's enumeration
	     * @see java.util.Enumeration#hasMoreElements
	     */
	    public boolean hasMoreElements()
	    {
		return (enum != null);
	    }

	    /**
	     * Return the next weighted object element in this table's
	     * enumeration.  Also, set up the enum to be the next
	     * weighted object in the threaded sequence.
	     * @return Object that is the next in the sequence
	     * @see java.util.Enumeration#nextElement
	     * @exception java.util.NoSuchElementException if is no
	     * next element in the ordering
	     */
	    public synchronized Object nextElement() throws NoSuchElementException
	    {
		Object nextElt;
		FullID nextItem;

		if (enum == null)
		    throw new NoSuchElementException("Attempt to iterate past end of InsertionOrderWtdObjTable");
		else
		{
		    // Save a copy of the nextElement
		    nextElt = new WtdObj(enum.getID(),enum.getWeight(),debug);
		    // Register that we've supplied another item from this enumeration
		    numIteratedOver++;
		    // Move pointer on to next item in enumeration
		    nextItem = enum.getNext();
		    if (nextItem != null)
		    {
			enum = (WtdObjSingleLink) get(nextItem);
			if (enum == null)
			    // This should not happen!!
			    debug.dumpTrace("InsertionOrderWtdObjTable.nextElement: " +
					    "Previously inserted elements has " +
					    "vanished from the table!!");
		    }
		    else
			// End of the list...
			enum = null;
		}
		
		return nextElt;
	    }

	    /**
	     * Skip forward a given number of elements in this enumeration.
	     * @param k number of elements to skip over
	     * @exception java.util.NoSuchElementException if we skip past the
	     * end of the enumeration
	     */
	    public void skip( int k ) throws NoSuchElementException
	    {
		// Make sure a valid value for k was supplied
		if (k < 0)
		    debug.dumpTrace("InsertionOrderWtdObjTableEnum.skip: " +
				    "attempt to skip backward in enumeration");
		else
		{
		    for (int i=0; i < k; i++)
		    {
			// If we iterate past the end, the statement
			// below should throw NoSuchElementException,
			// which we do not catch here, but let
			// propagate back up the calling chain to be
			// caught elsewhere
			this.nextElement();
		    }
		}
	    }

	    /**
	     * Return the number of elements still to be iterated
	     * over.
	     * @return the exact number of elements still to be
	     * iterated over
	     */
	    public int exactNumRemaining()
	    {
		return InsertionOrderWtdObjTable.this.size() - numIteratedOver;
	    }

	    /**
	     * Return the approximate number of elements still to be
	     * iterated over.  This approximation is the same as the
	     * exact number remaining, as the value is easy to
	     * compute.
	     * @return the approximate number of elements still to be
	     * iterated over
	     */
	    public int approxNumRemaining()
	    {
		return exactNumRemaining();
	    }

	    /**
	     * Return the maximum number of elements still to be
	     * iterated over.  This is the same as the exact number
	     * remaining.
	     * @return the maximum number of elements still to be
	     * iterated over
	     */
	    public int maxNumRemaining()
	    {
		return exactNumRemaining();
	    }
	}
	
	return new InsertionOrderWtdObjTableEnum();
    }
}