#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2013 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_GRAPHICS_HELPERS_LRUMAP_H
#define NUCLEX_GRAPHICS_HELPERS_LRUMAP_H

#include <unordered_map>

namespace Nuclex { namespace Graphics { namespace Helpers {

  // ------------------------------------------------------------------------------------------- //

  /// <summary>Map which also keeps track of which items were least recently used</summary>
  /// <typeparam name="TKey">Key by which the map is indexed</typeparam>
  /// <typeparam name="TValue">Type of value stored in the map</typeparam>
  /// <typeparam name="THash">Functor that will be used to hash the map's keys</typeparam>
  template<
    typename TKey, typename TValue, typename THash = std::hash<TKey>
  >
  class LruMap {

    #pragma region struct Entry

    /// <summary>Stores an entry in the LruMap</summary>
    private: struct Entry {

      /// <summary>Initializes a new least recently used map entry</summary>
      /// <param name="key">Key the entry is stored under</param>
      /// <param name="value">Value that has been stored in the least recently used map</param>
      public: Entry(const TKey &key, const TValue &value) :
        Key(key),
        Value(value) {}

      /// <summary>Inserts the entry into the list before the specified other entry</summary>
      /// <param name="before">Entry before which this entry will be inserted</param>
      public: void Link(Entry *before) {
        this->Next = before->Next;
        this->Previous = before;

        before->Next = this;
        this->Next->Previous = this;
      }

      /// <summary>Unlinks the entry from the map</summary>
      public: void Unlink() {
        this->Previous->Next = this->Next;
        this->Next->Previous = this->Previous;
      }

      /// <summary>Moves the entry to a new place in the list</summary>
      /// <param name="before">Other entry before which this entry will be moved</param>
      public: void Move(Entry *before) {
        Unlink();
        Link(before);
      }

      /// <summary>Key the entry is stored under</summary>
      public: TKey Key;
      /// <summary>Value carried by the entry</summary>
      public: TValue Value;

      /// <summary>Next least recently used entry in the map</summary>
      public: Entry *Previous;
      /// <summary>Next most recently used entry in the map</summary>
      public: Entry *Next;

    };

    #pragma endregion // struct Entry

    /// <summary>Initializes a new least recently used map</summary>
    public: LruMap() :
      mostRecentlyUsed(nullptr) {}

    /// <summary>Frees all memory used by the least recently used map</summary>
    public: ~LruMap() {
      EntryMap::iterator iterator = this->entries.begin();
      for(; iterator != this->entries.end(); ++iterator) {
        delete iterator->second;
      }
    }

    /// <summary>Attempts to retrieve and touch an entry in the map</summary>
    /// <param name="key">Key whose associated value will be retrieved</param>
    /// <param name="value">Receives the value if the specified key was found</param>
    /// <returns>True if the specified key was found</returns>
    public: bool TryGetAndTouch(const TKey &key, TValue &value) {
      EntryMap::iterator iterator = this->entries.find(key);
      if(iterator == this->entries.end()) {
        return false;
      }

      Entry *entry = iterator->second;
      entry->Move(this->mostRecentlyUsed);
      this->mostRecentlyUsed = entry;

      value = entry->Value;
      return true;
    }

    /// <summary>Adds an entry to the map</summary>
    /// <param name="key">Key under which the value can be looked up</param>
    /// <param name="value">Value that will be added to the map</param>
    public: void Add(const TKey &key, const TValue &value) {
      Entry *entry = new Entry(key, value);
      if(this->mostRecentlyUsed == nullptr) {
        entry->Previous = entry;
        entry->Next = entry;
      } else {
        entry->Link(this->mostRecentlyUsed);
      }
      this->mostRecentlyUsed = entry;

      this->entries.insert(std::make_pair(key, entry));
    }

