#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <algorithm>
#include <map>
#include <deque>

/************************************************************************/
/* 
	懒得改中文了。。。。将就着看。。。
	This cache was implemented with a hash_map and a deque;                       
*/
/************************************************************************/

// A list is NOT enough to implement the "LRU" feature
// So we DO need other attribute in this struct like 
// the KeyNode pointer
struct KeyNode;
struct ValueNode {
	int value;
	ValueNode *prev;
	ValueNode *next;
	KeyNode *key_node;

	ValueNode(int _v, KeyNode *_k, ValueNode *_p = NULL, ValueNode *_n = NULL) : 
		value(_v), key_node(_k), prev(_p), next(_n) { }
};

// We use hash_map to store the key
struct KeyNode {
	int key;
	ValueNode *value_node;

	KeyNode(int _k, ValueNode *_v = NULL) : key(_k), value_node(_v) { }
};

// Double list implementation
class LRUStack {
public:
	LRUStack() : size(0), first(NULL), last(new ValueNode(0, NULL)) { }

	void push(ValueNode *new_node)
	{
		// Size increment
		++size;

		if (this->first == NULL)
		{
			this->first = new_node;
			this->first->prev = NULL;
			this->first->next = this->last;
			this->last->prev = this->first;

			return;
		}

		// Change the original first node
		this->first->prev = new_node;

		// Change the new node
		new_node->next = this->first;
		new_node->prev = NULL;

		// Set current first to new node
		this->first = new_node;
	}
	
	ValueNode *pop()
	{
	    if (size != 0) --size;
	    
		// Pop the last out
		ValueNode* result = this->last->prev;

		if (result == NULL) return result;

		this->last->prev = result->prev;
		if (result->prev != NULL) 
			result->prev->next = this->last;
		else 
			first = NULL;

		result->prev = NULL;
		result->next = NULL;

		return result;
	}

	// Return the size of this stack
	inline int cap() {
		return size;
	}

	// Special function for LRU
	void use(ValueNode *node)
	{
		if (node == first) return;

		// Erase the node from list
		if (node->prev != NULL)
			node->prev->next = node->next;
		if (node->next != NULL)
			node->next->prev = node->prev;

		// Put this node in the top
		node->next	= this->first;
		node->prev	= NULL;
		this->first->prev = node;
		this->first = node;
	}

private:
	int size;
	ValueNode *first;
	ValueNode *last;
};

class LRUCache{
public:
	LRUCache(int capacity) : key_hash_map(), _capacity(capacity) { }

	// Get the value from the hash_map which store the key and the pointer to value
	// O(1)
	int get(int key) {
		std::map<int, KeyNode *>::iterator iter = this->key_hash_map.find(key);

		// If we didn't find the key, we would get pointer to the end of our hash_map
		if (iter == this->key_hash_map.end()) return -1;
		else 
		{
			this->value_stack.use(iter->second->value_node);
			return iter->second->value_node->value;
		}
	}

	// We add a new value with new key into the cache 
	// O(1)
	void set(int key, int value) {
		// Firstly, find the key in hash_map
		std::map<int, KeyNode *>::iterator iter = this->key_hash_map.find(key);

		// If we find the key in hash_map successfully
		if (iter != this->key_hash_map.end())
		{
			iter->second->value_node->value = http://www.mamicode.com/value;>
  这个题目我做了4个小时，真是累死了，妈蛋，主要是自己写了一个LRUStack，然后各种情况都没考虑到，唉。。。看来我还是太连清，还在最后还是把bug都fix了，反思一下，以后只要是自己独立创建的数据结构，一定要好好好好的认真写，不能随便写写以为能用就行，每个数据结构都要足够的健壮，不然会把自己都坑死的。。。。
  这题目，最后用一个hash，会发现，set和get都是O(1)，速度挺快的，使用了一个双链表和一个hash表就实现了。

【LeetCode】LRU Cache