Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Ruby で双方向リスト

More than 1 year has passed since last update.

せっかく双方向なんだから 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
yuya_takeyama
Ruby / PHP / JavaScript / Golang
http://yuyat.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away