PriorityQueue


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