A queue that switches from FIFO mode to priority mode

Question

I implemented a queue capable of operating both in the FIFO mode and in the priority mode: when the priority mode is enabled, the elements are taken in order of decreasing priority; when the priority mode in disabled, the elements are taken in order of their arrival.

In order to manage the priority, I thought of using multiple queues (an array of Queue objects, that is m_PriorityQueues in the following code sample), one for each type of element; in this way, I can manage a priority based on the element type: just take first the elements from the queue at a higher priority and progressively from lower priority queues. In order to set the priority of different types of elements, I thought I'd pass an array of Type objects in ascending order of priority, so that each Type is associated with the index of a queue.

The user does not see multiple queues, but it uses the queue as if it were a single queue, so that the elements leave the queue in the order they arrive when the priority mode is disabled. In order to properly manage the switch from priority mode to FIFO mode, I have thought to use an additional queue (that is m_FifoOrder field in the following code sample) to manage the order of arrival of the types of elements: essentially, when a new item is enqueued, it is added to the i-th queue, and the i value which indexes the array of queues is inserted to this additional queue of integers.

public class PriorityQueue
{
    private Queue[] m_PriorityQueues;
    private LinkedList<int> m_FifoOrder;
    private Dictionary<Type, int> m_TypeMapping;

    public PriorityQueue(Type[] prioritySet)
    {
        m_TypeMapping = new Dictionary<Type, int>();
        for (int p = 0; p < prioritySet.Length; p++)
        {
            if (!m_TypeMapping.ContainsKey(prioritySet[p]))
                m_TypeMapping.Add(prioritySet[p], p);
        }

        m_PriorityQueues = new Queue[m_TypeMapping.Count];
        for (int i = 0; i < m_PriorityQueues.Length; i++)
            m_PriorityQueues[i] = new Queue();
        m_FifoOrder = new LinkedList<int>();
    }

    // Enable or disable the priority mode.
    public bool IsPriorityEnabled { get; set; }

    // Gets the priority count.
    public int PriorityCount { get { return m_TypeMapping.Count; } }

    // Gets the number of items actually enqueued in this queue.
    public int Count { get { return m_FifoOrder.Count; } }

    // Removes all objects from this queue.
    public void Clear()
    {
        for (int i = 0; i < m_PriorityQueues.Length; i++)
            m_PriorityQueues[i].Clear();
        m_FifoOrder.Clear();
    }

    // Add an object to the end of this queue
    public int Enqueue(object item)
    {
        int priority;
        if (item == null)
        {
            priority = PriorityCount - 1; // higher priority
        }
        else if (!m_TypeMapping.TryGetValue(item.GetType(), out priority))
        {
            priority = 0; // lower priority for unknown types
        }

        m_PriorityQueues[priority].Enqueue(item);
        m_FifoOrder.AddLast(priority);

        return priority;
    }

    // Removes and returns the object at the beginning of this queue.
    public bool TryDequeue(out object item)
    {
        if (IsPriorityEnabled)
        {
            for (int p = PriorityCount - 1; p >= 0; p--)
            {
                if (m_PriorityQueues[p].Count > 0)
                {
                    item = m_PriorityQueues[p].Dequeue();
                    m_FifoOrder.Remove(p);
                    return true;
                }
            }
        }
        else
        {
            if (m_FifoOrder.Count > 0)
            {
                int index = m_FifoOrder.First.Value;
                item = m_PriorityQueues[index].Dequeue();
                m_FifoOrder.RemoveFirst();
                return true;
            }
        }

        item = null;
        return false;
    }
}

UPDATE: I performed some tests and I noticed that the TryDequeue method of the version proposed above suffers from performance issues when the priority mode is enabled: the Remove method, called on m_FifoOrder linked list, performs a linear search, that is an O(n) operation. Obviously, the performance is reduced more so when n is very large.

In order to reduce the latency caused by this method, I created a new version of the priority queue: the FastPriorityQueue class. The inner class ItemInfo simply contains the object to be enqueued and the priority that is assigned during the queuing operation. An ItemInfo object is always inserted at the end of the m_FifoOrder linked list, so that the AddLast method returns a reference to the last added LinkedListNode<ItemInfo>: this reference is enqueued to one of the m_PriorityQueues queues depending on the chosen priority.

