class Foobara::LruCache

def cached(key)
  mutex.synchronize do
    if @key_to_node.key?(key)
      node = @key_to_node[key]
      move_node_to_front(node)
      return node.value
    end
  end
  value = yield
  mutex.synchronize do
    if @key_to_node.key?(key)
      node = @key_to_node[key]
      move_node_to_front(node)
    else
      node = Node.new(key, value)
      @key_to_node[key] = node
      prepend_node(node)
    end
  end
  value
end

def get(key)
  mutex.synchronize do
    if @key_to_node.key?(key)
      node = @key_to_node[key]
      move_node_to_front(node)
      return true, node.value
    end
  end
end

def initialize(capacity = 10)
  @capacity = capacity
  @size = 0
  @key_to_node = {}
  @head = @tail = nil
end

def key?(key)
  @key_to_node.key?(key)
end

def move_node_to_front(node)
  return if node == @head
  prev_node = node.prev
  next_node = node.next
  if node == @tail
    @tail = prev_node
    @tail.next = nil
  else
    prev_node.next = next_node
    next_node.prev = prev_node
  end
  @head.prev = node
  node.next = @head
  node.prev = nil
  @head = node
end

def mutex
  @mutex ||= Mutex.new
end

def prepend_node(node)
  if @size == 0
    @head = @tail = node
    @size = 1
  else
    @head.prev = node
    node.next = @head
    @head = node
    if @size < @capacity
      @size += 1
    else
      @key_to_node.delete(@tail.key)
      prev_node = @tail.prev
      if prev_node
        prev_node.next = nil
        @tail = prev_node
      end
    end
  end
end

def reset!
  mutex.synchronize do
    @size = 0
    @key_to_node.clear
    @head = @tail = nil
  end
end

def set_if_missing(key, value)
  mutex.synchronize do
    unless @key_to_node.key?(key)
      node = Node.new(key, value)
      @key_to_node[key] = node
      prepend_node(node)
    end
  end
end