Back to Repositories

Validating Suffix Array Implementations in williamfiset/Algorithms

This test suite validates the implementation of Suffix Array data structures, focusing on various algorithms for suffix array construction and Longest Common Prefix (LCP) array computation.

The suite thoroughly tests three different implementations: slow, medium, and fast suffix array construction methods.

Test Coverage Overview

The test suite provides comprehensive coverage of suffix array operations:

Suffix array length validation
LCP array computation for unique characters
Increasing LCP patterns
Specific LCP test cases with predefined values
Suffix array construction comparison across implementations

Implementation Analysis

The testing approach implements a comparative methodology, validating three different suffix array implementations against identical inputs.
The suite utilizes JUnit 5 framework features with @BeforeEach setup and @Test annotations, employing Google Truth assertions for precise verification.

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
SecureRandom and Random for test data generation
Constant test parameters for size and iteration control
ASCII letter string constants for character-based tests

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Systematic test case organization
Comprehensive edge case coverage
Consistent verification across multiple implementations
Clear test method naming
Efficient test data generation and management

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/suffixarray/SuffixArrayTest.java

            
package com.williamfiset.algorithms.datastructures.suffixarray;

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

import java.security.SecureRandom;
import java.util.Random;
import org.junit.jupiter.api.*;

public class SuffixArrayTest {

  static final SecureRandom random = new SecureRandom();
  static final Random rand = new Random();

  static final int LOOPS = 1000;
  static final int TEST_SZ = 40;
  static final int NUM_NULLS = TEST_SZ / 5;
  static final int MAX_RAND_NUM = 250;

  String ASCII_LETTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

  @BeforeEach
  public void setup() {}

  @Test
  public void suffixArrayLength() {
    String str = "ABCDE";

    SuffixArray sa1 = new SuffixArraySlow(str);
    SuffixArray sa2 = new SuffixArrayMed(str);
    SuffixArray sa3 = new SuffixArrayFast(str);

    assertThat(sa1.getSa().length).isEqualTo(str.length());
    assertThat(sa2.getSa().length).isEqualTo(str.length());
    assertThat(sa3.getSa().length).isEqualTo(str.length());
  }

  @Test
  public void lcsUniqueCharacters() {

    SuffixArray sa1 = new SuffixArraySlow(ASCII_LETTERS);
    SuffixArray sa2 = new SuffixArrayMed(ASCII_LETTERS);
    SuffixArray sa3 = new SuffixArrayFast(ASCII_LETTERS);

    SuffixArray[] suffixArrays = {sa1, sa2, sa3};

    for (SuffixArray sa : suffixArrays) {
      for (int i = 0; i < sa.getSa().length; i++) {
        assertThat(sa.getLcpArray()[i]).isEqualTo(0);
      }
    }
  }

  @Test
  public void increasingLCPTest() {

    String UNIQUE_CHARS = "KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK";

    SuffixArray sa1 = new SuffixArraySlow(UNIQUE_CHARS);
    SuffixArray sa2 = new SuffixArrayMed(UNIQUE_CHARS);
    SuffixArray sa3 = new SuffixArrayFast(UNIQUE_CHARS);

    SuffixArray[] suffixArrays = {sa1, sa2, sa3};

    for (SuffixArray sa : suffixArrays) {
      for (int i = 0; i < sa.getSa().length; i++) {
        assertThat(sa.getLcpArray()[i]).isEqualTo(i);
      }
    }
  }

  @Test
  public void lcpTest1() {

    String text = "ABBABAABAA";
    int[] lcpValues = {0, 1, 2, 1, 4, 2, 0, 3, 2, 1};

    SuffixArray sa1 = new SuffixArraySlow(text);
    SuffixArray sa2 = new SuffixArrayMed(text);
    SuffixArray sa3 = new SuffixArrayFast(text);

    SuffixArray[] suffixArrays = {sa1, sa2, sa3};

    for (SuffixArray sa : suffixArrays) {
      for (int i = 0; i < sa.getSa().length; i++) {
        assertThat(lcpValues[i]).isEqualTo(sa.getLcpArray()[i]);
      }
    }
  }

  @Test
  public void lcpTest2() {
    String text = "ABABABAABB";
    int[] lcpValues = {0, 1, 3, 5, 2, 0, 1, 2, 4, 1};

    SuffixArray sa1 = new SuffixArraySlow(text);
    SuffixArray sa2 = new SuffixArrayMed(text);
    SuffixArray sa3 = new SuffixArrayFast(text);

    SuffixArray[] suffixArrays = {sa1, sa2, sa3};

    for (SuffixArray sa : suffixArrays) {
      for (int i = 0; i < sa.getSa().length; i++) {
        assertThat(lcpValues[i]).isEqualTo(sa.getLcpArray()[i]);
      }
    }
  }

  @Test
  public void saConstruction() {
    // Test inspired by LCS. Make sure constructed SAs are equal.
    // Use digits 0-9 to fake unique tokens
    String text = "BAAAAB0ABAAAAB1BABA2ABA3AAB4BBBB5BB";

    SuffixArray sa1 = new SuffixArraySlow(text);
    SuffixArray sa2 = new SuffixArrayMed(text);
    SuffixArray sa3 = new SuffixArrayFast(text);
    SuffixArray[] suffixArrays = {sa1, sa2, sa3};

    for (int i = 0; i < suffixArrays.length; i++) {
      for (int j = i + 1; j < suffixArrays.length; j++) {
        SuffixArray s1 = suffixArrays[i];
        SuffixArray s2 = suffixArrays[j];
        for (int k = 0; k < s1.getSa().length; k++) {
          assertThat(s1.getSa()[k]).isEqualTo(s2.getSa()[k]);
        }
      }
    }
  }
}