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