moduleを使ったTailQueueの実装
id:ha-tan:20060425:1145982179の続きでmoduleを使ってTailQueueを実装してみました。attr_accessor :next, :prevさえ定義しておけば、とりあえずTailQueue::Headには入れることができます。
TailQueue::Nodeのinsert_after()とdelete()でTailQueue::Headを引数に指定するのはいまいちなインターフェースです。TailQueue::HeadをTailQueue::Nodeのオブジェクト変数に持たせるのもアレなので妥協しました。
昨日のコードはいまひとつ読みにくかった(+ バグがいっぱいひそんでそう)けど、少しはましになったかな。
#!/usr/bin/env ruby module TailQueue module Node attr_accessor :next, :prev def insert_after(head, node) case self when head.tail head.push(node) else node.next = self.next node.prev = self self.next.prev = node if self.next self.next = node end node end def delete(head) case self when head.head head.shift when head.tail head.pop else self.next.prev = self.prev if self.next self.prev.next = self.next if self.prev self.next = nil self.prev = nil end self end end class Head attr_reader :head, :tail include Enumerable def initialize(node = nil) unshift(node) if node end def unshift(node) if @head node.next, node.prev = @head, nil @head.prev = node @head = node else node.next, node.prev = nil, nil @head = @tail = node end node end def shift return nil unless @head node = @head @head = node.next if @head @head.prev = nil else @tail = nil end node.next, node.prev = nil, nil node end def push(node) if @tail node.next, node.prev = nil, @tail @tail.next = node @tail = node else node.next, node.prev = nil, nil @head = @tail = node end node end def pop return nil unless @tail node = @tail @tail = node.prev if @tail @tail.next = nil else @head = nil end node.next, node.prev = nil, nil node end def each return unless @head node = @head begin # p [node, node.prev, node.next, @head, @tail] yield(node) end while node = node.next self end def inspect inject('(') {|s, node| s += node.inspect + (node.next ? ', ' : '') } + ')' end end end if __FILE__ == $0 class HogeNode include TailQueue::Node def initialize(id) @id = id end attr_reader :id def inspect @id.inspect end end puts '-' * 40 head = TailQueue::Head.new head.unshift(HogeNode.new(5)) head.unshift(HogeNode.new(4)) head.unshift(HogeNode.new(3)) head.unshift(HogeNode.new(2)) head.unshift(HogeNode.new(1)) p head # => (1, 2, 3, 4, 5) puts '-' * 40 6.times do puts "shift ... #{head.shift.inspect} #{head.inspect}" # => shift ... 1 (2, 3, 4, 5) # shift ... 2 (3, 4, 5) # shift ... 3 (4, 5) # shift ... 4 (5) # shift ... 5 () # shift ... nil () end puts '-' * 40 head = TailQueue::Head.new head.push(HogeNode.new(1)) head.push(HogeNode.new(2)) head.push(HogeNode.new(3)) head.push(HogeNode.new(4)) head.push(HogeNode.new(5)) p head # => (1, 2, 3, 4, 5) puts '-' * 40 6.times do puts "pop ... #{head.pop.inspect} #{head.inspect}" # => pop ... 5 (1, 2, 3, 4) # pop ... 4 (1, 2, 3) # pop ... 3 (1, 2) # pop ... 2 (1) # pop ... 1 () # pop ... nil () end puts '-' * 40 head = TailQueue::Head.new(HogeNode.new(1)) node = head.head node = node.insert_after(head, HogeNode.new(2)) node = node.insert_after(head, HogeNode.new(3)) node = node.insert_after(head, HogeNode.new(4)) node = node.insert_after(head, HogeNode.new(5)) p head # => (1, 2, 3, 4, 5) puts '-' * 40 p head.find{|node| node.id == 0 } # => nil p head.find{|node| node.id == 3 } # => 3 puts '-' * 40 head.find{|node| node.id == 3 }.delete(head) p head # => (1, 2, 4, 5) head.find{|node| node.id == 4 }.delete(head) p head # => (1, 2, 5) head.find{|node| node.id == 2 }.delete(head) p head # => (1, 5) head.find{|node| node.id == 1 }.delete(head) p head # => (5) head.find{|node| node.id == 5 }.delete(head) p head # => () end