Back to Repositories

Testing Segment Tree Range Operations in williamfiset/Algorithms

This test suite validates the MinQuerySumUpdateSegmentTree implementation, focusing on range update and query operations for minimum value calculations in a segment tree data structure.

Test Coverage Overview

The test suite provides comprehensive coverage of the MinQuerySumUpdateSegmentTree implementation with a focus on range operations.

Tests simple range updates and queries with predefined arrays
Validates minimum value queries across different ranges
Tests random range sum updates with extensive iterations
Covers edge cases with negative values and boundary conditions

Implementation Analysis

The testing approach employs both deterministic and randomized testing strategies using JUnit 5.

Uses assertThat style assertions with Google Truth framework
Implements brute force validation methods for comparison
Utilizes TestUtils for random array generation and value selection
Performs iterative testing with 1000 iterations for thorough validation

Technical Details

The test suite leverages several technical components:

JUnit Jupiter test framework
Google Truth assertion library
Custom TestUtils for test data generation
Gradle test runner configuration
BeforeEach setup methods for test initialization

Best Practices Demonstrated

The test implementation showcases several testing best practices:

Separate test methods for different scenarios
Comprehensive validation using brute force comparisons
Randomized testing for edge case discovery
Clear test method naming conventions
Efficient test organization with helper methods

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/segmenttree/MinQuerySumUpdateSegmentTreeTest.java

            
/**
 * gradle test --info --tests
 * "com.williamfiset.algorithms.datastructures.segmenttree.MinQuerySumUpdateSegmentTreeTest"
 */
package com.williamfiset.algorithms.datastructures.segmenttree;

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

import com.williamfiset.algorithms.utils.TestUtils;
import org.junit.jupiter.api.*;

public class MinQuerySumUpdateSegmentTreeTest {

  static int ITERATIONS = 1000;

  @BeforeEach
  public void setup() {}

  @Test
  public void simpleTest() {
    long[] ar = {2, 1, 3, 4, -1};
    MinQuerySumUpdateSegmentTree st = new MinQuerySumUpdateSegmentTree(ar);

    st.rangeUpdate1(0, 4, 1);

    assertThat(st.rangeQuery1(0, 4)).isEqualTo(0);
    assertThat(st.rangeQuery1(1, 3)).isEqualTo(2);
    assertThat(st.rangeQuery1(2, 4)).isEqualTo(0);
    assertThat(st.rangeQuery1(3, 3)).isEqualTo(5);

    st.rangeUpdate1(3, 4, 4);

    assertThat(st.rangeQuery1(0, 4)).isEqualTo(2);
    assertThat(st.rangeQuery1(0, 1)).isEqualTo(2);
    assertThat(st.rangeQuery1(3, 4)).isEqualTo(4);
    assertThat(st.rangeQuery1(1, 1)).isEqualTo(2);
    assertThat(st.rangeQuery1(2, 2)).isEqualTo(4);
    assertThat(st.rangeQuery1(3, 3)).isEqualTo(9);
    assertThat(st.rangeQuery1(1, 3)).isEqualTo(2);
    assertThat(st.rangeQuery1(2, 3)).isEqualTo(4);
    assertThat(st.rangeQuery1(1, 2)).isEqualTo(2);

    st.rangeUpdate1(1, 3, 3);

    assertThat(st.rangeQuery1(0, 4)).isEqualTo(3);
    assertThat(st.rangeQuery1(0, 2)).isEqualTo(3);
    assertThat(st.rangeQuery1(2, 4)).isEqualTo(4);
    assertThat(st.rangeQuery1(1, 3)).isEqualTo(5);
    assertThat(st.rangeQuery1(0, 0)).isEqualTo(3);
    assertThat(st.rangeQuery1(1, 1)).isEqualTo(5);
    assertThat(st.rangeQuery1(2, 2)).isEqualTo(7);
    assertThat(st.rangeQuery1(3, 3)).isEqualTo(12);
    assertThat(st.rangeQuery1(4, 4)).isEqualTo(4);
  }

  @Test
  public void testRandomRangeSumUpdatesWithSumRangeQueries() {
    for (int n = 5; n < ITERATIONS; n++) {
      long[] ar = TestUtils.randomLongArray(n, -100, +100);
      MinQuerySumUpdateSegmentTree st = new MinQuerySumUpdateSegmentTree(ar);

      for (int i = 0; i < n; i++) {
        // System.out.printf("n = %d, i = %d\n", n, i);
        int j = TestUtils.randValue(0, n - 1);
        int k = TestUtils.randValue(0, n - 1);
        int i1 = Math.min(j, k);
        int i2 = Math.max(j, k);

        j = TestUtils.randValue(0, n - 1);
        k = TestUtils.randValue(0, n - 1);
        int i3 = Math.min(j, k);
        int i4 = Math.max(j, k);

        // Range update
        long randValue = TestUtils.randValue(-10, 10);
        // System.out.printf("UPDATE [%d, %d] with %d\n", i3, i4, randValue);
        bruteForceSumRangeUpdate(ar, i3, i4, randValue);
        st.rangeUpdate1(i3, i4, randValue);

        // Range query
        long bfMin = bruteForceMin(ar, i1, i2);
        long segTreeMin = st.rangeQuery1(i1, i2);
        // System.out.printf("QUERY [%d, %d], want = %d, got = %d\n", i1, i2, bfMin, segTreeMin);
        assertThat(bfMin).isEqualTo(segTreeMin);
      }
    }
  }

  // Finds the sum in an array between [l, r] in the `values` array
  private static long bruteForceSum(long[] values, int l, int r) {
    long s = 0;
    for (int i = l; i <= r; i++) {
      s += values[i];
    }
    return s;
  }

  // Finds the min value in an array between [l, r] in the `values` array
  private static long bruteForceMin(long[] values, int l, int r) {
    long m = values[l];
    for (int i = l; i <= r; i++) {
      m = Math.min(m, values[i]);
    }
    return m;
  }

  // Finds the max value in an array between [l, r] in the `values` array
  private static long bruteForceMax(long[] values, int l, int r) {
    long m = values[l];
    for (int i = l; i <= r; i++) {
      m = Math.max(m, values[i]);
    }
    return m;
  }

  private static void bruteForceSumRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] += x;
    }
  }

  private static void bruteForceMulRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] *= x;
    }
  }

  private static void bruteForceAssignRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] = x;
    }
  }
}