    /// <summary>Adds an entry to the map and trims the map to the specified size</summary>
    /// <param name="key">Key under which the value can be looked up</param>
    /// <param name="value">Value that will be added to the map</param>
    /// <param name="maximumSize">Maximum size the map is allowed to have</param>
    /// <remarks>
    ///   Prefer this method to separately calling Add() and Trim() because it allows the
    ///   map to reuse internal data structures instead of freeing and reallocating them.
    /// </remarks>
    public: void AddAndTrim(const TKey &key, const TValue &value, std::size_t maximumSize) {
      std::size_t actualSize = this->entries.size();
      if((actualSize == 0) || (actualSize < maximumSize)) {
        Add(key, value);
      } else {
        EntryMap::iterator iterator = this->entries.find(this->mostRecentlyUsed->Key);
        this->entries.erase(iterator);

        // Yep, since it's a circularly linked list, we can do this without adjusting
        // any pointers. Just imagine it like turning a wheel one notch backwards :)
        this->mostRecentlyUsed = this->mostRecentlyUsed->Previous;
        this->mostRecentlyUsed->Key = key;
        this->mostRecentlyUsed->Value = value;

        this->entries.insert(std::make_pair(key, this->mostRecentlyUsed));
      }
    }

    /// <summary>Attempts to remove the entry with the specified key from the map</summary>
    /// <param name="key">Key of the entry that will be removed if found</param>
    /// <returns>True if the key was found and the entry removed, false otherwise</returns>
    public: bool TryRemove(const TKey &key) {
      EntryMap::iterator iterator = this->entries.find(key);
      if(iterator == this->entries.end()) {
        return false;
      }

      Entry *entry = iterator->second;
      this->entries.erase(iterator);

      // If the removed entry was the most recently used one, we need to update
      // our most recently used variable. This will always be true when the last
      // entry is removed from the list.
      if(entry == this->mostRecentlyUsed) {
        if(this->entries.empty()) {
          this->mostRecentlyUsed = nullptr;
        } else {
          this->mostRecentlyUsed = entry->Next;
          entry->Unlink();
        }
      }

      delete entry;
    }

    /// <summary>Reduces the size of the map to at most the specified number of items</summary>
    /// <param name="maximumSize">Maximal size the map is allowed to have</param>
    public: void Trim(std::size_t maximumSize) {

      // If the list is empty, there's nothing to do (and the algorithm below would
      // blow up, incidentally)
      if(this->mostRecentlyUsed == nullptr) {
        return;
      }

      // Keep removing the least recently used entry until we hit our budget. We do
      // not care about list integrity at this point.
      Entry *leastRecentlyUsed = this->mostRecentlyUsed->Previous;
      while(this->entries.size() > maximumSize) {
        EntryMap::iterator iterator = this->entries.find(leastRecentlyUsed->Key);
        this->entries.erase(iterator);

        Entry *previous = leastRecentlyUsed->Previous;
        delete leastRecentlyUsed;
        leastRecentlyUsed = previous;
      }

      // If the entire map was emptied, there will be no entries left, so just clear
      // the LRU list. Otherwise, reestablish the loop between the last and the first entry.
      if(maximumSize == 0) {
        this->mostRecentlyUsed = nullptr;
      } else {
        leastRecentlyUsed->Next = this->mostRecentlyUsed;
        this->mostRecentlyUsed->Previous = leastRecentlyUsed;
      }

    }

    /// <summary>Removes all entries from the map</summary>
    public: void Clear() {
      EntryMap::iterator iterator = this->entries.begin();
      for(; iterator != this->entries.end(); ++iterator) {
        delete iterator->second;
      }

      this->entries.clear();
      this->mostRecentlyUsed = nullptr;
    }

    private: LruMap(const LruMap &);
    private: LruMap &operator =(const LruMap &);

    /// <summary>Map that associates keys with entries</summary>
    private: typedef std::unordered_map<TKey, Entry *, THash> EntryMap;

    /// <summary>Stores the entries in the least recently used map</summary>
    private: EntryMap entries;
    /// <summary>Points to the most recently used entry in the map</summary>
    private: Entry *mostRecentlyUsed;

  };

  // ------------------------------------------------------------------------------------------- //

}}} // namespace Nuclex::Graphics::Helpers

#endif // NUCLEX_GRAPHICS_HELPERS_LRUMAP_H