/*
 *  TnUniqueQueue.h
 *  
 *
 *  Created by Thant on 5/15/2013
 *  Copyright 2013 TeleNav Inc. All rights reserved.
 *
 *  This is a first-in-first-out queue. It is different than STL
 *  queues in two ways:
 *
 *  1) 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 will be
 *  ignored.
 *
 *  2) The test for whether a queue contains an item is efficient. It
 *  also allows arbitrary items to be removed efficiently.
 *
 */


#include <list>
#include <map>
#include <boost/optional.hpp>
#include <foundation/SharedPtr.h>


#ifndef TN_UNIQUE_QUEUE_INCLUDED
#define TN_UNIQUE_QUEUE_INCLUDED


template <typename ITEM>
struct TnUniqueQueue
{
    typedef Tn::Foundation::shared_ptr<TnUniqueQueue> ptr;

    /*  Returns true if the ITEM was not already in the queue and was therefore
     *  successfully pushed onto the back.
     */
    bool Push(ITEM const &);


    /*  Returns the ITEM at the head of the queue, or an empty option
     *  if the queue was empty.
     */
    boost::optional<ITEM> Pop();


    /*  Returns true if the ITEM is already in the queue.
     */
    bool Exists(ITEM const &) const;

    /*  Returns true if the ITEM was in the queue and was therefore
     *  successfully removed.
     */
    bool Remove(ITEM const &);

    void RemoveAll();

private:

    typedef typename std::list<ITEM> List;
    typedef typename std::map<ITEM, typename List::iterator> Locations;
    typedef typename std::pair<ITEM, typename List::iterator> LocationsEntry;

    List m_list;
    Locations m_locations;
};


template <typename ITEM>
bool TnUniqueQueue<ITEM>::Push(ITEM const & item)
{
    if (Exists(item)) return false;

    /* Push on front. Pop off back. */

    m_list.push_front(item);
    typename List::iterator it = m_list.begin();

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

    return true;
} 


template <typename ITEM>
boost::optional<ITEM> TnUniqueQueue<ITEM>::Pop()
{
    /* Push on front. Pop off back. */

    if (m_list.empty())
    {
        return boost::optional<ITEM>();
    }

    boost::optional<ITEM> result(m_list.back());
    m_list.pop_back();

    typename Locations::iterator it = m_locations.find(*result);
    assert(it != m_locations.end());
    m_locations.erase(it);
    
    return result;
}


template <typename ITEM>
bool TnUniqueQueue<ITEM>::Exists(ITEM const & item) const
{
    typename Locations::const_iterator it = m_locations.find(item);

    return (it != m_locations.end());
}


template <typename ITEM>
bool TnUniqueQueue<ITEM>::Remove(ITEM const & item)
{
    typename Locations::iterator it = m_locations.find(item);

    if (it == m_locations.end()) return false;

    m_list.erase(it->second);
    m_locations.erase(it);

    return true;
}

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

#endif
