PriorityQueue hat Objekte mit derselben Priorität

Question

Ich verwende eine Prioritätswarteschlange, um eine große Anzahl von benutzerdefinierten Objekten zu sortieren und zu verwenden. Die Objekte haben ein "Gewicht", das ihre natürliche Ordnung ist. Verschiedene Objekte, die in die Prioritätswarteschlange eingefügt werden, können jedoch dasselbe "Gewicht" haben. In solchen Fällen möchte ich, dass die Prioritätswarteschlange sie in der Reihenfolge anordnet, in der sie in die Warteschlange eingereiht wurden.

Zum Beispiel, wenn ich in CustomObjects A hinzufügen, B, C, D in dieser Reihenfolge, alle mit dem gleichen „Gewicht“, als die Prioritätswarteschlange sie in dieser Reihenfolge auch zurückkehren sollte - auch wenn ich eine Umfrage oder mehr der Objekte vor dem Hinzufügen in den anderen.

Hier ist die CompareTo für mein benutzerdefiniertes Objekt ist:

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

Während ich dachte, dass dies, dass die Erstbestellung halten würde, ist es nicht. Dies tritt auf, wenn ich A, B, C mit der Gewichtung 1 eingabe; Umfrage A; und addiere D, E auch mit Gewicht 1. Irgendwie sind D und E nach B sortiert, aber vor C.

Ich bin mir bewusst, dass der Iterator für PriorityQueues nicht die richtige Reihenfolge zurückgibt, so dass ich in meiner limitiert bin Fähigkeit, die Reihenfolge zu betrachten - aber ich kann die Reihenfolge sehen, dass die Elemente die Warteschlange verlassen und es folgt eindeutig nicht dem Weg, den ich es will.

Vorschläge?

Answer 1

Wenn Sie eine Bestellung nach der Einführung haben müssen, um die Sie benötigen ein zusätzliches Element für Zeitstempel zu verwenden. I.e. Bei Einfügungen und gleichem Gewicht verwenden Sie timestamp, um zu sehen, welches Element zuerst eingefügt wurde. CustomObject sollte also sein, so etwas wie:

class CustomObject { 
    int weight; 
    long timestamp; 
} 

Und der Vergleich sein sollte:

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

Die kleinere timestamp bedeutet es früher eingeführt wurde, so dass Sie im Anzeigenauftrag halten.

Sie könnten auch eine "logische" Zeit verwenden, indem Sie einen Zähler pflegen, den Sie auf jedem add oder remove aktualisieren.

Answer 2

Sie könnten eine automatisch inkrementierte Sequenznummer als Sekundärschlüssel verwenden und sie zum Brechen von Bindungen verwenden.

Javadoc für PriorityBlockingQueue enthält ein Beispiel für diese Technik:

Operationen auf dieser Klasse machen keine Garantien über die Reihenfolge der Elemente mit gleicher Priorität. Wenn Sie eine Reihenfolge erzwingen müssen, können Sie benutzerdefinierte Klassen oder Komparatoren definieren, die einen sekundären Schlüssel verwenden, um Beziehungen in primären Prioritätswerten zu trennen. Zum Beispiel ist hier eine Klasse, die First-in-First-Out-Tie-Breaking auf vergleichbare Elemente anwendet. Um es zu verwenden, würden Sie anstelle eines einfachen Eintrags ein neues FIFOEntry(anEntry) einfügen.

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