A Ruby implementation of a Priority Queue data structure using a Sorted Double Linked List

priority_queue.rb

require 'test/unit'

class PriorityQueue
    include Enumerable

    Node = Struct.new :priority, :element, :prev, :next

    attr_reader :head, :tail, :size

    def initialize(items = [])
        @head, @tail = nil, nil
        @size = 0 
    end

    # O(n)
    def enqueue(priority, element)
        n = Node.new priority, element

        found_min = @tail
        while found_min && found_min.priority > n.priority
            found_min = found_min.prev
        end

        unless found_min
            push_front n
        else
            insert_after found_min, n
        end

        [priority, element]
    end

    alias_method :<<, :enqueue
    alias_method :push, :enqueue

    # O(1)
    def dequeue
        return nil unless @head

        n = @head
        if @size == 1
            clear
            return [n.priority, n.element]
        end
        
        @head.next.prev = nil
        @head = @head.next
        @size -= 1
        [n.priority, n.element]
    end

    alias_method :pop, :dequeue

    # O(1)
    def min
        return nil unless @head
        [@head.priority, @head.element] 
    end
    
    alias_method :front, :min

    # O(1)
    def empty?
        @size == 0
    end

    # O(1)
    def clear
        @head, @tail = nil, nil
        @size = 0
    end

    # O(n)
    def each_forward
        return unless @head

        n = @head
        while n
            yield n.priority, n.element
            n = n.next
        end
    end

    alias_method :each, :each_forward

    # O(n)
    def each_backward
        return unless @tail

        n = @tail
        while n
            yield n.priority, n.element
            n = n.prev
        end
    end

    alias_method :reverse_each, :each_backward

private

    def push_front(n)
        if @head
            n.next = @head
            @head.prev = n
            @head = n
        else
            @head = @tail = n
        end
        @size += 1
    end

    def insert_after(predecessor, successor)
        successor.next = predecessor.next
        predecessor.next = successor
        successor.prev = predecessor
        @size += 1
    end
end

if __FILE__ == $0
    class TestPriorityQueue < Test::Unit::TestCase
        
        def setup
            @queue = PriorityQueue.new
        end

        def teardown
            @queue.clear
        end

        def test_simple
            @queue.enqueue 2, "world"

            assert [email protected]?
            assert_equal 1, @queue.size
            assert_equal [2, "world"], @queue.front

            @queue.enqueue 1, "hello"
            assert_equal 2, @queue.size
            assert_equal [1, "hello"], @queue.front

            assert_equal [1, "hello"], @queue.dequeue
            assert_equal 1, @queue.size

            assert_equal [2, "world"], @queue.dequeue
            assert_equal 0, @queue.size
            assert @queue.empty? 
        end
    end
end