Back to Repositories

Testing Sliding Window Maximum Algorithm Implementation in williamfiset/Algorithms

This test suite validates the implementation of a Sliding Window Maximum algorithm, ensuring correct maximum value tracking as the window advances and shrinks through an array. The tests combine specific window movement validation with randomized testing for comprehensive coverage.

Test Coverage Overview

The test suite provides thorough coverage of the Sliding Window Maximum implementation through two main test cases:

Specific window movement validation with predetermined values
Randomized testing with varying window sizes up to 1500 elements
Edge cases including positive/negative numbers and window size variations
Boundary conditions for window advancement and shrinkage

Implementation Analysis

The testing approach employs JUnit Jupiter framework with Google Truth assertions for precise validation. The implementation uses a dual-strategy approach combining deterministic and stochastic testing patterns:

Deterministic testing with known sequences and expected maxima
Randomized testing with dynamic window size adjustments
Comparative validation against brute-force maximum calculation

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
Custom random number generation for test data
Parameterized test execution for multiple window sizes

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Combination of specific and randomized test cases
Systematic validation of window operations
Comprehensive edge case coverage
Clear test method organization and naming
Efficient test data generation and validation

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/other/SlidingWindowMaximumTest.java

            
package com.williamfiset.algorithms.other;

import static com.google.common.truth.Truth.assertThat;

import org.junit.jupiter.api.*;

public class SlidingWindowMaximumTest {

  final int TESTS = 1500;

  @Test
  public void smallWindowTest() {

    int[] values = {1, 2, 1, 3, 0, 4};
    SlidingWindowMaximum w = new SlidingWindowMaximum(values);

    w.advance();
    assertThat(w.getMax()).isEqualTo(1);
    w.advance();
    assertThat(w.getMax()).isEqualTo(2);
    w.advance();
    assertThat(w.getMax()).isEqualTo(2);
    w.shrink();
    assertThat(w.getMax()).isEqualTo(2);
    w.shrink();
    assertThat(w.getMax()).isEqualTo(1);
    w.advance();
    assertThat(w.getMax()).isEqualTo(3);
    w.advance();
    assertThat(w.getMax()).isEqualTo(3);
    w.advance();
    assertThat(w.getMax()).isEqualTo(4);
    w.shrink();
    assertThat(w.getMax()).isEqualTo(4);
    w.shrink();
    assertThat(w.getMax()).isEqualTo(4);
    w.shrink();
    assertThat(w.getMax()).isEqualTo(4);
  }

  @Test
  public void randomizedSlidingWindowTest() {
    for (int sz = 1; sz <= TESTS; sz++) {
      randomizedTest(sz);
    }
  }

  private static void fillRandom(int[] ar) {
    for (int i = 0; i < ar.length; i++) {
      if (Math.random() < 0.5) {
        ar[i] = (int) (Math.random() * +25);
      } else {
        ar[i] = (int) (Math.random() * -25);
      }
    }
  }

  public static void randomizedTest(int n) {

    double r = Math.max(0.1, Math.random());
    int[] ar = new int[n];
    fillRandom(ar);

    SlidingWindowMaximum window = new SlidingWindowMaximum(ar);
    int lo = 0, hi = 0;
    while (hi < n) {

      // increase hi
      if (Math.random() < r) {
        window.advance();
        hi++;

        // increase lo if we can
      } else {
        if (lo + 1 < hi) {
          lo++;
          window.shrink();
        }
      }

      // Ignore invalid queries
      if (window.lo == window.hi) continue;

      // Manually find the window maximum
      int max = Integer.MIN_VALUE;
      for (int i = lo; i < hi; i++) max = Math.max(max, ar[i]);

      assertThat(window.getMax()).isEqualTo(max);
    }
  }
}