问从PriorityQueue中删除带时间戳的项目
EN

Stack Overflow用户

提问于 2015-02-18 05:11:34

回答 1查看 210关注 0票数 0

我使用的是优先级队列(java.util.PriorityQueue<T>)，其中具有相同优先级的项目需要以先进先出的方式进行处理。

我通过将时间戳成员添加到要添加到队列中的项来解决这个问题，每添加一个项，该成员就会递增。(参见PriorityQueue has objects with the same priority和http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html )

所以使用我的文档中的FIFOEntry类

 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;
   }
 }

我现在想要做的是能够确定一个项目是否在队列中，和/或能够从队列中删除一个项目。我不能直接使用contains或remove函数，因为队列保存的是FIFOEntry对象，而不是E对象。

队列的contains(Object o)和remove(Object o)函数依赖于参数的o.equals(e)函数。我可以通过将equals()函数添加到仅使用entry成员进行比较的FIFOEntry类来删除项。

我需要一个比这个更好的方法，因为这个新的equals函数打破了“与相等一致”的规则。

创建一个具有entry成员(相同类型E)的新的独立类，并将equals()函数移动到另一个类，会不会更好？如果使用比较器呢？

附注：更多上下文:这将在Android中使用。

java

priority-queue

回答 1

Stack Overflow用户

发布于 2015-02-18 06:36:49

如果您为E类(entry)正确地覆盖了hashcode、compareTo和equals，那么一切都将正常工作。

上面的FIFOEntry类是Composition的一个例子。

就像您可以覆盖equals方法一样，如下所示。

@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);
}

如果在FiFOEntry类中设置的Entry对象将具有same entry object reference和相同的序号，则FIFOEntry compareTo将返回0。基本上是同一个物体本身。

compareTo和equals的一致性将取决于您如何在E类中实现它们。

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;
        }
    }
}