Immutable queue

immutable_queue.rb

class ImmutableQueue
  attr_reader :first, :last, :count
  def initialize
    @count = 0
  end

  def << object
    object = object.dup rescue object
    node = Node.new(object)
    duplicate do
      if first
        @last.next = node
        @last = node
      else
        @first = node
        @last = node
      end
      @count += 1

      self
    end
  end

  def empty?
    count == 0
  end

  def pop
    popped = first.object
    new_queue = duplicate do
      @first = first.next
      @last = first unless first
      @count -= 1
    end

    [popped, new_queue]
  end

  def peek
    first.object
  end

  def == other
    return false unless other.is_a?(self.class) && other.count == count
    current = first
    other_current = other.first
    loop do
      return true if current.nil?
      return false if current.object != other_current.object
      current = current.next
      other_current = other_current.next
    end
  end

  class Node
    attr_reader :object
    attr_accessor :next
    def initialize object
      @object = object
    end

    def == other
      other.is_a?(self.class) && other.object == object
    end
  end

  private

  def duplicate &block
    duplicate = dup
    duplicate.instance_exec(&block)
    duplicate
  end
end

immutable_queue_spec.rb

describe ImmutableQueue do
  let(:queue) { ImmutableQueue.new }

  it 'is empty when created' do
    expect(queue).to be_empty
  end

  describe 'adding values' do
    it 'returns a queue with the added value' do
      combined = queue << 1
      expect(combined).to be_a ImmutableQueue
      expect(combined.first.object).to be 1
    end

    it 'does not modify the existing queue' do
      queue << 1
      expect(queue).to be_empty
    end

    it 'does not let modified values go through to the queue' do
      string = 'foo'
      queue_with_string = queue << string
      string << 'bar'
      queue_with_string.peek.should == 'foo'
    end
  end

  describe 'removing values' do
    let(:queue) { ImmutableQueue.new << 1 << 2 << 3 }

    it 'returns an array of the popped value and the modified queue' do
      expect(queue.pop).to eq [1, (ImmutableQueue.new << 2 << 3)]
    end

    it 'does not modify the existing queue' do
      original = queue.dup
      queue.pop
      expect(queue).to eq original
    end
  end
end

@last is still shared between Queues and thus can't be mutated, right?

given

a = ImmutableQueue.new << 1
b = a << 2
c = a << 3

b and c share the same object in @last, so when you do b << 4, the value in c will change.

Ahh, I see what you mean now. I thought you were referring to @last.object.