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あたりがちょっとトリッキーだからなー。