1 | /** |
---|
2 | * Licensed to the Apache Software Foundation (ASF) under one or more |
---|
3 | * contributor license agreements. See the NOTICE file distributed with |
---|
4 | * this work for additional information regarding copyright ownership. |
---|
5 | * The ASF licenses this file to You under the Apache License, Version 2.0 |
---|
6 | * (the "License"); you may not use this file except in compliance with |
---|
7 | * the License. You may obtain a copy of the License at |
---|
8 | * |
---|
9 | * http://www.apache.org/licenses/LICENSE-2.0 |
---|
10 | * |
---|
11 | * Unless required by applicable law or agreed to in writing, software |
---|
12 | * distributed under the License is distributed on an "AS IS" BASIS, |
---|
13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
---|
14 | * See the License for the specific language governing permissions and |
---|
15 | * limitations under the License. |
---|
16 | */ |
---|
17 | |
---|
18 | package org.apache.hadoop.util; |
---|
19 | |
---|
20 | |
---|
21 | /** A PriorityQueue maintains a partial ordering of its elements such that the |
---|
22 | least element can always be found in constant time. Put()'s and pop()'s |
---|
23 | require log(size) time. */ |
---|
24 | public abstract class PriorityQueue<T> { |
---|
25 | private T[] heap; |
---|
26 | private int size; |
---|
27 | private int maxSize; |
---|
28 | |
---|
29 | /** Determines the ordering of objects in this priority queue. Subclasses |
---|
30 | must define this one method. */ |
---|
31 | protected abstract boolean lessThan(Object a, Object b); |
---|
32 | |
---|
33 | /** Subclass constructors must call this. */ |
---|
34 | @SuppressWarnings("unchecked") |
---|
35 | protected final void initialize(int maxSize) { |
---|
36 | size = 0; |
---|
37 | int heapSize = maxSize + 1; |
---|
38 | heap = (T[]) new Object[heapSize]; |
---|
39 | this.maxSize = maxSize; |
---|
40 | } |
---|
41 | |
---|
42 | /** |
---|
43 | * Adds an Object to a PriorityQueue in log(size) time. |
---|
44 | * If one tries to add more objects than maxSize from initialize |
---|
45 | * a RuntimeException (ArrayIndexOutOfBound) is thrown. |
---|
46 | */ |
---|
47 | public final void put(T element) { |
---|
48 | size++; |
---|
49 | heap[size] = element; |
---|
50 | upHeap(); |
---|
51 | } |
---|
52 | |
---|
53 | /** |
---|
54 | * Adds element to the PriorityQueue in log(size) time if either |
---|
55 | * the PriorityQueue is not full, or not lessThan(element, top()). |
---|
56 | * @param element |
---|
57 | * @return true if element is added, false otherwise. |
---|
58 | */ |
---|
59 | public boolean insert(T element){ |
---|
60 | if (size < maxSize){ |
---|
61 | put(element); |
---|
62 | return true; |
---|
63 | } |
---|
64 | else if (size > 0 && !lessThan(element, top())){ |
---|
65 | heap[1] = element; |
---|
66 | adjustTop(); |
---|
67 | return true; |
---|
68 | } |
---|
69 | else |
---|
70 | return false; |
---|
71 | } |
---|
72 | |
---|
73 | /** Returns the least element of the PriorityQueue in constant time. */ |
---|
74 | public final T top() { |
---|
75 | if (size > 0) |
---|
76 | return heap[1]; |
---|
77 | else |
---|
78 | return null; |
---|
79 | } |
---|
80 | |
---|
81 | /** Removes and returns the least element of the PriorityQueue in log(size) |
---|
82 | time. */ |
---|
83 | public final T pop() { |
---|
84 | if (size > 0) { |
---|
85 | T result = heap[1]; // save first value |
---|
86 | heap[1] = heap[size]; // move last to first |
---|
87 | heap[size] = null; // permit GC of objects |
---|
88 | size--; |
---|
89 | downHeap(); // adjust heap |
---|
90 | return result; |
---|
91 | } else |
---|
92 | return null; |
---|
93 | } |
---|
94 | |
---|
95 | /** Should be called when the Object at top changes values. Still log(n) |
---|
96 | * worst case, but it's at least twice as fast to <pre> |
---|
97 | * { pq.top().change(); pq.adjustTop(); } |
---|
98 | * </pre> instead of <pre> |
---|
99 | * { o = pq.pop(); o.change(); pq.push(o); } |
---|
100 | * </pre> |
---|
101 | */ |
---|
102 | public final void adjustTop() { |
---|
103 | downHeap(); |
---|
104 | } |
---|
105 | |
---|
106 | |
---|
107 | /** Returns the number of elements currently stored in the PriorityQueue. */ |
---|
108 | public final int size() { |
---|
109 | return size; |
---|
110 | } |
---|
111 | |
---|
112 | /** Removes all entries from the PriorityQueue. */ |
---|
113 | public final void clear() { |
---|
114 | for (int i = 0; i <= size; i++) |
---|
115 | heap[i] = null; |
---|
116 | size = 0; |
---|
117 | } |
---|
118 | |
---|
119 | private final void upHeap() { |
---|
120 | int i = size; |
---|
121 | T node = heap[i]; // save bottom node |
---|
122 | int j = i >>> 1; |
---|
123 | while (j > 0 && lessThan(node, heap[j])) { |
---|
124 | heap[i] = heap[j]; // shift parents down |
---|
125 | i = j; |
---|
126 | j = j >>> 1; |
---|
127 | } |
---|
128 | heap[i] = node; // install saved node |
---|
129 | } |
---|
130 | |
---|
131 | private final void downHeap() { |
---|
132 | int i = 1; |
---|
133 | T node = heap[i]; // save top node |
---|
134 | int j = i << 1; // find smaller child |
---|
135 | int k = j + 1; |
---|
136 | if (k <= size && lessThan(heap[k], heap[j])) { |
---|
137 | j = k; |
---|
138 | } |
---|
139 | while (j <= size && lessThan(heap[j], node)) { |
---|
140 | heap[i] = heap[j]; // shift up child |
---|
141 | i = j; |
---|
142 | j = i << 1; |
---|
143 | k = j + 1; |
---|
144 | if (k <= size && lessThan(heap[k], heap[j])) { |
---|
145 | j = k; |
---|
146 | } |
---|
147 | } |
---|
148 | heap[i] = node; // install saved node |
---|
149 | } |
---|
150 | } |
---|