libjava/classpath/java/util/PriorityQueue.java

   1 /* PriorityQueue.java -- Unbounded priority queue
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package java.util;
  40
  41 import java.io.Serializable;
  42
  43 /**
  44  * @author Tom Tromey (tromey@redhat.com)
  45  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  46  * @since 1.5
  47  */
  48 public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
  49 {
  50   private static final int DEFAULT_CAPACITY = 11;
  51
  52   private static final long serialVersionUID = -7720805057305804111L;
  53
  54   /** Number of elements actually used in the storage array.  */
  55   int used;
  56
  57   /**
  58    * This is the storage for the underlying binomial heap.
  59    * The idea is, each node is less than or equal to its children.
  60    * A node at index N (0-based) has two direct children, at
  61    * nodes 2N+1 and 2N+2.
  62    */
  63   E[] storage;
  64
  65   /**
  66    * The comparator we're using, or null for natural ordering.
  67    */
  68   Comparator<? super E> comparator;
  69
  70   public PriorityQueue()
  71   {
  72     this(DEFAULT_CAPACITY, null);
  73   }
  74
  75   public PriorityQueue(Collection<? extends E> c)
  76   {
  77     this(Math.max(1, (int) (1.1 * c.size())), null);
  78
  79     // Special case where we can find the comparator to use.
  80     if (c instanceof SortedSet)
  81       {
  82         SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
  83         this.comparator = (Comparator<? super E>) ss.comparator();
  84         // We can insert the elements directly, since they are sorted.
  85         int i = 0;
  86         for (E val : ss)
  87           {
  88             if (val == null)
  89               throw new NullPointerException();
  90             storage[i++] = val;
  91           }
  92       }
  93     else if (c instanceof PriorityQueue)
  94       {
  95         PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
  96         this.comparator = (Comparator<? super E>)pq.comparator();
  97         // We can just copy the contents.
  98         System.arraycopy(pq.storage, 0, storage, 0, pq.storage.length);
  99       }
 100
 101     addAll(c);
 102   }
 103
 104   public PriorityQueue(int cap)
 105   {
 106     this(cap, null);
 107   }
 108
 109   public PriorityQueue(int cap, Comparator<? super E> comp)
 110   {
 111     if (cap < 1)
 112       throw new IllegalArgumentException();
 113     this.used = 0;
 114     this.storage = (E[]) new Object[cap];
 115     this.comparator = comp;
 116   }
 117
 118   public PriorityQueue(PriorityQueue<? extends E> c)
 119   {
 120     this(Math.max(1, (int) (1.1 * c.size())),
 121          (Comparator<? super E>)c.comparator());
 122     // We can just copy the contents.
 123     System.arraycopy(c.storage, 0, storage, 0, c.storage.length);
 124   }
 125
 126   public PriorityQueue(SortedSet<? extends E> c)
 127   {
 128     this(Math.max(1, (int) (1.1 * c.size())),
 129          (Comparator<? super E>)c.comparator());
 130     // We can insert the elements directly, since they are sorted.
 131     int i = 0;
 132     for (E val : c)
 133       {
 134         if (val == null)
 135           throw new NullPointerException();
 136         storage[i++] = val;
 137       }
 138   }
 139
 140   public void clear()
 141   {
 142     Arrays.fill(storage, null);
 143     used = 0;
 144   }
 145
 146   public Comparator<? super E> comparator()
 147   {
 148     return comparator;
 149   }
 150
 151   public Iterator<E> iterator()
 152   {
 153     return new Iterator<E>()
 154     {
 155       int index = -1;
 156       int count = 0;
 157
 158       public boolean hasNext()
 159       {
 160         return count < used;
 161       }
 162
 163       public E next()
 164       {
 165         while (storage[++index] == null)
 166           ;
 167         ++count;
 168         return storage[index];
 169       }
 170
 171       public void remove()
 172       {
 173         PriorityQueue.this.remove(index);
 174         index--;
 175       }
 176     };
 177   }
 178
 179   public boolean offer(E o)
 180   {
 181     if (o == null)
 182       throw new NullPointerException();
 183
 184     int slot = findSlot(-1);
 185
 186     storage[slot] = o;
 187     ++used;
 188     bubbleUp(slot);
 189
 190     return true;
 191   }
 192
 193   public E peek()
 194   {
 195     return used == 0 ? null : storage[0];
 196   }
 197
 198   public E poll()
 199   {
 200     if (used == 0)
 201       return null;
 202     E result = storage[0];
 203     remove(0);
 204     return result;
 205   }
 206
 207   public boolean remove(Object o)
 208   {
 209     if (o != null)
 210       {
 211         for (int i = 0; i < storage.length; ++i)
 212           {
 213             if (o.equals(storage[i]))
 214               {
 215                 remove(i);
 216                 return true;
 217               }
 218           }
 219       }
 220     return false;
 221   }
 222
 223   public int size()
 224   {
 225     return used;
 226   }
 227
 228   // It is more efficient to implement this locally -- less searching
 229   // for free slots.
 230   public boolean addAll(Collection<? extends E> c)
 231   {
 232     if (c == this)
 233       throw new IllegalArgumentException();
 234
 235     int newSlot = -1;
 236     int save = used;
 237     for (E val : c)
 238       {
 239         if (val == null)
 240           throw new NullPointerException();
 241         newSlot = findSlot(newSlot);
 242         storage[newSlot] = val;
 243         ++used;
 244         bubbleUp(newSlot);
 245       }
 246
 247     return save != used;
 248   }
 249
 250   int findSlot(int start)
 251   {
 252     int slot;
 253     if (used == storage.length)
 254       {
 255         resize();
 256         slot = used;
 257       }
 258     else
 259       {
 260         for (slot = start + 1; slot < storage.length; ++slot)
 261           {
 262             if (storage[slot] == null)
 263               break;
 264           }
 265         // We'll always find a slot.
 266       }
 267     return slot;
 268   }
 269
 270   void remove(int index)
 271   {
 272     // Remove the element at INDEX.  We do this by finding the least
 273     // child and moving it into place, then iterating until we reach
 274     // the bottom of the tree.
 275     while (storage[index] != null)
 276       {
 277         int child = 2 * index + 1;
 278
 279         // See if we went off the end.
 280         if (child >= storage.length)
 281           {
 282             storage[index] = null;
 283             break;
 284           }
 285
 286         // Find which child we want to promote.  If one is not null,
 287         // we pick it.  If both are null, it doesn't matter, we're
 288         // about to leave.  If neither is null, pick the lesser.
 289         if (child + 1 >= storage.length || storage[child + 1] == null)
 290           {
 291             // Nothing.
 292           }
 293         else if (storage[child] == null
 294                  || (Collections.compare(storage[child], storage[child + 1],
 295                                          comparator) > 0))
 296           ++child;
 297         storage[index] = storage[child];
 298         index = child;
 299       }
 300     --used;
 301   }
 302
 303   void bubbleUp(int index)
 304   {
 305     // The element at INDEX was inserted into a blank spot.  Now move
 306     // it up the tree to its natural resting place.
 307     while (index > 0)
 308       {
 309         // This works regardless of whether we're at 2N+1 or 2N+2.
 310         int parent = (index - 1) / 2;
 311         if (Collections.compare(storage[parent], storage[index], comparator)
 312             <= 0)
 313           {
 314             // Parent is the same or smaller than this element, so the
 315             // invariant is preserved.  Note that if the new element
 316             // is smaller than the parent, then it is necessarily
 317             // smaller than the parent's other child.
 318             break;
 319           }
 320
 321         E temp = storage[index];
 322         storage[index] = storage[parent];
 323         storage[parent] = temp;
 324
 325         index = parent;
 326       }
 327   }
 328
 329   void resize()
 330   {
 331     E[] new_data = (E[]) new Object[2 * storage.length];
 332     System.arraycopy(storage, 0, new_data, 0, storage.length);
 333     storage = new_data;
 334   }
 335 }