View Javadoc
1   /*
2    * Copyright 2015 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty.util.internal;
17  
18  import java.util.AbstractQueue;
19  import java.util.Arrays;
20  import java.util.Comparator;
21  import java.util.Iterator;
22  import java.util.NoSuchElementException;
23  
24  import static io.netty.util.internal.PriorityQueueNode.INDEX_NOT_IN_QUEUE;
25  
26  /**
27   * A priority queue which uses natural ordering of elements. Elements are also required to be of type
28   * {@link PriorityQueueNode} for the purpose of maintaining the index in the priority queue.
29   * @param <T> The object that is maintained in the queue.
30   */
31  public final class DefaultPriorityQueue<T extends PriorityQueueNode> extends AbstractQueue<T>
32                                                                       implements PriorityQueue<T> {
33      private static final PriorityQueueNode[] EMPTY_ARRAY = new PriorityQueueNode[0];
34      private final Comparator<T> comparator;
35      private T[] queue;
36      private int size;
37  
38      @SuppressWarnings("unchecked")
39      public DefaultPriorityQueue(Comparator<T> comparator, int initialSize) {
40          this.comparator = ObjectUtil.checkNotNull(comparator, "comparator");
41          queue = (T[]) (initialSize != 0 ? new PriorityQueueNode[initialSize] : EMPTY_ARRAY);
42      }
43  
44      @Override
45      public int size() {
46          return size;
47      }
48  
49      @Override
50      public boolean isEmpty() {
51          return size == 0;
52      }
53  
54      @Override
55      public boolean contains(Object o) {
56          if (!(o instanceof PriorityQueueNode)) {
57              return false;
58          }
59          PriorityQueueNode node = (PriorityQueueNode) o;
60          return contains(node, node.priorityQueueIndex(this));
61      }
62  
63      @Override
64      public boolean containsTyped(T node) {
65          return contains(node, node.priorityQueueIndex(this));
66      }
67  
68      @Override
69      public void clear() {
70          for (int i = 0; i < size; ++i) {
71              T node = queue[i];
72              if (node != null) {
73                  node.priorityQueueIndex(this, INDEX_NOT_IN_QUEUE);
74                  queue[i] = null;
75              }
76          }
77          size = 0;
78      }
79  
80      @Override
81      public void clearIgnoringIndexes() {
82          size = 0;
83      }
84  
85      @Override
86      public boolean offer(T e) {
87          if (e.priorityQueueIndex(this) != INDEX_NOT_IN_QUEUE) {
88              throw new IllegalArgumentException("e.priorityQueueIndex(): " + e.priorityQueueIndex(this) +
89                      " (expected: " + INDEX_NOT_IN_QUEUE + ") + e: " + e);
90          }
91  
92          // Check that the array capacity is enough to hold values by doubling capacity.
93          if (size >= queue.length) {
94              // Use a policy which allows for a 0 initial capacity. Same policy as JDK's priority queue, double when
95              // "small", then grow by 50% when "large".
96              queue = Arrays.copyOf(queue, queue.length + ((queue.length < 64) ?
97                                                           (queue.length + 2) :
98                                                           (queue.length >>> 1)));
99          }
100 
101         bubbleUp(size++, e);
102         return true;
103     }
104 
105     @Override
106     public T poll() {
107         if (size == 0) {
108             return null;
109         }
110         T result = queue[0];
111         result.priorityQueueIndex(this, INDEX_NOT_IN_QUEUE);
112 
113         T last = queue[--size];
114         queue[size] = null;
115         if (size != 0) { // Make sure we don't add the last element back.
116             bubbleDown(0, last);
117         }
118 
119         return result;
120     }
121 
122     @Override
123     public T peek() {
124         return (size == 0) ? null : queue[0];
125     }
126 
127     @SuppressWarnings("unchecked")
128     @Override
129     public boolean remove(Object o) {
130         final T node;
131         try {
132             node = (T) o;
133         } catch (ClassCastException e) {
134             return false;
135         }
136         return removeTyped(node);
137     }
138 
139     @Override
140     public boolean removeTyped(T node) {
141         int i = node.priorityQueueIndex(this);
142         if (!contains(node, i)) {
143             return false;
144         }
145 
146         node.priorityQueueIndex(this, INDEX_NOT_IN_QUEUE);
147         if (--size == 0 || size == i) {
148             // If there are no node left, or this is the last node in the array just remove and return.
149             queue[i] = null;
150             return true;
151         }
152 
153         // Move the last element where node currently lives in the array.
154         T moved = queue[i] = queue[size];
155         queue[size] = null;
156         // priorityQueueIndex will be updated below in bubbleUp or bubbleDown
157 
158         // Make sure the moved node still preserves the min-heap properties.
159         if (comparator.compare(node, moved) < 0) {
160             bubbleDown(i, moved);
161         } else {
162             bubbleUp(i, moved);
163         }
164         return true;
165     }
166 
167     @Override
168     public void priorityChanged(T node) {
169         int i = node.priorityQueueIndex(this);
170         if (!contains(node, i)) {
171             return;
172         }
173 
174         // Preserve the min-heap property by comparing the new priority with parents/children in the heap.
175         if (i == 0) {
176             bubbleDown(i, node);
177         } else {
178             // Get the parent to see if min-heap properties are violated.
179             int iParent = (i - 1) >>> 1;
180             T parent = queue[iParent];
181             if (comparator.compare(node, parent) < 0) {
182                 bubbleUp(i, node);
183             } else {
184                 bubbleDown(i, node);
185             }
186         }
187     }
188 
189     @Override
190     public Object[] toArray() {
191         return Arrays.copyOf(queue, size);
192     }
193 
194     @SuppressWarnings("unchecked")
195     @Override
196     public <X> X[] toArray(X[] a) {
197         if (a.length < size) {
198             return (X[]) Arrays.copyOf(queue, size, a.getClass());
199         }
200         System.arraycopy(queue, 0, a, 0, size);
201         if (a.length > size) {
202             a[size] = null;
203         }
204         return a;
205     }
206 
207     /**
208      * This iterator does not return elements in any particular order.
209      */
210     @Override
211     public Iterator<T> iterator() {
212         return new PriorityQueueIterator();
213     }
214 
215     private final class PriorityQueueIterator implements Iterator<T> {
216         private int index;
217 
218         @Override
219         public boolean hasNext() {
220             return index < size;
221         }
222 
223         @Override
224         public T next() {
225             if (index >= size) {
226                 throw new NoSuchElementException();
227             }
228 
229             return queue[index++];
230         }
231 
232         @Override
233         public void remove() {
234             throw new UnsupportedOperationException("remove");
235         }
236     }
237 
238     private boolean contains(PriorityQueueNode node, int i) {
239         return i >= 0 && i < size && node.equals(queue[i]);
240     }
241 
242     private void bubbleDown(int k, T node) {
243         final int half = size >>> 1;
244         while (k < half) {
245             // Compare node to the children of index k.
246             int iChild = (k << 1) + 1;
247             T child = queue[iChild];
248 
249             // Make sure we get the smallest child to compare against.
250             int rightChild = iChild + 1;
251             if (rightChild < size && comparator.compare(child, queue[rightChild]) > 0) {
252                 child = queue[iChild = rightChild];
253             }
254             // If the bubbleDown node is less than or equal to the smallest child then we will preserve the min-heap
255             // property by inserting the bubbleDown node here.
256             if (comparator.compare(node, child) <= 0) {
257                 break;
258             }
259 
260             // Bubble the child up.
261             queue[k] = child;
262             child.priorityQueueIndex(this, k);
263 
264             // Move down k down the tree for the next iteration.
265             k = iChild;
266         }
267 
268         // We have found where node should live and still satisfy the min-heap property, so put it in the queue.
269         queue[k] = node;
270         node.priorityQueueIndex(this, k);
271     }
272 
273     private void bubbleUp(int k, T node) {
274         while (k > 0) {
275             int iParent = (k - 1) >>> 1;
276             T parent = queue[iParent];
277 
278             // If the bubbleUp node is less than the parent, then we have found a spot to insert and still maintain
279             // min-heap properties.
280             if (comparator.compare(node, parent) >= 0) {
281                 break;
282             }
283 
284             // Bubble the parent down.
285             queue[k] = parent;
286             parent.priorityQueueIndex(this, k);
287 
288             // Move k up the tree for the next iteration.
289             k = iParent;
290         }
291 
292         // We have found where node should live and still satisfy the min-heap property, so put it in the queue.
293         queue[k] = node;
294         node.priorityQueueIndex(this, k);
295     }
296 }