The past week I’ve been playing with implementing LinkedList in Ruby, mainly Single and Double. Both of them include an Enumerable like module called Iteration. It provides methods like: each, count, map, select etc. Double also inclues IterationReverse which provides: reverse, map_reverse etc. As you can tell there’s a lot of code common between the two Iteration modules. The only real difference is each. Iteration#each starts at tail and iterates to head, while IterationReverse#each starts at head and iterates to tail. head being the first node added to list, while tail is last node added. (I know crappy class names right, we’ll fix it later). Late last night I started thinking about ways to DRY the two modules, this post is direct result of that.

First I renamed Iteration and IterationReverse to BackwardIteration and ForwardIteration. My original plan then was to extract out the common methods into Iteration, while implementing each in the respective modules.

module Iteration
  def map
  end
end

module ForwardIteration
  include Iteration

  def each
  end

module BackwardIteration
  include Iteration

  def each
  end
end

class SingleLinkedList
  include ForwardIteration
end

class DoubleLinkedList
  include ForwardIteration
  include BackwardIteration
end

The problem here is when you include BackwardIteration in DoubleLinkedList, it will override ForwardIteration#each.

Before we get any further, let’s write some specs. The below should be fairly self explanatory. We test #first which returns first added node, #last, first’s counterpart. #to_a iterates through list from head to tail, while #to_a_reverse, well you can guess. The last test was a regression test, which we’ll get to later.

describe 'LinkedList' do
  context SingleLinkedList do
    subject { described_class.new }

    it 'returns first character' do
      subject.first.should == 'F'
    end
  end

  context DoubleLinkedList do
    subject { described_class.new }

    it 'returns first character' do
      subject.first.should == 'F'
    end

    it 'returns last character' do
      subject.first_reverse.should == 'B'
    end

    it 'returns array from head to tail' do
      subject.to_a.should == %w(F o r w a r d)
    end

    it 'returns array from tail to head' do
      subject.to_a_reverse.should == %w(B a c k w a r d)
    end

    it 'does not override #each method' do
      subject.to_a_reverse.should == %w(B a c k w a r d)
      subject.to_a.should == %w(F o r w a r d)
    end
  end
end

What we need to do is to stop ForwardIteration#each from clashing with BackwardIteration#each, while also renaming the methods in BackwardIteration with _reverse added to them if ForwardIteration is defined.

First I tried to do this:

module BackwardIteration
  def self.included(base)
    if base.ancestors.include?(ForwardIteration)
      instance_methods.each do |method|
        base.class_eval do
          alias_method "#{method}_reverse", method

          define_method method do
            unbound = ForwardIteration.instance_method(method)
            unbound.bind(self).call
          end
        end
      end
    end
  end
end

What it does is it looks for ForwardIteration, if its defined, it changes its own method name, by adding _reverse to it. Then it forwards the method to point to ForwardIteration. Ruby lets you get a method as an object with #instance_method(method), you’ll have to bind the method to the object, i.e. put the method in the lookup chain, then you can call it. But it didn’t work as I thought it would, so I decided to try another way.

Below I use method_missing is catch methods with _reverse suffix. For those methods, I temporarily redefine each to point to BackwardIteration#each and then call the method. Once done, I redefine each to point to ForwardIteration#each.

module BackwardIteration
  include Iteration

  def method_missing(method, *args, &blk)
    if method.to_s =~ /^(.*)_reverse/
      define_each
      result = send($1.to_sym)
      undef_each

      result
    end
  end

  def define_each
    class << self
      define_method :each do
        e = BackwardIteration.instance_method(:each)
        e.bind(self).call
      end
    end
  end

  def undef_each
    class << self
      define_method :each do
        super()
      end
    end
  end

  def each
    'Backward'
  end
end

class DoubleLinkedList
  include ForwardIteration
  include BackwardIteration
end

Clearly the constant defining and redefining of each isn’t a very good idea, but this was just a learning experience and I had a whole lot of fun trying to get it to work. Hopefully the specs pass for you and you learned a little bit more about the dynamic nature of Ruby.