package cache

import (
	"container/heap"
)

// 定义lfu cache 结构体
type lfu struct {
	// 缓存最大容量，单位字节，这里值最大存放的 元素 的容量，key不算
	maxBytes int

	// 已使用的字节数，只包括value， key不算
	usedBytes int

	// 最小堆实现的队列
	queue *queue
	// map的key是字符串，value是entry
	cache map[string]*entry
}

// 创建一个新 Cache，如果 maxBytes 是0，则表示没有容量限制
func NewLfuCache(maxBytes int) Cache {
	queue := make(queue, 0)
	return &lfu{
		maxBytes: maxBytes,
		queue:    &queue,
		cache:    make(map[string]*entry),
	}
}

// 通过 Set 方法往 Cache 头部增加一个元素，如果存在则更新值
func (l *lfu) Set(key string, value interface{}) {
	if en, ok := l.cache[key]; ok {
		l.usedBytes = l.usedBytes - en.Len() + CalcLen(value) // 更新占用内存长度
		l.queue.update(en, value, en.weight+1)
	} else {
		en := &entry{
			key:   key,
			value: value,
		}

		heap.Push(l.queue, en)  // 插入queue 并重新排序为堆
		l.cache[key] = en       // 插入 map
		l.usedBytes += en.Len() // 更新内存占用

		// 如果超出内存长度，则删除最 '无用' 的元素，0表示无内存限制
		for l.maxBytes > 0 && l.usedBytes >= l.maxBytes {
			l.DelOldest()
		}
	}
}

// 获取指定元素,访问次数加1
func (l *lfu) Get(key string) interface{} {
	if en, ok := l.cache[key]; ok {
		l.queue.update(en, en.value, en.weight+1)
		return en.value
	}
	return nil
}

// 删除指定元素（删除queue和map中的val）
func (l *lfu) Del(key string) {
	if en, ok := l.cache[key]; ok {
		heap.Remove(l.queue, en.index)
		l.removeElement(en)
	}
}

// 删除最 '无用' 元素（删除queue和map中的val）
func (l *lfu) DelOldest() {
	if l.Len() == 0 {
		return
	}
	val := heap.Pop(l.queue)
	l.removeElement(val)
}

// 删除元素并更新内存占用大小
func (l *lfu) removeElement(v interface{}) {
	if v == nil {
		return
	}

	en := v.(*entry)

	delete(l.cache, en.key)
	l.usedBytes -= en.Len()
}

// 缓存池元素个数
func (l *lfu) Len() int {
	return l.queue.Len()
}

// 缓存池占用内存大小
func (l *lfu) UseBytes() int {
	return l.usedBytes
}