/*
*LRU:Least Recently Used,优先淘汰最少使用的算法
*实现：链表+hashmap。链表用来存放数据，hashmap用来加速查找。
插入时如果链表满则先淘汰再插入头部。链表满时进行淘汰，优先淘汰尾部元素。
查找时用hashmap查找，然后将元素移动到表头
*性能：插入/删除/查找:O(1)
*/

package main
import (
    "fmt"
    "container/list"
)

type Item struct {
    key string
    val interface{}
}

type cache_lru struct {
    size int
    list list.List
    kmap map[string]*list.Element 
}

func (lru *cache_lru)init(size int) {
    lru.size = size
    lru.kmap = make(map[string]*list.Element)
    //lru.list = list.New()
}

func (lru *cache_lru)set(item *Item) {
    if(lru.list.Len() >= lru.size) {
        delete(lru.kmap, item.key)
        lru.list.Remove(lru.list.Back())
    }

    elem := lru.list.PushFront(item)
    lru.kmap[item.key] = elem
}

func (lru *cache_lru)get(key string) *Item {
    item,ok := lru.kmap[key]
    if(!ok) {
        return nil
    }

    lru.list.MoveToFront(item)

    return item.Value.(*Item)
}

func (lru *cache_lru)print() {
    for v:= lru.list.Front(); v!=nil; v= v.Next() {
        item := v.Value.(*Item)
        fmt.Printf("%s:%d->", item.key, item.val.(int))
    }
    fmt.Println()
}

func main() {
    var lru cache_lru
    lru.init(5)

    fruits := map[string]int{"apple":100,"pear":200,"banana":300,"pineapple":400,"mango":600}
    for k,v := range fruits {
        lru.set(&Item{k,v})
    }
    lru.print()
    lru.get("watermelon")
    lru.print()
    banana := lru.get("banana")
    fmt.Printf("fruit:%s,calories:%d\n",banana.key,banana.val.(int))
    lru.print()
    lru.get("mango")
    lru.print()
    // should pop pineapple
    lru.set(&Item{"peach",700})
    lru.print()
}