/*
 *  TnPriorityQueue.h
 *  
 *  foundation/Util
 *
 *  Created by Thant on 5/15/2013
 *  Copyright 2013 TeleNav Inc. All rights reserved.
 *
 *  This is a first-in-first-out queue that also allows items to be
 *  sorted-by-priority. That is, higher-priority items will be popped
 *  off the queue before lower-priority items. But items with the same
 *  priority will be fetched in the order that they were inserted.
 *
 *  Also, only one of an item exists in the queue at a time. If an
 *  item already exists in the queue, an attempt to re-insert it with
 *  the same or lower priority will be silently ignored. Re-inserting
 *  an item with a higher priority will replace the lower-priority
 *  item. (If the user wants to explicitly lower the priority of an item in
 *  the queue, they can simply remove it first.)
 *
 */


#include <foundation/SharedPtr.h>
#include <foundation/Util/TnUniqueQueue.h>


#ifndef TN_PRIORITY_QUEUE_INCLUDED
#define TN_PRIORITY_QUEUE_INCLUDED


template <typename ITEM>
struct TnPriorityQueue
{

    /*  'Push' returns false if ITEM is already in the queue at the
     *  same or higher priority. It returns true otherwise.
     */
    bool Push(ITEM const &, int32_t priority);


    /*  'Pop' returns an empty optional if the queue is empty.
     */
    boost::optional<ITEM> Pop();

    /*  'Exists' returns the priority of ITEM if ITEM is in the
     *  queue. It returns an empty optional otherwise.
     */
    boost::optional<int32_t> Exists(ITEM const &) const;

    /*  'Remove' returns the priority of ITEM if ITEM was in the queue
     *  and therefore removed. It returns an empty optional otherwise.
     */
    boost::optional<int32_t> Remove(ITEM const &);

    void RemoveAll();

private:

    typedef typename std::map<int32_t, typename TnUniqueQueue<ITEM>::ptr> QueueMap;
    typedef typename std::pair<int32_t, typename TnUniqueQueue<ITEM>::ptr> QueueMapEntry;

    typedef typename std::map<ITEM, int32_t> Locations;
    typedef typename std::pair<ITEM, int32_t> LocationsEntry;

    typename TnUniqueQueue<ITEM>::ptr GetOrCreateUniqueQueue(int32_t);

    QueueMap m_queues;
    Locations m_locations;
};


template <typename ITEM>
typename TnUniqueQueue<ITEM>::ptr TnPriorityQueue<ITEM>::GetOrCreateUniqueQueue(int32_t priority)
{
    typename QueueMap::iterator it = m_queues.find(priority);

    if (it != m_queues.end()) return it->second;

    typename TnUniqueQueue<ITEM>::ptr queue = typename TnUniqueQueue<ITEM>::ptr(new TnUniqueQueue<ITEM>());
    std::pair<typename QueueMap::iterator, bool> result = m_queues.insert(QueueMapEntry(priority, queue));
    assert(result.second);
    
    return queue;
}


template <typename ITEM>
bool TnPriorityQueue<ITEM>::Push(ITEM const & item, int32_t priority)
{
    boost::optional<int32_t> priorityOpt = Exists(item);
    if (priorityOpt)
    {
        // Already in queue

        if (*priorityOpt >= priority)
        {
            // Already has equal or higher priority. Do nothing.

            return false;
        }
        else
        {
            // In queue but has lower priority. Remove old one before
            // inserting new one.

            Remove(item);
        }
    }

    typename TnUniqueQueue<ITEM>::ptr const & queue = GetOrCreateUniqueQueue(priority);
    assert(queue);

    bool success = queue->Push(item);
    assert(success);

    std::pair<typename Locations::iterator, bool> result = m_locations.insert(LocationsEntry(item, priority));
    assert(result.second);

    return true;
}


template <typename ITEM>
boost::optional<ITEM> TnPriorityQueue<ITEM>::Pop()
{
    /*  Note searching backwards (higher-priorities first)
     * 
     *  After a long and violent argument with myself, decided to go
     *  ahead and clean up empty queues. That trades the overhead of
     *  recreating them for being sure that the performance of Pop
     *  doesn't degenerate in the case of lots of different priorities
     *  being used.
     */

    typename QueueMap::reverse_iterator queueIter = m_queues.rbegin();
    while (queueIter != m_queues.rend())
    {
        boost::optional<ITEM> itemOpt = queueIter->second->Pop();
        if (itemOpt) {
            typename Locations::iterator locationIter = m_locations.find(*itemOpt);
            assert(locationIter != m_locations.end());
            m_locations.erase(locationIter);
            return itemOpt;
        }

        /* Empty queue. Clean it up. (And can't pass a reverse
         * iterator to erase, so have to refind it.
         */
        int32_t priority = queueIter->first;
        typename QueueMap::iterator deadQueueIter = m_queues.find(priority);
        assert(deadQueueIter != m_queues.end());
        m_queues.erase(deadQueueIter);

        queueIter = m_queues.rbegin();
    }

    // all empty stacks or no stacks left
    return boost::optional<ITEM>();
}


template <typename ITEM>
boost::optional<int32_t> TnPriorityQueue<ITEM>::Exists(ITEM const & item) const
{
    typename Locations::const_iterator it = m_locations.find(item);
    if (it != m_locations.end())
    {
        return boost::optional<int32_t>(it->second);
    }
    return boost::optional<int32_t>();
}


template <typename ITEM>
boost::optional<int32_t> TnPriorityQueue<ITEM>::Remove(ITEM const & item)
{
    typename Locations::iterator locationIter = m_locations.find(item);

    if (locationIter != m_locations.end())
    {
        int32_t priority = locationIter->second;

        typename QueueMap::iterator queueIter = m_queues.find(priority);

        if (queueIter != m_queues.end())
        {
            bool success = queueIter->second->Remove(item);
            assert(success);

            m_locations.erase(locationIter);
            return boost::optional<int32_t>(priority);
        }
        else
        {
            // not supposed to happen
            assert(false);
        }
    }
    return boost::optional<int32_t>();
}

template <typename ITEM>
void TnPriorityQueue<ITEM>::RemoveAll()
{
    m_locations.clear();
    m_queues.clear();
}


#endif
