Removing time-stamped items from a PriorityQueue

Question

I'm using a priority queue (java.util.PriorityQueue<T>) where items with the same priority need to be handled in a first-in first-out basis.

I have managed that fine by adding a timestamp member to the item being added to the queue that is incremented for each item added. (See PriorityQueue has objects with the same priority and http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html )

So using the FIFOEntry class from the docs I have

 class FIFOEntry<E extends Comparable<? super E>>
     implements Comparable<FIFOEntry<E>> {
   final static AtomicLong seq = new AtomicLong();
   final long seqNum;
   final E entry;
   public FIFOEntry(E entry) {
     seqNum = seq.getAndIncrement();
     this.entry = entry;
   }
   public E getEntry() { return entry; }
   public int compareTo(FIFOEntry<E> other) {
     int res = entry.compareTo(other.entry);
     if (res == 0 && other.entry != this.entry)
       res = (seqNum < other.seqNum ? -1 : 1);
     return res;
   }
 }

What I'd like to do now is to be able to determine if an item is in the queue and/or to be able to remove an item from it. I can't directly use the contains or remove functions because the queue holds FIFOEntry objects, not E ojects.

The contains(Object o) and the remove(Object o) functions of the queue depend on the arguments' o.equals(e) function. I was able to remove items by adding the equals() function to the FIFOEntry class that only uses the entry member for comparison.

I need a better method than this because this new equals function breaks the "consistent with equals" rule.

Would it be better to create a new, separate class that has a member for entry (same type E) and move the equals() function to this other class? What about using a Comparator instead?

p.s. More context: this is to be used in Android.

Answer 1

If you override the hashcode, compareTo and equals properly for the E class (entry), then everything will work fine.

The FIFOEntry class above is an example of Composition.

Like you can override the equals method as below.

@Override public boolean equals(Object o){
   if(!(o instanceof FIFOEntry)){
      return false;
   }
   FIFOEntry cp= (FIFOEntry) o;
   return cp.entry.equals(entry) && cp.seqNum.equals(seqNum);
}

The FiFOEntry compareTo will return 0 if the Entry objects set in the FIFOEntry class will have same entry object reference and the same seq number. Basically the same Object on itself.

The compareTo and equals consistency will depend on how you implement both of them in your E class.

import java.util.Iterator;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.atomic.AtomicLong;

public class Test123 {
    public static void main(String[] args) {
        E x = new Test123.E(1);
        PrivateBlockingQueue queue = new Test123.PrivateBlockingQueue();
        FIFOEntry<E> e1 = new Test123.FIFOEntry<E>(x);
        FIFOEntry<E> e2 = new Test123.FIFOEntry<E>(new E(2));
        FIFOEntry<E> e3 = new Test123.FIFOEntry<E>(new E(1));

        queue.add(e1);
        queue.add(e2);
        queue.add(e3);

        System.out.println(queue.contains(x));
        while (true) {
            FIFOEntry<E> t = queue.poll();
            if (t == null) {
                break;
            }
            if (t.equals(e1)) {
                System.out.println("hi this is E1");
                System.out.println(t.compareTo(e1));
            }
            System.out.println(t.getEntry().getInt() + " " + t.seqNum);
        }

    }

    @SuppressWarnings("serial")
    static class PrivateBlockingQueue extends
            PriorityBlockingQueue<FIFOEntry<E>> {
        public boolean contains(E o) {
            Iterator<FIFOEntry<E>> itr = iterator();
            while (itr.hasNext()) {
                FIFOEntry<E> x = itr.next();
                if (x.entry.equals(o)) {
                    return true;
                }
            }
            return false;
        }
    }

    static class E implements Comparable<E> {
        final private Integer xyz;

        public E(int e) {
            this.xyz = e;
        }

        public Integer getInt() {
            return xyz;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof E)) {
                return false;
            }
            E test = (E) obj;
            return test.getInt() == xyz;
        }

        @Override
        public int compareTo(E o) {
            if (xyz < o.getInt()) {
                return -1;
            }
            if (xyz > o.getInt()) {
                return 1;
            }
            return 0;
        }
    }

    static class FIFOEntry<E extends Comparable<? super E>> implements
            Comparable<FIFOEntry<E>> {
        final static AtomicLong seq = new AtomicLong();
        final long seqNum;
        final E entry;

        public FIFOEntry(E entry) {
            seqNum = seq.getAndIncrement();
            this.entry = entry;
        }

        public E getEntry() {
            return entry;
        }

        public int compareTo(FIFOEntry<E> other) {
            int res = entry.compareTo(other.entry);
            if (res == 0 && other.entry != this.entry)
                res = (seqNum < other.seqNum ? -1 : 1);
            return res;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof FIFOEntry)) {
                return false;
            }
            @SuppressWarnings("rawtypes")
            FIFOEntry cp = (FIFOEntry) o;
            return cp.entry.equals(entry) && cp.seqNum == seqNum;
        }
    }
}

EDIT

As per your requirement to check if a class E exists or not in the priorityqueue and also to maintain equals and compareTo consistency, you can extend and overload the contains (and other places where equals will be called), check the above code snippet (edited it).