Back to Repositories

Testing Priority Queue Operations in javascript-algorithms

This test suite thoroughly validates the implementation of a Priority Queue data structure in JavaScript, covering core functionality like insertion, polling, priority changes, and value searching. The tests ensure proper queue behavior with both primitive and object values while maintaining priority ordering.

Test Coverage Overview

The test suite provides comprehensive coverage of Priority Queue operations:

Queue initialization and basic operations
Priority-based insertion and retrieval
Support for different data types (numbers and objects)
Dynamic priority modifications
Value search functionality

Implementation Analysis

Tests employ Jest’s describe/it pattern for clear test organization. The implementation validates both simple and complex queue operations, with particular attention to priority ordering maintenance after modifications.

Each test case builds upon previous functionality, creating a logical progression from basic to advanced features.

Technical Details

Testing Framework: Jest
Test Structure: BDD-style describe/it blocks
Assertions: Jest’s expect API
Test Scope: Unit tests
Test Environment: Node.js

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test cases with clear purposes
Progressive complexity in test scenarios
Comprehensive edge case coverage
Consistent assertion patterns
Clear test descriptions

trekhleb/javascript-algorithms

src/data-structures/priority-queue/__test__/PriorityQueue.test.js

            
import PriorityQueue from '../PriorityQueue';

describe('PriorityQueue', () => {
  it('should create default priority queue', () => {
    const priorityQueue = new PriorityQueue();

    expect(priorityQueue).toBeDefined();
  });

  it('should insert items to the queue and respect priorities', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    expect(priorityQueue.peek()).toBe(10);

    priorityQueue.add(5, 2);
    expect(priorityQueue.peek()).toBe(10);

    priorityQueue.add(100, 0);
    expect(priorityQueue.peek()).toBe(100);
  });

  it('should be possible to use objects in priority queue', () => {
    const priorityQueue = new PriorityQueue();

    const user1 = { name: 'Mike' };
    const user2 = { name: 'Bill' };
    const user3 = { name: 'Jane' };

    priorityQueue.add(user1, 1);
    expect(priorityQueue.peek()).toBe(user1);

    priorityQueue.add(user2, 2);
    expect(priorityQueue.peek()).toBe(user1);

    priorityQueue.add(user3, 0);
    expect(priorityQueue.peek()).toBe(user3);
  });

  it('should poll from queue with respect to priorities', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    priorityQueue.add(5, 2);
    priorityQueue.add(100, 0);
    priorityQueue.add(200, 0);

    expect(priorityQueue.poll()).toBe(100);
    expect(priorityQueue.poll()).toBe(200);
    expect(priorityQueue.poll()).toBe(10);
    expect(priorityQueue.poll()).toBe(5);
  });

  it('should be possible to change priority of head node', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    priorityQueue.add(5, 2);
    priorityQueue.add(100, 0);
    priorityQueue.add(200, 0);

    expect(priorityQueue.peek()).toBe(100);

    priorityQueue.changePriority(100, 10);
    priorityQueue.changePriority(10, 20);

    expect(priorityQueue.poll()).toBe(200);
    expect(priorityQueue.poll()).toBe(5);
    expect(priorityQueue.poll()).toBe(100);
    expect(priorityQueue.poll()).toBe(10);
  });

  it('should be possible to change priority of internal nodes', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    priorityQueue.add(5, 2);
    priorityQueue.add(100, 0);
    priorityQueue.add(200, 0);

    expect(priorityQueue.peek()).toBe(100);

    priorityQueue.changePriority(200, 10);
    priorityQueue.changePriority(10, 20);

    expect(priorityQueue.poll()).toBe(100);
    expect(priorityQueue.poll()).toBe(5);
    expect(priorityQueue.poll()).toBe(200);
    expect(priorityQueue.poll()).toBe(10);
  });

  it('should be possible to change priority along with node addition', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    priorityQueue.add(5, 2);
    priorityQueue.add(100, 0);
    priorityQueue.add(200, 0);

    priorityQueue.changePriority(200, 10);
    priorityQueue.changePriority(10, 20);

    priorityQueue.add(15, 15);

    expect(priorityQueue.poll()).toBe(100);
    expect(priorityQueue.poll()).toBe(5);
    expect(priorityQueue.poll()).toBe(200);
    expect(priorityQueue.poll()).toBe(15);
    expect(priorityQueue.poll()).toBe(10);
  });

  it('should be possible to search in priority queue by value', () => {
    const priorityQueue = new PriorityQueue();

    priorityQueue.add(10, 1);
    priorityQueue.add(5, 2);
    priorityQueue.add(100, 0);
    priorityQueue.add(200, 0);
    priorityQueue.add(15, 15);

    expect(priorityQueue.hasValue(70)).toBe(false);
    expect(priorityQueue.hasValue(15)).toBe(true);
  });
});