Testing some policy-based design

cache.cpp

#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <unordered_set>
#include <utility>

class PolicyBase {
public:
    template <typename CacheType>
    void elementAdded(CacheType* c, const typename CacheType::KeyType& k) {}

    template <typename CacheType>
    void elementRemoved(CacheType* c, const typename CacheType::KeyType& k) {}

    template <typename CacheType>
    void elementAccessed(CacheType* c, const typename CacheType::KeyType& k) {}

    template <typename CacheType>
    void missed(CacheType* c, const typename CacheType::KeyType& k) {}

    template <typename CacheType>
    bool shouldSet(CacheType* c, const typename CacheType::KeyType& k) {
        return true;
    }
};

template <typename K, typename V, typename CachePolicy>
class Cache : private CachePolicy {
private:
    using CachePolicy::elementAdded;
    using CachePolicy::elementRemoved;
    using CachePolicy::elementAccessed;
    using CachePolicy::missed;
    using CachePolicy::shouldSet;

    std::unordered_map<K, V> _storage;

public:
    typedef V ValueType;
    typedef K KeyType;
    typedef CachePolicy Policy;

    inline size_t size() const {
         return _storage.size();
    }

    void set(const K& key, V value) {
        if (this->shouldSet(this, key)) {
            _storage.insert({key, std::move(value)});
        }
        elementAdded(this, key);
    }

    V& get(const K& key) {
        auto it = _storage.find(key);

        if (it != _storage.end()) {
            elementAccessed(this, key);
            return it->second;
        }

        missed(this, key);

        V& val = _storage.at(key);

        elementAccessed(this, key);

        return val;
    }

    void remove(const K& key) {
        auto it = _storage.find(key);

        if (it == _storage.end()) {
            return;
        }

        _storage.erase(it);

        elementRemoved(this, key);
    }
};

template <typename Generator, typename = void>
class GeneratorPolicy {};

template <typename Generator>
class GeneratorPolicy<Generator, typename std::enable_if<std::is_empty<Generator>::value>::type>
    : public PolicyBase
{
public:
    template <typename CacheType>
    void missed(CacheType* c, const typename CacheType::KeyType& k) {
        c->set(k, ((Generator*)nullptr)->operator()(c, k));
    }
};

template <typename Generator>
class GeneratorPolicy<Generator, typename std::enable_if<!std::is_empty<Generator>::value>::type>
    : public PolicyBase
{
private:
    Generator _g;

public:
    template <typename CacheType>
    void missed(CacheType* c, const typename CacheType::KeyType& k) {
        c->set(k, _g(c, k));
    }
};

template <size_t MaxElements, typename ValueType>
class LRUPolicy : public PolicyBase {
private:
    std::deque<ValueType> _lru;
    std::unordered_set<ValueType> _uniqueElements;

    void garbageCollect() {
        if (_lru.size() <= MaxElements) {
            return;
        }

        std::unordered_set<ValueType> unique;

        size_t p = 0;
        for (size_t i = 0; i < _lru.size(); ++i) {
            if (unique.count(_lru[i]) == 0) {
                if (p != i) {
                    _lru[p] = std::move(_lru[i]);
                }
                unique.insert(_lru[p]);
                ++p;
            }
        }

        _lru.resize(unique.size());
    }

public:
    template <typename CacheType>
    void elementAccessed(CacheType* c, const typename CacheType::KeyType& k) {
        _lru.push_front(k);
        garbageCollect();
    }

    template <typename CacheType>
    void elementAdded(CacheType* c, const typename CacheType::KeyType& k) {
        _lru.push_front(k);
        _uniqueElements.insert(k);

        if (_uniqueElements.size() > MaxElements) {
            auto key = _lru.back();
            _lru.pop_back();

            if (_uniqueElements.count(key) == 1) {
                _uniqueElements.erase(key);
            }

            c->remove(key);
        }

        garbageCollect();
    }
};

struct NextInt {
    template <typename Cache>
    int operator()(Cache*, int i) {
        return i + 1;
    }
};

#include <iostream>

struct NextFibonacciGenerator {
    template <typename Cache>
    int operator()(Cache* c, int i) {
        if (i == 0) {
            return 0;
        }
        if (i == 1) {
            return 1;
        }
        return c->get(i - 2) + c->get(i - 1);
    }
};

int main() {
    std::cout << "next integer generator:" << std::endl;

    Cache<int, int, GeneratorPolicy<NextInt>> nextInt;

    nextInt.set(1, 2);
    std::cout << nextInt.get(1) << std::endl;
    std::cout << nextInt.get(2) << std::endl;
    std::cout << nextInt.get(3) << std::endl;

    std::cout << "lru cache:" << std::endl;

    Cache<std::string, int, LRUPolicy<2, std::string>> lru;

    lru.set("foo", 1);
    lru.set("bar", 2);

    std::cout << lru.size() << std::endl;
    std::cout << lru.get("foo") << std::endl;

    lru.set("foobar", 3);

    std::cout << lru.size() << std::endl;
    std::cout << lru.get("foobar") << std::endl;

    std::cout << "fibonacci generator:" << std::endl;

    Cache<int, int, GeneratorPolicy<NextFibonacciGenerator>> fib;

    std::cout << fib.get(10) << std::endl;
    std::cout << fib.get(9) << std::endl;
    std::cout << fib.get(8) << std::endl;
    std::cout << fib.get(7) << std::endl;
    std::cout << fib.get(6) << std::endl;
    std::cout << fib.get(5) << std::endl;
    std::cout << fib.get(4) << std::endl;
    std::cout << fib.get(3) << std::endl;
    std::cout << fib.get(2) << std::endl;
    std::cout << fib.get(1) << std::endl;

    std::cout << "sizeof unordered_map<int, int>: "
        << sizeof(std::unordered_map<int, int>) << std::endl;
    std::cout << "sizeof next int generator: "
        << sizeof(nextInt) << std::endl;
    std::cout << "sizeof lru cache: "
        << sizeof(lru) << std::endl;
    std::cout << "sizeof fibonacci generator: "
        << sizeof(fib) << std::endl;
}