void dump_mru_to_lru(std::ostream & os) const;

private:
typedef std::pair > Val;

typedef std::map > MAP_TYPE;

private:
Val * _update_or_insert(const K & key);
Val * _update(typename MAP_TYPE::iterator it);
Val * _insert(const K & key);

private:
MAP_TYPE _map;
Val * _mru;
Val * _lru;
int _maxsize;
};

// Reserve enough space to avoid resizing later on and thus invalidate iterators
template
LRUCacheH4::LRUCacheH4(int maxsize)
: _mru(NULL),
_lru(NULL),
_maxsize(maxsize)
{
if (_maxsize <= 0)
throw "LRUCacheH4: expecting cache size >= 1";
}

template
LRUCacheH4::LRUCacheH4(const LRUCacheH4 & other)
: _maxsize(other._maxsize),
_mru(NULL),
_lru(NULL)
{
for (const_iterator it = other.lru_begin(); it != other.end(); ++it)
this->insert(it.key(), it.value());
}

template
V & LRUCacheH4::operator[](const K & key)
{
return _update_or_insert(key)->second._v;
}

template
void LRUCacheH4::insert(const K & key, const V & value)
{
_update_or_insert(key)->second._v = value;
}

template
int LRUCacheH4::size() const
{
return _map.size();
}

template
int LRUCacheH4::maxsize() const
{
return _maxsize;
}

template
bool LRUCacheH4::empty() const
{
return size() > 0;
}

// updates MRU
template
typename LRUCacheH4::const_iterator LRUCacheH4::find(const K & key)
{
typename MAP_TYPE::iterator it = _map.find(key);

if (it != _map.end())
return const_iterator(_update(it), const_iterator::MRU_TO_LRU);
else
return end();
}

// does not update MRU
template
typename LRUCacheH4::const_iterator LRUCacheH4::find(const K & key) const
{
typename MAP_TYPE::iterator it = _map.find(key);

if (it != _map.end())
return const_iterator(&*it, const_iterator::MRU_TO_LRU);
else
return end();
}

template
void LRUCacheH4::dump_mru_to_lru(std::ostream & os) const
{
os << "LRUCacheH4(" << size() << "/" << maxsize() << "): MRU --> LRU: " << std::endl;
for (const_iterator it = mru_begin(); it != end(); ++it)
os << it.key() << ": " << it.value() << std::endl;
}

template
typename LRUCacheH4::const_iterator LRUCacheH4::mru_begin() const
{
return const_iterator(_mru, const_iterator::MRU_TO_LRU);
}

template
typename LRUCacheH4::const_iterator LRUCacheH4::lru_begin() const
{
return const_iterator(_lru, const_iterator::LRU_TO_MRU);
}

template
typename LRUCacheH4::const_iterator LRUCacheH4::end() const
{
return const_iterator();
}

template
typename LRUCacheH4::Val * LRUCacheH4::_update_or_insert(const K & key)
{
typename MAP_TYPE::iterator it = _map.find(key);
if (it != _map.end())
return _update(it);
else
return _insert(key);
}

template
typename LRUCacheH4::Val * LRUCacheH4::_update(typename MAP_TYPE::iterator it)
{
LRUCacheH4Value & v = it->second;
Val * older = v._older;
Val * newer = v._newer;
Val * moved = &*it;

// possibly update the LRU
if (moved == _lru && _lru->second._newer)
_lru = _lru->second._newer;

if (moved != _mru) {
// "remove" key from current position
if (older)
older->second._newer = newer;
if (newer)
newer->second._older = older;

// "insert" key to MRU position
v._older = _mru;
v._newer = NULL;
_mru->second._newer = moved;
_mru = moved;
}

return moved;
}