001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.util;
014
015 import org.jikesrvm.VM;
016
017 /**
018 * This class implements a priority queue using the standard
019 * (balanced partially-ordered tree, i.e., "heap") algorithm.
020 * Smaller priority objects are in the front of the queue.
021 */
022 public class PriorityQueueRVM {
023
024 /**
025 * the queue, we use elements 1..queue.length
026 */
027 private PriorityQueueNode[] queue;
028
029 /**
030 * the number of elements actually in the queue
031 */
032 private int numElements = 0;
033
034 protected PriorityQueueRVM() {
035 queue = new PriorityQueueNode[20];
036
037 // We don't use element #0
038 for (int i = 1; i < queue.length; i++) {
039 queue[i] = new PriorityQueueNode();
040 }
041 }
042
043 /**
044 * Determines number of elements in the queue
045 * @return number of elements in the queue
046 */
047 public final synchronized int numElements() {
048 return numElements;
049 }
050
051 /**
052 * Checks if the queue is empty
053 * @return is the queue empty?
054 */
055 protected final synchronized boolean isEmpty() {
056 return numElements == 0;
057 }
058
059 /**
060 * Starting at the position passed, swap with parent until heap condition
061 * is satisfied, i.e., bubble up
062 * @param startingElement the position to start at
063 */
064 private void reheapify(int startingElement) {
065 int current = startingElement;
066 int parent = numElements / 2;
067 // keep checking parents that violate the magic condition
068 while (parent > 0 && queue[parent].priority < queue[current].priority) {
069 // System.out.println("Parent: "+ parent +", Current: "+ current);
070 // System.out.println("Contents before: "+ this);
071 // exchange parrent and current values
072 PriorityQueueNode tmp = queue[parent];
073 queue[parent] = queue[current];
074 queue[current] = tmp;
075
076 // System.out.println("Contents after: "+ this);
077 // go up 1 level
078 current = parent;
079 parent = parent / 2;
080 }
081 }
082
083 /**
084 * Insert the object passed with the priority value passed
085 * @param _priority the priority of the inserted object
086 * @param _data the object to insert
087 */
088 public synchronized void insert(double _priority, Object _data) {
089 numElements++;
090
091 if (numElements == queue.length) {
092 PriorityQueueNode[] tmp = new PriorityQueueNode[(int) (queue.length * 1.5)];
093 System.arraycopy(queue, 0, tmp, 0, queue.length);
094 for (int i = queue.length; i < tmp.length; i++) {
095 tmp[i] = new PriorityQueueNode();
096 }
097 queue = tmp;
098 }
099
100 queue[numElements].data = _data;
101 queue[numElements].priority = _priority;
102
103 // re-heapify
104 reheapify(numElements);
105 }
106
107 /**
108 * Remove and return the front (minimum) object
109 * @return the front (minimum) object or null if the queue is empty.
110 */
111 public synchronized Object deleteMin() {
112 if (isEmpty()) return null;
113
114 Object returnValue = queue[1].data;
115 // move the "last" element to the root and reheapify by pushing it down
116 queue[1].priority = queue[numElements].priority;
117 queue[1].data = queue[numElements].data;
118 numElements--;
119
120 // reheapify!!!
121 int current = 1;
122
123 // The children live at 2*current and 2*current+1
124 int child1 = 2 * current;
125 while (child1 <= numElements) {
126 int child2 = 2 * current + 1;
127
128 // find the smaller of the two children
129 int smaller;
130 if (child2 <= numElements && queue[child2].priority > queue[child1].priority) {
131 smaller = child2;
132 } else {
133 smaller = child1;
134 }
135
136 if (queue[smaller].priority <= queue[current].priority) {
137 break;
138 } else {
139 // exchange parrent and current values
140 PriorityQueueNode tmp = queue[smaller];
141 queue[smaller] = queue[current];
142 queue[current] = tmp;
143
144 // go down 1 level
145 current = smaller;
146 child1 = 2 * current;
147 }
148 }
149 return returnValue;
150 }
151
152 /**
153 * Return the priority of front object without removing it
154 * @return the priority of the front object
155 */
156 public final synchronized double rootValue() {
157 if (VM.VerifyAssertions) VM._assert(!isEmpty());
158
159 return queue[1].priority;
160 }
161
162 /**
163 * Prints the contents of the queue
164 * @return the queue contents
165 */
166 @Override
167 public synchronized String toString() {
168 final StringBuilder sb = new StringBuilder(" --> ");
169 sb.append("Dumping Queue with ");
170 sb.append(numElements);
171 sb.append(" elements:\n");
172 if (numElements >= 1) sb.append("\t");
173
174 for (int i = 1; i <= numElements; i++) {
175 sb.append(queue[i].toString());
176 if (i < numElements) sb.append("\n\t");
177 }
178 return sb.toString();
179 }
180
181 /**
182 * A local class that holds the nodes of the priority tree
183 */
184 private static class PriorityQueueNode {
185
186 /**
187 * the value to compare on, larger is better
188 */
189 public double priority;
190
191 /**
192 * the associated data
193 */
194 public Object data;
195
196 @Override
197 public String toString() {
198 return data + " ... [" + priority + "]";
199 }
200 }
201 }
202