public class FastPriorityQueue
{
    private class ItemInfo
    {
        public object Data { get; set; }
        public int Priority { get; set; }
    }

    private LinkedList<ItemInfo> m_FifoOrder;
    private Queue<LinkedListNode<ItemInfo>>[] m_PriorityQueues;
    private Dictionary<Type, int> m_TypeMapping;

    public FastPriorityQueue(Type[] prioritySet)
    {
        m_TypeMapping = new Dictionary<Type, int>();
        for (int p = 0; p < prioritySet.Length; p++)
        {
            if (!m_TypeMapping.ContainsKey(prioritySet[p]))
                m_TypeMapping.Add(prioritySet[p], p);
        }

        m_PriorityQueues = new Queue<LinkedListNode<ItemInfo>>[m_TypeMapping.Count];
        for (int i = 0; i < m_PriorityQueues.Length; i++)
            m_PriorityQueues[i] = new Queue<LinkedListNode<ItemInfo>>();
        m_FifoOrder = new LinkedList<ItemInfo>();
    }

    // Enable or disable the priority mode.
    public bool IsPriorityEnabled { get; set; }

    // Gets the priority count.
    public int PriorityCount { get { return m_TypeMapping.Count; } }

    // Gets the number of items actually enqueued in this queue.
    public int Count { get { return m_FifoOrder.Count; } }

    // Removes all objects from this queue.
    public void Clear()
    {
        for (int i = 0; i < m_PriorityQueues.Length; i++)
            m_PriorityQueues[i].Clear();
        m_FifoOrder.Clear();
    }

    // Add an object to the end of this queue
    public int Enqueue(object item)
    {
        int priority;
        if (item == null)
        {
            priority = PriorityCount - 1; // higher priority
        }
        else if (!m_TypeMapping.TryGetValue(item.GetType(), out priority))
        {
            priority = 0; // lower priority for unknown types
        }

        LinkedListNode<ItemInfo> enqueued = m_FifoOrder.AddLast(
            new ItemInfo
            {
                Data = item,
                Priority = priority
            });
        m_PriorityQueues[priority].Enqueue(enqueued);

        return priority;
    }

    // Removes and returns the object at the beginning of this queue.
    public bool TryDequeue(out object item)
    {
        if (IsPriorityEnabled)
        {
            for (int p = PriorityCount - 1; p >= 0; p--)
            {
                if (m_PriorityQueues[p].Count > 0)
                {
                    LinkedListNode<ItemInfo> dequeued = m_PriorityQueues[p].Dequeue();
                    item = dequeued.Value.Data;
                    m_FifoOrder.Remove(dequeued); // This method is an O(1) operation.
                    return true;
                }
            }
        }
        else
        {
            if (m_FifoOrder.Count > 0)
            {
                ItemInfo nodeItem = m_FifoOrder.First.Value;
                item = nodeItem.Data;
                m_PriorityQueues[nodeItem.Priority].Dequeue();
                m_FifoOrder.RemoveFirst();
                return true;
            }
        }

        item = null;
        return false;
    }
}

Please review the above code samples and provide suggestions on how to improve them. Are there simpler solutions or more efficient than these? Also, if there are other solutions to switch between the two modes (FIFO mode or priority mode), please provide some details.

UPDATE 2: here is an example of initialization of a PriorityQueue object. When the queue works in FIFO mode, therefore the priorities are ignored. Instead, when the priority mode is enabled, the next item removed from the queue depends on the priority of its type: items with the highest priority will be dequeued first.

// list of types in order of priority
Type[] priorities = new Type[] { typeof(ObjectWithLowerPriority), typeof(ObjectWithIntermediatePriority), typeof(ObjectWithHigherPriority) };

PriorityQueue queue = new PriorityQueue(priorities);
queue.Enqueue(...);
queue.Enqueue(...);
// ... other calls to Enqueue method

