package main

import (
	"container/list"
	"fmt"
)

type LRU struct {
	list.List
	Max int
}

func (this *LRU) Add(value int) {
	head := this.Front()
	for head != nil {
		// 命中缓存
		if head.Value == value {
			this.PushFront(head.Value)
			this.Remove(head)
			return
		}
		head = head.Next()
	}

	// 未命中缓存
	if this.Len() >= this.Max {
		this.Remove(this.Back())
	}

	this.PushFront(value)
}

func NewLRU(max int) *LRU {
	return &LRU{
		Max: max,
	}
}

func testLRU() {
	lru := NewLRU(5)
	lru.Add(1)
	lru.Add(2)
	lru.Add(3)
	lru.Add(4)
	lru.Add(5)
	lru.Add(6)
	lru.Add(7)
	lru.Add(5)

	head := lru.Front()
	for head != nil {
		fmt.Println(head.Value)
		head = head.Next()
	}
}