LRUCache.go

// Go coding exercise: implement LRU Caching service
package main

func main() {}

type QueueNode struct {
	next *QueueNode
	prev *QueueNode
	key  string
}

type DataPoint struct {
	value string
	qNode *QueueNode
}

type Queue struct {
	head      *QueueNode
	tail      *QueueNode
	length    uint
	maxLength uint
}

type Cache struct {
	data  map[string]DataPoint
	queue Queue
}

func NewCache(maxSize uint) Cache {
	return Cache{make(map[string]DataPoint), Queue{nil, nil, 0, maxSize}}
}

func (cache *Cache) Get(key string) string {
	data, ok := cache.data[key]
	if ok {
		defer cache.queue.hit(key, &data)
	}
	return data.value
}

func (cache *Cache) Set(key, value string) {
	data, ok := cache.data[key]
	if ok {
		data.value = value
		cache.queue.hit(key, &data)
	} else {
		point := DataPoint{value, nil}
		toRemove := cache.queue.hit(key, &point)
		if toRemove != "" {
			delete(cache.data, toRemove)
		}
		cache.data[key] = point
	}
}

func (queue *Queue) hit(key string, dp *DataPoint) string {

	qNode := dp.qNode

	// 1. Update el
	if qNode != nil {

		if qNode.next == nil {
			// node is already tail: nothing to do
			return ""
		} else if qNode.prev == nil {
			next, tail := qNode.next, queue.tail

			queue.head = next
			queue.tail = qNode

			qNode.next = nil
			qNode.prev = tail

			next.prev = nil

			tail.next = qNode
		} else {
			prev, next, tail := qNode.prev, qNode.next, queue.tail

			prev.next = next
			next.prev = prev

			tail.next = qNode

			qNode.next = nil
			qNode.prev = tail

			queue.tail = qNode
		}

		return ""
	}

	// 2. New el
	newNode := QueueNode{queue.tail, nil, key}
	dp.qNode = &newNode
	if queue.length == 0 {
		queue.tail = &newNode
		queue.head = &newNode
		queue.length = 1
	} else if queue.length < queue.maxLength {
		//   2.1 has space
		queue.length++
		queue.tail.next = &newNode
		queue.tail = &newNode
	} else {
		//   2.1 no space left
		oldHeadKey := queue.head.key
		queue.tail.next = &newNode
		queue.tail = &newNode
		queue.head = queue.head.next
		return oldHeadKey
	}

	return ""
}