queue.IsPriorityEnabled = false;
queue.Dequeue();
// ...

queue.IsPriorityEnabled = true;  // priority mode enabled
queue.Dequeue();
// ...

Answer 1

Layout looks good, I like the use of white space, and tabs. You have too many redundant comments that are unneeded.

I am not big on the use of m_ to signify class members, I think the _ is more commonly used, but that is a debate for another time. I have changed it to _ because that is what my eyes are used to.

I would get rid of the Queue array and make it a dictionary of <int, LinkedList<ItemInfo>> This will keep the data structures you are using in the class more consistent, and the brain is able to deal with them a little more. The three class members can all be make readonly.

I would change the Type[] variable in the constructor to IEnumerable. This will block any changes to the list within the class, and might improve speed a little. To initialize it, you can use the link .ToList() which changes it back to a list, and enables you to run the initialization code. Any changes made to the new list will not propagate back to the calling code. I would also change the p variable to priority, this makes the code more readable.

The initialization of the _typeMapping dictionary should be moved to its own method to declutter the constructor. I would also initialize your IsPriorityEnabled property here, just to make sure it starts off in a known condition

So the constructor now looks like:

public FastPriorityQueue(IEnumerable<Type> prioritySet)
{
    _typeMapping = new Dictionary<Type, int>();
    _priorityQueues = new Dictionary<int, LinkedList<ItemInfo>>();
    _fifoOrder = new LinkedList<ItemInfo>();
    IsPriorityEnabled = false;

    InitializeTypeMapping(prioritySet);
}

private void InitializeTypeMapping(IEnumerable<Type> prioritySet)
{
    var priorityList = prioritySet.ToList();
    for (var priority = 0; priority < priorityList.Count; priority++)
    {
        if (!_typeMapping.ContainsKey(priorityList[priority]))
        {
            _typeMapping.Add(priorityList[priority], priority);
        }
    }
}

The Clear method could be streamlined a little but using a foreach loop.

public void Clear()
{
    foreach (var list in _priorityQueues.Values)
    {
        list.Clear();
    }

    _fifoOrder.Clear();
}

The Enqueue method can be cleaned up a lot. I'd start by pulling the logic to determine the priority out into its own method. At the same time, you could redo the if statements to make it much more readable. First check should be the null item check. If it is null, no point in going any further. The second check can be either an if statement, or the ? : operator as I used.

private int DeterminePriority(object item)
{
    if (item == null)
    {
        return PriorityCount - 1; // higher priority
    }

    var itemType = item.GetType();
    return _typeMapping.ContainsKey(itemType) ? _typeMapping[itemType] : 0;
}

You could then create the queueItem and add it to the queues. I suggest moving priority enqueue and the regular enqueue out into their own methods. I moved the regular Enqueue(ItemInfo x) into its own method to keep things consistent.

public int Enqueue(object item)
{
    var priority = DeterminePriority(item);

    var queueItem = 
        new ItemInfo
        {
            Data = item,
            Priority = priority
        };

    PriorityEnqueue(queueItem);
    Enqueue(queueItem);

    return priority;
}

private void Enqueue(ItemInfo queueItem)
{
    _fifoOrder.AddLast(queueItem);
}

private void PriorityEnqueue(ItemInfo item)
{
    if (!_priorityQueues.ContainsKey(item.Priority))
    {
        _priorityQueues[item.Priority] = new LinkedList<ItemInfo>();
    }

    _priorityQueues[item.Priority].AddLast(item);
}

For your TryDequeue method, I would again separate the priority and regular dequeue into their own methods. This will allow you to use the ? : operator in the TryDequeue method and really clean it up. Again, do your fail check first in each method so you don't execute more code than you need to. You'll notice I've added a RemoveItem() method which removes the item from both Queues. Because the way the item was found, there is no need to figure out which dictionary row the item came from.

public bool TryDequeue(out object item)
{   
    return IsPriorityEnabled ? PriorityDequeue(out item) : Dequeue(out item);
}

