Deque

deque.rb

require 'forwardable'

class Deque
  extend Forwardable

  def_delegators :@deque, :push, :pop, :unshift, :shift

  def initialize
    @deque = ActualDeque.new
  end

  private # not like Ruby cares

  ActualDeque = Class.new do
    attr_accessor :head, :tail

    def initialize
      @head = @tail = GuardNode.new(self)
    end

    def push(item)
      @tail = @tail.append(item)
    end

    def pop
      @tail.item.tap { @tail = @tail.pre }
    end

    def unshift(item)
      @head = @head.prepend(item)
    end

    def shift
      @head.item.tap { @head = @head.post }
    end
  end

  class GuardNode
    def initialize(deque)
      @deque = deque
    end

    def append(item)
      @deque.head = Node.new(item, pre: self, post: self)
    end

    def prepend(item)
      @deque.tail = Node.new(item, pre: self, post: self)
    end

    def item
      raise 'all outta gum'
    end
  end

  class Node < Struct.new(:item, :pre, :post)
    def initialize(item, pre: nil, post: nil)
      super(item, pre, post)
    end

    def append(item)
      self.post = Node.new(item, pre: self)
    end

    def prepend(item)
      self.pre = Node.new(item, post: self)
    end
  end
end