Source for java.util.PriorityQueue

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