001 /*
002 NGramJ - n-gram based text classification
003 Copyright (C) 2001 Frank S. Nestel (frank at spieleck.de)
004
005 This program is free software; you can redistribute it and/or modify
006 it under the terms of the GNU Lesser General Public License as published
007 by the Free Software Foundation; either version 2.1 of the License, or
008 (at your option) any later version.
009
010 This program is distributed in the hope that it will be useful,
011 but WITHOUT ANY WARRANTY; without even the implied warranty of
012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013 GNU General Public License for more details.
014
015 You should have received a copy of the GNU Lesser General Public License
016 along with this program (lesser.txt); if not, write to the Free Software
017 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
018 */
019
020 package de.spieleck.util;
021
022 import java.util.Comparator;
023
024 /** A PriorityQueue maintains a partial ordering of its elements such that the
025 least element can always be found in constant time.
026 <P>
027 This is achieved by a heap implementation, therefore
028 Put()'s and pop()'s require log(size) time. Note that this heap is
029 realized by linear insertion and not by "bubbling".
030 <P>
031 This class can either be directly used by passing a
032 <code>java.util.Comparator</code>
033 object to the constructor, or by subclassing and overriding the
034 <code>lessThan()</code> method.
035 <P>
036 <B>XXX</B> This is an lazy implementation which spoils the very first
037 entry in the heap!
038 <P>
039 <B>Caution:</B>This class is unsynchronized and therefore
040 needs external synchronization in an multithreading environment.
041 */
042
043 public class PriorityQueue
044 {
045 protected int size;
046 protected Object[] heap;
047
048 protected Comparator myComp;
049
050 public PriorityQueue(int initialSize, Comparator comp)
051 {
052 myComp = comp;
053 initialize(initialSize);
054 }
055
056 /** Determines the ordering of objects in this priority queue.
057 * Subclasses can override this method.
058 */
059 protected boolean lessThan(Object a, Object b)
060 {
061 return myComp.compare(a,b) < 0;
062 }
063
064 public void setComparator(Comparator comp)
065 {
066 myComp = comp;
067 resort();
068 }
069
070 /** Subclass constructors must call this. */
071 protected final void initialize(int initialSize)
072 {
073 size = 0;
074 int heapSize = initialSize;
075 heap = new Object[heapSize];
076 }
077
078 /** Adds an Object to a PriorityQueue in log(size) time.
079 Unless resize occurs ...
080 */
081 public final void put(Object element)
082 {
083 size++;
084 if ( size >= heap.length )
085 {
086 Object[] newHeap = new Object[2*heap.length];
087 for (int i = 1; i < size; i++ )
088 {
089 newHeap[i] = heap[i];
090 heap[i] = null; // help GC() ?!
091 }
092 heap = newHeap;
093 }
094 heap[size] = element;
095 upHeap();
096 }
097
098 /**
099 * Replace the topmost element.
100 */
101 public final void setTop(Object element)
102 {
103 heap[1] = element;
104 adjustTop();
105 }
106
107 /** Returns the least element of the PriorityQueue in constant time. */
108 public final Object top()
109 {
110 if (size > 0)
111 return heap[1];
112 else
113 return null;
114 }
115
116 /** Removes and returns the least element of the PriorityQueue in log(size)
117 time. */
118 public final Object pop()
119 {
120 if (size > 0)
121 {
122 Object result = heap[1]; // save first value
123 heap[1] = heap[size]; // move last to first
124 heap[size] = null; // permit GC of objects
125 size--;
126 downHeap(1); // adjust heap
127 return result;
128 }
129 else
130 return null;
131 }
132
133 /** Should be called when the Object at top changes values. Still log(n)
134 * worst case, but it's at least twice as fast to <pre>
135 * { pq.top().change(); pq.adjustTop(); }
136 * </pre> instead of <pre>
137 * { o = pq.pop(); o.change(); pq.push(o); }
138 * </pre>
139 */
140 public final void adjustTop()
141 {
142 downHeap(1);
143 }
144
145
146 /** Returns the number of elements currently stored in the PriorityQueue. */
147 public final int getSize()
148 {
149 return size;
150 }
151
152 /** Returns current capacity */
153 public final int getCapacity()
154 {
155 return heap.length;
156 }
157
158 /** Removes all entries from the PriorityQueue. */
159 public final void clear()
160 {
161 for (int i = 1; i < size; i++)
162 heap[i] = null;
163 size = 0;
164 }
165
166 /** Rearrange the heap, this is supposed to be
167 O(n*log(n)) but better than nothing
168 */
169 public void resort()
170 {
171 int i = size / 2;
172 while ( i > 1 )
173 {
174 downHeap(i);
175 i--;
176 }
177 }
178
179 /**
180 * readjust last node in the heap to maintain heap condition.
181 */
182 protected final void upHeap()
183 {
184 int i = size;
185 Object node = heap[i]; // save bottom node
186 int j = i >>> 1;
187 while (j > 0 && lessThan(node, heap[j]))
188 {
189 heap[i] = heap[j]; // shift parents down
190 i = j;
191 j = j >>> 1;
192 }
193 heap[i] = node; // install saved node
194 }
195
196 /**
197 * readjust top node in the heap to maintain heap condition.
198 */
199 protected final void downHeap(int top)
200 {
201 int i = top;
202 Object node = heap[i]; // save top node
203 int j = i << 1; // find smaller child
204 int k = j + 1;
205 if (k <= size && lessThan(heap[k], heap[j]))
206 j = k;
207 while (j <= size && lessThan(heap[j], node))
208 {
209 heap[i] = heap[j]; // sift up child
210 i = j;
211 j = i << 1;
212 k = j + 1;
213 if (k <= size && lessThan(heap[k], heap[j]))
214 j = k;
215 }
216 heap[i] = node; // place saved node
217 }
218 }