001: /* Licensed to the Apache Software Foundation (ASF) under one or more
002: * contributor license agreements. See the NOTICE file distributed with
003: * this work for additional information regarding copyright ownership.
004: * The ASF licenses this file to You under the Apache License, Version 2.0
005: * (the "License"); you may not use this file except in compliance with
006: * the License. You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package java.util;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022:
023: /**
024: * PriorityQueue holds elements on a priority heap, which orders elements
025: * according to the comparator specified at construction or their natural order.
026: * If the queue uses natural order, any element that is not comparable is not
027: * permitted to insert to the queue.
028: *
029: * The least element of the specified ordering is stored at the head of the
030: * queue and the greatest element is stored at the tail of the queue.
031: *
032: * PriorityQueue is not synchronized. If multiple threads will access it
033: * concurrently, use the PriorityBlockingQueue.
034: */
035: public class PriorityQueue<E> extends AbstractQueue<E> implements
036: Serializable {
037:
038: private static final long serialVersionUID = -7720805057305804111L;
039:
040: private static final int DEFAULT_CAPACITY = 11;
041:
042: private static final double DEFAULT_INIT_CAPACITY_RATIO = 1.1;
043:
044: private static final int DEFAULT_CAPACITY_RATIO = 2;
045:
046: private int size;
047:
048: private Comparator<? super E> comparator;
049:
050: private transient E[] elements;
051:
052: /**
053: * Constructs a priority queue with the capacity of 11 and natural ordering.
054: */
055: public PriorityQueue() {
056: this (DEFAULT_CAPACITY);
057: }
058:
059: /**
060: * Constructs a priority queue with specified capacity and natural ordering.
061: *
062: * @param initialCapacity the specified capacity.
063: * @throws IllegalArgumentException if the initialCapacity is less than 1
064: */
065: public PriorityQueue(int initialCapacity) {
066: this (initialCapacity, null);
067: }
068:
069: /**
070: * Constructs a priority queue with specified capacity and comparator.
071: *
072: * @param initialCapacity the specified capacity.
073: * @param comparator the specified comparator. If it is null, the natural
074: * ordering will be used.
075: * @throws IllegalArgumentException if the initialCapacity is less than 1
076: */
077: public PriorityQueue(int initialCapacity,
078: Comparator<? super E> comparator) {
079: if (initialCapacity < 1) {
080: throw new IllegalArgumentException();
081: }
082: elements = newElementArray(initialCapacity);
083: this .comparator = comparator;
084: }
085:
086: /**
087: * Constructs a priority queue that contains the elements of a collection.
088: * The constructed priority queue has the initial capacity of 110% the
089: * collection. And the priority queue uses natural ordering to order its
090: * elements.
091: *
092: * @param c the collection whose elements will be added to the priority
093: * queue to be constructed.
094: * @throws ClassCastException if any of the elements in the collection is
095: * not comparable.
096: * @throws NullPointerExcepiton if any of the elements in the collection is
097: * null.
098: */
099: public PriorityQueue(Collection<? extends E> c) {
100: if (c instanceof PriorityQueue) {
101: getFromPriorityQueue((PriorityQueue<? extends E>) c);
102: } else if (c instanceof SortedSet) {
103: getFromSortedSet((SortedSet<? extends E>) c);
104: } else {
105: initSize(c);
106: addAll(c);
107: }
108: }
109:
110: /**
111: * Constructs a priority queue that contains the elements of another
112: * priority queue. The constructed priority queue has the initial capacity
113: * of 110% the latter one. And the two priority queue has the same
114: * comparator.
115: *
116: * @param c the priority queue whose elements will be added to the priority
117: * queue to be constructed.
118: */
119: public PriorityQueue(PriorityQueue<? extends E> c) {
120: getFromPriorityQueue(c);
121: }
122:
123: /**
124: * Constructs a priority queue that contains the elements of a sorted set.
125: * The constructed priority queue has the initial capacity of 110% the
126: * sorted set. And the priority queue has the same comparator of the sorted
127: * set.
128: *
129: * @param c the sorted set whose elements will be added to the priority
130: * queue to be constructed.
131: */
132: public PriorityQueue(SortedSet<? extends E> c) {
133: getFromSortedSet(c);
134: }
135:
136: /**
137: * Gets the iterator of the priority queue, which will not return elements
138: * in any specified ordering.
139: *
140: * @return the iterator of the priority queue.
141: */
142: @Override
143: public Iterator<E> iterator() {
144: return new PriorityIterator();
145: }
146:
147: /**
148: * Gets the size of the priority queue. If the size of the queue is greater
149: * than the Integer.MAX, then it returns Integer.MAX.
150: *
151: * @return the size of the priority queue.
152: */
153: @Override
154: public int size() {
155: return size;
156: }
157:
158: /**
159: * Removes all the elements of the priority queue.
160: */
161: @Override
162: public void clear() {
163: Arrays.fill(elements, null);
164: size = 0;
165: }
166:
167: /**
168: * Inserts the element to the priority queue.
169: *
170: * @return true
171: * @throws ClassCastException if the element cannot be compared with the
172: * elements in the priority queue using the ordering of the priority
173: * queue.
174: * @throws NullPointerExcepiton if the element is null.
175: */
176: public boolean offer(E o) {
177: if (null == o) {
178: throw new NullPointerException();
179: }
180: growToSize(size + 1);
181: elements[size] = o;
182: siftUp(size++);
183: return true;
184: }
185:
186: /**
187: * Gets and removes the head of the queue.
188: *
189: * @return the head of the queue. Null if the queue is empty.
190: */
191: public E poll() {
192: if (isEmpty()) {
193: return null;
194: }
195: E result = elements[0];
196: removeAt(0);
197: return result;
198: }
199:
200: /**
201: * Gets but not removes the head of the queue.
202: *
203: * @return the head of the queue. Null if the queue is empty.
204: */
205: public E peek() {
206: if (isEmpty()) {
207: return null;
208: }
209: return elements[0];
210: }
211:
212: /**
213: * Gets the comparator of the priority queue.
214: *
215: * @return the comparator of the priority queue. Null if the natural
216: * ordering is used.
217: */
218: public Comparator<? super E> comparator() {
219: return comparator;
220: }
221:
222: /**
223: * Removes the specified object of the priority queue.
224: *
225: * @param o the object to be removed.
226: * @return true if the object is in the priority queue, false if the object
227: * is not in the priority queue.
228: */
229: @Override
230: @SuppressWarnings("unchecked")
231: public boolean remove(Object o) {
232: if (o == null) {
233: return false;
234: }
235: int targetIndex;
236: for (targetIndex = 0; targetIndex < size; targetIndex++) {
237: if (0 == this .compare((E) o, elements[targetIndex])) {
238: break;
239: }
240: }
241: if (size == 0 || size == targetIndex) {
242: return false;
243: }
244: removeAt(targetIndex);
245: return true;
246: }
247:
248: /**
249: * Adds the specified object to the priority queue.
250: *
251: * @param o the object to be added.
252: * @return true.
253: * @throws ClassCastException if the element cannot be compared with the
254: * elements in the priority queue using the ordering of the priority
255: * queue.
256: * @throws NullPointerExcepiton if the element is null.
257: */
258: @Override
259: public boolean add(E o) {
260: return offer(o);
261: }
262:
263: private class PriorityIterator implements Iterator<E> {
264:
265: private int currentIndex = -1;
266:
267: private boolean allowRemove = false;
268:
269: public boolean hasNext() {
270: return currentIndex < size - 1;
271: }
272:
273: public E next() {
274: if (!hasNext()) {
275: throw new NoSuchElementException();
276: }
277: allowRemove = true;
278: return elements[++currentIndex];
279: }
280:
281: public void remove() {
282: if (!allowRemove) {
283: throw new IllegalStateException();
284: }
285: allowRemove = false;
286: removeAt(currentIndex--);
287: }
288: }
289:
290: @SuppressWarnings("unchecked")
291: private void readObject(ObjectInputStream in) throws IOException,
292: ClassNotFoundException {
293: in.defaultReadObject();
294: int capacity = in.readInt();
295: elements = newElementArray(capacity);
296: for (int i = 0; i < size; i++) {
297: elements[i] = (E) in.readObject();
298: }
299: }
300:
301: @SuppressWarnings("unchecked")
302: private E[] newElementArray(int capacity) {
303: return (E[]) new Object[capacity];
304: }
305:
306: private void writeObject(ObjectOutputStream out) throws IOException {
307: out.defaultWriteObject();
308: out.writeInt(elements.length);
309: for (int i = 0; i < size; i++) {
310: out.writeObject(elements[i]);
311: }
312: }
313:
314: @SuppressWarnings("unchecked")
315: private void getFromPriorityQueue(PriorityQueue<? extends E> c) {
316: initSize(c);
317: comparator = (Comparator<? super E>) c.comparator();
318: System.arraycopy(c.elements, 0, elements, 0, c.size());
319: size = c.size();
320: }
321:
322: @SuppressWarnings("unchecked")
323: private void getFromSortedSet(SortedSet<? extends E> c) {
324: initSize(c);
325: comparator = (Comparator<? super E>) c.comparator();
326: Iterator<? extends E> iter = c.iterator();
327: while (iter.hasNext()) {
328: elements[size++] = iter.next();
329: }
330: }
331:
332: private void removeAt(int index) {
333: size--;
334: elements[index] = elements[size];
335: siftDown(index);
336: elements[size] = null;
337: }
338:
339: private int compare(E o1, E o2) {
340: if (null != comparator) {
341: return comparator.compare(o1, o2);
342: }
343: return ((Comparable<? super E>) o1).compareTo(o2);
344: }
345:
346: private void siftUp(int childIndex) {
347: E target = elements[childIndex];
348: int parentIndex;
349: while (childIndex > 0) {
350: parentIndex = (childIndex - 1) / 2;
351: E parent = elements[parentIndex];
352: if (compare(parent, target) <= 0) {
353: break;
354: }
355: elements[childIndex] = parent;
356: childIndex = parentIndex;
357: }
358: elements[childIndex] = target;
359: }
360:
361: private void siftDown(int rootIndex) {
362: E target = elements[rootIndex];
363: int childIndex;
364: while ((childIndex = rootIndex * 2 + 1) < size) {
365: if (childIndex + 1 < size
366: && compare(elements[childIndex + 1],
367: elements[childIndex]) < 0) {
368: childIndex++;
369: }
370: if (compare(target, elements[childIndex]) <= 0) {
371: break;
372: }
373: elements[rootIndex] = elements[childIndex];
374: rootIndex = childIndex;
375: }
376: elements[rootIndex] = target;
377: }
378:
379: private void initSize(Collection<? extends E> c) {
380: if (null == c) {
381: throw new NullPointerException();
382: }
383: if (c.isEmpty()) {
384: elements = newElementArray(1);
385: } else {
386: int capacity = (int) Math.ceil(c.size()
387: * DEFAULT_INIT_CAPACITY_RATIO);
388: elements = newElementArray(capacity);
389: }
390: }
391:
392: private void growToSize(int size) {
393: if (size > elements.length) {
394: E[] newElements = newElementArray(size
395: * DEFAULT_CAPACITY_RATIO);
396: System.arraycopy(elements, 0, newElements, 0,
397: elements.length);
398: elements = newElements;
399: }
400: }
401: }
|