moduleを使った双方向リストの実装

http://hoge.mine.nu/~koji/diary/?date=20060423#p01を見て、ふと線形リストってベタで実装することが多いけど、どうやったら上手く再利用できるかなーと考えてみました。
とりあえず今回はRubyのmoduleを使って実装しました。使い方は__FILE__以下のコードを参照してください。

#!/usr/bin/env ruby

module List
  include Enumerable

  attr_accessor :next, :prev

  def insert(list)
    list.next = self.next
    list.prev = self
    self.next.prev = list if self.next
    self.next = list
    list
  end

  def delete
    self.prev.next = self.next if self.prev
    self.next.prev = self.prev if self.next
    self
  end

  def each
    list = self
    begin
      yield(list)
    end while list = list.next
    self
  end

  def inspect_list
    inject('(') {|s, list| s += list.inspect + (list.next ? ', ' : ')') }
  end
end

class ListHead
  include Enumerable

  class DummyList; include List; end

  def initialize(list = nil)
    @head = DummyList.new
    @head.insert(list) if list
  end

  def head
    @head.next
  end

  def unshift(list)
    @head.insert(list)
  end

  def shift
    @head.next ? @head.next.delete : nil
  end

  def each(&block)
    @head.next.each(&block) if @head.next
  end

  def inspect
    @head.next ? @head.next.inspect_list : '()'
  end
end

if __FILE__ == $0
  class HogeList
    include List
    
    def initialize(id)
      @id = id
    end
    attr_reader :id
    
    def inspect
      @id.inspect
    end
  end

  head = ListHead.new
  head.unshift(HogeList.new(:node5))
  head.unshift(HogeList.new(:node4))
  head.unshift(HogeList.new(:node3))
  head.unshift(HogeList.new(:node2))
  head.unshift(HogeList.new(:node1))
  p head # => (:node1, :node2, :node3, :node4, :node5)
  
  6.times do
    print "shift ... #{head.shift.inspect} "
    p head
    # => shift ... :node1 (:node2, :node3, :node4, :node5)
    #    shift ... :node2 (:node3, :node4, :node5)
    #    shift ... :node3 (:node4, :node5)
    #    shift ... :node4 (:node5)
    #    shift ... :node5 ()
    #    shift ... nil ()  
  end
  
  head = ListHead.new(HogeList.new(1))
  list = head.head
  list = list.insert(HogeList.new(2))
  list = list.insert(HogeList.new(3))
  list = list.insert(HogeList.new(4))
  list = list.insert(HogeList.new(5))
  p head # => (1, 2, 3, 4, 5)
  
  p head.find{|list| list.id == 0 } # => nil
  
  head.find{|list| list.id == 3 }.delete
  p head # => (1, 2, 4, 5)
  head.find{|list| list.id == 4 }.delete
  p head # => (1, 2, 5)
  head.find{|list| list.id == 2 }.delete
  p head # => (1, 5)
  head.find{|list| list.id == 1 }.delete
  p head # => (5)
  head.find{|list| list.id == 5 }.delete
  p head # => ()
end

今回moduleを使った理由としては、(1)(貴重な)継承関係をリストのために使いたくない、(2)(リストの要素のクラスをhas-aしたListクラスを作った場合にくらべて)コードが簡単になりそう、というところかしら。でもmoduleにするとnext、prevあたりがちょっとトリッキーだからなー。