[cp-patches] [generics] Patch: FYI: PriorityQueue

[Tom Tromey]

I'm checking this in on the generics branch.

This is a first implementation of PriorityQueue.  It is complete
untested, not even compiled yet.

This patch also fixes a couple buglets in AbstractQueue.

Tom

Index: ChangeLog
from  Tom Tromey  <address@hidden>

        * java/util/AbstractQueue.java (addAll): Return a result.
        (element): Fixed typo.
        * java/util/PriorityQueue.java: New file.

Index: java/util/AbstractQueue.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/util/Attic/AbstractQueue.java,v
retrieving revision 1.1.2.1
diff -u -r1.1.2.1 AbstractQueue.java
--- java/util/AbstractQueue.java 7 Aug 2004 20:31:55 -0000 1.1.2.1
+++ java/util/AbstractQueue.java 16 Aug 2004 19:22:17 -0000
@@ -58,8 +58,13 @@
   {
     if (c == this)
       throw new IllegalArgumentException();
+    boolean result = false;
     for (T val : c)
-      add(val);
+      {
+       if (add(val))
+         result = true;
+      }
+    return result;
   }
 
   public void clear()
@@ -68,7 +73,7 @@
       ;
   }
 
-  public t element()
+  public T element()
   {
     T result = peek();
     if (result == null)
Index: java/util/PriorityQueue.java
===================================================================
RCS file: java/util/PriorityQueue.java
diff -N java/util/PriorityQueue.java
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ java/util/PriorityQueue.java 16 Aug 2004 19:22:17 -0000
@@ -0,0 +1,324 @@
+/* PriorityQueue.java -- Unbounded priority queue
+   Copyright (C) 2004 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., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 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;
+
+/**
+ * @since 1.5
+ */
+public class PriorityQueue<E> extends AbstractQueue<E>
+{
+  private static final int DEFAULT_CAPACITY = 11;
+
+  /** 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<? extends E>)
+      {
+       SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
+       this.comparator = 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<? extends E>)
+      {
+       PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
+       this.comparator = 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)
+  {
+    this.used = 0;
+    this.storage = new E[cap];
+    this.comparator = comp;
+  }
+
+  public PriorityQueue(PriorityQueue<? extends E> c)
+  {
+    this(Math.max(1, (int) (1.1 * c.size())), 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())), 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];
+      }
+
+      void remove()
+      {
+       remove(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 = new E[2 * storage.length];
+    System.arraycopy(storage, 0, new_data, 0, storage.length);
+    storage = new_data;
+  }
+}