public final class LinkedList {

  public class LinkedListNode {
    var value: Int
    var next: LinkedListNode?
    weak var previous: LinkedListNode?
    
    public init(value: Int) {
      self.value = value
    }
  }
  public typealias Node = LinkedListNode

  fileprivate var head: Node?
  
  public init() {}
  
  public var isEmpty: Bool {
    return head == nil
  }
  
  public var first: Node? {
    return head
  }
  
  public var last: Node? {
    if var node = head {
      while let next = node.next {
        node = next
      }
      return node
    } else {
      return nil
    }
  }
  
  public var count: Int {
    if var node = head {
      var c = 1
      while let next = node.next {
        node = next
        c += 1
      }
      return c
    } else {
      return 0
    }
  }

  public func node(atIndex index: Int) -> Node? {
    if index >= 0 {
      var node = head
      var i = index
      while node != nil {
        if i == 0 { return node }
        i -= 1
        node = node!.next
      }
    }
    return nil
  }
  
  public subscript(index: Int) -> Int {
    let node = self.node(atIndex: index)
    assert(node != nil)
    return node!.value
  }
  
  public func append(_ value: Int) {
    let newNode = Node(value: value)
    self.append(newNode)
  }
  
  public func append(_ node: Node) {
    let newNode = LinkedListNode(value: node.value)
    if let lastNode = last {
      newNode.previous = lastNode
      lastNode.next = newNode
    } else {
      head = newNode
    }
  }
  
  public func append(_ list: LinkedList) {
    var nodeToCopy = list.head
    while let node = nodeToCopy {
      self.append(node.value)
      nodeToCopy = node.next
    }
  }
  
  private func nodesBeforeAndAfter(index: Int) -> (Node?, Node?) {
    assert(index >= 0)
    
    var i = index
    var next = head
    var prev: Node?
    
    while next != nil && i > 0 {
      i -= 1
      prev = next
      next = next!.next
    }
    assert(i == 0)  // if > 0, then specified index was too large
    
    return (prev, next)
  }
  
  public func insert(_ value: Int, atIndex index: Int) {
    let newNode = Node(value: value)
    self.insert(newNode, atIndex: index)
  }
  
  public func insert(_ node: Node, atIndex index: Int) {
    let (prev, next) = nodesBeforeAndAfter(index: index)
    let newNode = LinkedListNode(value: node.value)
    newNode.previous = prev
    newNode.next = next
    prev?.next = newNode
    next?.previous = newNode
    
    if prev == nil {
      head = newNode
    }
  }
  
  public func insert(_ list: LinkedList, atIndex index: Int) {
    if list.isEmpty { return }
    var (prev, next) = nodesBeforeAndAfter(index: index)
    var nodeToCopy = list.head
    var newNode: Node?
    while let node = nodeToCopy {
      newNode = Node(value: node.value)
      newNode?.previous = prev
      if let previous = prev {
        previous.next = newNode
      } else {
        self.head = newNode
      }
      nodeToCopy = nodeToCopy?.next
      prev = newNode
    }
    prev?.next = next
    next?.previous = prev
  }
  
  public func removeAll() {
    head = nil
  }
  
  @discardableResult public func remove(node: Node) -> Int {
    let prev = node.previous
    let next = node.next
    
    if let prev = prev {
      prev.next = next
    } else {
      head = next
    }
    next?.previous = prev
    
    node.previous = nil
    node.next = nil
    return node.value
  }
  
  @discardableResult public func removeLast() -> Int {
    assert(!isEmpty)
    return remove(node: last!)
  }
  
  @discardableResult public func remove(atIndex index: Int) -> Int {
    let node = self.node(atIndex: index)
    assert(node != nil)
    return remove(node: node!)
  }

}

class LRUCache {

  private let capacity: Int
  private var cache: [Int:Int] = [:]
  var linkedList: LinkedList = LinkedList()
  private var key2node: [Int: LinkedList.LinkedListNode] = [:]

  init(_ capacity: Int) {
    self.capacity = capacity
  }
  
  func get(_ key: Int) -> Int {
    guard let val = cache[key] else {
      return -1
    }
    
    remove(key)
    put(key, val)
    
    return val
  }
  
  private func remove(_ key: Int) {
    cache.removeValue(forKey: key)
    guard let node = key2node[key] else {
      return
    }
    linkedList.remove(node: node)
    key2node.removeValue(forKey: key)
  }
  
  func put(_ key: Int, _ value: Int) {
    if cache[key] != nil {
      remove(key)
    } else if linkedList.count >= capacity, let keyToRemove = linkedList.last?.value {
      remove(keyToRemove)
    }
    
    insert(key, value)
  }

  func insert(_ key: Int, _ value: Int) {
    cache[key] = value
    linkedList.insert(key, atIndex: 0)
    guard let first = linkedList.first else {
      return
    }
    key2node[key] = first
  }
}