package main

import (
	"container/list"
	"fmt"
	"math/rand"
	"time"
)

type Storage interface {
	Get(int) int
}

type LowSpeedStorage struct {
	Storage
}

type LruCache struct {
	LowSpeedStorage
	capacity int
}

type MyLruCache struct {
	LruCache
	capacity int
	dq       *list.List
	cacheMap map[int]*list.Element
}

func NewLruCache(cap int) *LruCache {
	return &LruCache{
		capacity: cap,
	}
}

func NewMyLruCache(cap int) *MyLruCache {
	return &MyLruCache{
		capacity: cap,
		cacheMap: make(map[int]*list.Element, 0),
		dq:       list.New(),
	}
}

func (low *LowSpeedStorage) Get(k int) int {
	v := rand.Int()
	time.Sleep(1 * time.Second)
	return v
}

func (lru *LruCache) Get(k int) int {
	return lru.LowSpeedStorage.Get(k)
}

func (lru *MyLruCache) Get(k int) int {
	if v, ok := lru.cacheMap[k]; ok {
		// cache hit, move ele to front
		fmt.Printf("cache hit, move key: %d to front\n", k)
		lru.dq.MoveToFront(v)
		return v.Value.(int)
	}
	v := lru.LruCache.Get(k)
	if lru.dq.Len() == lru.capacity {
		last := lru.dq.Back()
		fmt.Printf("dq is full, remove last ele: %d\n", last.Value)
		lru.dq.Remove(last)
	}
	// add new ele to cache
	lru.dq.PushFront(k)
	lru.cacheMap[k] = lru.dq.Front()
	return v
}

func (lru *MyLruCache) PrintAll() {
	for e := lru.dq.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

func main() {
	myLru := NewMyLruCache(4)
	myLru.Get(1)
	myLru.Get(2)
	myLru.Get(3)
	myLru.Get(1)
	myLru.Get(4)
	myLru.Get(5)
	myLru.PrintAll()
	return
}