lru.go

lru.go

package main
import (
    "fmt"
    "container/list"
    "strconv"
)

type LRUObj struct {
    lruLookup map[string]interface{}
    lru *list.List
    limit int
}

type KeyVal struct {
    key string
    val string
}

func main() {
 //Enter your code here. Read input from STDIN. Print output to STDOUT
    var lru LRUObj
    lru.lruLookup = make(map[string]interface{})
    lru.lru = list.New()
    lru.limit = 0
    
    var n int
    fmt.Scan(&n)
    
    for i:=0; i<n ; i++ {
        var cmd, key, val string
        fmt.Scanf("%s", &cmd)
        
        switch cmd {
            case "BOUND":
                fmt.Scanf("%s", &val)
                limit, _ := strconv.Atoi(val)
                setNewLRULimit(limit , &lru)
            case "GET":
                fmt.Scanf("%s", &key)
                out := getFromLRU(key, &lru)
                fmt.Println(out)
            case "PEEK":
                fmt.Scanf("%s", &key)
                out := peekFromLRU(key, &lru)
                fmt.Println(out)
            case "SET":
                fmt.Scanf("%s", &key)
                fmt.Scanf("%s", &val)
                addToLRU(key, val, &lru)
            case "DUMP":
                dumpLRU(&lru)
            case "REMOVE":
                lru.lru.Remove(lru.lru.Back())
        }
    }
}

func setNewLRULimit(limit int, lru *LRUObj) {
    
    if lru.limit <= limit {
        lru.limit = limit
    } else {
        length := lru.lru.Len()
        diff := lru.limit - limit
        if (lru.limit - diff) < length {
            for i:= 0; i<diff; i++ {
                e := lru.lru.Back()
                delete(lru.lruLookup, e.Value.(KeyVal).key)
                lru.lru.Remove(lru.lru.Back())
            }
        }
        lru.limit = limit
    }

}

func dumpLRU(lru *LRUObj) {
	for e := lru.lru.Back(); e != nil; e = e.Prev() {
		fmt.Printf("%s %s\n",e.Value.(KeyVal).key, e.Value.(KeyVal).val)
	}
}

func addToLRU(key string, val string, lru *LRUObj) {
    var value KeyVal
    value.key = key
    value.val = val
    e, ok := lru.lruLookup[key]
    if ok {
        lru.lru.MoveToFront(e.(*list.Element))
        
        e.(*list.Element).Value = value
        
    } else {   
        if lru.lru.Len() < (lru.limit ) {
            // Add the value to front of lru
            e := lru.lru.PushFront(value)
            // Add key to hash with e as value
            lru.lruLookup[key] = e
        } else {

            b := lru.lru.Back()
  
            delete(lru.lruLookup, b.Value.(KeyVal).key) 
            lru.lru.Remove(lru.lru.Back())

             // Add the value to front of lru

            e := lru.lru.PushFront(value)
            // Add key to hash with e as value
            lru.lruLookup[key] = e 

        }
    }
}

func getFromLRU(key string, lru *LRUObj) string {
    e, ok := lru.lruLookup[key]
    if ok {
        lru.lru.MoveToFront(e.(*list.Element))
        return e.(*list.Element).Value.(KeyVal).val
    }
    
    return "NULL"
}

func peekFromLRU(key string, lru *LRUObj) string {
    e, ok := lru.lruLookup[key]
    if ok {
        return e.(*list.Element).Value.(KeyVal).val
    }
    
    return "NULL"
}