Ruby で双方向リスト

せっかく双方向なんだから list[-1] とかによるアクセスにも対応したほうがいいんだろうけど, 何となく満足したのでここまで.

doubly_linked_list.rb

class DoublyLinkedList
  class Bucket
    attr_accessor :data, :next, :prev

    def initialize(data = nil)
      @data = data
    end
  end

  class BucketIterator
    include Enumerable

    def initialize(head)
      @head = head
    end

    def each
      bucket = @head
      while not bucket.next == @head
        bucket = bucket.next
        yield bucket
      end
      self
    end
  end

  class BucketNotFoundException < Exception; end

  include Enumerable

  attr_reader :head

  def initialize
    @head = Bucket.new
    @head.next = @head.prev = @head
  end

  def each
    buckets.each {|bucket| yield bucket.data }
    self
  end

  def push(data)
    new_bucket = Bucket.new(data)
    tail = find_tail_bucket
    new_bucket.next = head
    new_bucket.prev = tail
    tail.next = new_bucket
    head.prev = new_bucket
    self
  end

  def delete_at(n)
    bucket = find_bucket(n)
    bucket.prev.next = bucket.next
    bucket.next.prev = bucket.prev
    self
  end

  def []=(key, value)
    find_bucket(key).data = value
  end

  def [](key)
    find_bucket(key).data
  end

  private
  def buckets
    BucketIterator.new(head)
  end

  def find_tail_bucket
    buckets.reduce(head) {|last_bucket, next_bucket| next_bucket }
  end

  def find_bucket(n)
    bucket = head
    (n + 1).times do
      raise BucketNotFoundException if bucket.next == head
      bucket = bucket.next
    end
    bucket
  end
end

doubly_linked_list_spec.rb

# coding: utf-8
require './doubly_linked_list'

describe DoublyLinkedList::Bucket do
  let(:bucket) { DoublyLinkedList::Bucket.new }
  subject { bucket }

  describe '#data' do
    subject { bucket.data }

    context '値がセットされていないとき' do
      it { should be_nil }
    end

    context '次の要素をセットしたとき' do
      before { bucket.data = some_data }
      let(:some_data) { :foo }

      it { should == some_data }
    end

    context 'コンストラクタに値をセットしたとき' do
      subject { DoublyLinkedList::Bucket.new(:foo) }
      its(:data) { should == :foo }
    end
  end

  describe '#next' do
    subject { bucket.next }

    context '次の要素が無いとき' do
      it { should be_nil }
    end

    context '次の要素をセットしたとき' do
      before { bucket.next = next_bucket }
      let(:next_bucket) { DoublyLinkedList::Bucket.new }

      it { should === next_bucket }
    end
  end

  describe '#prev' do
    subject { bucket.prev }

    context '前の要素が無いとき' do
      it { should be_nil }
    end

    context '前の要素をセットしたとき' do
      before { bucket.prev = prev_bucket }
      let(:prev_bucket) { DoublyLinkedList::Bucket.new }

      it { should === prev_bucket }
    end
  end
end

describe DoublyLinkedList do
  subject { list }
  let(:list) { DoublyLinkedList.new }

  describe '#to_a' do
    subject { list.to_a }

    context '要素が何も無いとき' do
      it { should == [] }
    end

    context '要素をひとつ (:foo) 追加したとき' do
      before { list.push(:foo) }
      it { should == [:foo] }
    end

    context '要素をふたつ (:foo, :bar) 追加したとき' do
      before { list.push(:foo).push(:bar) }
      it { should == [:foo, :bar] }
    end
  end

  describe '#haed' do
    context 'リストに要素が何も無いとき' do
      it 'next は自分自身を指す' do
        list.head.next.should === list.head
      end

      it 'prev は自分自身を指す' do
        list.head.prev.should === list.head
      end
    end
  end

  describe '#push' do
    context '要素をひとつ追加したとき' do
      before { list.push(:foo) }

      it 'head の next の data にその値が入る' do
        list.head.next.data.should == :foo
      end

      it 'head の next の prev は head を指す' do
        list.head.next.prev.should === list.head
      end

      it 'head の next の next は head を指す' do
        list.head.next.next.should === list.head
      end

      it 'head の prev は head の next を指す' do
        list.head.prev.should === list.head.next
      end
    end

    context '要素をふたつ (:foo, :bar) 追加したとき' do
      before do
        list.push(:foo)
        list.push(:bar)
      end

      it 'head の next の data には :foo が入る' do
        list.head.next.data.should == :foo
      end

      it 'head の next の next の data には :bar が入る' do
        list.head.next.next.data.should == :bar
      end

      it 'head の next の next の next は head を指す' do
        list.head.next.next.next.should === list.head
      end

      it 'head の prev の prev の prev は head を指す' do
        list.head.prev.prev.prev.should === list.head
      end
    end
  end

  describe '#[]' do
    context '指定した要素がセットされていないとき' do
      it 'BucketNotFoundException を投げる' do
        proc { list[0] }.should raise_error(DoublyLinkedList::BucketNotFoundException)
      end
    end

    context '要素がセットされているとき' do
      before { list.push(:foo).push(:bar).push(:baz) }
      it 'セットされた要素を取得する' do
        list[2].should == :baz
      end
    end
  end

  describe '#[]=' do
    context '指定した要素が存在しないとき' do
      it 'BucketNotFoundException を投げる' do
        proc { list[0] = :foo }.should raise_error(DoublyLinkedList::BucketNotFoundException)
      end
    end

    context '指定した要素が存在するとき' do
      before do
        list.push(:foo)
        list[0] = :override
      end

      it 'セットされた要素の値を上書く' do
        list[0].should == :override
      end
    end
  end

  describe '#delete_at' do
    subject { list.entries }

    context '要素が 3 つ (:foo, :bar, :baz) あるとき' do
      before { list.push(:foo).push(:bar).push(:baz) }

      context '0 番目の要素を削除したら' do
        before { list.delete_at(0) }
        it { should == [:bar, :baz] }
      end

      context '1 番目の要素を削除したら' do
        before { list.delete_at(1) }
        it { should == [:foo, :baz] }
      end

      context '2 番目の要素を削除したら' do
        before { list.delete_at(2) }
        it { should == [:foo, :bar] }
      end

      context '存在しない要素を削除しようとしたら' do
        it 'BucketNotFoundException を投げる' do
          proc { list.delete_at(3) }.should raise_error(DoublyLinkedList::BucketNotFoundException)
        end
      end
    end
  end
end