Last active
August 29, 2015 14:09
-
-
Save kunalkushwaha/7db1a73798ac6160cf5a to your computer and use it in GitHub Desktop.
lru.go
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment