/******************************************************************************
    Priority Queue

----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.container;
import java.util.Enumeration;

/**
PriorityQueue extends Queue since it is a queue if all priorities are equal.
A heap is used as the storage model as using a Sequence would make add
O(size) in time or remove O(size) in time.  The default add stores
objects with a user specified DefaultPriority at PriorityQueue creation time.
A new add method is provided to add objects with different priorities.

<P> Using a PriorityQueue as a Queue is relatively inefficient as both add
and remove are O(log(size)) in time instead of O(1).

@author Gunnar Gotshalks
@version 1.0 1999 Jan 16
@see SLList
@see Sequence
@see Container
*/

public class PriorityQueue extends Queue {

/**
Default constructor.  Sets the defaultPriority to 0;  The priority
comparison for larger integers to have higher priority.

@param capacity The maximum number of elements that can be stored.

@exception TooSmallException when capacity is < 2.

*/

  public PriorityQueue(int capacity) {
    if (capacity < 2) throw new TooSmallException();
//    comparison = new PriorityItemGreaterThan();
//    equalsTo = new PriorityItemEqual();
    container = new Heap(capacity, new PriorityItemGreaterThan(),
                                   new PriorityItemEqual());
    DefaultPriority = 0;
  }

/** Set all PriorityQueue parameters.

@param capacity The maximum number of elements that can be stored.

@param highNumberhighPriority Determine whether larger integers mean higher or
lower priority.  Set to True if you want larger integers to be higher priority.
Set to false if you want smaller integers to be higher priority.

@param defaultPriority Determine priority level for default add.

@exception TooSmallException when capacity is < 2.
*/

  public PriorityQueue(int capacity,
                       boolean highNumberhighPriority,
                       int defaultPriority) {
    if (capacity < 2) throw new TooSmallException();

    BinaryPredicate comparison;
    if (highNumberhighPriority) 
         comparison = new PriorityItemGreaterThan();
    else comparison = new PriorityItemLessThan();
    
    container = new Heap(capacity, comparison, new PriorityItemEqual());
    DefaultPriority = defaultPriority;
  }

/*******************************************************************************
   Defining the component objects
*******************************************************************************/
/**  The queue storage area */
  
  protected final int DefaultPriority;

/** Keep track of which serial number to use next.  Mut be defined here as
Java does not permit static variables in inner classes -- Why not, a class is
a class is a class.  Inner has only to do with scoping. */

    protected int currentSerialNumber = 0;
  
/*******************************************************************************
   Access Methods -- need to override some Queue methods as PriorityQueues deal
   with Items.
*******************************************************************************/

/** Determines whether a datum is in the tree irrespective of priority.
O(size) due to linear search.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> contains(obj) => result = true
&nbsp     not contains(obj) => result = false
</PRE>
*/

  synchronized public boolean contains(Object obj) {
    Enumeration<Object> e = elements();
    while (e.hasMoreElements()) {
      if (obj.equals(e.nextElement())) return true;
    }
    return false;
  }

/** Returns an enumerator over the contents of the queue.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/
  
  synchronized public Enumeration<Object> elements() {
    return new Enumeration<Object>() {
      private Enumeration<Object> e = container.elements();
      public boolean hasMoreElements() { return e.hasMoreElements(); }
      public Object nextElement() { return ((Item) e.nextElement()).datum; }
    };
  }

/*******************************************************************************
   Update Methods -- need to override Queue methods as PriorityQueues deal with
   Items.
*******************************************************************************/
/** Add <CODE>obj</CODE> with DefaultPriority.

<P><PRE><B>Requires:</B> size < Capacity
<B>Ensures:</B> subsequence(DefaultPriority) = subsequence(DefaultPriority) ^ obj
</PRE>

@exception ContainerFullException when container already contains Capacity
elements.
*/
 
  synchronized public void add(final Object obj) {
    container.add(new Item(obj, DefaultPriority));
  }
 

/** Add <CODE>obj</CODE> with a specific priority.

<P><PRE><B>Requires:</B> size < Capacity
<B>Ensures:</B> subsequence(priority) = subsequence(priority) ^ obj
</PRE>

@exception ContainerFullException when container already contains Capacity
elements.
*/

  synchronized public void add(final Object obj, int priority) { 
    container.add(new Item(obj, priority));
  }
  
/** Return the first element in the queue.

<P><PRE><B>Requires:</B> isEmpty = false
<B>Ensures:</B> old sequence = obj ^ sequence
</PRE>

@exception ContainerEmptyException when container is empty.
elements.
*/

  synchronized public Object remove() {
      return ((Item) (container.remove())).datum; }

/*******************************************************************************
   Object Methods -- need to override clone due to type clashes.
*******************************************************************************/

// Need to know about heap type explicitly for clone.  A default PriorityQueue
// is created first to be the same size as the source.  Then the heap variables
// are overwritten by cloning the heap.

/** Return a shallow copy of the queue.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = copy of queue
</PRE>
*/

  synchronized public Object clone() {
    int resultCapacity = ((Heap) container).capacity();
    PriorityQueue result = new PriorityQueue(resultCapacity, true, DefaultPriority);
    result.container = (Container) container.clone();
    result.currentSerialNumber = currentSerialNumber;
    return result;
  }

/*******************************************************************************
  Support classes and methods
*******************************************************************************/
/** Define an Item to store in a priority queue as it is necessary to store
a priority and serialNumber in addition to the datum. */

  protected class Item {

    protected Item(Object obj, int priority) {
      datum = obj;  this.priority = priority;
      serialNumber = currentSerialNumber++;
    }

/** Store the data to be put in the queue. */
    
    protected Object datum;

/** The priority to use.  Using high or low numbers for higher priority depends
upon how the comparison methods is programmed. */

    int priority;

/** A unique serial number for each elements.  Used to keep elements with the same
priority to the FIFO discipline.  It is the seondary key to compare on. */

    int serialNumber;

/** Create string representation of an element. */

    synchronized public String toString() {
      return "<" + datum + "," + priority + "," + serialNumber + ">";
    }

/** Items are equal if the datum and priority are the same.  The serial number
is unique for each element. */

    protected boolean equalsTo(Item otherItem) {
      return otherItem != null
             && otherItem instanceof Item
             && datum.equals(otherItem.datum)
             && priority == otherItem.priority;
    }
  }  // End class Item

////////////////////////////////
/** Special comparitor for PriorityQueue Items to compare the priority field
and if they are equal to compare the serial number.  Serial number must always
be ascending. */

  protected class PriorityItemLessThan implements BinaryPredicate{
    public final boolean execute(final Object a, final Object b) {
      if (   a == null
          || b == null
          || !(a instanceof Item)
          || !(b instanceof Item)
          || ((Item) a).priority > ((Item) b).priority ) return false;
      
      if (((Item) a).priority < ((Item) b).priority) return true;
      if (((Item) a).serialNumber < ((Item) b).serialNumber) return true;
      return false;
    }
  }

/** Special comparitor for PriorityQueue Items to compare the priority field
and if they are equal to compare the serial number.  Serial number must always
be ascending. */
  
  protected class PriorityItemGreaterThan implements BinaryPredicate {
    public final boolean execute(final Object a, final Object b) {
      if (   a == null
          || b == null
          || !(a instanceof Item)
          || !(b instanceof Item)
          || ((Item) a).priority < ((Item) b).priority ) return false;
      
      if (((Item) a).priority > ((Item) b).priority) return true;
      if (((Item) a).serialNumber < ((Item) b).serialNumber) return true;
      return false;
    }
  }

/** Items are equal if the datum and priority are the same.  The serial number
is unique for each element. */

  protected class PriorityItemEqual implements BinaryPredicate {
    public final boolean execute(final Object a, final Object b) {
      if (   a == null || b == null) return false;
      return a instanceof Item
          && b instanceof Item
          && ((Item) a).datum.equals(((Item) b).datum)
          && ((Item) a).priority == ((Item) b).priority;
    }
  }

}