package LeastRecentlyUsedCache;

/**
 * @author Mahsa Sadi
 * 
 * @since 2020 - 05 - 19
 * 
 * License Creative Commons
 * 
 * Copyright by Mahsa Sadi
 *
 *
 *
 */
import java.util.HashMap;
import java.util.Map;





public class LRUCacheS2 extends LRUCache {
	
	/**
	 * Problem: LRU Cache
	 * 
	 * 
	 * 
	 * 
	 * Description:
	 * 
	 * Design and implement a data structure for Least Recently Used (LRU) cache. 
	 * It should support the following operations: get and put.
	 * get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
	 * put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
	 * The cache is initialized with a positive capacity.
	 * Follow up:
	 * Could you do both operations in O(1) time complexity?
	 * 
	 * 
	 * Algorithm:
	 * 
	 * 1- Consider the cache as a variant of a FIFO linked list in which each node contains a key and a value.
	 *     The nodes in the linked list always are kept sorted based on the access time
	 *     (i.e; based on the time for get and put request of the keys).
	 *     Each node in the list has a unique key; i.e.; there are no two nodes with the same keys.
	 *     
	 *     
	 *     
	 * 
	 * 2- To keep the linked list sorted based on the access time:
	 * 
	 *    1- Upon each put and get request for a key, first find the key in the linked list.
	 *    
	 *    2- If the key exists in the linked list, move it to the end of the linked list, and perform put and get operations.
	 *    
	 *    3- Else 
	 *    
	 *       1- If the request is put and the size of the list has not exceeded the capacity of the cache, 
	 *          add a new node to the end of the list related to the new key value pair.
	 *          
	 *       2- If the size of FIFO is exceeding the given capacity, evict the first node of the linked list.
	 *       
	 *       3- If the requests is get, the request is not valid and return -1.
	 * 
	 * 
	 *    
	 *    Note: The time of put and get is proportional to the size of the linked list at each step and it is not highly time efficient.
	 *
	 */


	LinkedSet recentUsage;
	int counter;
	int capacity;

	LRUCacheS2 (int capacity)

	{
		recentUsage = new LinkedSet ();
		counter = 0;
		this.capacity = capacity;
	}



	public void put (int key, int val)
	{
		recentUsage.add(key, val, capacity);
	}


	public int get (int key)
	{
		int val = recentUsage.add(key);
		return val;
	}




	public class NodeList {


		int key;
		int val;
		NodeList next;


		NodeList (int key, int val)
		{
			this.key = key;
			this.val = val;
			next = null;
		}

		void setNext (NodeList next)
		{
			this.next = next;
		}

	}




	public class LinkedList {


		NodeList first;
		NodeList last;
		int length;


		LinkedList ()
		{
			first = null;
			last = null;
			length = 0;
		}

		void add (int key, int val)
		{

			/*
			 * Adds the value to the end of the list
			 */
			NodeList n = new NodeList (key, val);

			if (first == null)
			{
				first = n;
				last = n;
			}

			else 
			{
				last.setNext(n);
				last = n;
			}

			length++;
		}


		public int deleteFirst ()
		{
			int key = first.key;
			first = first.next;
			length--;
			return key;

		}


		NodeList find (int key)
		{
			/*
			 * Returns the node previous to the node with the wanted value;
			 */
			NodeList n = null;
			NodeList currentNode = first;
			NodeList previousNode = first;
			boolean found = false;

			while (currentNode != null && ! found)
			{
				if (currentNode.key == key)
				{
					n = previousNode;
					found = true;
				}
				else
				{  
					previousNode = currentNode;
					currentNode =  currentNode.next;
				}
			}

			return n;
		}


	}


	public class LinkedSet extends LinkedList {

		public LinkedSet ()
		{
			super ();
		}


		public int add (int key)
		{
			int value = -1;
			NodeList n = find (key);
			if ( n != null)
			{

				if (n.key == key)
				{
					value = n.val;
				}

				else
				{
					value = n.next.val;
				}

				moveToTheEndOfList (n, key, value);
			}
			return value;

		}



		public void add (int key, int val, int capacity)
		{

			/*
			 * If the node with the wanted value does not exit in the list, it adds a new node with the wanted value to the end of the list;
			 * Else if the node with the wanted value exist in the list, it will be moved to the end of the list;
			 */

			NodeList n;

			if (first == null)
				addToTheBeginningOfList (key, val);

			else 
			{
				n = find (key);

				if (n == null)
				{
					if (length == capacity)
						deleteFirst();
					

					if (length == 0)
						addToTheBeginningOfList (key, val);

					else 
						addToTheEndOfList (key, val);
				}

				else 
					moveToTheEndOfList (n, key, val);
			}

		}



		public void addToTheBeginningOfList (int key , int val)
		{
			NodeList n = new NodeList (key, val);
			first = n;
			last = n;
			length++;
		}




		public void addToTheEndOfList (int key , int val)
		{
			NodeList n = new NodeList (key, val);
			last.next = n;
			last = n;
			length++;
		}




		public void moveToTheEndOfList (NodeList n, int key, int val)
		{
			NodeList nodeToBeMoved;

			if (first != last && !(n.next.key == key && n.next == last))
			{

				if (n.key == key)
				{
					/*
					 * In case the node containing the wanted value is the first node;
					 */
					nodeToBeMoved = n;
					first = n.next;
				}

				else  
				{

					nodeToBeMoved = n.next;
					n.next = nodeToBeMoved.next;
				}


				last.next = nodeToBeMoved;
				nodeToBeMoved.next = null;
				last = nodeToBeMoved;

			}


			last.val = val;

		}




	}



}