local Deque = {}
Deque.__mt = {}

function Deque.new()
    local obj =
        { first = 1
        , last = 0
        , size = 0
        }
    return setmetatable(obj, {__index = Deque.__mt})
end

function Deque.__mt:right()
    return self[self.last]
end

function Deque.__mt:left()
    return self[self.first]
end

function Deque.__mt:push_left(value)
  local first = self.first - 1
  self.first = first
  self[first] = value
  self.size = self.size + 1
end

function Deque.__mt:push_right(value)
  local last = self.last + 1
  self.last = last
  self[last] = value
  self.size = self.size + 1
end

function Deque.__mt:pop_left()
  local first = self.first
  if self.size == 0 then error("deque is empty") end
  local value = self[first]
  self[first] = nil
  self.first = first + 1
  self.size = self.size - 1
  return value
end

function Deque.__mt:pop_right()
  local last = self.last
  if self.size == 0 then error("deque is empty") end
  local value = self[last]
  self[last] = nil
  self.last = last - 1
  self.size = self.size - 1
  return value 
end

return Deque