LruQueue.hpp

#pragma once
#ifndef LRU_QUEUE_H_
#define LRU_QUEUE_H_
#include <list>
#include <stdio.h>
#include <map>
#include <algorithm>

using namespace std;

template <typename ValType>
class LruQueue{
private:
    typedef list<ValType> LRU_List_t;
    typedef map<ValType, typename LRU_List_t::iterator> LRU_Map_t;
public:
    const ValType& top() const;
    void push(const ValType& value);
    bool empty()const {return(internal_map.empty());}
    size_t size()const {return(internal_map.size());}
    void pop();
protected:
    LRU_Map_t internal_map;
    LRU_List_t internal_list;
};

/* Definitions in header because it's a template class */

template <typename V>
const V& LruQueue<V>::top() const {
    if (size() < 1) {
        fprintf(stderr, "Called top on empty LRU Queue!\n");
    }
    return(internal_list.front());
}

template <typename V>
void LruQueue<V>::push(const V& value) {
    if (internal_map.find(value) != internal_map.end()) {
        internal_list.erase(internal_map[value]);
    }
    internal_list.push_back(value);
    internal_map[value] = prev(internal_list.end());
}

template <typename V>
void LruQueue<V>::pop() {
    V val = internal_list.front();
    internal_list.pop_front();
    internal_map.erase(val);
}
#endif