PriorityQueue.java

/* PriorityQueue.java -- Unbounded priority queue
   Copyright (C) 2004, 2005 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.util;

import java.io.Serializable;

/**
 * @author Tom Tromey (tromey@redhat.com)
 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
 * @since 1.5
 */
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
{
  private static final int DEFAULT_CAPACITY = 11;

  private static final long serialVersionUID = -7720805057305804111L;

  /** Number of elements actually used in the storage array.  */
  int used;

  /**
   * This is the storage for the underlying binomial heap.
   * The idea is, each node is less than or equal to its children.
   * A node at index N (0-based) has two direct children, at
   * nodes 2N+1 and 2N+2.
   */
  E[] storage;

  /**
   * The comparator we're using, or null for natural ordering.
   */
  Comparator<? super E> comparator;

  public PriorityQueue()
  {
    this(DEFAULT_CAPACITY, null);
  }

  public PriorityQueue(Collection<? extends E> c)
  {
    this(Math.max(1, (int) (1.1 * c.size())), null);

    // Special case where we can find the comparator to use.
    if (c instanceof SortedSet)
      {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        // We can insert the elements directly, since they are sorted.
        int i = 0;
        for (E val : ss)
          {
            if (val == null)
              throw new NullPointerException();
            storage[i++] = val;
          }
      }
    else if (c instanceof PriorityQueue)
      {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>)pq.comparator();
        // We can just copy the contents.
        System.arraycopy(pq.storage, 0, storage, 0, pq.storage.length);
      }

    addAll(c);
  }

  public PriorityQueue(int cap)
  {
    this(cap, null);
  }

  public PriorityQueue(int cap, Comparator<? super E> comp)
  {
    if (cap < 1)
      throw new IllegalArgumentException();
    this.used = 0;
    this.storage = (E[]) new Object[cap];
    this.comparator = comp;
  }

  public PriorityQueue(PriorityQueue<? extends E> c)
  {
    this(Math.max(1, (int) (1.1 * c.size())),
         (Comparator<? super E>)c.comparator());
    // We can just copy the contents.
    System.arraycopy(c.storage, 0, storage, 0, c.storage.length);
  }

  public PriorityQueue(SortedSet<? extends E> c)
  {
    this(Math.max(1, (int) (1.1 * c.size())),
         (Comparator<? super E>)c.comparator());
    // We can insert the elements directly, since they are sorted.
    int i = 0;
    for (E val : c)
      {
        if (val == null)
          throw new NullPointerException();
        storage[i++] = val;
      }
  }

  public void clear()
  {
    Arrays.fill(storage, null);
    used = 0;
  }

  public Comparator<? super E> comparator()
  {
    return comparator;
  }

  public Iterator<E> iterator()
  {
    return new Iterator<E>()
    {
      int index = -1;
      int count = 0;

      public boolean hasNext()
      {
        return count < used;
      }

      public E next()
      {
        while (storage[++index] == null)
          ;

        ++count;
        return storage[index];
      }

      public void remove()
      {
        PriorityQueue.this.remove(index);
        index--;
      }
    };
  }

  public boolean offer(E o)
  {
    if (o == null)
      throw new NullPointerException();

    int slot = findSlot(-1);

    storage[slot] = o;
    ++used;
    bubbleUp(slot);

    return true;
  }

  public E peek()
  {
    return used == 0 ? null : storage[0];
  }

  public E poll()
  {
    if (used == 0)
      return null;
    E result = storage[0];
    remove(0);
    return result;
  }

  public boolean remove(Object o)
  {
    if (o != null)
      {
        for (int i = 0; i < storage.length; ++i)
          {
            if (o.equals(storage[i]))
              {
                remove(i);
                return true;
              }
          }
      }
    return false;
  }

  public int size()
  {
    return used;
  }

  // It is more efficient to implement this locally -- less searching
  // for free slots.
  public boolean addAll(Collection<? extends E> c)
  {
    if (c == this)
      throw new IllegalArgumentException();

    int newSlot = -1;
    int save = used;
    for (E val : c)
      {
        if (val == null)
          throw new NullPointerException();
        newSlot = findSlot(newSlot);
        storage[newSlot] = val;
        ++used;
        bubbleUp(newSlot);
      }

    return save != used;
  }

  int findSlot(int start)
  {
    int slot;
    if (used == storage.length)
      {
        resize();
        slot = used;
      }
    else
      {
        for (slot = start + 1; slot < storage.length; ++slot)
          {
            if (storage[slot] == null)
              break;
          }
        // We'll always find a slot.
      }
    return slot;
  }

  void remove(int index)
  {
    // Remove the element at INDEX.  We do this by finding the least
    // child and moving it into place, then iterating until we reach
    // the bottom of the tree.
    while (storage[index] != null)
      {
        int child = 2 * index + 1;

        // See if we went off the end.
        if (child >= storage.length)
          {
            storage[index] = null;
            break;
          }

        // Find which child we want to promote.  If one is not null,
        // we pick it.  If both are null, it doesn't matter, we're
        // about to leave.  If neither is null, pick the lesser.
        if (child + 1 >= storage.length || storage[child + 1] == null)
          {
            // Nothing.
          }
        else if (storage[child] == null
                 || (Collections.compare(storage[child], storage[child + 1],
                                         comparator) > 0))
          ++child;
        storage[index] = storage[child];
        index = child;
      }
    --used;
  }

  void bubbleUp(int index)
  {
    // The element at INDEX was inserted into a blank spot.  Now move
    // it up the tree to its natural resting place.
    while (index > 0)
      {
        // This works regardless of whether we're at 2N+1 or 2N+2.
        int parent = (index - 1) / 2;
        if (Collections.compare(storage[parent], storage[index], comparator)
            <= 0)
          {
            // Parent is the same or smaller than this element, so the
            // invariant is preserved.  Note that if the new element
            // is smaller than the parent, then it is necessarily
            // smaller than the parent's other child.
            break;
          }

        E temp = storage[index];
        storage[index] = storage[parent];
        storage[parent] = temp;

        index = parent;
      }
  }

  void resize()
  {
    E[] new_data = (E[]) new Object[2 * storage.length];
    System.arraycopy(storage, 0, new_data, 0, storage.length);
    storage = new_data;
  }
}