How to Iterate Over a Priorityqueue

How to iterate over a PriorityQueue?

From the Javadocs

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

There are probably other equivalent mechanisms.

Java iterate through priority queue

import java.util.Date;
import java.util.Comparator;
import java.util.PriorityQueue;

class Job implements Runnable{

 Priority priority;
 Date dateOccurance;

 public Job(Priority priority, Date occurance){
    this.priority = priority;
    this.dateOccurance = occurance;
 }

 public void run(){
    //Job execution
    System.out.println("executed");
 }
}

enum Priority {
 High,
 Medium,
 Low
}

class JobComparator implements Comparator<Job>  {

 @Override
 public int compare(Job j1, Job j2) {

    if(j1.priority.ordinal() > j2.priority.ordinal()) {
        return 1;
    } else if (j1.priority == j2.priority) {
        if(j1.dateOccurance.after(j2.dateOccurance)) {
            return 1;
        } else if (j1.dateOccurance.before(j2.dateOccurance)) {
            return -1;
        } else {
            return 0;
        }
    }  
    return -1;
 }

}

public class PriorityQueueTest {

public static void main(String[] args) throws InterruptedException {
    Date d = new Date();
    Job job1 = new Job(Priority.High, d);
    Job job2 = new Job(Priority.High, d);
    Job job3 = new Job(Priority.Medium, d);
    Job job4 = new Job(Priority.Low, d);    
    Thread.sleep(2000);
    Date l = new Date();
    Job job5 = new Job(Priority.Low, l);    

    Comparator<Job> jComp = new JobComparator();
    PriorityQueue<Job> queue = 
        new PriorityQueue<Job>(10, jComp);

    queue.add(job4);
    queue.add(job3);
    queue.add(job1);
    queue.add(job2);
    queue.add(job5);

    while (queue.size() != 0)
    {
        Job j = queue.remove();
        System.out.println(j.priority +"     "+j.dateOccurance);
    }
 }      

}

How should I iterate a priority queue properly?

Yes, if you need to check every single element in the collection, an iterator or for each is probably best.

Iterator<E> iter = myPriorityQueue.iterator();
while (iter.hasNext()) {
    current = iter.next();
    // do something with current
}

Or

for (Element e : myQueue) {
        // do something with e
}

Is iterator the best way to loop through PriorityQueue

If you want ordered retrieval of your elements, you must poll/remove elements from the queue; using iterator will not be enough.

How to iterate and change the value of each item in a priority queue in Java

You can simply create another queue and populate it by adding decremented values from the first one:

PriorityQueue<Integer> q = new PriorityQueue<Integer>(size, Collections.reverseOrder());
PriorityQueue<Integer> q2 = new PriorityQueue<Integer>(size, Collections.reverseOrder());

// code that adds items to q

for (Integer item: q) {
   q2.add(--item);
}

Updating a PriorityQueue when iterating it

This code is in the Java 6 implementation of PriorityQueue:

private class Itr implements Iterator<E> {
  /**
   * The modCount value that the iterator believes that the backing
   * Queue should have.  If this expectation is violated, the iterator
   * has detected concurrent modification.
   */
  private int expectedModCount = modCount;

  public E next() {
    if(expectedModCount != modCount) {
      throw new ConcurrentModificationException();
    }

  }

}

Now, why is this code here? If you look at the Javadoc for ConcurrentModificationException you will find that the behaviour of an iterator is undefined if modification occurs to the underlying collection before iteration completes. As such, many of the collections implement this modCount mechanism.

To fix your code

You need to ensure that you don't modify the code mid-loop. If your code is single threaded (as it appears to be) then you can simply do as your coworker suggested and copy it into a list for later inclusion. Also, the use of the Iterator.remove() method is documented to prevent ConcurrentModificationExceptions. An example:

List<Entry> toAdd = new ArrayList<Entry>();
Iterator it = mEntries.iterator();
while(it.hasNext()) {
  Entry e = it.next();

  if(e.getId().equals(someId)) {
    Entry newEntry = e.setData(newData);
    it.remove();
    toAdd.add(newEntry);
  }
}
mEntries.addAll(toAdd);

---

Related Topics