PriorityQueue의 우선 순위가 동일한 개체가 있습니다.

Question

우선 순위 큐를 사용하여 많은 수의 사용자 지정 개체를 정렬하고 사용하고 있습니다. 객체에는 자연 순서가있는 "가중치"가 있습니다. 그러나 우선 순위 큐에 삽입 된 다른 개체는 동일한 "가중치"를 가질 수 있습니다. 그런 경우 우선 순위 큐가 대기열에 넣은 순서대로 순서를 지정하기를 원합니다.

예를 들어 CustomObjects 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도 가중치 1을 추가합니다. 어쨌든 D와 E는 B 다음 C 순으로 정렬됩니다.

PriorityQueues에 대한 반복자가 올바른 순서를 반환하지 않기 때문에 순서를 보는 기능 - 요소가 큐를 떠나는 순서를 볼 수 있으며 원하는 경로를 명확하게 따르지 않습니다.

제안 사항?

Answer 1

당신이 타임 스탬프에 대한 추가 요소를 사용할 필요가 삽입 순서를 따라 주문이 필요합니다. 즉, 삽입 및 동등한 무게에 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 작은 그것이 그래서 당신이 삽입 순서로 계속 이전 를 삽입 의미

class CustomObject { 
    int weight; 
    long timestamp; 
} 

그리고 비교해야한다 : 그래서 CustomObject 뭔가 같이해야합니다.

각 add 또는 remove에서 업데이트하는 카운터를 유지함으로써 "논리적"시간을 사용할 수도 있습니다.

Answer 2

자동으로 증가하는 일련 번호를 보조 키로 사용하여 연결을 끊을 수 있습니다. 이 클래스에

작업이 동일한 우선 순위를 가진 요소의 순서에 대해 보장하지 않습니다 : PriorityBlockingQueue에 대한

자바 독은이 기술의 예를 포함한다. 주문을 시행해야하는 경우 보조 키를 사용하는 사용자 지정 클래스 또는 비교자를 정의하여 기본 우선 순위 값의 연결을 끊을 수 있습니다. 예를 들어, 선입 선출 (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; 
    } 
}