LRUCache

LRUCache.go

package main

import (
        "container/list"
        "fmt"
        "time"
        "math/rand"
)
func init() {
        rand.Seed(time.Now().UnixNano())
}
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
func randstring(l int) string {
        r := make([]rune, l)

        for i := range r {
                r[i] = rune(letters[rand.Intn(len(letters))])
        }
        return string(r)
}

type Cacheable interface {
        Key() string
        Size() int
}

type LRUCache struct {
        capcity int
        items map[string]*LRUCacheItem
        list *list.List
}

type LRUCacheItem struct {
        cacheable Cacheable
        listElement *list.Element
}

func New(capcity int) *LRUCache {
        return &LRUCache{
                capcity: capcity,
                items: make(map[string]*LRUCacheItem),
                list: list.New(),
        }
}

func (c *LRUCache) get(key string) Cacheable {
        item, exists := c.items[key]
        if !exists {
                return nil
        }

        c.promote(item)
        return item.cacheable
}

func (c *LRUCache) promote(item *LRUCacheItem) {
        c.list.MoveToFront(item.listElement)
}

func (c *LRUCache) set(cacheable Cacheable) bool {
        if c.capcity < cacheable.Size() {
                c.prune()
        }
        if c.capcity < cacheable.Size() {
                return false
        }

        if item, exists := c.items[cacheable.Key()]; exists {
                c.promote(item)
                return true
        }

        key := cacheable.Key()
        item := &LRUCacheItem{
                cacheable: cacheable,
                listElement: c.list.PushFront(key),
        }
        c.items[key] = item
        c.capcity -= cacheable.Size()

        return true
}

func (c *LRUCache) prune() {
        for i := 0; i < 50; i++ {
                tail := c.list.Back()
                if tail == nil {
                        return
                }

                key := c.list.Remove(tail)
                item := c.items[key.(string)]

                delete(c.items, key.(string))
                c.capcity += item.cacheable.Size()
        }
}

type p struct {key string}
type a struct {key string}

func (p) Size() int {
        return 10
}
func (p p) Key() string {
        return p.key
}
func (a) Size() int {
        return 5
}
func (a a) Key() string {
        return a.key
}


func main() {
        p1 := p{key: randstring(6)}
        lc := New(30)
        fmt.Println(lc.get(p1.Key()))

        lc.set(p1)
        fmt.Println(lc.get(p1.Key()))

        p2 := p{key: randstring(6)}
        lc.set(p2)
        fmt.Println(lc.get(p2.Key()))

        p3 := p{key: randstring(6)}
        lc.set(p3)
        fmt.Println(lc.get(p3.Key()))
        fmt.Println(lc.items)

        fmt.Println(lc.list.Front().Value)
        lc.get(p1.Key())
        fmt.Println(lc.list.Front().Value)

        a4 := a{key: randstring(4)}
        fmt.Println(lc.get(a4.Key()))
        lc.set(a4)
        fmt.Println(lc.items, lc.list.Len())

}