/*
 *  TnMapQueue.h
 *
 *  Created by Thant on 10/9/2013
 *  Copyright 2013 TeleNav Inc. All rights reserved.
 *
 */


#ifndef TN_MAP_QUEUE_INCLUDED
#define TN_MAP_QUEUE_INCLUDED

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


/*  This provides a fixed-length queue of dictionaries that can be
 *  used as a single dictionary.
 *
 *  The motivation was the need to provide a way to convert traffic IDs to
 *  latitude/longitude coordinates. The coordinates come from tile
 *  data, but are needed by the traffic proxy.
 *
 *
 */

template <typename KEY, typename VALUE>
struct TnMapQueue {

    typedef typename boost::optional<VALUE> ValueOpt;
    typedef typename Tn::Foundation::shared_ptr<TnMapQueue<KEY,VALUE> > ptr;

    TnMapQueue(uint32_t queueSize) : m_queueSize(queueSize) {}

    /* The push function creates a new, empty map on the front of the
     * queue, and pops the oldest map off the back of the queue. This
     * function must be called regularly to avoid leaking
     * memory. Also, the queue starts out empty, so calling insert
     * before calling push is an error. */

    void push();

    /* Returns true if insert is successful (i.e. there isn't already
     * an entry with the same key). */

    bool insert(KEY const &, VALUE const &);

    /* If find returns a valid value, a side effect is to move the
     * dictionary it is found in to the front of the queue, but behind
     * the head, because that's where new entries are being
     * inserted. */

    ValueOpt find(KEY const &);

private:

    typedef typename std::map<KEY, VALUE> Map;
    typedef Tn::Foundation::shared_ptr<Map> MapPtr;
    typedef typename std::pair<KEY, VALUE> MapEntry;
    
    typedef std::list<MapPtr> MapList;
    
    uint32_t m_queueSize;
    MapList m_mapList;
    mutable Tn::Foundation::mutex m_mutex;

    void promote(typename MapList::iterator it);
};


template <typename KEY, typename VALUE>
void TnMapQueue<KEY,VALUE>::push() {

    Tn::Foundation::lock_guard<Tn::Foundation::mutex> guard(m_mutex);

    /* Ignore push command if front of queue exists and is already empty. */

    if (!m_mapList.empty() && m_mapList.front()->empty()) return;

    if (m_mapList.size() > m_queueSize) {
        m_mapList.pop_back();
    }

    m_mapList.push_front(MapPtr(new Map()));
}


template <typename KEY, typename VALUE>
bool TnMapQueue<KEY,VALUE>::insert(KEY const & key, VALUE const & value) {

    Tn::Foundation::lock_guard<Tn::Foundation::mutex> guard(m_mutex);

    if (m_mapList.empty()) return false;

    std::pair<typename Map::iterator, bool> result = m_mapList.front()->insert(MapEntry(key, value));
    return result.second;
}


template <typename KEY, typename VALUE>
typename TnMapQueue<KEY,VALUE>::ValueOpt TnMapQueue<KEY,VALUE>::find(KEY const & key) {

    Tn::Foundation::lock_guard<Tn::Foundation::mutex> guard(m_mutex);


    for (typename MapList::iterator i = m_mapList.begin();
         i != m_mapList.end();
         ++i) {

        MapPtr map = *i;

        typename Map::iterator it = map->find(key);
        if (it != map->end()) {

            promote(i);
            return ValueOpt(it->second);
        }
    }

    return ValueOpt();
}


template <typename KEY, typename VALUE>
void TnMapQueue<KEY,VALUE>::promote(typename MapList::iterator it)
{
    /* This moves a queue entry to second position (thus delaying its eviction). */

    if (m_mapList.size() < 3) return;

    typename MapList::iterator front = m_mapList.begin();
    if (it == front) return;

    /* Skip front because it's the active dictionary. */
    ++front;

    if (it == front) return;

    MapPtr map = *it;

    m_mapList.erase(it);
    m_mapList.insert(front, map);
}


#endif
