# Notes: LRU cache implementation in Go

LRU (Least Recently Used) is a common caching algorithm. This algorithm is used to keep track of recently used items while evicting the least recently used items when the cache is full. In our example, we'll implement a basic LRU cache implementation.

In LRU cache we use two data structures in conjunction, `Map` to reduce lookup time to `O(1)` while doubly-linked list to keep the cached objects in sequence and reduce eviction time to `O(1)` as it evicts tail element. We'll use a common lock for reading and writing on the cache to avoid dirty reads and writes.

Our cache object will contain key and value, key for the uniqueness of the record, and the value contains the actual required value to be cached.
```
type cacheKey int
type cacheValue interface{}

type CacheObject struct {
	key   cacheKey
	value cacheValue
}
```

Now our LRU cache data structure will look like this. Note that we have added capacity as well to allow eviction on least recently used cached objects and maintain the fixed size. Here `list` is a doubly-linked list from the library ([list](https://pkg.go.dev/container/list)), `elements` is the map that maps the cache object key with the address of the object cached in the `list` and lastly, the mutex is the common lock.
```
type LRUCache struct {
	capacity int
	list     *list.List
	elements map[cacheKey]*list.Element
	mutex    *sync.RWMutex
}
```

A simple diagram representing the mapping. Source: [Roman Glushko Blog](https://www.romaglushko.com/)
![Screenshot 2022-06-21 at 5.32.19 PM.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1655812960691/pqAZ20NyS.png align="left")

Now that our cache object and LRU cache are defined, we'll have three functional methods to handle caching operations.

1. `Get`: In this method, we check if `key` exists in the map. If it does, we return the value in `O(1)` time, else we return *"cache key not found"* error. And in case the `key` was there, we push the searched element to the top of our `list`.
```
func (cache *LRUCache) Get(key cacheKey) (cacheValue, error) {
	cache.mutex.RLock()
	defer cache.mutex.RUnlock()

	elem, ok := cache.elements[key]
	if ok {
		value := elem.Value.(*CacheObject).value
		cache.list.MoveToFront(elem)
		return value, nil
	}

	return nil, fmt.Errorf("cache key not found")
}
```

2. `Put`: In this method, first we check if the key exists. If it does, we update the value/ element associated with the `key` and push that on top of the `list`. If the `key` is not found, we first check if there is space left on the cache. If our cache is full, we evict the last element of the `list` and remove it from the *map* as well. After that, we add our new element to the top of the `list` and add a value in the *map* pointing to it.
```
func (cache *LRUCache) Put(key cacheKey, value cacheValue) {
	cache.mutex.Lock()
	defer cache.mutex.Unlock()

	elem, ok := cache.elements[key]
	if ok {
		elem.Value = &CacheObject{
			key:   key,
			value: value,
		}

		cache.list.MoveToFront(elem)
	} else {
		if cache.list.Len() == cache.capacity {
			key := cache.list.Back().Value.(*CacheObject).key
			delete(cache.elements, key)
			cache.list.Remove(cache.list.Back())
		}

		cacheObj := &CacheObject{
			key:   key,
			value: value,
		}

		pointer := cache.list.PushFront(cacheObj)
		cache.elements[key] = pointer
	}
}
```

3. `Purge`: This method basically resets the cache and creates a fresh new cache with old **capacity**.
```
func (cache *LRUCache) Purge() {
	cache.list = new(list.List)
	cache.elements = make(map[cacheKey]*list.Element, cache.capacity)
	cache.mutex = &sync.RWMutex{}
}
```
You can check the below code with the expected results marked with comments `//`. Try testing with different other versions as well to get a better understanding and maybe extend with your improvements. Complete working code:

```
package main

import (
	"container/list"
	"fmt"
	"sync"
)

type cacheKey int
type cacheValue interface{}

// actual cache object to be stored in LRU cache
type CacheObject struct {
	key   cacheKey
	value cacheValue
}

// capacity: maximum capacity of cache
// list: doubly linked list to store our cache objects
// elements: map to point elements of linked list based on "key"
// mutex: to enable locking the cache
type LRUCache struct {
	capacity int
	list     *list.List
	elements map[cacheKey]*list.Element
	mutex    *sync.RWMutex
}

func New(capacity int) (*LRUCache, error) {
	if capacity == 0 {
		return nil, fmt.Errorf("capacity cannot be 0")
	}

	return &LRUCache{
		capacity: capacity,
		list:     new(list.List),
		elements: make(map[cacheKey]*list.Element, capacity),
		mutex:    &sync.RWMutex{},
	}, nil
}

// lock for writers, open for readers
// if cache key exists, returns the value associated with it
// and moves the accessed element to the front of the list
// if not, return error
func (cache *LRUCache) Get(key cacheKey) (cacheValue, error) {
	cache.mutex.RLock()
	defer cache.mutex.RUnlock()

	elem, ok := cache.elements[key]
	if ok {
		value := elem.Value.(*CacheObject).value
		cache.list.MoveToFront(elem)
		return value, nil
	}

	return nil, fmt.Errorf("cache key not found")
}

// lock for all writers and readers
// if cache key exists, simply update the value abd move it to the front
// else, if max cache capacity is reached, delete last element from list and map
// and add new list element containing new cache object to the front of the list
// and add to the map
func (cache *LRUCache) Put(key cacheKey, value cacheValue) {
	cache.mutex.Lock()
	defer cache.mutex.Unlock()

	elem, ok := cache.elements[key]
	if ok {
		elem.Value = &CacheObject{
			key:   key,
			value: value,
		}

		cache.list.MoveToFront(elem)
	} else {
		if cache.list.Len() == cache.capacity {
			key := cache.list.Back().Value.(*CacheObject).key
			delete(cache.elements, key)
			cache.list.Remove(cache.list.Back())
		}

		cacheObj := &CacheObject{
			key:   key,
			value: value,
		}

		pointer := cache.list.PushFront(cacheObj)
		cache.elements[key] = pointer
	}
}

// purge all the cache and reinitializing everything except capacity
func (cache *LRUCache) Purge() {
	cache.list = new(list.List)
	cache.elements = make(map[cacheKey]*list.Element, cache.capacity)
	cache.mutex = &sync.RWMutex{}
}

// prints all the objects in the list from head to tail
func (cache *LRUCache) Print() {
	currentElem := cache.list.Front()

	if currentElem == nil {
		fmt.Println("nothing to show")
		return
	}

	for {
		if currentElem.Next() == nil {
			fmt.Printf("Key: %d, Value: %+v\n", currentElem.Value.(*CacheObject).key, currentElem.Value.(*CacheObject).value)
			break
		}

		fmt.Printf("Key: %d, Value: %+v\n", currentElem.Value.(*CacheObject).key, currentElem.Value.(*CacheObject).value)
		currentElem = currentElem.Next()
	}

	fmt.Println()
}

func main() {
	lru, _ := New(5)

	lru.Put(1, "hello") // 1
	lru.Put(2, 20)      // 1 -> 2
	lru.Put(3, 4.5)     // 1 -> 2 -> 3
	lru.Print()

	fmt.Println(lru.Get(1)) // 2 -> 3 -> 1
	fmt.Println(lru.Get(3)) // 2 -> 1 -> 3
	fmt.Println()
	lru.Print()

	lru.Put(1, true) // 2 -> 3 -> 1
	lru.Print()

	lru.Put(4, "world")         // 2 -> 3 -> 1 -> 4
	lru.Put(5, false)           // 2 -> 3 -> 1 -> 4 -> 5
	lru.Put(6, "drops 2 => 20") // 3 -> 1 -> 4 -> 5 -> 6
	lru.Print()

	lru.Purge()
	lru.Print()
	fmt.Println()

	lru.Put(1, "back") // 1
	lru.Put(2, 2)      // 1 -> 2
	lru.Put(3, true)   // 1 -> 2 -> 3
	lru.Print()
}
```