java queue with dynamic priority flag

Question

I need to build a queue where the elements will be added and removed in chronological order by default. But if the client sets the priority flag for the queue I need to be able to pull the elements based on the priority order of the elements.

I am thinking of creating a priority queue backed by a map that keeps track of the queue index in priority order and based on priority flag I can pull the items from the map and pop the item from index from the queue.

However with this approach the question will be, weather I create the map by default or only if the flag is set (considering the cost of creating the map on fly being high, I am inclining towards having it by default).

Please let me know if there is a better way of doing this or if there is an existing implementation that exists.

Here is what I currently have:

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

thank you efekctive. however my question was if the design will be optimal or do i go ahead with another data structure/approach? — dissatisfiedprogrammer
If all items in a priority queue have the same priority, queue push/pop should be very efficient, in O(1) time. — ZhongYu
Are you asking for a container from which the consumer can choose whether to remove the next element in priority order or, the next element in FIFO order? — Solomon Slow
If your queue of items isn't terribly large, simply reorder the queue based on the client's preference. That is, create a new queue using a different comparison function for ordering. How often does this preference change, and how many items are in your queue? — Jim Mischel

Priya Singh Priya Singh · Accepted Answer · 2017-02-15T13:56:18

For me implementation looks fine if your application have the requirement where the flag is changing very frequently. In such case you have both the queues ready to offer or poll object from queue. Although it makes your add operation heavy but retrieval is fast.

But if these changes are not frequent then you can think of re initializing the custom priority queue from FIFO queue only when flag changes. And perform all your peek,offer operation only on one queue instead of two. which will be more efficient if FIFO priority is being used. and if you do that modify your push operation as below -

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

java queue with dynamic priority flag

2 Answers