lru cache

main.go

package main

import (
	"fmt"
)

const (
	oldestRecordIndex = 0
)

type Vaulter interface {
	Put(k, val string)
	Get(k string) string
	Len() int
	Keys() []string
}

// Vault structure stores limited number of key-value elements.
// It stores most recently addressed elements, so if it already stores maximum elements allowed,
// when we add next one, it should delete least recently used one (either by Get or Put).
type vault struct {
	maxLen int

	storage map[string]string
	keysQueue []string
}

func (v *vault) Put(k, val string) {
	deleted := v.deleteKeyIfExists(k)

	if !deleted && len(v.keysQueue) >= v.maxLen {
		delete(v.storage, v.keysQueue[oldestRecordIndex]) // delete oldest key from storage map
		v.keysQueue = append([]string{}, v.keysQueue[1:]...) // delete oldest key from keys queue
	}

	v.keysQueue = append(v.keysQueue, k)
	v.storage[k] = val

	return
}


func (v *vault) Get(k string) string {
	if ok := v.deleteKeyIfExists(k); !ok {
		return ""
	}
	v.keysQueue = append(v.keysQueue, k)
	return v.storage[k]
}

// find out if key was already stored and delete it
func (v *vault) deleteKeyIfExists(k string) (isDeleted bool){
	for i, key := range v.keysQueue {
		if key == k {
			v.keysQueue = append(v.keysQueue[:i], v.keysQueue[(i+1):]...) // delete key
			return true
		}
	}
	return
}

func (v *vault) Len() int {
	return len(v.keysQueue)
}

func (v *vault) Keys() []string {
	return v.keysQueue
}

func NewVault(size int) Vaulter {
	return &vault{
		size,
		make(map[string]string),
		make([]string, size),
	}
}


func main() {
	v := NewVault(3) // Create vault to store 3 key-value elements (string: string)

	v.Put("key1", "value1") // Add "key1": "value1"
	fmt.Println(v.Len())    // 1

	v.Put("key2", "value2") // Add "key2": "value2"
	fmt.Println(v.Len())    // 2

	v.Put("key3", "value3") // Add "key3": "value3"
	fmt.Println(v.Len())    // 3

	fmt.Println(v.Get("key1")) // value1

	v.Put("key4", "value4") // Add "key3": "value3" and remove "key2" as least recently used one
	fmt.Println(v.Len())    // 3

	fmt.Println(v.Keys()) // [key1 key4 key3] // keys order doesn't matter here
}