java queue with dynamic priority flag

Question

Мне нужно создать очередь, в которой элементы будут добавлены и удалены в хронологическом порядке по умолчанию. Но если клиент устанавливает флаг приоритета для очереди, я должен иметь возможность вытягивать элементы на основе порядка приоритета элементов.

Я думаю о создании очереди приоритетов, поддерживаемой картой, которая отслеживает индекс очереди в порядке приоритета и на основе флага приоритета. Я могу вытащить элементы из карты и вытащить элемент из индекса из очереди.

Однако при таком подходе вопрос будет, погода я создаю карту по умолчанию или только если установлен флаг (учитывая, что стоимость создания карты на лету высока, я склонен к ее по умолчанию).

Пожалуйста, дайте мне знать, если есть лучший способ сделать это или существует существующая реализация.

Вот что я в настоящее время:

import javax.naming.OperationNotSupportedException; 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.concurrent.TimeUnit; 
import java.util.concurrent.locks.ReentrantLock; 

public class DynamicPriorityQueue<ComparableQueueElement> implements IQueue<ComparableQueueElement> { 

    private static final int CONSTANT_HUNDRED = 100; 
    private boolean fetchByCustomPriority = false; 
    private final ReentrantLock lock; 
    private final PriorityQueue<ComparableQueueElement> queue; 
    private final PriorityQueue<ComparableQueueElement> customPriorityQueue; 

    public DynamicPriorityQueue() { 
     this(null); 
    } 

    public DynamicPriorityQueue(Comparator<ComparableQueueElement> comparator) { 
     this.lock = new ReentrantLock(); 
     this.queue = new PriorityQueue<>(CONSTANT_HUNDRED); 
     if (comparator != null) 
      this.customPriorityQueue = new PriorityQueue<ComparableQueueElement>(CONSTANT_HUNDRED, comparator); 
     else 
      this.customPriorityQueue = null; 
    } 

    public void setFetchByCustomPriority(boolean fetchByCustomPriority) throws OperationNotSupportedException { 
     if (this.customPriorityQueue == null) 
      throw new OperationNotSupportedException("Object was created without a custom comparator."); 

     this.fetchByCustomPriority = fetchByCustomPriority; 
    } 

    public void push(ComparableQueueElement t) throws InterruptedException { 
     if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) { 
      try { 
       this.queue.offer(t); 
       if (this.customPriorityQueue != null) 
        this.customPriorityQueue.offer(t); 
      } finally { 
       this.lock.unlock(); 
      } 
     } 
    } 

    public ComparableQueueElement peek() { 
     return this.fetchByCustomPriority ? this.queue.peek() 
       : (this.customPriorityQueue != null ? this.customPriorityQueue.peek() : null); 
    } 

    public ComparableQueueElement pop() throws InterruptedException { 
     ComparableQueueElement returnElement = null; 
     if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) { 
      try { 
       if (this.fetchByCustomPriority && this.customPriorityQueue != null) { 
        returnElement = this.customPriorityQueue.poll(); 
        this.queue.remove(returnElement); 
       } 
       else { 
        returnElement = this.queue.poll(); 
        if (this.customPriorityQueue != null) { 
         this.customPriorityQueue.remove(returnElement); 
        } 
       } 
      } finally { 
       this.lock.unlock(); 
      } 
     } 
     return returnElement; 
    } 
} 

Answer 1

Я удалил свои комментарии после перечитывая вопрос, может усложниться. Вам нужно превратить fifo (хронологическую) очередь в приоритетную очередь с флагом. Ваша карта должна быть заказана и иметь возможность удерживать повторяющиеся значения. В противном случае вам нужно будет найти карту, чтобы найти наивысший приоритет или выполнить поиск в очереди. Я бы этого не сделал.

EDIT

Что об использовании класса оберточной:

class Pointer<T>{ 
    T element 
} 

И две очереди указателей, где очереди обмена указателями, но они возвращаются их по-разному? Единственное, что вам нужно сделать, это проверить, что «element» не является нулевым (вы устанавливаете его null, когда он покидает одну из очередей.

Ссылка на указатель остается в другой очереди, но вы проверяете значение null перед возвратом .

EDIT

Ваш код не имеет карту.

public ComparableQueueElement peek() { 
     return this.fetchByCustomPriority ? this.queue.peek() 
       : (this.customPriorityQueue != null ? this.customPriorityQueue.peek() : null); 
    } 

не является правильным. Если это не заказ, вы должны выглядывать из this.queue

EDIT

Обратите внимание, что с помощью класса оберточной вы сохраните себя удалить вызовы в другой очереди. Единственные накладные расходы - это то, что вам нужно проверить значение null при извлечении

Answer 2

Для меня реализация выглядит отлично, если ваше приложение имеет требование, когда флаг меняется очень часто. В этом случае у вас есть обе очереди, готовые предложить или опросить объект из очереди. Хотя это делает вашу операцию добавления тяжелой, но поиск выполняется быстро.

Но если эти изменения не являются частыми, вы можете подумать о повторной инициализации очереди пользовательского приоритета из очереди FIFO только при изменении флага. И выполнить все ваши взгляды, предлагать операцию только в одной очереди вместо двух. , который будет более эффективным, если используется приоритет FIFO. и если вы делаете это изменить ваш нажимной операцию, как показано ниже -

public void push(ComparableQueueElement t) throws InterruptedException { 
    if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) { 
     try { 
      this.queue.offer(t); 
      if (this.fetchByCustomPriority) // add to customPriorityQueue only when flag is enabled 
       this.customPriorityQueue.offer(t); 
     } finally { 
      this.lock.unlock(); 
     } 
    } 
}