sqrtspace-dotnet/tests/SqrtSpace.SpaceTime.Tests/Core/SpaceTimeCalculatorTests.cs

using FluentAssertions;
using SqrtSpace.SpaceTime.Core;
using Xunit;

namespace SqrtSpace.SpaceTime.Tests.Core;

public class SpaceTimeCalculatorTests
{
    [Theory]
    [InlineData(100, 10)]
    [InlineData(1_000, 31)]
    [InlineData(10_000, 100)]
    [InlineData(1_000_000, 1_000)]
    [InlineData(1_000_000_000, 31_622)]
    public void CalculateSqrtInterval_ReturnsCorrectValue(long dataSize, int expectedInterval)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateSqrtInterval(dataSize);

        // Assert
        result.Should().BeCloseTo(expectedInterval, 1);
    }

    [Theory]
    [InlineData(64, 8, 8)]  // Single cache line
    [InlineData(4096, 4, 256)]  // Should align to cache line
    [InlineData(10_000, 8, 96)]  // Should be multiple of cache line elements
    public void CalculateSqrtInterval_WithElementSize_AlignsToCache(long dataSize, int elementSize, int expectedInterval)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateSqrtInterval(dataSize, elementSize);

        // Assert
        result.Should().Be(expectedInterval);
        // Verify cache alignment
        var elementsPerCacheLine = 64 / elementSize;
        (result % elementsPerCacheLine).Should().Be(0);
    }

    [Fact]
    public void CalculateSqrtInterval_WithInvalidInput_ThrowsException()
    {
        // Act & Assert
        var action = () => SpaceTimeCalculator.CalculateSqrtInterval(-1);
        action.Should().Throw<ArgumentOutOfRangeException>()
            .WithMessage("*Data size must be positive*");
            
        var action2 = () => SpaceTimeCalculator.CalculateSqrtInterval(0);
        action2.Should().Throw<ArgumentOutOfRangeException>();
    }

    [Theory]
    [InlineData(1_000_000_000, 500_000_000, 31_622)]
    [InlineData(1_000_000, 2_000_000, 1_000)]
    [InlineData(1_000_000, 100_000, 100_000)]
    [InlineData(1_000_000, 10_000, 10_000)]  // Available memory is limiting factor
    public void CalculateOptimalBufferSize_ReturnsCorrectValue(long totalDataSize, long availableMemory, long expectedSize)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateOptimalBufferSize(totalDataSize, availableMemory);

        // Assert
        result.Should().Be(expectedSize);
    }

    [Fact]
    public void CalculateOptimalBufferSize_WithInvalidInputs_ThrowsException()
    {
        // Act & Assert
        var action1 = () => SpaceTimeCalculator.CalculateOptimalBufferSize(-1, 1000);
        action1.Should().Throw<ArgumentOutOfRangeException>();
        
        var action2 = () => SpaceTimeCalculator.CalculateOptimalBufferSize(1000, -1);
        action2.Should().Throw<ArgumentOutOfRangeException>();
    }

    [Theory]
    [InlineData(1_000_000, CheckpointStrategy.SqrtN, 1_000)]
    [InlineData(1_000_000, CheckpointStrategy.Linear, 1_000)]
    [InlineData(1_024, CheckpointStrategy.Logarithmic, 10)]
    [InlineData(1_000_000, CheckpointStrategy.None, 0)]
    [InlineData(100, CheckpointStrategy.SqrtN, 10)]
    [InlineData(16, CheckpointStrategy.Logarithmic, 4)]
    public void CalculateCheckpointCount_ReturnsCorrectValue(long totalOperations, CheckpointStrategy strategy, int expectedCount)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateCheckpointCount(totalOperations, strategy);

        // Assert
        result.Should().Be(expectedCount);
    }

    [Fact]
    public void CalculateCheckpointCount_WithInvalidInput_ThrowsException()
    {
        // Act & Assert
        var action = () => SpaceTimeCalculator.CalculateCheckpointCount(-1, CheckpointStrategy.SqrtN);
        action.Should().Throw<ArgumentOutOfRangeException>();
    }

    [Theory]
    [InlineData(1_000_000_000, 1_000_000, 96.8)]
    [InlineData(10_000, 10_000, 99.0)]
    [InlineData(1_000_000, 100, 68.4)]  // sqrt(100) = 10, savings = 1 - 10/sqrt(1M) = 99%
    public void EstimateMemorySavings_ReturnsCorrectPercentage(long standardMemory, long dataSize, double expectedSavings)
    {
        // Act
        var result = SpaceTimeCalculator.EstimateMemorySavings(standardMemory, dataSize);

        // Assert
        result.Should().BeApproximately(expectedSavings, 0.1);
    }

    [Theory]
    [InlineData(1024, 8 * 1024 * 1024, 8, 64)]  // 8MB L3 cache
    [InlineData(100, 1 * 1024 * 1024, 8, 50)]   // 1MB L3 cache
    [InlineData(512, 256 * 1024, 4, 32)]        // 256KB L2 cache
    public void CalculateCacheBlockSize_ReturnsOptimalBlockSize(int matrixSize, long cacheSize, int elementSize, int expectedBlockSize)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateCacheBlockSize(matrixSize, cacheSize, elementSize);

        // Assert
        result.Should().BeLessThanOrEqualTo(expectedBlockSize);
        result.Should().BeGreaterThan(0);
        // Verify it fits in cache
        var blockMemory = (long)result * result * elementSize;
        blockMemory.Should().BeLessThanOrEqualTo(cacheSize / 2); // Use half cache for safety
    }

    [Fact]
    public void CalculateCacheBlockSize_WithInvalidInputs_ThrowsException()
    {
        // Act & Assert
        var action1 = () => SpaceTimeCalculator.CalculateCacheBlockSize(-1, 1024, 8);
        action1.Should().Throw<ArgumentOutOfRangeException>();
        
        var action2 = () => SpaceTimeCalculator.CalculateCacheBlockSize(100, -1, 8);
        action2.Should().Throw<ArgumentOutOfRangeException>();
        
        var action3 = () => SpaceTimeCalculator.CalculateCacheBlockSize(100, 1024, -1);
        action3.Should().Throw<ArgumentOutOfRangeException>();
    }

    [Theory]
    [InlineData(1_000_000, 1.5, 668)]  // Time complexity O(n^1.5) -> sqrt(n)
    [InlineData(10_000, 2.0, 100)]      // Time complexity O(n^2) -> sqrt(n)
    [InlineData(1_000_000, 1.0, 1_000)] // Time complexity O(n) -> sqrt(n)
    public void CalculateSpaceForTimeComplexity_ReturnsOptimalSpace(long dataSize, double timeExponent, int expectedSpace)
    {
        // Act
        var result = SpaceTimeCalculator.CalculateSpaceForTimeComplexity(dataSize, timeExponent);

        // Assert
        result.Should().BeCloseTo(expectedSpace, 10);
    }

    [Theory]
    [InlineData(1000, 100)]   // 1KB -> 100 bytes
    [InlineData(1_000_000, 1_000)]  // 1MB -> 1KB
    [InlineData(1_000_000_000, 31_622)]  // 1GB -> ~31KB
    public void EstimateExternalStorageOverhead_ReturnsReasonableOverhead(long dataSize, long expectedOverhead)
    {
        // Act
        var blockSize = SpaceTimeCalculator.CalculateSqrtInterval(dataSize);
        var result = SpaceTimeCalculator.EstimateExternalStorageOverhead(dataSize, blockSize);

        // Assert
        result.Should().BeApproximately(expectedOverhead, expectedOverhead * 0.1);
        // Overhead should be proportional to sqrt(n)
        var ratio = (double)result / Math.Sqrt(dataSize);
        ratio.Should().BeApproximately(1.0, 0.2);
    }
}