// tasks/lru/source.cpp
// LRU Cache implemented in C++ using std::list + std::unordered_map.
// Agents must migrate this to Rust using Vec<(u64, u64)> (no HashMap, no unsafe).
//
// Key invariants:
//   - get()  moves the accessed key to the MRU (front) position
//   - put()  inserts at MRU; if key exists, update value and move to front
//   - put()  evicts the LRU (back) entry when capacity is exceeded
//   - Aeneas constraint: use Vec-based representation only

#include <iostream>
#include <list>
#include <unordered_map>
#include <optional>
#include <cstdint>

class LRUCache {
public:
    using Key = uint64_t;
    using Val = uint64_t;
    using Pair = std::pair<Key, Val>;

    explicit LRUCache(size_t capacity) : cap_(capacity) {}

    // Return value for key, or nullopt if not present.
    // Moves accessed key to MRU (front).
    std::optional<Val> get(Key key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        // Move to front
        order_.splice(order_.begin(), order_, it->second);
        return it->second->second;
    }

    // Insert or update key. Evict LRU if over capacity.
    void put(Key key, Val val) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->second = val;
            order_.splice(order_.begin(), order_, it->second);
        } else {
            if (order_.size() >= cap_) {
                // Evict LRU (back)
                auto lru = order_.back();
                map_.erase(lru.first);
                order_.pop_back();
            }
            order_.emplace_front(key, val);
            map_[key] = order_.begin();
        }
    }

    // Evict entries until size <= cap
    void evict(size_t cap) {
        while (order_.size() > cap) {
            auto lru = order_.back();
            map_.erase(lru.first);
            order_.pop_back();
        }
    }

    // Return current (MRU-first) order as vector of pairs
    std::vector<Pair> snapshot() const {
        return std::vector<Pair>(order_.begin(), order_.end());
    }

    size_t size() const { return order_.size(); }

private:
    size_t cap_;
    std::list<Pair> order_;                        // front = MRU, back = LRU
    std::unordered_map<Key, std::list<Pair>::iterator> map_;
};

int main() {
    LRUCache cache(2);
    cache.put(1, 10);
    cache.put(2, 20);
    auto v = cache.get(1);
    std::cout << "get(1) = " << (v ? std::to_string(*v) : "none") << "\n";  // 10
    cache.put(3, 30);   // evicts key 2 (LRU)
    v = cache.get(2);
    std::cout << "get(2) = " << (v ? std::to_string(*v) : "none") << "\n";  // none
    v = cache.get(3);
    std::cout << "get(3) = " << (v ? std::to_string(*v) : "30") << "\n";    // 30
    return 0;
}