lru.go

// 🍧
package main

import "fmt"

type LRUCache struct {
	size  int
	vals  map[string]string
	order PtrList
}

func NewLRUCache(size int) LRUCache {
	return LRUCache{size: size, vals: make(map[string]string, size), order: NewPtrList()}
}

func (s LRUCache) String() string { return fmt.Sprintf("{%d, %v, %s}", s.size, s.vals, s.order) }

func (s LRUCache) Set(k string, v string) {
	s.vals[k] = v
	s.order.MoveToTail(k)
	if len(s.vals) > s.size {
		delete(s.vals, s.order.PopHead())
	}
}

func (s LRUCache) Get(k string) string {
	s.order.MoveToTail(k)
	return s.vals[k]
}

type PtrList struct {
	pointers map[string]*Node
	*List
}

func NewPtrList() PtrList { return PtrList{pointers: make(map[string]*Node), List: &List{}} }

func (s PtrList) PopHead() string {
	p := s.List.Head
	if p == nil {
		return ""
	}
	s.List.Pop(p)
	delete(s.pointers, p.Value)
	return p.Value
}

func (s PtrList) MoveToTail(k string) {
	if p := s.pointers[k]; p != nil {
		s.List.Pop(p)
		s.List.PushTail(p)
		return
	}
	v := &Node{Value: k}
	s.List.PushTail(v)
	s.pointers[k] = v
}

type Node struct {
	Value string
	Next  *Node
	Prev  *Node
}

type List struct {
	Head *Node
	Tail *Node
}

func (l *List) Pop(v *Node) {
	if next := v.Next; next != nil {
		next.Prev = v.Prev
	}
	if prev := v.Prev; prev != nil {
		prev.Next = v.Next
	}
	if l.Head == v {
		l.Head = v.Next
	}
	if l.Tail == v {
		l.Tail = v.Prev
	}
	v.Next, v.Prev = nil, nil
}

func (l *List) PushTail(v *Node) {
	if tail := l.Tail; tail != nil {
		tail.Next, v.Prev = v, tail
	}
	l.Tail = v
	if l.Head == nil {
		l.Head = v
	}
}

func (l *List) String() string {
	s := "["
	for p := l.Head; p != nil; p = p.Next {
		s += fmt.Sprintf(`"%s" `, p.Value)
	}
	return s + "]"
}

func main() {
	s := NewLRUCache(3)
	s.Set("a", "1")
	s.Set("b", "2")
	s.Set("c", "3")
	s.Get("a")
	s.Set("d", "4")
	fmt.Printf("%s\n", s)
}