/* Include lib */
#include <stdio.h>
#include <assert.h>

/* Max elements for LRU */
#define LRU_MAX_SIZE    4

/* Define LRU cache */
int lru_cache[LRU_MAX_SIZE] = { 0 };
int lru_cache_size = 0;

/* API for LRU cache */
/* Get cache current capacity */
int lru_cache_capacity(void)
{
  return lru_cache_size;
}

/* Get value from cache index */
int lru_cache_get(unsigned int index, int *ret)
{
  int i, bak;

  /* Warning if index over size */
  if (index >= lru_cache_size) {
    printf("WARN: Input overflow cache size\n");
    return -1;
  }

  /* Warning if cache is empty */
  if (lru_cache_size == 0) {
    printf("WARN: Cache empty\n");
    return -1;
  }

  /* Shift down all element, except last element to move accessed value to it */
  bak = lru_cache[index];
  for (i = index; i < (lru_cache_size - 1); i++)
    lru_cache[i] = lru_cache[i + 1];
  lru_cache[lru_cache_size - 1] = bak;

  /* Return value */
  *ret = bak;
  return 0;
}

/* Fast get value at cache tail */
int lru_cache_fast_get(int *ret)
{

  /* Warning if cache is empty */
  if (lru_cache_size == 0) {
    printf("WARN: Cache empty\n");
    return -1;
  }

  /* Return tail value */
  *ret = lru_cache[lru_cache_size - 1];
  return 0;
}

/* Set new value to cache */
void lru_cache_set(int value)
{
  int i;

  /* If cache full, shift down all element, except last one to write new value to it */
  if (lru_cache_size == LRU_MAX_SIZE) {
    for (i = 0; i < (lru_cache_size - 1); i++)
      lru_cache[i] = lru_cache[i + 1];
    lru_cache[lru_cache_size - 1] = value;
  /* Otherwise write new value next to last element then increasing size */
  } else {
    lru_cache[lru_cache_size] = value;
    lru_cache_size++;
  }
}

/* Dump all value in lru cache */
void lru_cache_print(void) 
{
  int i;

  printf("Dump LRU cache: ");
  for (i = 0; i < lru_cache_size; i++)
    printf("%d ", lru_cache[i]);
  printf("\n");
}

int main(void)
{
  int sel, val;

  while (1) {
    printf("\n\nSelection:\n");
    printf("0-3: Get cache index\n");
    printf("4  : Fast get tail\n");
    printf("5  : Get cache capacity\n");
    printf("6  : Insert new value to cache\n");
    printf("8  : Dump cache\n");
    printf("9  : Exit\n");
    printf("\n");
    printf("Select: ");

    scanf("%d", &sel);
    printf("\n"); 
    if (sel == 8)
      lru_cache_print();
    else if (sel == 9)
      return 0;
    else if (sel >= 0 && sel <= 3) {
      if (lru_cache_get(sel, &val) == 0)
        printf("%d\n", val);
    } else if (sel == 4) {
      if (lru_cache_fast_get(&val) == 0)
        printf("%d\n", val);
    } else if (sel == 5) {
      printf("Cache size: %d", lru_cache_capacity());
    } else if (sel == 6) {
      printf("Input value: ");
      scanf("%d", &sel);
      lru_cache_set(sel);
    } else {
      printf("WARN: Option not available\n");
    }
  }

  return -1;
}

#if 0 /* Instruction */
// simple single threaded LRUCache
class LRUCache {  
  unordered_map<int, ListNode*> cache;  
  // each entry in linked list is <key, value>
  LinkedList cache_vals;
  int capacity; // total capacity
  
public:

   LRUCache(int capacity) {
    this->capacity = capacity;
  }
  
  ~LRUCache() {
    for (auto& t : cache) {
      delete t.second;
    }
  }
  
  int get(int key) {
    //TODO: Write - Your - Code
    return -1;
  }

  void set(int key, int value) {
    //TODO: Write - Your - Code
  }  
  
  string print() {
    string result = "";
    for (auto& x : cache) {
      result += "(" + std::to_string(x.first) + "," + std::to_string(x.second->value) + "),";
    }
    return result;
  }
};
#endif



#if 0  /* Sample for starting */
// simple single threaded LRUCache
class LRUCache {  
  unordered_map<int, ListNode*> cache;  
  // each entry in linked list is <key, value>
  LinkedList cache_vals;
  int capacity; // total capacity
  
public:

   LRUCache(int capacity) {
    this->capacity = capacity;
  }
  
  ~LRUCache() {
    for (auto& t : cache) {
      delete t.second;
    }
  }
  
  int get(int key) {
    //TODO: Write - Your - Code
    return -1;
  }

  void set(int key, int value) {
    //TODO: Write - Your - Code
  }  
  
  string print() {
    string result = "";
    for (auto& x : cache) {
      result += "(" + std::to_string(x.first) + "," + std::to_string(x.second->value) + "),";
    }
    return result;
  }
};
#endif