import java.util.*;/** * Randomized Meldable Priority Queue implementation based on a paper by Anna * Gambin and Adam Malinowski (1998). */public class MeldQueue<E extends Comparable<E>> { /** * Number of nodes in the tree (number of elements in the queue). */ private int size = 0; /** * Root of the tree (head of the queue). */ private MeldNode<E> root = null; /** * Random number generator used for melding subtrees. */ private Random coin = new Random(); /** * Default constructor that creates an empty <code>MeldQueue</code> instance * with a random seed for the coin flip mechanism. */ public MeldQueue() { this(1); } /** * Custom constructor that creates an empty <code>MeldQueue</code> instance * with the specified seed for the coin flip mechanism. * * @param seed the seed for the random number generator that is used for * melding subtrees */ public MeldQueue(long seed) { coin.setSeed(seed); } /** * Adds the specified element to this queue. * * For convenience, the inserted element is also returned by this method. * * @param obj the object to add * @return the element that was just added */ public E add(E obj) { MeldNode<E> branch = new MeldNode<E>(obj); root = meld(root, branch); size++; return(obj); } /** * Retrieves, but does not remove, the head of this queue, returning * <code>null</code> if this queue is empty. * * @return the element that is in front of the queue */ public E peek() { return(root.getObject()); } /** * Retrieves and removes the head of this queue, or <code>null</code> if this * queue is empty. * * @return the element that is in front of the queue */ public E poll() { if(size==0) return null; else { MeldNode<E> ori = root; root = meld(root.leftChild, root.rightChild); size--; return ori.getObject(); } } /** * Removes all elements from the priority queue. * * The queue will be empty after this call returns. */ public void clear() { size = 0; root = null; //we have infinite faith in garbage collection } /** * Returns the number of elements in the queue. * * @return the size of the queue */ public int size() { return size; } /** * Tells whether the queue is empty. * * @return <code>true</code> if the queue does not contain any elements, * <code>false</code> otherwise */ public boolean isEmpty() { return (size == 0); } /** * Melds the two trees rooted at <code>n1</code> and <code>n2</code>, and * returns the root of the resulting merged tree. * * @param n1 root of the first tree * @param n2 root of the first tree * @return the result of melding <code>n1</code> and <code>n2</code> */ private MeldNode<E> meld(MeldNode<E> n1, MeldNode<E> n2) { if(n1 == null) return n2; else if(n2 == null) return n1; else { int comp = n1.compareTo(n2); System.out.println(comp); if(comp > 0){ MeldNode<E> tmp = n1; n1 = n2; n2 = tmp; } boolean toss = coin.nextBoolean(); if(toss){ n1.leftChild = meld(n1.leftChild, n2); } else { n1.rightChild = meld(n1.rightChild, n2); } return n1; } } /** * Tree node used by the Randomized Meldable Priority Queue to store a single * element. */ private final class MeldNode<F extends Comparable<F>> implements Comparable<MeldNode<F>> { /** * The left child node of the (sub)tree rooted at this node. */ public MeldNode<F> leftChild = null; /** * The right child node of the (sub)tree rooted at this node. */ public MeldNode<F> rightChild = null; /** * The object (value) represented by this node. */ private F obj = null; /** * Default constructor that creates an <code>MeldNode</code> instance * for the given object. * * The new node will initially have no children. * * @param obj the object to store in this node */ public MeldNode(F obj) { this.obj = obj; } /** * Return the object (value) represented by this node. * * @return the contents of this node */ public F getObject() { return obj; } /** * Compares the value of this node with the value of the specified node for * order. * * @param other the node to compare with * @return a negative integer, zero, or a positive integer as this * node's value is less than, equal to, or greater than the * value of the specified node. * @see java.lang.Comparable */ public int compareTo(MeldNode<F> other) { Comparable<F> o = (Comparable<F>) other.getObject(); return o.compareTo(obj); } }}