001 /* PriorityQueue.java -- Unbounded priority queue 002 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 003 004 This file is part of GNU Classpath. 005 006 GNU Classpath is free software; you can redistribute it and/or modify 007 it under the terms of the GNU General Public License as published by 008 the Free Software Foundation; either version 2, or (at your option) 009 any later version. 010 011 GNU Classpath is distributed in the hope that it will be useful, but 012 WITHOUT ANY WARRANTY; without even the implied warranty of 013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 General Public License for more details. 015 016 You should have received a copy of the GNU General Public License 017 along with GNU Classpath; see the file COPYING. If not, write to the 018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 019 02110-1301 USA. 020 021 Linking this library statically or dynamically with other modules is 022 making a combined work based on this library. Thus, the terms and 023 conditions of the GNU General Public License cover the whole 024 combination. 025 026 As a special exception, the copyright holders of this library give you 027 permission to link this library with independent modules to produce an 028 executable, regardless of the license terms of these independent 029 modules, and to copy and distribute the resulting executable under 030 terms of your choice, provided that you also meet, for each linked 031 independent module, the terms and conditions of the license of that 032 module. An independent module is a module which is not derived from 033 or based on this library. If you modify this library, you may extend 034 this exception to your version of the library, but you are not 035 obligated to do so. If you do not wish to do so, delete this 036 exception statement from your version. */ 037 038 039 package java.util; 040 041 import java.io.Serializable; 042 043 /** 044 * @author Tom Tromey (tromey@redhat.com) 045 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 046 * @since 1.5 047 */ 048 public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable 049 { 050 private static final int DEFAULT_CAPACITY = 11; 051 052 private static final long serialVersionUID = -7720805057305804111L; 053 054 /** Number of elements actually used in the storage array. */ 055 int used; 056 057 /** 058 * This is the storage for the underlying binomial heap. 059 * The idea is, each node is less than or equal to its children. 060 * A node at index N (0-based) has two direct children, at 061 * nodes 2N+1 and 2N+2. 062 */ 063 E[] storage; 064 065 /** 066 * The comparator we're using, or null for natural ordering. 067 */ 068 Comparator<? super E> comparator; 069 070 public PriorityQueue() 071 { 072 this(DEFAULT_CAPACITY, null); 073 } 074 075 public PriorityQueue(Collection<? extends E> c) 076 { 077 this(Math.max(1, (int) (1.1 * c.size())), null); 078 079 // Special case where we can find the comparator to use. 080 if (c instanceof SortedSet) 081 { 082 SortedSet<? extends E> ss = (SortedSet<? extends E>) c; 083 this.comparator = (Comparator<? super E>) ss.comparator(); 084 // We can insert the elements directly, since they are sorted. 085 int i = 0; 086 for (E val : ss) 087 { 088 if (val == null) 089 throw new NullPointerException(); 090 storage[i++] = val; 091 } 092 } 093 else if (c instanceof PriorityQueue) 094 { 095 PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; 096 this.comparator = (Comparator<? super E>)pq.comparator(); 097 // We can just copy the contents. 098 System.arraycopy(pq.storage, 0, storage, 0, pq.storage.length); 099 } 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 168 ++count; 169 return storage[index]; 170 } 171 172 public void remove() 173 { 174 PriorityQueue.this.remove(index); 175 index--; 176 } 177 }; 178 } 179 180 public boolean offer(E o) 181 { 182 if (o == null) 183 throw new NullPointerException(); 184 185 int slot = findSlot(-1); 186 187 storage[slot] = o; 188 ++used; 189 bubbleUp(slot); 190 191 return true; 192 } 193 194 public E peek() 195 { 196 return used == 0 ? null : storage[0]; 197 } 198 199 public E poll() 200 { 201 if (used == 0) 202 return null; 203 E result = storage[0]; 204 remove(0); 205 return result; 206 } 207 208 public boolean remove(Object o) 209 { 210 if (o != null) 211 { 212 for (int i = 0; i < storage.length; ++i) 213 { 214 if (o.equals(storage[i])) 215 { 216 remove(i); 217 return true; 218 } 219 } 220 } 221 return false; 222 } 223 224 public int size() 225 { 226 return used; 227 } 228 229 // It is more efficient to implement this locally -- less searching 230 // for free slots. 231 public boolean addAll(Collection<? extends E> c) 232 { 233 if (c == this) 234 throw new IllegalArgumentException(); 235 236 int newSlot = -1; 237 int save = used; 238 for (E val : c) 239 { 240 if (val == null) 241 throw new NullPointerException(); 242 newSlot = findSlot(newSlot); 243 storage[newSlot] = val; 244 ++used; 245 bubbleUp(newSlot); 246 } 247 248 return save != used; 249 } 250 251 int findSlot(int start) 252 { 253 int slot; 254 if (used == storage.length) 255 { 256 resize(); 257 slot = used; 258 } 259 else 260 { 261 for (slot = start + 1; slot < storage.length; ++slot) 262 { 263 if (storage[slot] == null) 264 break; 265 } 266 // We'll always find a slot. 267 } 268 return slot; 269 } 270 271 void remove(int index) 272 { 273 // Remove the element at INDEX. We do this by finding the least 274 // child and moving it into place, then iterating until we reach 275 // the bottom of the tree. 276 while (storage[index] != null) 277 { 278 int child = 2 * index + 1; 279 280 // See if we went off the end. 281 if (child >= storage.length) 282 { 283 storage[index] = null; 284 break; 285 } 286 287 // Find which child we want to promote. If one is not null, 288 // we pick it. If both are null, it doesn't matter, we're 289 // about to leave. If neither is null, pick the lesser. 290 if (child + 1 >= storage.length || storage[child + 1] == null) 291 { 292 // Nothing. 293 } 294 else if (storage[child] == null 295 || (Collections.compare(storage[child], storage[child + 1], 296 comparator) > 0)) 297 ++child; 298 storage[index] = storage[child]; 299 index = child; 300 } 301 --used; 302 } 303 304 void bubbleUp(int index) 305 { 306 // The element at INDEX was inserted into a blank spot. Now move 307 // it up the tree to its natural resting place. 308 while (index > 0) 309 { 310 // This works regardless of whether we're at 2N+1 or 2N+2. 311 int parent = (index - 1) / 2; 312 if (Collections.compare(storage[parent], storage[index], comparator) 313 <= 0) 314 { 315 // Parent is the same or smaller than this element, so the 316 // invariant is preserved. Note that if the new element 317 // is smaller than the parent, then it is necessarily 318 // smaller than the parent's other child. 319 break; 320 } 321 322 E temp = storage[index]; 323 storage[index] = storage[parent]; 324 storage[parent] = temp; 325 326 index = parent; 327 } 328 } 329 330 void resize() 331 { 332 E[] new_data = (E[]) new Object[2 * storage.length]; 333 System.arraycopy(storage, 0, new_data, 0, storage.length); 334 storage = new_data; 335 } 336 }