Created
September 28, 2014 09:41
-
-
Save jseanj/2e5219928ad8d6fb6964 to your computer and use it in GitHub Desktop.
用Swift实现的一个LRU Cache
This file contains hidden or 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
| class Node { | |
| var key: Int | |
| var data: Int | |
| var prev: Node? | |
| var next: Node? | |
| init(key: Int, data: Int) { | |
| self.key = key | |
| self.data = data | |
| } | |
| } | |
| class Cache { | |
| let size = 3 | |
| var currentSize = 0 | |
| var head = Node(key: 0, data: 0) | |
| var tail = Node(key: 100, data: 100) | |
| var hashmap:[Int: Node] = [:] | |
| init() { | |
| head.next = tail | |
| tail.prev = head | |
| } | |
| func get(key: Int) -> Int?{ | |
| if let node = hashmap[key] { | |
| remove(node) | |
| insert(node) | |
| return node.data | |
| } else { | |
| return nil | |
| } | |
| } | |
| func put(key: Int, data: Int) { | |
| if let node = hashmap[key] { | |
| remove(node) | |
| insert(node) | |
| node.data = data | |
| } else { | |
| if currentSize > size { | |
| if let key = tail.prev?.key { | |
| hashmap[key] = nil | |
| } | |
| remove(tail.prev) | |
| } | |
| let node = Node(key: key, data: data) | |
| hashmap[key] = node | |
| insert(node) | |
| } | |
| } | |
| // remove the node | |
| func remove(node: Node!) { | |
| node.prev?.next = node.next | |
| node.next?.prev = node.prev | |
| currentSize-- | |
| } | |
| // insert the node to the head | |
| func insert(node: Node!) { | |
| node.next = head.next | |
| node.prev = head | |
| head.next = node | |
| node.next?.prev = node | |
| currentSize++ | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment