/*
 *  TnPruningMap.h
 *
 *  Created by Thant on 7/29/2013
 *  Copyright 2013 TeleNav Inc. All rights reserved.
 *
 */

#ifndef TN_PRUNING_MAP_INCLUDED
#define TN_PRUNING_MAP_INCLUDED

// for debugging and profiling
// #include <iostream>

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


/*
 *  This provides a standard KEY/VALUE map, but it cleans up invalid
 *  entries iteratively as it is used. KeyTest and ValueTest should
 *  return true if their argument is still considered valid. If either
 *  returns false, that entry in the map is removed.
 */


template <typename KEY, typename VALUE>
struct TnPruningMap {

    typedef bool (*KeyTest)(KEY const &);
    typedef bool (*ValueTest)(VALUE const &);

    typedef typename std::map<KEY, VALUE> Map;
    typedef typename std::map<KEY, VALUE>::iterator Iter;
    typedef typename std::map<KEY, VALUE>::const_iterator ConstIter;
    typedef typename std::pair<KEY, VALUE> Entry;
    typedef boost::optional<VALUE> ValueOpt;

    TnPruningMap(KeyTest keyTest, ValueTest valueTest) :
        m_keyTest(keyTest),
        m_valueTest(valueTest),
        m_validIter(false) {}


    // Returns true if successfully inserted (i.e. there wasn't
    // already a still-valid entry).
    bool insert(KEY const & that_key, VALUE const & that_value) {

        if (m_keyTest(that_key) && m_valueTest(that_value))
        {
            Iter it = m_map.find(that_key);
            if (it != m_map.end()) {
                KEY const & key = it->first;
                VALUE const & value = it->second;
                if (m_keyTest(key) && m_valueTest(value)) {
                    return false;
                }
                if (it == m_it) m_validIter = false;
                m_map.erase(it);
            }

            m_map.insert(Entry(that_key, that_value));
            prune();
            return true;
        }
        return false;
    }


    ValueOpt extract(KEY const & that_key) {

        ValueOpt result;
        Iter it = m_map.find(that_key);

        if (it != m_map.end())
        {
            KEY const & key = it->first;
            VALUE const & value = it->second;
            if (m_keyTest(key) && m_valueTest(value))
            {
                result = value;
            }
            if (it == m_it) m_validIter = false;
            m_map.erase(it);
        }

        prune();
        return result;
    }


    /*  Finds without extracting. 
     *
     */

    ValueOpt find(KEY const & that_key) {

        ValueOpt result;
        Iter it = m_map.find(that_key);

        if (it != m_map.end())
        {
            KEY const & key = it->first;
            VALUE const & value = it->second;
            if (m_keyTest(key) && m_valueTest(value))
            {
                result = value;
                return result;
            }
            // Otherwise stale entry.
            if (it == m_it) m_validIter = false;
            m_map.erase(it);
        }

        prune();
        return result;
    }


    uint32_t count() const {
        return m_map.size();
    }

private:

    KeyTest m_keyTest;
    ValueTest m_valueTest;

    Map m_map;
    Iter m_it;
    bool m_validIter;       // Whether the iterator is valid.

    // For debugging
    uint32_t aliveCount() const {
        uint32_t alive = 0;
        for (ConstIter it = m_map.begin();
             it != m_map.end();
             ++it)
        {
            if (m_keyTest(it->first) && m_valueTest(it->second)) ++alive;
        }
        return alive;
    }

    /*  This is a recursive map pruner.
     *  
     *  If the node passed in contains a dead key or value, this
     *  removes that node from the map. It continues until it either
     *  hits a live node, or the end of the map.
     *
     *  It returns either the first live node it detects, or the
     *  beginning of the map. It assumes it is passed an iterator to a
     *  valid node.
     */
    Iter prune(Iter it) {

        if (it == m_map.end()) return m_map.begin();

        Iter next = it;
        ++next;

        if (!m_keyTest(it->first) || !m_valueTest(it->second)) {

            m_map.erase(it);
            return prune(next);
        }

        // else
        return next;
    }

    /*  This is the top-level prune function.
     *  
     */

    void prune() {

#if 0
        // for debugging and profiling
        uint32_t count_before = m_map.size();
#endif

        if (m_map.empty()) {
            m_validIter = false;
            return;
        }

        if (!m_validIter) {
            m_it = m_map.begin();
            m_validIter = true;
        }

        m_it = prune(m_it);

#if 0
        // for debugging and profiling
        uint32_t count_after = m_map.size();

        uint32_t alive = aliveCount();

        if (count_before != count_after)
        {
            uint32_t removed = (count_before - count_after);
            uint32_t dead = (count_after - alive);

            std::cerr << "\n";
            std::cerr << "      removed: " << removed << "\n";
            std::cerr << "        alive: " << alive << "\n";
            std::cerr << "         dead: " << dead << "\n";
            std::cerr << "ratio garbage: " << (float(dead)/float(count_after)) << "\n";
        }
#endif
    }
};


#endif