private bool Dequeue(out object item)
{
    if (_fifoOrder.Count == 0)
    {
         item = null;
         return false;
    }

    var nextItem = _fifoOrder.First.Value;
    item = nextItem.Data;
    RemoveItem(nextItem);

    return true;        
}

private bool PriorityDequeue(out object item)
{
    var priorityQueue = _priorityQueues.Values.FirstOrDefault(v => v.Count > 0);

    if (priorityQueue == null)
    {
        item = null;
        return false;
    }

    var nextItem = priorityQueue.First.Value;
    item = nextItem.Data;
    RemoveItem(nextItem);

    return true;
}

private void RemoveItem(ItemInfo item)
{
    _priorityQueues[item.Priority].Remove(item);
    _fifoOrder.Remove(item);
}

So the whole class looks like:

public class FastPriorityQueue
{
    private class ItemInfo
    {
        public object Data { get; set; }
        public int Priority { get; set; }
    }

    private readonly LinkedList<ItemInfo> _fifoOrder;
    private readonly IDictionary<int, LinkedList<ItemInfo>> _priorityQueues;
    private readonly IDictionary<Type, int> _typeMapping;

    public FastPriorityQueue(IEnumerable<Type> prioritySet)
    {
        _typeMapping = new Dictionary<Type, int>();
        _priorityQueues = new Dictionary<int, LinkedList<ItemInfo>>();
        _fifoOrder = new LinkedList<ItemInfo>();

        InitializeTypeMapping(prioritySet);
    }

    private void InitializeTypeMapping(IEnumerable<Type> prioritySet)
    {
        var priorityList = prioritySet.ToList();
        for (var priority = 0; priority < priorityList.Count; priority++)
        {
            if (!_typeMapping.ContainsKey(priorityList[priority]))
            {
                _typeMapping.Add(priorityList[priority], priority);
            }
        }
    }

    public bool IsPriorityEnabled { get; set; }

    public int PriorityCount { get { return _typeMapping.Count; } }

    public int Count { get { return _fifoOrder.Count; } }

    public void Clear()
    {
        foreach (var t in _priorityQueues.Values)
        {
            t.Clear();
        }

        _fifoOrder.Clear();
    }

    public int Enqueue(object item)
    {
        var priority = DeterminePriority(item);

        var queueItem = 
            new ItemInfo
            {
                Data = item,
                Priority = priority
            };

        PriorityEnqueue(queueItem);
        Enqueue(queueItem);

        return priority;
    }

    private void Enqueue(ItemInfo queueItem)
    {
        _fifoOrder.AddLast(queueItem);
    }

    private void PriorityEnqueue(ItemInfo item)
    {
        if (!_priorityQueues.ContainsKey(item.Priority))
        {
            _priorityQueues[item.Priority] = new LinkedList<ItemInfo>();
        }

        _priorityQueues[item.Priority].AddLast(item);
    }

    private int DeterminePriority(object item)
    {
        if (item == null)
        {
            return PriorityCount - 1; // higher priority
        }

        var itemType = item.GetType();
        return _typeMapping.ContainsKey(item.GetType()) ? _typeMapping[itemType] : 0;
    }

    public bool TryDequeue(out object item)
    {   
        return IsPriorityEnabled ? DequeuePriority(out item) : Dequeue(out item);
    }

    private bool Dequeue(out object item)
    {
        if (_fifoOrder.Count == 0)
        {
            item = null;
            return false;
        }

        var nextItem = _fifoOrder.First.Value;
        item = nextItem.Data;
        RemoveItem(nextItem);

        return true;
    }

    private bool DequeuePriority(out object item)
    {
        var priorityQueue = _priorityQueues.Values.FirstOrDefault(v => v.Count > 0);

        if (priorityQueue == null)
        {
            item = null;
            return false;
        }

        var nextItem = priorityQueue.First.Value;
        item = nextItem.Data;
        RemoveItem(nextItem);

        return true;
    }

    private void RemoveItem(ItemInfo item)
    {
        _priorityQueues[item.Priority].Remove(item);
        _fifoOrder.Remove(item);
    }
}

I hope you picked up a few pointers with this.

Good luck.