Back to Repositories

Validating Pointer-based Segment Tree Operations in williamfiset/Algorithms

This test suite validates the functionality of a pointer-based Segment Tree implementation, focusing on sum operations and error handling. The tests ensure proper initialization and accurate range sum queries through comprehensive validation.

Test Coverage Overview

The test suite provides thorough coverage of the SegmentTreeWithPointers implementation, focusing on initialization validation and sum operations. Key test areas include:

Illegal tree creation scenarios with null and negative size inputs
Basic sum query operations on small arrays
Comprehensive sum query validation against brute force calculations
Edge cases handling for various array sizes and value ranges

Implementation Analysis

The testing approach employs JUnit 5 framework features with a combination of focused unit tests and property-based testing patterns. The implementation uses TestUtils for random array generation and Google Truth assertions for precise result validation.

BeforeEach setup methodology
Exception testing using assertThrows
Systematic test case organization
Comparative testing against bruteforce implementation

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
Custom TestUtils for test data generation
Gradle test execution configuration
Package-specific test organization

Best Practices Demonstrated

The test suite exemplifies several testing best practices including systematic test organization, comprehensive edge case coverage, and proper validation techniques.

Clear test method naming conventions
Isolated test cases with specific assertions
Comprehensive range testing
Helper method utilization for validation
Proper exception testing patterns

williamfiset/algorithms

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

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

import static com.google.common.truth.Truth.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

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

public class SegmentTreeWithPointersTest {

  @BeforeEach
  public void setup() {}

  @Test
  public void testIllegalSegmentTreeCreation1() {
    assertThrows(
        IllegalArgumentException.class,
        () -> {
          Node tree = new Node(null);
        });
  }

  @Test
  public void testIllegalSegmentTreeCreation2() {
    assertThrows(
        IllegalArgumentException.class,
        () -> {
          int size = -10;
          Node tree = new Node(size);
        });
  }

  @Test
  public void testSumQuery() {
    int[] values = {1, 2, 3, 4, 5};
    Node tree = new Node(values);

    assertThat(tree.sum(0, 1)).isEqualTo(1);
    assertThat(tree.sum(1, 2)).isEqualTo(2);
    assertThat(tree.sum(2, 3)).isEqualTo(3);
    assertThat(tree.sum(3, 4)).isEqualTo(4);
    assertThat(tree.sum(4, 5)).isEqualTo(5);
  }

  @Test
  public void testAllSumQueries() {
    int n = 100;
    int[] ar = TestUtils.randomIntegerArray(n, -1000, +1000);
    Node tree = new Node(ar);

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        long bfSum = bruteForceSum(ar, i, j);
        long segTreeSum = tree.sum(i, j);
        assertThat(bfSum).isEqualTo(segTreeSum);
      }
    }
  }

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