PriorityQueueには同じ優先順位のオブジェクトがあります

Question

優先キューを使用して多数のカスタムオブジェクトをソートして使用しています。オブジェクトには自然な順序付けである「重み」があります。ただし、優先度キューに挿入される異なるオブジェクトは、同じ「重み」を持つことがあります。そのような場合は、優先度キューにキューに入れられた順序と同じ順序で優先度キューを並べ替える必要があります。

たとえば、カスタムオブジェクトA、B、C、Dをこの順に追加した場合、優先度キューと同じ重みを持つものがすべてその順序で返されます。他のオブジェクトに追加する前にオブジェクトの多くを追加します。

はここに私のカスタムオブジェクトのためのCompareToです：

public int compareTo(CustomObject o) { 
    int thisWeight = this.weight; 
    int thatWeight = o.weight; 
    if(thisWeight < thatWeight){ 
     return -1; 
    } 
    else{ 
     return 1; 
    } 
} 

私は、これはその最初の秩序を維持するだろうと思ったが、それはしていません。これは、A、B、Cを重み1で入力したときに発生します。投票A;何らかの形で、DとEはBの後、Cの前にソートされます。

PriorityQueuesのIteratorが正しい順序を返さないことを知っています。オーダーを見る能力 - しかし、要素がキューから出る順序を見ることができ、それが私が望む経路にはっきりと従わない。

提案？

Answer 1

あなたがタイムスタンプのための余分な要素を使用する必要が挿入順序に従って、順序を持っている必要がある場合。 I.挿入および等重量で最初に挿入された要素を確認するにはtimestampを使用してください。 のでCustomObjectのようなものでなければなりません：

class CustomObject { 
    int weight; 
    long timestamp; 
} 

との比較は次のようになります。

public int compareTo (CustomObject o) { 
    int thisWeight = this.weight; 
    int thatWeight = o.weight; 
    if (thisWeight != thatWeight) { 
     return thisWeight - thatWeight; 
    } 
    else { 
     return this.timestamp - o.timestamp; 
    } 
} 

timestamp小さいが、あなたが挿入順に保つことが以前を挿入したことを意味します。

addまたはremoveで更新するカウンタを維持することによって、論理的な時間を使用することもできます。

Answer 2

自動増分されたシーケンス番号をセカンダリ・キーとして使用し、それを使用してタイを破ることができます。 PriorityBlockingQueueため

Javadocは、この技術の例が含まれています。このクラスに

動作は等しい優先度を持つ要素の順序についての保証をしません。順序を強制する必要がある場合は、セカンダリ・キーを使用するカスタム・クラスまたはコンパレータを定義して、プライマリ優先順位値のタイを解除することができます。たとえば、first-in-first-outタイブレークを比較可能な要素に適用するクラスがあります。これを使用するには、プレーンなエントリオブジェクトの代わりに新しいFIFOEntry(anEntry)を挿入します。

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