RSpec.shared_examples :priority_queue do

  subject{ described_class.new }

  context '#initialize' do

    it 'sorts from high to low when :order is :max' do
      subject = described_class.from_list([2, 1, 4, 5, 3, 0], order: :max)
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
    end

    it 'sorts from high to low when :order is :high' do
      subject = described_class.new(order: :high)
      [2, 1, 4, 5, 3, 0].each{|item| subject << item }
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
    end

    it 'sorts from low to high when :order is :min' do
      subject = described_class.from_list([2, 1, 4, 5, 3, 0], order: :min)
      expect(subject.pop).to eq 0
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 2
    end

    it 'sorts from low to high when :order is :low' do
      subject = described_class.new(order: :low)
      [2, 1, 4, 5, 3, 0].each{|item| subject << item }
      expect(subject.pop).to eq 0
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 2
    end

    it 'sorts from high to low by default' do
      subject = described_class.new
      subject = described_class.from_list([2, 1, 4, 5, 3, 0])
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
    end
  end

  context '#clear' do

    it 'removes all items from a populated queue' do
      10.times{|i| subject << i}
      subject.clear
      expect(subject).to be_empty
    end

    it 'has no effect on an empty queue' do
      subject.clear
      expect(subject).to be_empty
    end

    specify { expect(subject.clear).to be_truthy }
  end

  context '#delete' do

    it 'deletes the requested item when found' do
      10.times{|item| subject << item }
      subject.delete(5)
      expect(subject.pop).to eq 9
      expect(subject.pop).to eq 8
      expect(subject.pop).to eq 7
      expect(subject.pop).to eq 6
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
      expect(subject.pop).to eq 2
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    it 'deletes the requested item when it is the first element' do
      10.times{|item| subject << item }
      subject.delete(9)
      expect(subject.length).to eq 9
      expect(subject.pop).to eq 8
      expect(subject.pop).to eq 7
      expect(subject.pop).to eq 6
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
      expect(subject.pop).to eq 2
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    it 'deletes the requested item when it is the last element' do
      10.times{|item| subject << item }
      subject.delete(2)
      expect(subject.length).to eq 9
      expect(subject.pop).to eq 9
      expect(subject.pop).to eq 8
      expect(subject.pop).to eq 7
      expect(subject.pop).to eq 6
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    it 'deletes multiple matching items when present' do
      [2, 1, 2, 2, 2, 3, 2].each{|item| subject << item }
      subject.delete(2)
      expect(subject.pop).to eq 3
      expect(subject.pop).to eq 1
    end

    it 'returns true when found' do
      10.times{|i| subject << i}
      expect(subject.delete(2)).to be_truthy
    end

    it 'returns false when not found' do
      10.times{|i| subject << i}
      expect(subject.delete(100)).to be_falsey
    end

    it 'returns false when called on an empty queue' do
      expect(subject.delete(:foo)).to be_falsey
    end
  end

  context '#empty?' do

    it 'returns true for an empty queue' do
      expect(subject).to be_empty
    end

    it 'returns false for a populated queue' do
      10.times{|i| subject << i}
      expect(subject).not_to be_empty
    end
  end

  context '#include?' do

    it 'returns true if the item is found' do
      10.times{|i| subject << i}
      expect(subject).to include(5)
    end

    it 'returns false if the item is not found' do
      10.times{|i| subject << i}
      expect(subject).not_to include(50)
    end

    it 'returns false when the queue is empty' do
      expect(subject).not_to include(1)
    end

    it 'is aliased as #has_priority?' do
      10.times{|i| subject << i}
      expect(subject).to have_priority(5)
    end
  end

  context '#length' do

    it 'returns the length of a populated queue' do
      10.times{|i| subject << i}
      expect(subject.length).to eq 10
    end

    it 'returns zero when the queue is empty' do
      expect(subject.length).to eq 0
    end

    it 'is aliased as #size' do
      10.times{|i| subject << i}
      expect(subject.size).to eq 10
    end
  end

  context '#peek' do

    it 'returns the item at the head of the queue' do
      10.times{|i| subject << i}
      expect(subject.peek).to eq 9
    end

    it 'does not remove the item from the queue' do
      10.times{|i| subject << i}
      subject.peek
      expect(subject.length).to eq 10
      expect(subject).to include(9)
    end

    it 'returns nil when the queue is empty' do
      expect(subject.peek).to be_nil
    end
  end

  context '#pop' do

    it 'returns the item at the head of the queue' do
      10.times{|i| subject << i}
      expect(subject.pop).to eq 9
    end

    it 'removes the item from the queue' do
      10.times{|i| subject << i}
      subject.pop
      expect(subject.length).to eq 9
      expect(subject).not_to include(9)
    end

    it 'returns nil when the queue is empty' do
      expect(subject.pop).to be_nil
    end

    it 'returns nil when called multiple times while empty' do
      10.times do
        expect(subject.pop).to be nil
      end
    end

    it 'is aliased as #deq' do
      10.times{|i| subject << i}
      expect(subject.deq).to eq 9
    end

    it 'is aliased as #shift' do
      10.times{|i| subject << i}
      expect(subject.shift).to eq 9
    end
  end

  context '#push' do

    it 'raises an exception when attempting to enqueue nil' do
      expect {
        subject.push(nil)
      }.to raise_error(ArgumentError)
    end

    it 'adds the item to the queue' do
      subject.push(1)
      expect(subject).to include(1)
    end

    it 'sorts the new item in priority order' do
      3.times{|i| subject << i}
      expect(subject.pop).to eq 2
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    it 'arbitrarily orders equal items with respect to each other' do
      3.times{|i| subject << i}
      subject.push(1)
      expect(subject.pop).to eq 2
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    specify { expect(subject.push(10)).to be_truthy }

    it 'is aliased as <<' do
      subject << 1
      expect(subject).to include(1)
    end

    it 'is aliased as enq' do
      subject.enq(1)
      expect(subject).to include(1)
    end
  end

  context '.from_list' do

    it 'creates an empty queue from an empty list' do
      subject = described_class.from_list([])
      expect(subject).to be_empty
    end

    it 'creates a sorted, populated queue from an Array' do
      subject = described_class.from_list([2, 1, 4, 5, 3, 0])
      expect(subject.pop).to eq 5
      expect(subject.pop).to eq 4
      expect(subject.pop).to eq 3
      expect(subject.pop).to eq 2
      expect(subject.pop).to eq 1
      expect(subject.pop).to eq 0
    end

    it 'creates a sorted, populated queue from a Hash' do
      subject = described_class.from_list(two: 2, one: 1, three: 3, zero: 0)
      expect(subject.length).to eq 4
    end
  end
end

module Concurrent
  module Collection

    RSpec.describe RubyNonConcurrentPriorityQueue do

      it_should_behave_like :priority_queue
    end

    if Concurrent.on_jruby?

      RSpec.describe JavaNonConcurrentPriorityQueue do

        it_should_behave_like :priority_queue
      end
    end

    RSpec.describe NonConcurrentPriorityQueue do
      if Concurrent.on_jruby?
        it 'inherits from JavaNonConcurrentPriorityQueue' do
          expect(NonConcurrentPriorityQueue.ancestors).to include(JavaNonConcurrentPriorityQueue)
        end
      else
        it 'inherits from RubyNonConcurrentPriorityQueue' do
          expect(NonConcurrentPriorityQueue.ancestors).to include(RubyNonConcurrentPriorityQueue)
        end
      end
    end
  end
end