class Node {
  var val: (Int, Int)
  var next: Node?

  init(_ val: (Int, Int)) {
    self.val = val
  }
}

class LinkedList {
  var head: Node?
  var tail: Node?

  func add(_ val: (Int, Int)) {
    let node = Node(val)

    if tail == nil {
      tail = node
      head = node
    } else {
      tail!.next = node
      tail = node
    }
  }

  func search(_ key: Int) -> Node? {
    var node = head

    while node != nil {
      if node!.val.0 == key {
        return node!
      }

      node = node!.next
    }

    return nil
  }

  func remove(_ key: Int) -> Bool {
    let dummy = Node((0, 0))
    dummy.next = head
    var node = dummy

    while node.next != nil {
      if node.next!.val.0 == key {
        node.next = node.next!.next

        head = dummy.next

        return true
      }

      node = node.next!
    }

    return false
  }
}

class HashTable {
  public fileprivate(set) var capacity: Int
  fileprivate var lists = [LinkedList]()

  init(_ capacity: Int) {
    self.capacity = capacity

    for _ in 0 ..< capacity {
      lists.append(LinkedList())
    }
  }

  fileprivate func calcHashcode(_ key: Int) -> Int {
    return key % capacity
  }

  func put(_ key: Int, _ value: Int) {
    let list = lists[calcHashcode(key)]

    if let node = list.search(key) {
      node.val = (key, value)
    } else {
      list.add((key, value))
    }
  }

  func get(_ key: Int) -> Int? {
    let list = lists[calcHashcode(key)]

    if let node = list.search(key) {
      return node.val.1
    } else {
      return nil
    }
  }

  func remove(_ key: Int) -> Bool {
    let list = lists[calcHashcode(key)]

    return list.remove(key)
  }

  func printLists() {
    for (i, list) in lists.enumerated() {
      print("List: #\(i)")
      var node = list.head

      while node != nil {
        print(node!.val)
        node = node!.next
      }
    }
  }
}