diff options
Diffstat (limited to 'lru')
| -rw-r--r-- | lru/main.go | 372 |
1 files changed, 372 insertions, 0 deletions
diff --git a/lru/main.go b/lru/main.go new file mode 100644 index 0000000..e951d67 --- /dev/null +++ b/lru/main.go @@ -0,0 +1,372 @@ +package main + +import "fmt" + +type LRUCache struct { + head *Node + tail *Node + keys map[int]*Node + cap int + used int +} + +type Node struct { + key int + val int + next *Node + prev *Node +} + +func Constructor(capacity int) LRUCache { + return LRUCache{ + head: nil, + tail: nil, + keys: map[int]*Node{}, + cap: capacity, + used: 0, + } +} + +func (c *LRUCache) toFront(node *Node) { + if c.head.key == node.key { + return + } + + node.prev.next = node.next + if node.next == nil { + c.tail = node.prev + } else { + node.next.prev = node.prev + } + + node.prev = nil + node.next = c.head + c.head.prev = node + c.head = node +} + +func (this *LRUCache) Get(key int) int { + node, ok := this.keys[key] + if ok { + this.toFront(node) + return node.val + } + return -1 +} + +func (this *LRUCache) Put(key int, value int) { + node, ok := this.keys[key] + if ok { + node.val = value + } else { + this.used += 1 + if this.used > this.cap { + this.used -= 1 + delete(this.keys, this.tail.key) + this.tail = this.tail.prev + if this.tail != nil { + this.tail.next = nil + } + } + node = &Node{ + key: key, + val: value, + next: this.head, + prev: nil, + } + this.keys[key] = node + if this.tail == nil { + this.head = node + this.tail = node + return + } + this.head.prev = node + this.head = node + return + } + + this.toFront(node) +} + +func main() { + mismatches := 0 + lRUCache := Constructor(10) + lRUCache.Put(10, 13) + lRUCache.Put(3, 17) + lRUCache.Put(6, 11) + lRUCache.Put(10, 5) + lRUCache.Put(9, 10) + res6 := lRUCache.Get(13) + if res6 != -1 { + fmt.Printf("Mismatch at operation 6 (Get(13)): expected -1, got %d\n", res6) + mismatches++ + } + lRUCache.Put(2, 19) + res8 := lRUCache.Get(2) + if res8 != 19 { + fmt.Printf("Mismatch at operation 8 (Get(2)): expected 19, got %d\n", res8) + mismatches++ + } + res9 := lRUCache.Get(3) + if res9 != 17 { + fmt.Printf("Mismatch at operation 9 (Get(3)): expected 17, got %d\n", res9) + mismatches++ + } + lRUCache.Put(5, 25) + res11 := lRUCache.Get(8) + if res11 != -1 { + fmt.Printf("Mismatch at operation 11 (Get(8)): expected -1, got %d\n", res11) + mismatches++ + } + lRUCache.Put(9, 22) + lRUCache.Put(5, 5) + lRUCache.Put(1, 30) + res15 := lRUCache.Get(11) + if res15 != -1 { + fmt.Printf("Mismatch at operation 15 (Get(11)): expected -1, got %d\n", res15) + mismatches++ + } + lRUCache.Put(9, 12) + res17 := lRUCache.Get(7) + if res17 != -1 { + fmt.Printf("Mismatch at operation 17 (Get(7)): expected -1, got %d\n", res17) + mismatches++ + } + res18 := lRUCache.Get(5) + if res18 != 5 { + fmt.Printf("Mismatch at operation 18 (Get(5)): expected 5, got %d\n", res18) + mismatches++ + } + res19 := lRUCache.Get(8) + if res19 != -1 { + fmt.Printf("Mismatch at operation 19 (Get(8)): expected -1, got %d\n", res19) + mismatches++ + } + res20 := lRUCache.Get(9) + if res20 != 12 { + fmt.Printf("Mismatch at operation 20 (Get(9)): expected 12, got %d\n", res20) + mismatches++ + } + lRUCache.Put(4, 30) + lRUCache.Put(9, 3) + res23 := lRUCache.Get(9) + if res23 != 3 { + fmt.Printf("Mismatch at operation 23 (Get(9)): expected 3, got %d\n", res23) + mismatches++ + } + res24 := lRUCache.Get(10) + if res24 != 5 { + fmt.Printf("Mismatch at operation 24 (Get(10)): expected 5, got %d\n", res24) + mismatches++ + } + res25 := lRUCache.Get(10) + if res25 != 5 { + fmt.Printf("Mismatch at operation 25 (Get(10)): expected 5, got %d\n", res25) + mismatches++ + } + lRUCache.Put(6, 14) + lRUCache.Put(3, 1) + res28 := lRUCache.Get(3) + if res28 != 1 { + fmt.Printf("Mismatch at operation 28 (Get(3)): expected 1, got %d\n", res28) + mismatches++ + } + lRUCache.Put(10, 11) + res30 := lRUCache.Get(8) + if res30 != -1 { + fmt.Printf("Mismatch at operation 30 (Get(8)): expected -1, got %d\n", res30) + mismatches++ + } + lRUCache.Put(2, 14) + res32 := lRUCache.Get(1) + if res32 != 30 { + fmt.Printf("Mismatch at operation 32 (Get(1)): expected 30, got %d\n", res32) + mismatches++ + } + res33 := lRUCache.Get(5) + if res33 != 5 { + fmt.Printf("Mismatch at operation 33 (Get(5)): expected 5, got %d\n", res33) + mismatches++ + } + res34 := lRUCache.Get(4) + if res34 != 30 { + fmt.Printf("Mismatch at operation 34 (Get(4)): expected 30, got %d\n", res34) + mismatches++ + } + lRUCache.Put(11, 4) + lRUCache.Put(12, 24) + lRUCache.Put(5, 18) + res38 := lRUCache.Get(13) + if res38 != -1 { + fmt.Printf("Mismatch at operation 38 (Get(13)): expected -1, got %d\n", res38) + mismatches++ + } + lRUCache.Put(7, 23) + res40 := lRUCache.Get(8) + if res40 != -1 { + fmt.Printf("Mismatch at operation 40 (Get(8)): expected -1, got %d\n", res40) + mismatches++ + } + res41 := lRUCache.Get(12) + if res41 != 24 { + fmt.Printf("Mismatch at operation 41 (Get(12)): expected 24, got %d\n", res41) + mismatches++ + } + lRUCache.Put(3, 27) + lRUCache.Put(2, 12) + res44 := lRUCache.Get(5) + if res44 != 18 { + fmt.Printf("Mismatch at operation 44 (Get(5)): expected 18, got %d\n", res44) + mismatches++ + } + lRUCache.Put(2, 9) + lRUCache.Put(13, 4) + lRUCache.Put(8, 18) + lRUCache.Put(1, 7) + res49 := lRUCache.Get(6) + if res49 != -1 { + fmt.Printf("Mismatch at operation 49 (Get(6)): expected -1, got %d\n", res49) + mismatches++ + } + lRUCache.Put(9, 29) + lRUCache.Put(8, 21) + res52 := lRUCache.Get(5) + if res52 != 18 { + fmt.Printf("Mismatch at operation 52 (Get(5)): expected 18, got %d\n", res52) + mismatches++ + } + lRUCache.Put(6, 30) + lRUCache.Put(1, 12) + res55 := lRUCache.Get(10) + if res55 != -1 { + fmt.Printf("Mismatch at operation 55 (Get(10)): expected -1, got %d\n", res55) + mismatches++ + } + lRUCache.Put(4, 15) + lRUCache.Put(7, 22) + lRUCache.Put(11, 26) + lRUCache.Put(8, 17) + lRUCache.Put(9, 29) + res61 := lRUCache.Get(5) + if res61 != 18 { + fmt.Printf("Mismatch at operation 61 (Get(5)): expected 18, got %d\n", res61) + mismatches++ + } + lRUCache.Put(3, 4) + lRUCache.Put(11, 30) + res64 := lRUCache.Get(12) + if res64 != -1 { + fmt.Printf("Mismatch at operation 64 (Get(12)): expected -1, got %d\n", res64) + mismatches++ + } + lRUCache.Put(4, 29) + res66 := lRUCache.Get(3) + if res66 != 4 { + fmt.Printf("Mismatch at operation 66 (Get(3)): expected 4, got %d\n", res66) + mismatches++ + } + res67 := lRUCache.Get(9) + if res67 != 29 { + fmt.Printf("Mismatch at operation 67 (Get(9)): expected 29, got %d\n", res67) + mismatches++ + } + res68 := lRUCache.Get(6) + if res68 != 30 { + fmt.Printf("Mismatch at operation 68 (Get(6)): expected 30, got %d\n", res68) + mismatches++ + } + lRUCache.Put(3, 4) + res70 := lRUCache.Get(1) + if res70 != 12 { + fmt.Printf("Mismatch at operation 70 (Get(1)): expected 12, got %d\n", res70) + mismatches++ + } + res71 := lRUCache.Get(10) + if res71 != -1 { + fmt.Printf("Mismatch at operation 71 (Get(10)): expected -1, got %d\n", res71) + mismatches++ + } + lRUCache.Put(3, 29) + lRUCache.Put(10, 28) + lRUCache.Put(1, 20) + lRUCache.Put(11, 13) + res76 := lRUCache.Get(3) + if res76 != 29 { + fmt.Printf("Mismatch at operation 76 (Get(3)): expected 29, got %d\n", res76) + mismatches++ + } + lRUCache.Put(3, 12) + lRUCache.Put(3, 8) + lRUCache.Put(10, 9) + lRUCache.Put(3, 26) + res81 := lRUCache.Get(8) + if res81 != 17 { + fmt.Printf("Mismatch at operation 81 (Get(8)): expected 17, got %d\n", res81) + mismatches++ + } + res82 := lRUCache.Get(7) + if res82 != 22 { + fmt.Printf("Mismatch at operation 82 (Get(7)): expected 22, got %d\n", res82) + mismatches++ + } + res83 := lRUCache.Get(5) + if res83 != 18 { + fmt.Printf("Mismatch at operation 83 (Get(5)): expected 18, got %d\n", res83) + mismatches++ + } + lRUCache.Put(13, 17) + lRUCache.Put(2, 27) + lRUCache.Put(11, 15) + res87 := lRUCache.Get(12) + if res87 != -1 { + fmt.Printf("Mismatch at operation 87 (Get(12)): expected -1, got %d\n", res87) + mismatches++ + } + lRUCache.Put(9, 19) + lRUCache.Put(2, 15) + lRUCache.Put(3, 16) + res91 := lRUCache.Get(1) + if res91 != 20 { + fmt.Printf("Mismatch at operation 91 (Get(1)): expected 20, got %d\n", res91) + mismatches++ + } + lRUCache.Put(12, 17) + lRUCache.Put(9, 1) + lRUCache.Put(6, 19) + res95 := lRUCache.Get(4) + if res95 != -1 { + fmt.Printf("Mismatch at operation 95 (Get(4)): expected -1, got %d\n", res95) + mismatches++ + } + res96 := lRUCache.Get(5) + if res96 != 18 { + fmt.Printf("Mismatch at operation 96 (Get(5)): expected 18, got %d\n", res96) + mismatches++ + } + res97 := lRUCache.Get(5) + if res97 != 18 { + fmt.Printf("Mismatch at operation 97 (Get(5)): expected 18, got %d\n", res97) + mismatches++ + } + lRUCache.Put(8, 1) + lRUCache.Put(11, 7) + lRUCache.Put(5, 2) + lRUCache.Put(9, 28) + res102 := lRUCache.Get(1) + if res102 != 20 { + fmt.Printf("Mismatch at operation 102 (Get(1)): expected 20, got %d\n", res102) + mismatches++ + } + lRUCache.Put(2, 2) + lRUCache.Put(7, 4) + lRUCache.Put(4, 22) + lRUCache.Put(7, 24) + lRUCache.Put(9, 26) + lRUCache.Put(13, 28) + lRUCache.Put(11, 26) + if mismatches == 0 { + fmt.Println("All Gets matched expected outputs!") + } else { + fmt.Printf("Total mismatches: %d\n", mismatches) + } +} |