ActiveX Programming Unleashed CD/AXU.iso/jgl_1_1/jgl_1_1.exe/src/PriorityQueue.java

Java Source | 1996-09-10 | 5.6 KB | 231 lines

// Copyright(c) 1996 ObjectSpace, Inc.
// Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.

package jgl;

import java.util.Enumeration;

/**
 * A PriorityQueue is an adapter that allows you to access items in a sorted order.
 * It allows you to specify a comparator that is used to sort the items.
 * <p>
 * A PriorityQueue uses the generic heap algorithms to access its underlying Array
 * as a heap. This means that although objects will always pop in the order determined
 * by the comparator, the objects are not necessarily stored in that order within
 * the heap structure.
 * <p>
 * @see jgl.Array
 * @see jgl.Heap
 * @see jgl.examples.PriorityQueueExamples
 * @version 1.1
 * @author ObjectSpace, Inc.
 */

public class PriorityQueue implements Container
  {
  Array myArray;
  BinaryPredicate myComparator;

  /**
   * Construct myself to be an empty PriorityQueue.
   * Order elements based on their hash code.
   */
  public PriorityQueue()
    {
    this( new HashComparator() );
    }

  /**
   * Construct myself to be an empty PriorityQueue.
   * Order elements using the specified comparator.
   * @param comparator The comparator to be used for comparing elements.
   */
  public PriorityQueue( BinaryPredicate comparator )
    {
    myArray = new Array();
    myComparator = comparator;
    }

  /**
   * Construct myself to be a shallow copy of a specified PriorityQueue.
   * A shallow copy is made of its underlying sequence.
   * @param queue The instance of PriorityQueue to be copied.
   */
  public PriorityQueue( PriorityQueue queue )
    {
    myArray = (Array) queue.myArray.clone();
    myComparator = queue.myComparator;
    }

  /**
   * Return a string that describes me.
   */
  public synchronized String toString()
    {
    return "PriorityQueue( " + myArray.toString() + " )";
    }

  /**
   * Return a shallow copy of myself.
   */
  public synchronized Object clone()
    {
    return new PriorityQueue( this );
    }

  /**
   * Become a shallow copy of a specified PriorityQueue.
   * By underlying data structure becomes a shallow copy of the specified
   * PriorityQueue's data structure.
   * @param queue The PriorityQueue to be copied.
   */
  public synchronized void copy( PriorityQueue queue )
    {
    if( this != queue )
      {
      myArray = (Array) queue.myArray.clone();
      myComparator = queue.myComparator;
      }
    }

  /**
   * Return true if object is a PriorityQueue whose underlying sequence is equal to mine.
   * @param object Any object.
   */
  public boolean equals( Object object )
    {
    return object instanceof PriorityQueue && equals( (PriorityQueue) object );
    }

  /**
   * Return true if a specified PriorityQueue's sequence is equal to mine.
   * @param queue The PriorityQueue to compare myself against.
   */
  public synchronized boolean equals( PriorityQueue queue )
    {
    return myArray.equals( queue.myArray );
    }

  /**
   * Return my hash code for support of hashing containers
   */
  public int hashCode()
    {
    return Hashing.orderedHash( this );
    }

  /**
   * Return true if I contain no objects.
   */
  public boolean isEmpty()
    {
    return myArray.isEmpty();
    }

  /**
   * Return the number of objects that I contain.
   */
  public int size()
    {
    return myArray.size();
    }

  /**
   * Return the maximum number of objects that I can contain.
   */
  public int maxSize()
    {
    return myArray.maxSize();
    }

  /**
   * Remove all of my objects.
   */
  public synchronized void clear()
    {
    myArray.clear();
    }

  /**
   * Return an Enumeration of my elements.
   */
  public synchronized Enumeration elements()
    {
    return myArray.elements();
    }

  /**
   * Return an iterator positioned at my first item.
   */
  public synchronized ForwardIterator start()
    {
    return myArray.start();
    }

  /**
   * Return an iterator positioned immediately afer my last item.
   */
  public synchronized ForwardIterator finish()
    {
    return myArray.finish();
    }

  /**
   * Return my top object.
   * @exception jgl.InvalidOperationException If the PriorityQueue is empty.
   */
  public synchronized Object top()
    {
    return myArray.front();
    }

  /**
   * Push an object.  Add always works so return null.
   * @param object The object to push.
   */
  public Object add( Object object )
    {
    push( object );
    return null;
    }

  /**
   * Push an object.
   * @param object The object to push.
   */
  public synchronized void push( Object object )
    {
    myArray.pushBack( object );
    Heap.pushHeap( myArray.begin(), myArray.end(), myComparator );
    }

  /**
   * Pop the last object that was pushed onto me.
   * @exception jgl.InvalidOperationException If the PriorityQueue is empty.
   */
  public synchronized Object pop()
    {
    if( myArray.isEmpty() )
      throw new InvalidOperationException( "PriorityQueue is empty" );

    Heap.popHeap( myArray.begin(), myArray.end(), myComparator );
    return myArray.popBack();
    }

  /**
   * Swap my contents with another PriorityQueue.
   * @param queue The PriorityQueue that I will swap my contents with.
   */
  public synchronized void swap( PriorityQueue queue )
    {
    Array tmpArray = myArray;
    myArray = queue.myArray;
    queue.myArray = tmpArray;

    BinaryPredicate tmpComparator = myComparator;
    myComparator = queue.myComparator;
    queue.myComparator = tmpComparator;
    }
  }