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 */
013package org.jikesrvm.util;
014
015import 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 */
022public 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