Robust/src/ClassLibrary/MGC/gnu/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   Object/*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     this.used = 0;
 112     this.storage = /*(E[])*/ new Object[cap];
 113     this.comparator = comp;
 114   }
 115
 116   public PriorityQueue(PriorityQueue/*<? extends E>*/ c)
 117   {
 118     this(Math.max(1, (int) (1.1 * c.size())),
 119         (Comparator/*<? super E>*/)c.comparator());
 120     // We can just copy the contents.
 121     System.arraycopy(c.storage, 0, storage, 0, c.storage.length);
 122   }
 123
 124   /*public PriorityQueue(SortedSet<? extends E> c)
 125   {
 126     this(Math.max(1, (int) (1.1 * c.size())),
 127          (Comparator<? super E>)c.comparator());
 128     // We can insert the elements directly, since they are sorted.
 129     int i = 0;
 130     for (E val : c)
 131       {
 132         if (val == null)
 133           throw new NullPointerException();
 134         storage[i++] = val;
 135       }
 136   }*/
 137
 138   public void clear()
 139   {
 140     //Arrays.fill(storage, null);
 141     for(int i = 0; i<storage.length; i++) {
 142       storage[i] = null;
 143     }
 144     used = 0;
 145   }
 146
 147   public Comparator/*<? super E>*/ comparator()
 148   {
 149     return comparator;
 150   }
 151
 152   public Iterator/*<E>*/ iterator()
 153   {
 154     return (Iterator)(new PriorityQueueIterator/*<E>*/(this));
 155   }
 156
 157   public boolean offer(Object/*E*/ o)
 158   {
 159     if (o == null)
 160       throw new NullPointerException();
 161
 162     int slot = findSlot(-1);
 163
 164     storage[slot] = o;
 165     ++used;
 166     bubbleUp(slot);
 167
 168     return true;
 169   }
 170
 171   public Object/*E*/ peek()
 172   {
 173     return used == 0 ? null : storage[0];
 174   }
 175
 176   public Object/*E*/ poll()
 177   {
 178     if (used == 0)
 179       return null;
 180     Object/*E*/ result = storage[0];
 181     remove(0);
 182     return result;
 183   }
 184
 185   public boolean remove(Object o)
 186   {
 187     if (o != null)
 188     {
 189       for (int i = 0; i < storage.length; ++i)
 190       {
 191         if (o.equals(storage[i]))
 192         {
 193           remove(i);
 194           return true;
 195         }
 196       }
 197     }
 198     return false;
 199   }
 200
 201   public int size()
 202   {
 203     return used;
 204   }
 205
 206   // It is more efficient to implement this locally -- less searching
 207   // for free slots.
 208   public boolean addAll(Collection/*<? extends E>*/ c)
 209   {
 210     if (c == this)
 211       throw new IllegalArgumentException();
 212
 213     int newSlot = -1;
 214     int save = used;
 215     //for (Object/*E*/ val : c)
 216     Iterator it = c.iterator();
 217     while(it.hasNext())
 218     {
 219       Object val = it.next();
 220       if (val == null)
 221         throw new NullPointerException();
 222       newSlot = findSlot(newSlot);
 223       storage[newSlot] = val;
 224       ++used;
 225       bubbleUp(newSlot);
 226     }
 227
 228     return save != used;
 229   }
 230
 231   int findSlot(int start)
 232   {
 233     int slot;
 234     if (used == storage.length)
 235     {
 236       resize();
 237       slot = used;
 238     }
 239     else
 240     {
 241       for (slot = start + 1; slot < storage.length; ++slot)
 242       {
 243         if (storage[slot] == null)
 244           break;
 245       }
 246       // We'll always find a slot.
 247     }
 248     return slot;
 249   }
 250
 251   void remove(int index)
 252   {
 253     // Remove the element at INDEX.  We do this by finding the least
 254     // child and moving it into place, then iterating until we reach
 255     // the bottom of the tree.
 256     while (storage[index] != null)
 257     {
 258       int child = 2 * index + 1;
 259
 260       // See if we went off the end.
 261       if (child >= storage.length)
 262       {
 263         storage[index] = null;
 264         break;
 265       }
 266
 267       // Find which child we want to promote.  If one is not null,
 268       // we pick it.  If both are null, it doesn't matter, we're
 269       // about to leave.  If neither is null, pick the lesser.
 270       if (child + 1 >= storage.length || storage[child + 1] == null)
 271       {
 272         // Nothing.
 273       }
 274       else if (storage[child] == null
 275           || (Collections.compare(storage[child], storage[child + 1],
 276               comparator) > 0))
 277         ++child;
 278       storage[index] = storage[child];
 279       index = child;
 280     }
 281     --used;
 282   }
 283
 284   void bubbleUp(int index)
 285   {
 286     // The element at INDEX was inserted into a blank spot.  Now move
 287     // it up the tree to its natural resting place.
 288     while (index > 0)
 289     {
 290       // This works regardless of whether we're at 2N+1 or 2N+2.
 291       int parent = (index - 1) / 2;
 292       if (Collections.compare(storage[parent], storage[index], comparator)
 293           <= 0)
 294       {
 295         // Parent is the same or smaller than this element, so the
 296         // invariant is preserved.  Note that if the new element
 297         // is smaller than the parent, then it is necessarily
 298         // smaller than the parent's other child.
 299         break;
 300       }
 301
 302       Object/*E*/ temp = storage[index];
 303       storage[index] = storage[parent];
 304       storage[parent] = temp;
 305
 306       index = parent;
 307     }
 308   }
 309
 310   void resize()
 311   {
 312     Object/*E*/[] new_data = /*(E[])*/ new Object[2 * storage.length];
 313     System.arraycopy(storage, 0, new_data, 0, storage.length);
 314     storage = new_data;
 315   }
 316 }
 317
 318 public class PriorityQueueIterator implements Iterator {
 319   int index = -1;
 320   int count = 0;
 321   PriorityQueue queue;
 322
 323   public PriorityQueueIterator(PriorityQueue queue) {
 324     this.queue = queue;
 325   }
 326
 327   public boolean hasNext()
 328   {
 329     return count < used;
 330   }
 331
 332   public Object/*E*/ next()
 333   {
 334     while (this.queue.storage[++index] == null)
 335       ;
 336
 337     ++count;
 338     return this.queue.storage[index];
 339   }
 340
 341   public void remove()
 342   {
 343     this.queue.remove(index);
 344   }
 345 }