PriorityQueue, aynı öncelikte olan nesnelere sahip

Question

Çok sayıda özel nesneyi sıralamak ve kullanmak için bir öncelik sırası kullanıyorum. Nesnelerin, doğal düzenleri olan "ağırlığı" vardır. Bununla birlikte, öncelik sırasına eklenen farklı nesneler aynı "ağırlığa" sahip olabilir. Bu gibi durumlarda, öncelik sırasının, sıraya eklendikleri sırayla sipariş vermelerini istiyorum.

Örneğin, CustomObjects A, B, C, D'yi bu sıraya eklediğimde, öncelik sırasından aynı "ağırlığa" sahip olanların tümü de bunları sırayla döndürmelidir. diğerlerine eklemeden önce daha fazla nesne.

İşte benim özel nesne için CompareTo geçerli:

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

Bu o ilk düzeni korumak düşündüm ederken, öyle değil. Bu, 1 ile A, B, C'yi girdiğimde oluşur; Anket A; ve D, E'yi de ağırlık 1 ile de ekleyin. Her nasılsa, D ve E B'den sonra, ancak C'den önce sıralanır.

PriorityQueues için yineleyicinin doğru sıralamayı döndürmediğinin farkındayım, bu yüzden siparişe bakma yeteneği - ancak, elemanların kuyruğu terk ettiği sırayı görebiliyorum ve açıkça istediğim yolu takip etmiyor.

Öneriler?

Answer 1

Eğer zaman damgası için ekstra eleman kullanmak gerekir ekleme talimatına göre bir sıralama olması gerekir. I.e. Eklenenler ve eşit ağırlıkta hangi öğenin eklendiğini görmek için timestamp kullanın.

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 küçük o böylece kampanya siparişinde tutmak önceki sokulmuş demektir:

class CustomObject { 
    int weight; 
    long timestamp; 
} 

Ve karşılaştırma olmalıdır: Yani CustomObject şey gibi olmalıdır.

Ayrıca, her bir add veya remove numaralı güncelleştirmede güncelleştirdiğiniz bir sayacı koruyarak "mantıklı" bir süre kullanabilirsiniz.

Answer 2

Otomatik olarak artırılmış bir sıra numarasını ikincil anahtar olarak kullanabilir ve bağları koparmak için kullanabilirsiniz. Bu sınıfta

Operasyonlar eşit önceliğe sahip elemanların sıralanması hakkında hiçbir garanti: PriorityBlockingQueue için

Javadoc bu tekniğin bir örnek içermektedir. Bir siparişi zorlamanız gerekiyorsa, birincil öncelik değerlerinde bağları koparmak için ikincil bir anahtar kullanan özel sınıflar veya karşılaştırıcılar tanımlayabilirsiniz. Örneğin, burada karşılaştırılabilir öğelere ilk giren ilk çıkar çatışmayı uygulayan bir sınıf var. Bunu kullanmak için düz giriş nesnesi yerine yeni bir FIFOEntry(anEntry) eklersiniz.

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