package main
/*
算法：頁面cache算法之LFU(Least Frequently Used),優(yōu)先淘汰最少使用的數(shù)據(jù)
基于：如果一個數(shù)據(jù)最近被使用的次數(shù)很少抵碟，將來被使用的可能性也很小
特點：優(yōu)先淘汰最少使用的數(shù)據(jù)
實現(xiàn)：最小堆+hashmap。最小堆按使用次數(shù)來排隊，hashmap用來加速查找
插入/刪除：O(logN)，查找：O(1)
*/

import (
    "container/heap"
    "fmt"
    //"errors"
)

type Item struct {
    value       string
    priority    int
    index       int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority    
    heap.Fix(pq, item.index)
}

func minheap_test() {

    items := map[string]int{
        "banana": 3, "apple": 2, "pear": 4,
    }   
    // Create a priority queue, put the items in it, and
    // establish the priority queue (heap) invariants.
    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq)

    // Insert a new item and then modify its priority.
    item := &Item{
        value:    "orange",
        priority: 1,
    }
    heap.Push(&pq, item)
    pq.update(item, item.value, 5)

    // Take the items out; they arrive in decreasing priority order.
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("%.2d:%s\n", item.priority, item.value)
    }
}

type cache_lfu struct {
    minheap PriorityQueue
    kmap map[string] *Item
}

func (lfu* cache_lfu)init(size int) {
    lfu.minheap = make([]*Item, 0, size)
    heap.Init(&(lfu.minheap))
    lfu.kmap = make(map[string] *Item)
}

func (lfu* cache_lfu)set(val string) {
    if(len(lfu.minheap) == cap(lfu.minheap)) {
        item := heap.Pop(&(lfu.minheap)).(*Item)
        fmt.Printf("pop %s\n", item.value);
    }

    item := &Item{value:val, priority:0}

    heap.Push(&(lfu.minheap), item)
    heap.Fix(&(lfu.minheap), item.index)

    lfu.kmap[val] = item
}

func (lfu* cache_lfu)get(val string) {
    item,ok := lfu.kmap[val]
    if(ok) {
        item.priority += 1
        heap.Fix(&(lfu.minheap), item.index)
    }
}

func (lfu *cache_lfu)print() {
    for lfu.minheap.Len() > 0 {
        item := heap.Pop(&(lfu.minheap)).(*Item)
        fmt.Printf("%d:%s\n", item.priority, item.value)
    }   
}

func lfu_test() {
    var lfu cache_lfu
    lfu.init(5)

    items := [5]string {"banana","apple","pear", "mango", "watermelon"}

    for _,val := range items {
        lfu.set(val)
    }

    lfu.get("apple")
    lfu.get("apple")
    lfu.get("pear")
    lfu.print()

    for _,val := range items {
        lfu.set(val)
    }

    lfu.get("apple")
    lfu.get("apple")
    lfu.get("apple")
    lfu.get("apple")
    lfu.get("apple")
    lfu.get("pear")
    lfu.get("pear")
    lfu.get("pear")
    lfu.get("pear")
    lfu.get("banana")
    lfu.get("banana")
    lfu.get("banana")
    lfu.get("mango")
    lfu.get("mango")
    lfu.get("watermelon")

    // pop watermelon this time
    lfu.set("pipeapple")
    //lfu.print()
}
func main() {

    minheap_test()
    lfu_test()
}